Scientific knowledge map · Paper #19
5PM: Secure Pattern Matching
2012 · 8th Conference on Security and Cryptography for Networks (SCN)
- Theory
- protocol
- primitive
Research question
What does the paper try to establish?
Can two parties privately evaluate expressive pattern queries—exact match, single-character wildcards, non-binary substring/Hamming matching, and optionally hidden pattern length—with communication below the size of a generic matching circuit and security against malicious participants?
Central answer
What is the proposed answer?
5PM turns pattern matching into linear operations over character-delay vectors and an activation vector, enabling an honest-but-curious protocol from generic additively homomorphic encryption and a malicious protocol from threshold ElGamal plus zero-knowledge proofs. The source proves conditional security and gives sublinear-in-circuit communication and low round counts; only the honest-but-curious variant is implemented and benchmarked in the audited full version.
Evidence profile
Six dimensions, kept separate
The chart summarizes documented evidence and process. It is not a correctness probability, confidence score, or ranking, and no composite score is calculated.
LowMediumHighN/A = not assessed
A smaller value means less documented support for that dimension, not that the paper is false or unimportant.
- Epistemic evidence High
-
The full version provides explicit functionality and adversary models, theorem statements, extensive simulation-based proofs, asymptotic analysis, and an honest-but-curious implementation with benchmarks. The malicious variant is not implemented and neither proof nor benchmark was independently reproduced in this audit.
Security theorems and complexity claims Simulation-based proof details Honest-but-curious implementation and benchmark tables - Auditability High
-
A complete IACR full version and an author-uploaded full text make the construction, proofs, and benchmarks directly inspectable. This audit did not obtain a locally hashed binary or public implementation source.
Problem, functionality, and claimed contributions Simulation-based proof details Honest-but-curious implementation and benchmark tables - Production provenance Medium
-
Named authorship, public ePrint, conference DOI, author upload, and later journal record establish a clear publication lineage. Contributor roles, code versions, benchmark scripts, and revision history are not documented.
Problem, functionality, and claimed contributions Official conference publication record Subsequent journal full-version record - External scrutiny High
-
The work passed SCN review, received a journal full-version publication, and has a substantial citation trail. Review reports, independent proof checking, and implementation replication were not located.
Official conference publication record Subsequent journal full-version record Citation-count snapshot - Reception High
-
ResearchGate displayed 56 citations on 2026-07-11, exceeding the rubric's 11-citation high threshold. The count may merge conference, ePrint, and journal versions, and citing contexts were not reviewed.
Citation-count snapshot - Contribution significance High
-
The work provides a general algebraic primitive, malicious-security construction, favorable communication/round complexity, and a prototype, and it has a sustained citation and publication trail.
Problem, functionality, and claimed contributions Security theorems and complexity claims Honest-but-curious implementation and benchmark tables Citation-count snapshot
Assessment: Ai draft author review pending · 2026-07-11 · rubric 0.2. These dimensions describe documented support and process, not truth, correctness, or a universal ranking. No composite score is calculated.
Top-down and bottom-up view
Hierarchical knowledge map
Collapse a branch for a top-level reading, or follow its source links and child nodes to audit the evidence and boundaries underneath it.
5PM
A two-party secure pattern-matching protocol family based on an algebraic reduction and additively homomorphic encryption.
Problem, functionality, and claimed contributions-
question Research question
research questionCan expressive non-binary pattern search be securely computed with communication linear in text-plus-pattern length rather than linear in a quadratic generic circuit?
Problem, functionality, and claimed contributions -
contribution Central answer
formally supportedRepresent candidate matches as linear matrix/vector operations over character-delay vectors, then evaluate those operations homomorphically with protocol-specific checks for semi-honest or malicious behavior.
Linear-algebra formulation and Stretch/Cut/ColSum operations Honest-but-curious 5PM protocol Malicious-static-corruption protocol and zero-knowledge checks -
scope Functionality and parties explicitly scoped
A server holds text of length n and a client holds a pattern of length m over an arbitrary alphabet; outputs can represent exact, single-wildcard, substring/Hamming matches, with optional pattern-length hiding.
Problem, functionality, and claimed contributions-
threat model Semi-honest and malicious models
definedSeparate constructions address honest-but-curious behavior and static malicious corruption in the stand-alone model; privacy is defined through simulation and allowed leakage such as public length bounds.
Honest-but-curious 5PM protocol Malicious-static-corruption protocol and zero-knowledge checks Simulation-based proof details
-
-
primitive Character-delay-vector matching
algorithmically definedEach pattern character creates delayed contributions to an activation vector; a match is detected where the accumulated value equals the pattern length, with adjustments for wildcards and allowed Hamming distance.
Insecure pattern-matching algorithm and character-delay vectors -
primitive Linear-algebra reduction
proposedMatrix multiplication followed by Stretch, Cut, and column summation expresses matching using additions and scalar products compatible with additive homomorphism.
Linear-algebra formulation and Stretch/Cut/ColSum operations -
protocol Two-round honest-but-curious protocol
proven conditional and implementedThe client encrypts preprocessed pattern material, the server evaluates the linear matching computation over ciphertexts, and the client decrypts the blinded result; security relies on semantic security of the chosen additive homomorphic scheme.
Honest-but-curious 5PM protocol Security theorems and complexity claims -
protocol Eight-round malicious protocol
proven conditional not implementedThreshold ElGamal, commitments, and interleaved zero-knowledge arguments constrain both parties to well-formed encrypted inputs and protocol steps while preserving the algebraic matching path.
Malicious-static-corruption protocol and zero-knowledge checks Security theorems and complexity claims -
formal claim Semi-honest security
theorem in sourceTheorem 1 establishes simulation-based security of the honest-but-curious construction assuming a semantically secure additively homomorphic encryption scheme over the specified group.
Security theorems and complexity claims Simulation-based proof details -
formal claim Malicious security
theorem in sourceTheorem 2 establishes security of the malicious construction under the Decisional Diffie-Hellman assumption and the soundness/zero-knowledge properties of its proof subprotocols.
Security theorems and complexity claims Simulation-based proof details -
formal claim Communication and round complexity
asymptotic analysisThe malicious construction uses O((m+n)k^2) bandwidth and O(m+n) encryptions and completes in eight rounds; the honest-but-curious construction completes in two rounds, with computational work still scaling with pattern-text interactions.
Problem, functionality, and claimed contributions Security theorems and complexity claims -
formal evidence Simulation proof chain
human proofThe full version supplies hybrid/simulator arguments for the protocol components and their composition; this map records the chain but does not independently verify every proof step.
Simulation-based proof details -
empirical evidence Honest-but-curious prototype
measured prototypeA C++ Paillier-based implementation on a dual quad-core 2.93 GHz machine reports, for alphabet 36, pattern 100, and text 10,000, about 7.55 seconds at 1024-bit keys and 25.01 seconds at 2048-bit keys.
Honest-but-curious implementation and benchmark tables -
limitation group Implementation and evidence limits
materialThe malicious protocol is not implemented in the reported evaluation, benchmarks use an older single-machine setup, preprocessing and key generation are separated from online totals, and no public code or independent reproduction was located.
Honest-but-curious implementation and benchmark tables -
artifact group Artifacts
paper and proof onlyThe IACR full version exposes detailed constructions, proofs, and benchmark tables; an author-uploaded full text is also public, but no code repository, test vectors, or locally fixed PDF was obtained.
Simulation-based proof details Honest-but-curious implementation and benchmark tables -
scrutiny External scrutiny and reception
conference and journal reviewedA preliminary version appeared at SCN 2012, a full version later appeared in the Journal of Computer Security, and ResearchGate reports 56 citations; review reports and independent proof/implementation audits were not inspected.
Official conference publication record Subsequent journal full-version record Citation-count snapshot -
lineage Research lineage
documented5PM contributes a reusable linear representation for secure string search and supplies the cryptographic search primitive later used and surveyed in application-oriented private-search work.
Problem, functionality, and claimed contributions Linear-algebra formulation and Stretch/Cut/ColSum operations
Audit trail
Source index
Locators state the depth of the current audit. PDF page numbers, where present, are one-based file pages; metadata-, summary-, and abstract-bounded records explicitly identify their limitations.
- Problem, functionality, and claimed contributions Abstract and Section 1, PDF pages 1-4
- Insecure pattern-matching algorithm and character-delay vectors Section 2.1, PDF pages 5-7
- Linear-algebra formulation and Stretch/Cut/ColSum operations Sections 2.2-2.3, PDF pages 7-10
- Honest-but-curious 5PM protocol Section 3.2, PDF pages 11-12
- Malicious-static-corruption protocol and zero-knowledge checks Section 3.3, PDF pages 12-16
- Security theorems and complexity claims Theorems 1-2 and Section 4, PDF pages 12-18
- Simulation-based proof details Proof sections and appendices, PDF pages 32-48
- Honest-but-curious implementation and benchmark tables Implementation section and Table 13, PDF pages 48-50
- Official conference publication record SCN 2012, pages 222-240, DOI record
- Subsequent journal full-version record Journal of Computer Security 21(5), pages 601-625
- Citation-count snapshot ResearchGate displayed Citations (56), observed 2026-07-11; coverage and merging of conference, ePrint, and journal versions may differ from other indexes.