REVIEW 3 major objections 4 minor 29 references
Bridging the Gap Between PHE and FHE: A Performance and Trade-off Analysis of The Somewhat Homomorphic BGN Cryptosystem
T0 review · 3 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read The paper claims that the BGN cryptosystem, long relegated to theory, is practically deployable for encrypted vector analytics when bandwidth—not computation—is the bottleneck, with 3–6 KB keys and two-digit precision sufficing to reproduce
desk verdict Real, usable BGN implementation with honest trade-off numbers, but the precision-2 ranking claim is unsupported and the abstract overstates what was actually run. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central mechanism is the bilinear pairing e: G1 × G1 → GT, mapping two layer-1 ciphertexts (points on a supersingular elliptic curve) to a multiplicative target group. The pairing annihilates blinding terms, yielding g^{m1·m2}·h_T^R, which can be combined with other such results indefinitely—'boundless aggregation after one multiplication.' This enables encrypted dot products. The complement is two-tier decryption: linear-layer recovery is a bounded-interval DLP; target-layer recovery is a discrete-log search over the accumulated plaintext, which the paper keeps tractable by restricting encoding precision to two digits.
What would settle it
Run the paper's benchmark with three or four decimal digits of precision instead of two, keeping the same 128-dimensional facial embeddings; if the ranking against the plaintext baseline changes, or if decryption time grows beyond, say, an hour, the claim that two digits suffice is refuted. Alternatively, run a 512-dimensional dot product at precision 2: if the encrypted ranking diverges from plaintext or the discrete-log search fails, the 'boundless aggregation' claim is falsified in practice.
Extended reading notes
Core claim
BGN, a pairing-based somewhat-homomorphic scheme, supports unlimited additions and exactly one ciphertext multiplication; that single multiplication projects inputs into a target group where all product terms can be aggregated. This suffices for encrypted cosine similarity, squared Euclidean distance, and linear-regression inference on 128-dimensional vectors. Measured trade-off: the homomorphic dot product takes 209–1451 seconds at 80/112-bit security versus fractions of a second for FHE, while public keys are 3–6 KB versus 45–451 MB. Two-decimal precision is claimed to match plaintext ranking, keeping the final discrete-log decryption within a bounded search. The paper positions BGN as a b
Load-bearing premise
The entire practical viability of BGN hinges on the assumption that the accumulated encrypted values—products of two-digit-decimal encodings summed over 128 dimensions—stay small enough that the target-group discrete-log search can find them in hundreds of seconds and that they never wrap the plaintext modulus; if vector magnitudes, dimensionality, or precision grow, decryption becomes exponentially costlier and the ranking-equivalence claim degrades.
Editorial extensions
If this is right
- An encrypted×encrypted dot product or squared distance can be computed end-to-end over BGN with a public key of a few kilobytes, making privacy-preserving vector queries feasible for edge and IoT clients that cannot download tens or hundreds of megabytes of parameters.
- The same circuit pattern—many additions, one multiplication, then unbounded additions—covers a broad class of quadratic analytics: cosine similarity, squared Euclidean distance, and linear-regression inference on encrypted inputs.
- When one operand is public (encrypted×plain), the paper's benchmarks show PHE schemes are strictly preferable: they are faster by orders of magnitude and support higher precision, so BGN should be reserved for the fully-encrypted case.
- The precision-2 result implies that for typical embedding vectors, quantization to two decimals does not change ranking outcomes, reducing the decryption search space enough to make BGN usable in practice.
- Since BGN key generation is a one-time offline step (about 90 seconds at 1024 bits and up to 16 minutes at 2048 bits), the reported setup cost does not affect online inference after keys are pre-generated.
Reading between the lines
- The paper's implementation is in pure Python, and the reported latencies (hundreds to thousands of seconds) reflect that. A native binding or hardware-accelerated pairing library would likely shrink the computational gap, potentially making BGN competitive even for moderate-scale server-side workloads.
- The precision-2 sufficiency claim rests on the magnitudes of the embedding values and the number of dimensions. Higher-dimensional vectors with larger coordinate ranges would increase the accumulated plaintext and thus the decryption search space; the claimed ranking equivalence should be tested across datasets with different value distributions before being used as a general rule.
- BGN's security depends on factoring and discrete logarithms, so it is not post-quantum resistant. The bandwidth advantage that BGN offers today would not survive a forced migration to lattice-based FHE, suggesting BGN is best suited for short-to-medium-term deployments.
- The algebraic pattern BGN exploits—one multiplication followed by unbounded additions—also appears in other SWHE schemes; the benchmarking methodology here could be reused to compare those schemes under the same bandwidth-vs-latency lens.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper describes a Python implementation of the Boneh-Goh-Nissim (BGN) somewhat homomorphic encryption scheme inside the lightphe library. It presents the mathematical construction (§2): composite-order group generation over a supersingular curve, encryption, unbounded additions, one ciphertext-ciphertext multiplication via pairings, and two-tier decryption. The authors benchmark 128-dimensional encrypted vector operations (cosine similarity and squared Euclidean distance) against three PHE schemes and CKKS via TenSEAL. The reported results show BGN is much slower (homomorphic operations from ~70 s to ~1500 s) but uses public keys of 3–6 KB and ciphertext payloads of 24–56 B, versus 45–451 MB for TenSEAL. The paper further claims that two-decimal precision is sufficient to reproduce plaintext ranking baselines on real LFW/FaceNet embeddings, thereby mitigating BGN's target-group discrete-log decryption bottleneck.
Significance. If fully supported, the paper would be a useful systems contribution: it provides an accessible, open-source BGN implementation, validates the scheme's algebraic behavior, and quantifies a computation-communication trade-off that is genuinely different from both PHE and FHE. The algebraic core as presented is sound: p ≡ 3 (mod 4) under the stated parameter choice, the curve has #E = p+1 = n·l, h has order q1, and the q1 exponentiation in Eqs. (13)–(14) correctly recovers products after a bounded discrete log. The benchmark methodology is largely transparent (same Apple Silicon host, multiple runs, openly available code), and the key-size advantage is large even at 112-bit security (3–6 KB vs. 45–451 MB). The main risk is the precision-2 ranking-fidelity claim, which is asserted without supporting measurement and is essential to the paper's headline conclusion that BGN is practical for bandwidth-constrained analytics.
major comments (3)
- [§4 and Eqs. (13)–(14)] The central claim that precision 2 'suffices to match plaintext ranking baselines' and 'overcomes' the target-group DLP bottleneck is not supported by any reported experiment. Decryption in G_T (Eq. 14) is a discrete-log search whose cost scales with the accumulated plaintext value m, not with the number of additions. For a 128-dimensional dot product or squared Euclidean distance at precision 2, m can be on the order of 10^6 for unit-normalized vectors and much larger otherwise. The paper gives no protocol, no table of m magnitudes, no ranking-agreement metric (e.g., accuracy or rank correlation), and no decryption-time distribution for the claimed LFW/FaceNet experiment. Please add the missing empirical details, including worst-case accumulated values, checks against wrap-around modulo q2, and a clear statement of the normalization and range of the embeddings.
- [Table 4 and abstract (128-bit claim)] The abstract states that benchmarks are run 'under 80-bit, 112-bit and 128-bit security levels,' and the headline comparison emphasizes BGN's key-size advantage over FHE. However, BGN is only evaluated at 80- and 112-bit security (Table 4), while TenSEAL/ CKKS is evaluated at 128-bit. The text acknowledges this mismatch, but the conclusion 'BGN vs. FHE' is still drawn across unequal security tiers. Since §2.1 says 128-bit BGN requires a 3072-bit modulus, the key-size advantage is likely preserved, but it is not measured. Either run BGN at 128-bit or explicitly qualify all cross-scheme comparisons as security-level-dependent; at minimum, add an estimated 128-bit BGN public-key size.
- [Table 3 (Encrypted×Plain BGN)] For an Encrypted×Plain dot product, no ciphertext-ciphertext multiplication is needed; the operation reduces to 128 scalar multiplications plus additions. Yet Table 3 reports BGN homomorphic-operation times of 70–496 s, which are comparable to the encrypted×encrypted times in Table 4. This suggests the benchmark may be encrypting the 'plaintext' vector and running the pairing-based multiplication, which would not represent an Encrypted×Plain scenario. Please specify the exact circuit measured. If pairings are used, the decision rule in §4.1 that BGN 'should be strictly avoided' for Encrypted×Plain is untested; if pairings are not used, the timing needs a concrete explanation.
minor comments (4)
- [Abstract and Section 4] The abstract claims 128-bit BGN benchmarking, but no BGN-128 row appears in Table 4. Please align the abstract with the experiments actually reported.
- [Eq. (14)] The notation 'mod F_p2' and 'g_base ≡ g_target' is nonstandard; the discrete log takes place in the multiplicative group of F_{p^2}, so this should be written in multiplicative group notation, e.g., g_target = g_base^m in F*_{p^2}.
- [Snippet 2 and §2.2] Snippet 2 encrypts negative plaintexts (e.g., -1 and -2), but §2.2 defines plaintext m ∈ Z_n. Please explain how negative values are encoded and how the bounded discrete-log decryption recovers the intended sign.
- [Figure 1] Figure 1 appears to be a citation to an external slide deck rather than a self-contained diagram. Either include a proper figure or remove the reference.
Circularity Check
No significant circularity: BGN performance and precision claims are empirical measurements, not derivations that reduce to their inputs.
full rationale
The paper's central results are (1) BGN supports one ciphertext multiplication followed by unlimited additions, (2) measured key sizes, latencies and ciphertext payloads, and (3) a claimed precision-2 ranking fidelity. Step (1) is the standard BGN construction (Boneh-Goh-Nissim, ref [5], external), reproduced in Eqs. 5-11; the 'boundless aggregation' is just the observation that after pairing all products live in G_T and multiply, which follows from bilinearity by construction rather than from any fitted quantity. Steps (2) are direct measurements of the shipped lightphe code on a stated Apple M4 Max environment; no fitted parameter is renamed as a prediction. Step (3) is presented as an empirical validation ('our empirical validation confirmed ... identical similarity metrics and distance rankings'), not derived from first principles; although the paper omits the LFW/FaceNet ranking table and treats precision 2 as 'optimal,' that is an evidence/reproducibility gap, not a definitional equivalence. The self-citations ([6], [24], [25], [28]) are used for the framework and benchmark suites, not to establish BGN's algebra, and no uniqueness theorem or ansatz is imported from the authors' prior work. The paper's own limitations (no 128-bit BGN execution, recommendation to prefer PHE for encrypted×plain workloads) further show the conclusions are scoped measurements rather than forced by a self-citation chain.
Assumptions & free parameters
free parameters (5)
- BGN decimal precision =
2 digits
- PHE decimal precision =
19 digits
- TenSEAL #1 parameters =
n=2^13, log2 q=200, scale 2^40
- TenSEAL #2 parameters =
n=2^14, log2 q=422, scale 2^60
- BGN modulus size / security labels =
1024-bit -> 80-bit; 2048-bit -> 112-bit
assumptions (5)
- domain assumption Hardness of factoring n = q1*q2 and the subgroup decision problem on E(F_p) secure BGN.
- standard math For p ≡ 3 (mod 4), E: y^2 = x^3 + x over F_p is supersingular with #E(F_p) = p + 1 = n*l.
- standard math A non-degenerate modified Tate pairing with distortion map (lightecc dependency) is computable over F_{p^2}.
- domain assumption Precision-2 encoded plaintexts and their 128-term aggregates stay well below q2 and within the decryption DLP search range.
- domain assumption TenSEAL configurations (n=2^13, log2 q=200, scale 2^40; n=2^14, log2 q=422, scale 2^60) satisfy the HE Security Standard at 128-bit.
Cite this review
Pith. "Pith review of Bridging the Gap Between PHE and FHE: A Performance and Trade-off Analysis of The Somewhat Homomorphic BGN Cryptosystem." pith.science (2026). https://pith.science/paper/BTHWKUGU
@misc{pith2026260728700,
author = {Pith},
title = {Pith review of: Bridging the Gap Between PHE and FHE: A Performance and Trade-off Analysis of The Somewhat Homomorphic BGN Cryptosystem},
year = {2026},
howpublished = {\url{https://pith.science/paper/BTHWKUGU}},
note = {Machine review of arXiv:2607.28700}
}
read the original abstract
Homomorphic encryption (HE) enables privacy-preserving data analytics, but practitioners often face a trade-off between lightweight Partially Homomorphic Encryption (PHE) and computationally dominant Fully Homomorphic Encryption (FHE). The Boneh-Goh-Nissim (BGN) cryptosystem bridges this gap as a Somewhat Homomorphic Encryption (SWHE) scheme supporting unlimited additions and one ciphertext multiplication. Despite its algebraic elegance, practical BGN adoption has been hindered by a lack of accessible software implementations. This paper presents a comparative analysis of BGN against PHE and FHE paradigms through its integration into the lightphe Python framework, allowing deployment in just a few lines of code. We benchmark encrypted 128-dimensional vector operations under 80-bit, 112-bit and 128-bit security levels against Paillier, Damgard-Jurik, Okamoto-Uchiyama, and the FHE CKKS scheme via TenSEAL. Results reveal a computation-communication trade-off: BGN is computationally slower due to bilinear pairings compared to PHE and SIMD-optimized FHE, but retains a microscopic public key size of 3-6 KB, up to five orders of magnitude smaller than FHE. Crucially, BGN enables boundless homomorphic aggregation after a single multiplication, supporting complex tasks such as linear regression inference, Cosine Similarity, and Squared Euclidean Distance. Furthermore, an optimized precision of 2 digits suffices to match plaintext ranking baselines, overcoming the target-group discrete logarithm decryption bottleneck. By open-sourcing this pipeline in lightphe, this work establishes BGN as a practical engine for bandwidth-constrained, decentralized architectures.
Figures
Reference graph
Works this paper leans on
-
[1]
Springer, 2021
Cetin Kaya Koc, Funda Ozdemir, and Zeynep Odemis Ozger.Partially Homomorphic Encryption. Springer, 2021
2021
-
[2]
Fully homomorphic encryption using ideal lattices
Craig Gentry. Fully homomorphic encryption using ideal lattices. InProceedings of the 41st Annual ACM Symposium on Theory of Computing, pages 169–178, 2009. doi:10.1145/1536414.1536440
arXiv 2009
-
[3]
Homomorphic encryption for arithmetic of approximate numbers
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. InInternational conference on the theory and application of cryptology and information security, pages 409–437. Springer, 2017
2017
-
[4]
(leveled) fully homomorphic encryption without bootstrapping.ACM Transactions on Computation Theory (TOCT), 6(3):1–36, 2014
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping.ACM Transactions on Computation Theory (TOCT), 6(3):1–36, 2014
2014
-
[5]
Evaluating 2-dnf formulas on ciphertexts
Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. Evaluating 2-dnf formulas on ciphertexts. InTheory of cryptography conference, pages 325–341. Springer, 2005
2005
-
[6]
Alper Ozpinar and Sefik Ilkin Serengil. Sustainable cryptography: Carbon asymmetry in partially homomorphic encryption in the cloud.Symmetry, 18(5):832, 2026. doi:10.3390/sym18050832. URL https://www.mdpi. com/2073-8994/18/5/832. Special Issue: Symmetry in Cryptography and Cybersecurity
-
[7]
Rivest, Adi Shamir, and Leonard Adleman
Ronald L. Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems.Communications of the ACM, 21(2):120–126, 1978. doi:10.1145/359340.359342
arXiv 1978
-
[8]
Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms.IEEE Transactions on Information Theory, 31(4):469–472, 1985. doi:10.1109/TIT.1985.1057074
arXiv 1985
Show all 29 references
-
[9]
Sutikno, A
S. Sutikno, A. Surya, and R. Effendi. An implementation of elgamal elliptic curves cryptosystems. InIEEE Asia-Pacific Conference on Circuits and Systems, pages 483–486, 1998. doi:10.1109/APCCAS.1998.743829
1998
-
[10]
Victor S. Miller. Use of elliptic curves in cryptography. InAdvances in Cryptology. CRYPTO 1985, pages 417–426. Springer, 1985. doi:10.1007/3-540-39799-X_31
1985 doi
-
[11]
Elliptic curve cryptosystems.Mathematics of Computation, 48(177):203–209, 1987
Neal Koblitz. Elliptic curve cryptosystems.Mathematics of Computation, 48(177):203–209, 1987. doi:10.1090/S0025-5718-1987-0866109-5
1987 doi
-
[12]
Harold M. Edwards. A normal form for elliptic curves.Bulletin of the American Mathematical Society, 44(3): 393–422, 2007. doi:10.1090/S0273-0979-07-01153-6
2007 doi
-
[13]
Public-key cryptosystems based on composite degree residuosity classes
Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. InAdvances in Cryptology. EUROCRYPT 1999, pages 223–238. Springer, 1999. doi:10.1007/3-540-48910-X_16
1999 doi
-
[14]
A generalisation, a simplification and some applications of paillier’s probabilistic public-key system
Ivan Damgård and Mads Jurik. A generalisation, a simplification and some applications of paillier’s probabilistic public-key system. InPublic Key Cryptography. PKC 2001, pages 119–136. Springer, 2001. doi:10.1007/3-540- 44586-2_9. 15 Bridging PHE and FHE: Performance Analysis ...
2001 doi
-
[15]
A new public-key cryptosystem as secure as factoring
Tatsuaki Okamoto and Shigenori Uchiyama. A new public-key cryptosystem as secure as factoring. InAdvances in Cryptology. EUROCRYPT 1998, pages 308–318. Springer, 1998. doi:10.1007/BFb0054135
1998 doi
-
[16]
Dense probabilistic encryption
Josh Benaloh. Dense probabilistic encryption. InSelected Areas in Cryptography, pages 120–128, 1994
1994
-
[17]
A new public key cryptosystem based on higher residues
David Naccache and Jacques Stern. A new public key cryptosystem based on higher residues. InProceed- ings of the 5th ACM Conference on Computer and Communications Security, pages 59–66. ACM, 1998. doi:10.1145/288090.288106
1998
-
[18]
Probabilistic encryption.Journal of Computer and System Sciences, 28(2): 270–299, 1984
Shafi Goldwasser and Silvio Micali. Probabilistic encryption.Journal of Computer and System Sciences, 28(2): 270–299, 1984. ISSN 0022-0000. doi:10.1016/0022-0000(84)90070-9
1984 doi
-
[19]
Non-interactive cryptocomputing for nc/sup 1
Tomas Sander, Adam Young, and Moti Yung. Non-interactive cryptocomputing for nc/sup 1. In40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 554–566. IEEE, 1999
1999
-
[20]
Tenseal: A library for encrypted tensor operations using homomorphic encryption, 2021
Ayoub Benaissa, Bilal Retiat, Bogdan Cebere, and Alaa Eddine Belfedhal. Tenseal: A library for encrypted tensor operations using homomorphic encryption, 2021
2021
-
[21]
Victor S. Miller. The Weil pairing, and its efficient calculation.Journal of Cryptology, 17(4):235–261, 2004. doi:10.1007/s00145-004-0315-8. Presented at CRYPTO 1985
2004 doi
-
[22]
Short signatures from the Weil pairing
Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the Weil pairing. In Colin Boyd, editor, Advances in Cryptology — ASIACRYPT 2001, volume 2248 ofLecture Notes in Computer Science, pages 514–532. Springer, 2001. doi:10.1007/3-540-45682-1_3
2001 doi
-
[23]
Pairings are not dead, just resting
D Aranha. Pairings are not dead, just resting. In21st Workshop on Elliptic Curve Cryptography, (November 2017), 2017. URLhttps://ecc2017.cs.ru.nl/slides/ecc2017-aranha.pdf
2017
-
[24]
Encrypted vector similarity computations using partially homomor- phic encryption: Applications and performance analysis.arXiv preprint arXiv:2503.05850, 2025
Sefik Serengil and Alper Ozpinar. Encrypted vector similarity computations using partially homomor- phic encryption: Applications and performance analysis.arXiv preprint arXiv:2503.05850, 2025. doi: 10.48550/arXiv.2503.05850. [Online]. Available:https://arxiv.org/abs/2503.05850
-
[25]
Cipherface: A fully homomorphic encryption-driven framework for secure cloud-based facial recognition.arXiv preprint arXiv:2502.18514, 2025
Sefik Serengil and Alper Ozpinar. Cipherface: A fully homomorphic encryption-driven framework for secure cloud-based facial recognition.arXiv preprint arXiv:2502.18514, 2025. doi: 10.48550/arXiv.2502.18514. [Online]. Available:https://arxiv.org/abs/2502.18514
-
[26]
Labeled faces in the wild: A database for studying face recognition in unconstrained environments
Gary B Huang, Manu Ramesh, Tamara Berg, and Erik Learned-Miller. Labeled faces in the wild: A database for studying face recognition in unconstrained environments. Technical Report 07-49, University of Massachusetts, Amherst, 2007
2007
-
[27]
Facenet: A unified embedding for face recognition and clustering
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 815–823, 2015
2015
-
[28]
Lightface: A hybrid deep face recognition framework
Sefik Ilkin Serengil and Alper Ozpinar. Lightface: A hybrid deep face recognition framework. In2020 innovations in intelligent systems and applications conference (ASYU), pages 1–5. IEEE, 2020
2020
-
[29]
On ideal lattices and learning with errors over rings
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Annual international conference on the theory and applications of cryptographic techniques, pages 1–23. Springer, 2010. 16
2010
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.