{"id":"7e6b837b-df78-4e8e-93f1-966b360efbe4","arxiv_id":"2505.15476","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Pura lets twin cloud servers perform face recognition directly on encrypted feature vectors using threshold Paillier encryption, with exact accuracy and up to 16x speedup at database size 1,000.","lead":"This paper describes a face-recognition system in which two cloud servers work on encrypted face data and never see the raw face images or stored templates. The authors report it runs up to 16 times faster than a leading encrypted face-recognition method on small databases, while keeping the same accuracy as unencrypted matching.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Concern: 2-SMIN's comparison value D is not shown to hide x−y; Theorem 2 only proves sign is hidden, and the proof is deferred to prior work.","rationale":"The reader's weakest_assumption is the semi-honest non-colluding twin-server model. That is a genuine limitation, but it is an explicit and standard threat-model assumption: any (2,2)-threshold Paillier scheme collapses if both key shares are combined. I do not treat that as the most load-bearing defect. The more immediate technical risk is that the security of 2-SMIN itself is not actually demonstrated in this manuscript. Algorithm 3 makes S2 learn a plaintext D that is a randomized function of the secret difference x−y. Section VII's Corollary 3 points to Theorem 2, but Theorem 2 argues only that the sign of the comparison is hidden by the random bit π; it says nothing about whether the exact value of D leaks information about x−y. The constraints on r2 (r2≤N/2 and r1+r2>N/2) mean r2 is not drawn from a standard uniform range, so one cannot simply invoke a one-time-pad argument. Since n-SMIN repeats 2-SMIN n−1 times, S2 sees many such D values and could accumulate leakage if any dependence on the distances exists. This is a proof gap rather than a demonstrated break; a self-contained proof or a machine-checked module for 2-SMIN would settle it. Until then, the paper is correctly CONDITIONAL, and I do not move the verdict.","tokens_in":21602,"tokens_out":21733,"duration_ms":194614,"concrete_test":"Independently re-derive the masking lemma for the exact distribution of D in Algorithm 3: for a 1024-bit N and σ=128, compute the statistical distance between the distributions of D induced by x−y=d and x−y=d' for representative d,d', with r1 uniform in [1,2^128) and r2 uniform in [N/2−r1+1, N/2]. If a distinguisher recovers d with advantage larger than 2^−128, or if a chi-square test on 10^6 samples rejects equality of the two distributions, the privacy claim fails; if the distributions are computationally indistinguishable, the proof gap is patchable and the conditional verdict can stand.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Algorithm 3 (Section V-B), S1 sends JdK and Jd1K to S2; S2 threshold-decrypts and learns the plaintext D = r1(x−y+1)+r2 (when π=0) or D = r1(y−x)+r2 (when π=1), with r1 sampled from {0,1}^σ\\{0} and r2 constrained by r2≤N/2 and r1+r2>N/2, so r2 lies in a narrow interval near N/2. Corollary 3's proof (Section VII) asserts that Theorem 2 prevents S2 from learning x, y, and min(x,y), but Theorem 2 only establishes that Pr[D>N/2]=1/2—that is, the sign of the comparison is hidden by the random bit π. It does not establish that the exact value of D is independent of x−y, nor that the constrained distribution of r2 makes D a CPA one-time pad. Because n-SMIN runs 2-SMIN n−1 times (Algorithm 4), S2 accumulates many such D values; any residual dependence of D on the underlying distances would leak comparison outcomes or distance magnitudes, contradicting Theorem 3's no-leakage claim. The proof is delegated to [40], and the +1 offset in the π=0 expression is not covered by the cited lemma. This is a proof gap, not a demonstrated break, but it is load-bearing because it sits at the core of the minimum-computation privacy claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes Pura, a twin-server privacy-preserving face recognition scheme based on the threshold Paillier cryptosystem. The authors design two building blocks: BatchSquare, which securely computes squares of encrypted integers in batches via a packing technique, and 2-SMIN/n-SMIN, which securely compute the minimum of encrypted values. The recognition phase encrypts the probe and the database, computes squared Euclidean distances homomorphically, finds the minimum distance via n-SMIN, and compares it with an encrypted threshold. The paper claims exact accuracy, no client-server interaction after submission, and runtime up to 16 times faster than the state-of-the-art, with experiments on LFW and CASIA-WebFace using 512-dimensional FaceNet features.","tokens_in":21880,"tokens_out":15737,"duration_ms":124048,"significance":"If the security claims were fully proven, Pura would be a practically relevant PPFR construction: the exact-accuracy property is achieved by construction (identical integer arithmetic on plaintext and ciphertext), the architecture is non-interactive for the user, and the benchmarks are concrete and reproducible in the sense that the protocol algebra is spelled out. The main weakness is that the security of the minimum-selection core (2-SMIN) is not rigorously established; the proof for S2's view does not follow from the cited theorem, which only addresses the sign of a blinded comparison. Since the no-leakage claim of the whole system depends on this core, the significance of the contribution is currently limited by an unproven load-bearing step.","major_comments":[{"comment":"The proof that 2-SMIN hides x and y from S2 is incomplete. In Algorithm 3, when π=0, S2 obtains D = r1(x−y+1)+r2, and when π=1, D = r1(y−x)+r2, with r2 ∈ (N/2−r1, N/2]. Theorem 2 only establishes that the sign of D−N/2 is balanced, but S2 also sees the exact integer D. The distribution of D−N/2 is uniform on an interval of length r1 whose location is shifted by r1(x−y+1) (or −r1(y−x)), so the observed value carries information about the magnitude of x−y. Since n-SMIN invokes 2-SMIN n−1 times on distance values that depend on the probe and database, S2 accumulates multiple such observations, which can leak ordinal information about the distances and ultimately about the recognition result. A valid security proof must show that D is statistically or computationally independent of x and y, or provide a simulator for S2's view that does not use x or y; the current proof does neither.","section":"Section VII, Corollary 3 and Algorithm 3"},{"comment":"Theorem 2 is stated without proof and delegated to reference [40], which shares authors with this paper. The theorem's formal claim (Pr[d>N/2]=Pr[d≤N/2]=1/2) is only about the sign of the comparison; it does not state that the distribution of d is independent of x−y, which is what Corollary 3 needs. Moreover, the +1 offset in the π=0 expression is not explicitly covered by the theorem as stated. Please provide a self-contained proof or a precise statement of the result from [40] that covers the exact distribution of d in Algorithm 3, and explain why that result implies that S2 cannot learn x, y, or min(x,y).","section":"Section VII, Theorem 2"},{"comment":"The proof for A_S2 says that 'according to Theorem 1 and Theorem 2, A_S2 fails to obtain x, y and min(x,y) from r1(x−y)+(r1+r2) or r1(y−x)+r2.' This is a non-sequitur: Theorem 1 applies to x+r (an additive one-time pad), while the expression observed by S2 is r1·(x−y)+(r1+r2), in which the difference is multiplied by the secret r1. The proof does not construct a simulator for S2's view, and it does not account for the fact that S2 sees the exact decrypted D, not merely whether D>N/2. Please replace this argument with a full simulation-based proof that handles the actual expression observed by S2.","section":"Section VII, Proof of Corollary 3"}],"minor_comments":[{"comment":"The phrase 'A_S2 and A_S2' should read 'A_S1 and A_S2'.","section":"Section VII, last paragraph"},{"comment":"The sentence 'the proposed encryption scheme has no affect on the performance' contains a typo; 'affect' should be 'effect'.","section":"Section VIII-B"},{"comment":"Figure 4 appears corrupted in the manuscript, with raw font codes such as '/uni00000013' visible; please regenerate the figure.","section":"Figure 4"},{"comment":"The Wilcoxon p-values are reported as exactly 1 for all entries; since Pura and baseline perform identical integer arithmetic, this is expected, but the table should state that the outputs are identical or report the actual test statistic.","section":"Table II"},{"comment":"The constraint on r2 is described as 'r2 ≤ N/2 and r1+r2 > N/2'; please write it explicitly as r2 ∈ (N/2−r1, N/2] for clarity and to aid reproducibility.","section":"Section V-B, Algorithm 3"},{"comment":"The abstract's claim of being 'up to 16 times faster' should be contextualized; from Fig. 7(b), the speedup relative to [28] is about 16x at dataset size 1,000 but only about 2x at 10,000.","section":"Abstract and Section VIII-C"}],"recommendation":"major_revision","confidential_remarks":"The paper relies heavily on the authors' own prior work (SOCI, [40]) for the core security theorem. I recommend that the editors verify that the theorem in [40] indeed covers the exact expression used here, and that the cited reference is not under review elsewhere. The non-collusion assumption, justified by commercial competition, is not cryptographically enforced; if the journal requires security against colluding servers, this limitation should be stated more prominently. The current security analysis of 2-SMIN is the main obstacle to acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: Pura is a well-engineered PPFR scheme with a clean twin-server design and honest exact-accuracy claims. But the security of 2-SMIN is not established: the proof delegates to SOCI [40] while the actual protocol adds a +1 offset and a different randomization, so the cited theorem doesn't apply. The stress-test note is right to flag this.\n\nWhat's genuinely new: the BatchSquare packing is a reasonable improvement over BatchSMUL for squares, and the non-interactive pipeline (database split, parallel computation, mask-and-recover) is a sensible instantiation of the threshold Paillier framework. The experiments are honest about the exactness (it's the same integer arithmetic) and the runtimes are measured, not fitted. I believe the 16x speedup claim is only at 1k database size; at 10k it drops to about 2x, and communication cost overtakes [28] above 9k. That's not dishonest, but it's a narrower win than the abstract suggests.\n\nThe soft spots, in order of importance. First, 2-SMIN. The protocol makes S2 learn D = r1(x−y+1)+r2 or r1(y−x)+r2. The distribution of D is not shown to be independent of x−y. The sign of D−N/2 tells S2 which of the two expressions is positive, and though the random bit π prevents a direct read of the comparison, the magnitude of D is a function of the distance. With repeated runs (as in n-SMIN), S2 can accumulate information about the distances. The proof of Corollary 3 is not self-contained; it cites Theorem 2 from [40], which only shows the sign is balanced, not that the exact value is hidden. This is a load-bearing gap, not a cosmetic one. If the authors can provide a proper simulation-based proof or fix the protocol to mask D's distribution, the paper could be salvageable. Second, the threat model's non-collusion assumption is standard but worth stating as an assumption, not a guarantee. Third, no code or data are released, which makes the benchmark numbers hard to verify independently.\n\nWho is this for? The privacy-preserving biometrics crowd will find the design ideas useful, but only after the security proof is fixed. The paper deserves a serious referee, but the referee should be told to focus on 2-SMIN. I'd not cite it in its current form.","headline":"The architecture is neat and the benchmarks are real, but the core 2-SMIN security proof is a load-bearing gap that the paper's own theorems don't cover.","tokens_in":22459,"tokens_out":15078,"would_cite":false,"duration_ms":121893,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Pura computes face recognition entirely over encrypted features: neither cloud server learns the probe, the database, or the match, and recognition runs up to 16 times faster than prior protocols.","keywords":["privacy-preserving face recognition","threshold Paillier cryptosystem","homomorphic encryption","secure multiparty computation","twin-server architecture","batch secure square","secure minimum protocol","encrypted nearest neighbor search"],"falsifier":"Allow the two servers to exchange their partial keys sk1 and sk2 and run one recognition query; the claim predicts they still learn nothing, whereas a colluding pair would decrypt the probe, the database rows, and the masked result, recovering the user's face and the match identity.","tokens_in":21382,"feed_emoji":"🔐","tokens_out":5996,"duration_ms":48323,"temperature":0.7,"pith_summary":"Privacy-preserving face recognition typically forces a client to interact with the server repeatedly, leaks intermediate feature data to the cloud, or loses recognition accuracy. Pura proposes a twin-server architecture built on the threshold Paillier cryptosystem in which neither server ever sees the plaintext probe, the plaintext database, or the recognition result. The key move is to split the encrypted database between two non-colluding servers and run two carefully built protocols—BatchSquare for computing squared Euclidean distances over packed ciphertexts and n-SMIN for finding a minimum among encrypted distances—so the user only sends one encrypted vector and receives one masked answer. The paper shows that this costs no accuracy: precision, recall, and the equal error rate are identical to a plaintext baseline, while recognition is up to 16 times faster than the previous best protocol.","feed_headline":"Encrypted face recognition runs 16x faster with zero leaks","feed_subtitle":"Squared distances and minimums are computed over Paillier ciphertexts, so neither server ever sees a face.","key_machinery":"Three mechanisms carry the argument. First, the (2,2)-threshold Paillier cryptosystem splits decryption into two partial keys so that no single server can decrypt on its own. Second, BatchSquare, a batch secure-squaring protocol, packs many blinded ciphertexts into one Paillier ciphertext using a shared constant L, lets the second server perform a single threshold decryption to recover the blinded values, and then removes the blinding homomorphically; it extends the earlier BatchSMUL protocol and handles negative inputs by adding a shared offset δ. Third, n-SMIN, a secure minimum protocol built by iterating a two-input comparison 2-SMIN, hides the comparison direction with a random bit π and masks the difference with random numbers r1 and r2. The twin-server split plus an offline random-number generation phase lets both servers compute in parallel, which is what delivers the speedup.","core_discovery":"Pura claims that face recognition can be performed as a non-interactive computation over encrypted data with complete privacy toward both servers. The organization encrypts the feature-vector database under a (2,2)-threshold Paillier public key and horizontally splits the ciphertexts between servers S1 and S2, each holding one partial private key. A user encrypts a probe feature vector and sends it to both servers; the servers jointly compute the squared Euclidean distance between the probe and every database row using the BatchSquare protocol, find the minimum distance with n-SMIN, compare it with an encrypted threshold, and return a masked value that only the user can unmask. Neither server learns the probe, the database contents, the minimum distance, or the identity of the match, provided the two servers are semi-honest and non-colluding. The empirical part reports that Pura matches a plaintext baseline exactly in precision, recall, and EER, and is up to 16 times faster than the BFV-plus-garbled-circuit protocol of Huang and Wang.","pith_inferences":["The privacy guarantee is only as strong as the business incentive against collusion; if a threat model with active or colluding servers is required, the same protocols would need to be wrapped in hardware enclaves or reputation-based slashing to keep the two cloud providers apart.","The same BatchSquare-plus-n-SMIN machinery applies to any nearest-neighbor or threshold-matching task over encrypted fixed-length vectors, not just faces—fingerprints, iris codes, or embeddings for arbitrary objects.","Because communication grows linearly with the database size (about 0.2 GB per 1,000 rows), the scheme will suit moderate galleries; very large galleries would need a hierarchical or indexed search to avoid a full scan.","One could test the protocols on higher-dimensional embeddings (e.g., 1,024-d) and larger galleries to map where BatchSquare's packing limit, which depends on the modulus N and the parameter L, starts to degrade throughput."],"forward_implications":["Users interact once: they encrypt a probe, send it to both servers, and receive a masked result they alone can decrypt; no client-server round trips are needed during recognition.","Database updates are cheap because the encrypted database is stored row-wise rather than column-wise, so a new face is appended to one server's share without re-encrypting the whole database.","Recognition accuracy is unchanged: precision, recall, and equal error rate match a plaintext baseline exactly, because all operations are exact over integers after scaling features by a constant.","A single server storing the encrypted database consumes about 1 GB for 10,000 identities, far less than the BFV-based schemes compared in the paper.","The runtime advantage grows with dataset size: Pura is 16x faster than the best comparison scheme at 1,000 identities and still about 2x faster at 10,000."],"supporting_citations":[{"why":"Supplies the (2,2)-threshold Paillier cryptosystem that underpins every encryption, partial decryption, and threshold decryption in the scheme.","marker":"[29]"},{"why":"Provides the BatchSMUL protocol that BatchSquare extends to compute squares in batches; also motivates the packing with constant L.","marker":"[41]"},{"why":"Contributes the SOCI+ toolkit and offline random-number precomputation mechanism used to speed up the online recognition phase.","marker":"[31]"},{"why":"Gives the SOCI secure-comparison protocol (SCMP) and the security proof of the x+r blinding that the privacy analysis reuses for BatchSMUL, BatchSquare, 2-SMIN and n-SMIN.","marker":"[40]"},{"why":"Serves as the state-of-the-art BFV-plus-garbled-circuit PPFR protocol that Pura is compared against for runtime, storage, and communication.","marker":"[28]"},{"why":"Provides the other FHE-based PPFR baseline whose storage cost and row-wise strategy frame the comparison.","marker":"[23]"},{"why":"Defines the FaceNet model used to extract the 512-dimensional feature vectors from LFW and WebFace images.","marker":"[33]"}],"fun_headline_variants":["Face recognition on encrypted data: 16x faster, fully private","No server sees your face: Pura does encrypted recognition 16x faster","Pura: encrypted face matching with zero data leaks, 16x speedup","Privacy-preserving face recognition: 16x faster with threshold Paillier"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire privacy guarantee assumes the two cloud servers are honest-but-curious and never collude; if they combined their partial private keys, they could decrypt the probe, the database, and the recognition result together.","fun_headline_variants_meta":{"raw":{"variants":["Face recognition on encrypted data: 16x faster, fully private","No server sees your face: Pura does encrypted recognition 16x faster","Pura: encrypted face matching with zero data leaks, 16x speedup","Privacy-preserving face recognition: 16x faster with threshold Paillier"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000192,"raw_usage":{"total_tokens":1330,"prompt_tokens":913,"completion_tokens":417,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":529,"completion_tokens_details":{"reasoning_tokens":335}},"tokens_in":529,"tokens_out":417,"duration_ms":3409,"temperature":1.0,"reasoning_tokens":335,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:17:00.243864+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Allow the two servers to exchange their partial keys sk1 and sk2 and run one recognition query; the claim predicts they still learn nothing, whereas a colluding pair would decrypt the probe, the database rows, and the masked result, recovering the user's face and the match identity.","supporting_citations":[{"cited_title":"Efficient privacy-preserving face identification protocol,","cited_arxiv_id":null,"evidence_quote":"Supplies the (2,2)-threshold Paillier cryptosystem that underpins every encryption, partial decryption, and threshold decryption in the scheme."},{"cited_title":"SOCI: A toolkit for secure outsourced computation on integers,","cited_arxiv_id":null,"evidence_quote":"Provides the BatchSMUL protocol that BatchSquare extends to compute squares in batches; also motivates the packing with constant L."},{"cited_title":"Face recogni- tion: A literature review,","cited_arxiv_id":null,"evidence_quote":"Contributes the SOCI+ toolkit and offline random-number precomputation mechanism used to speed up the online recognition phase."},{"cited_title":"Out- sourceable two-party privacy-preserving biometric authentication,","cited_arxiv_id":null,"evidence_quote":"Serves as the state-of-the-art BFV-plus-garbled-circuit PPFR protocol that Pura is compared against for runtime, storage, and communication."},{"cited_title":"Privacy-preserving face recogni- tion with outsourced computation,","cited_arxiv_id":null,"evidence_quote":"Provides the other FHE-based PPFR baseline whose storage cost and row-wise strategy frame the comparison."}],"review_version":1}