Server holds text T of length n over alphabet Sigma; Client holds pattern p of length m, optionally containing wildcards, and learns either matching locations or a decision while Server learns no output.

1. definition

   Matching semantics

   defined

   The same activation-vector construction supports exact matches, single-character wildcards, nonbinary Hamming distance, and thresholded substring matching; multiple distance thresholds can reuse one protocol execution.

   Pattern-matching inputs, outputs, wildcards, and substring semantics · Honest-but-curious protocol and Theorem 1
2. threat model

   Static two-party corruption

   defined

   The formal analyses treat one statically corrupted party in either the honest-but-curious or malicious stand-alone setting; the malicious proof is simulation-based for the stated ideal functionality.

   Ideal functionality, static corruption model, and simulators · HBC and malicious realization theorems
3. assumption

   Cryptographic assumptions

   assumed

   The HBC theorem assumes semantically secure additive homomorphic encryption over a prime-order cyclic group; the concrete malicious construction uses threshold ElGamal and assumes DDH hardness plus the specified commitment and zero-knowledge machinery.

   Cryptographic tools and linear-algebra operators · HBC and malicious realization theorems

5PM transforms the insecure character-delay-vector algorithm into matrix multiplication, Stretch, Cut, and column-sum operations that remain computable when one operand is encrypted.

1. component

   Two-round HBC protocol

   specified and proved

   Client encrypts its character-delay matrix and threshold; Server forms and blinds an encrypted activation vector; Client decrypts zero entries to identify matches.

   Honest-but-curious protocol and Theorem 1
2. component

   Eight-round malicious protocol

   specified and proved

   Both parties independently derive encrypted activation vectors, compare affine hashes, and prove matrix formation, partial decryption, randomization, and final-decryption consistency through interleaved zero-knowledge arguments.

   Eight-round malicious protocol and consistency subprotocols

The paper makes functionality, round/complexity, simulation-security, and implementation-performance claims.

1. claim

   Rounds and asymptotic cost

   analytically supported

   The paper reports two one-way rounds for HBC and eight for malicious security; the malicious construction uses O((m+n)k^2) bandwidth and O(m+n) encryptions, while pattern-length hiding adds no asymptotic computation or bandwidth.

   Problem, functionality, complexity, and round claims · Eight-round malicious protocol and consistency subprotocols
2. claim

   Simulation security

   proved conditional

   Theorems 4 and 5 state realization of the specified pattern-matching functionality for static HBC corruption under semantic security and static malicious corruption under DDH, respectively.

   HBC and malicious realization theorems
3. claim

   HBC implementation

   experimentally supported

   A Paillier-based HBC prototype is timed on one dual-quad-core 2.93 GHz Ubuntu 10.10 machine for DNA and alphanumeric alphabets, text lengths through 100,000, and 1024/2048-bit keys.

   Implementation platform and timing table

Support consists of explicit protocols, ideal-world simulations, asymptotic accounting, and a timing table for an HBC prototype.

1. evidence

   Formal proof path

   paper proof not machine checked

   The full version specifies ideal functionalities and simulators for corrupted Client and Server; this map records the theorem boundaries but has not mechanically checked every hybrid and extractor argument.

   Ideal functionality, static corruption model, and simulators · HBC and malicious realization theorems
2. evidence

   Benchmark evidence

   reported not reproduced

   Table 13 decomposes search, blinding, and decryption time across parameter choices, but supplies neither source code nor repeated-run uncertainty in the audited full version.

   Implementation platform and timing table

The strongest statements are conditional on a static two-party model and cryptographic assumptions; empirical evidence covers only the HBC prototype.

1. limitation

   Unmodeled deployment risks

   out of scope

   The proofs do not cover adaptive corruption, multi-session/composable deployment, leakage through repeated queries, implementation side channels, key compromise, or denial of service.

   Ideal functionality, static corruption model, and simulators
2. limitation

   No malicious-protocol benchmark

   explicitly limited

   The performance section evaluates the honest-but-curious implementation; it does not report an implementation or benchmark of the eight-round malicious protocol.

   Implementation platform and timing table