The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Fully Homomorphic Encryption over the Integers with Shorter Public Keys
Open accessAbstract
At Eurocrypt 2010 van Dijk et al. described a fully homomorphic encryption scheme over the integers. The main appeal of this scheme (compared to Gentry's) is its conceptual simplicity. This simplicity comes at the expense of a public key size in O(λ10) which is too large for any practical system. In this paper we reduce the public key size to O(λ7) by encrypting with a quadratic form in the public key elements, instead of a linear form. We prove that the scheme remains semantically secure, based on a stronger variant of the approximate-GCD problem, already considered by van Dijk et al. We alsodescribe the first implementation of the resulting fully homomorphic scheme. Borrowing some optimizations from the recent Gentry-Halevi implementation of Gentry's scheme, we obtain roughly the same level of efficiency. This shows that fully homomorphic encryption can be implemented using simple arithmetic operations.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
Paillier, P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_16 · Cited by 7,250
Fully homomorphic encryption using ideal lattices
Gentry, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536440 · Cited by 6,806
Encyclopedia of Mathematics and its Applications.
L., Y. L., Jones, W. B., & Thron, W. J. (1982) · Mathematics of Computation · doi:10.2307/2007638 · Cited by 4,119
A fully homomorphic encryption scheme
Boneh, D., & Gentry, C. (2009) · Cited by 2,341
Lide, R., & Niederreiter, H. (1996) · Cited by 2,213
Fully Homomorphic Encryption over the Integers
van Dijk, M., Gentry, C., Halevi, S., & Vaikuntanathan, V. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13190-5_2 · Cited by 1,858
New hash functions and their use in authentication and set equality
Wegman, M. N., & Carter, J. L. (1981) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(81)90033-7 · Cited by 1,402
Lidl, R. (1983) · Cited by 1,390
(2000) · Lecture Notes in Computer Science · doi:10.1007/10722028 · Cited by 1,001
Advances in Cryptology — EUROCRYPT ’99
(1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x · Cited by 902
Implementing Gentry’s Fully-Homomorphic Encryption Scheme
Gentry, C., & Halevi, S. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-20465-4_9 · Cited by 889
Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes
Smart, N. P., & Vercauteren, F. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13013-7_25 · Cited by 808
Katz, J., & Robshaw, M. J. B. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53018-4 · Cited by 795
Finite fields: Encyclopedia of mathematics and its applications
(1997) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(97)84597-x · Cited by 680
(2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13190-5 · Cited by 500
Public-key cryptosystems from lattice reduction problems
Goldreich, O., Goldwasser, S., & Halevi, S. (1997) · Lecture Notes in Computer Science · doi:10.1007/bfb0052231 · Cited by 482
Gama, N., & Nguyen, P. Q. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78967-3_3 · Cited by 413
The World Is Not Enough: Another Look on Second-Order DPA
Standaert, F., Veyrat-Charvillon, N., Oswald, E., Gierlichs, B., Medwed, M., Kasper, M., & Mangard, S. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-17373-8_7 · Cited by 356
Faster Fully Homomorphic Encryption
Stehlé, D., & Steinfeld, R. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17373-8_22 · Cited by 330
The Two Faces of Lattices in Cryptology
Nguyen, P. Q., & Stern, J. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44670-2_12 · Cited by 252
(2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-20465-4 · Cited by 252
Improved low-density subset sum algorithms
Coster, M. J., Joux, A., LaMacchia, B. A., Odlyzko, A. M., Schnorr, C.-P., & Stern, J. (1992) · Computational Complexity · doi:10.1007/bf01201999 · Cited by 243
Multi-query Computationally-Private Information Retrieval with Constant Communication Rate
Groth, J., Kiayias, A., & Lipmaa, H. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-13013-7_7 · Cited by 214
Improving Lattice Based Cryptosystems Using the Hermite Normal Form
Micciancio, D. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44670-2_11 · Cited by 173
On the multiplicative complexity of Boolean functions over the basis (∧,⊕,1)
Boyar, J., Peralta, R., & Pochuev, D. (2000) · Theoretical Computer Science · doi:10.1016/s0304-3975(99)00182-6 · Cited by 93
A Binary Recursive Gcd Algorithm
Stehlé, D., & Zimmermann, P. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24847-7_31 · Cited by 52
Cited by
(Leveled) fully homomorphic encryption without bootstrapping
Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2012) · Proceedings of the 3rd Innovations in Theoretical Computer Science Conference · doi:10.1145/2090236.2090262 · Cited by 1,782
Gentry, C., Sahai, A., & Waters, B. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40041-4_5 · Cited by 1,492
(Leveled) Fully Homomorphic Encryption without Bootstrapping
Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2014) · ACM Transactions on Computation Theory · doi:10.1145/2633600 · Cited by 1,430
A Survey on Homomorphic Encryption Schemes: Theory and Implementation
Acar, A., Aksu, H., Uluagac, A. S., & Conti, M. (2019) · ACM Computing Surveys · doi:10.1145/3214303 · Cited by 1,397
Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
Brakerski, Z. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-32009-5_50 · Cited by 1,252
Metadata
- Authors
- Coron, J.-S., Mandal, A., Naccache, D., & Tibouchi, M.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2011
- Pages
- 487-504
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W1497981337
- Cited by
- 466
- References
- 27
- FWCI
- 32.66
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.