The DOI matches its Crossref record; 59 of the 59 references it cites were found in a registry or an index.
Lattice-Based Cryptography
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
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Factoring polynomials with rational coefficients
Lenstra, A. K., Lenstra, H. W., & Lovász, L. (1982) · Mathematische Annalen · doi:10.1007/bf01457454 · Cited by 4,018
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904
A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
Goldwasser, S., Micali, S., & Rivest, R. L. (1988) · SIAM Journal on Computing · doi:10.1137/0217017 · Cited by 2,804
Trapdoors for hard lattices and new cryptographic constructions
Gentry, C., Peikert, C., & Vaikuntanathan, V. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374407 · Cited by 2,435
On lattices, learning with errors, random linear codes, and cryptography
Regev, O. (2005) · Proceedings of the thirty-seventh annual ACM symposium on Theory of computing · doi:10.1145/1060590.1060603 · Cited by 2,313
Self-citationNTRU: A ring-based public key cryptosystem
Hoffstein, J., Pipher, J., & Silverman, J. H. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0054868 · Cited by 1,947
Integer Programming with a Fixed Number of Variables
Lenstra, H. W. (1983) · Mathematics of Operations Research · doi:10.1287/moor.8.4.538 · Cited by 1,440
Generating hard instances of lattice problems (extended abstract)
Ajtai, M. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237838 · Cited by 1,405
Universal one-way hash functions and their cryptographic applications
Naor, M., & Yung, M. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73011 · Cited by 959
On Lovász’ lattice reduction and the nearest lattice point problem
Babai, L. (1986) · Combinatorica · doi:10.1007/bf02579403 · Cited by 938
Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
Micciancio, D., & Regev, O. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447360 · Cited by 907
Self-citationA Framework for Efficient and Composable Oblivious Transfer
Peikert, C., Vaikuntanathan, V., & Waters, B. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-85174-5_31 · Cited by 678
Lossy Trapdoor Functions and Their Applications
Peikert, C., & Waters, B. (2011) · SIAM Journal on Computing · doi:10.1137/080733954 · Cited by 649
A hierarchy of polynomial time lattice basis reduction algorithms
Schnorr, C. P. (1987) · Theoretical Computer Science · doi:10.1016/0304-3975(87)90064-8 · Cited by 648
A public-key cryptosystem with worst-case/average-case equivalence
Ajtai, M., & Dwork, C. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258604 · Cited by 642
Generating Hard Instances of Lattice ProblemsPreprint
Ajtai, M. (1996) · Electronic colloquium on computational complexity · Cited by 606
Noise-tolerant learning, the parity problem, and the statistical query model
Blum, A., Kalai, A., & Wasserman, H. (2003) · Journal of the ACM · doi:10.1145/792538.792543 · Cited by 598
A sieve algorithm for the shortest lattice vector problem
Ajtai, M., Kumar, R., & Sivakumar, D. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380857 · Cited by 558
A Generalized Birthday Problem
Wagner, D. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45708-9_19 · Cited by 539
Complexity of Lattice Problems
Micciancio, D., & Goldwasser, S. (2002) · Springer eBooks · doi:10.1007/978-1-4615-0897-7 · Cited by 484
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
New bounds in some transference theorems in the geometry of numbers
Banaszczyk, W. (1993) · Mathematische Annalen · doi:10.1007/bf01445125 · Cited by 461
Improved algorithms for integer programming and related lattice problems
Kannan, R. (1983) · Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83 · doi:10.1145/800061.808749 · Cited by 441
Complexity of lattice problems : a cryptographic perspective
Micciancio, D., & Goldwasser, S. (2002) · Cited by 439
Another NP-complete problem and the complexity of computing short vectors in a lattice
Boas, P. V. E. (1981) · Medical Entomology and Zoology · Cited by 412
The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract)
Ajtai, M. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276705 · Cited by 409
Solving low-density subset sum problems
Lagarias, J. C., & Odlyzko, A. M. (1985) · Journal of the ACM · doi:10.1145/2455.2461 · Cited by 397
NTRUSign: Digital Signatures Using the NTRU Lattice
Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J. H., & Whyte, W. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-36563-x_9 · Cited by 302
New lattice-based cryptographic constructions
Regev, O. (2004) · Journal of the ACM · doi:10.1145/1039488.1039490 · Cited by 292
Self-citationGeneralized Compact Knapsacks Are Collision Resistant
Lyubashevsky, V., & Micciancio, D. (2006) · Lecture Notes in Computer Science · doi:10.1007/11787006_13 · Cited by 268
SWIFFT: A Modest Proposal for FFT Hashing
Lyubashevsky, V., Micciancio, D., Peikert, C., & Rosen, A. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-71039-4_4 · Cited by 265
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
Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
Lagarias, J. C., Lenstra, H. W., & Schnorr, C. P. (1990) · Combinatorica · doi:10.1007/bf02128669 · Cited by 251
On the Limits of Nonapproximability of Lattice Problems
Goldreich, O., & Goldwasser, S. (2000) · Journal of Computer and System Sciences · doi:10.1006/jcss.1999.1686 · Cited by 231
Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices
Peikert, C., & Rosen, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_8 · Cited by 229
Coppersmith, D., & Shamir, A. (1997) · Lecture notes in computer science · doi:10.1007/3-540-69053-0_5 · Cited by 216
Hardness of approximating the shortest vector problem in lattices
Khot, S. (2005) · Journal of the ACM · doi:10.1145/1089023.1089027 · Cited by 212
Quantum Computation and Lattice Problems
Regev, O. (2004) · SIAM Journal on Computing · doi:10.1137/s0097539703440678 · Cited by 188
Self-citationA Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU
Howgrave-Graham, N. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-74143-5_9 · Cited by 185
Aharonov, D., & Regev, O. (2005) · Journal of the ACM · doi:10.1145/1089023.1089025 · Cited by 179
Self-citationLattice-Based Identification Schemes Secure Under Active Attacks
Lyubashevsky, V. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78440-1_10 · Cited by 179
Asymptotically Efficient Lattice-Based Digital Signatures
Lyubashevsky, V., & Micciancio, D. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78524-8_3 · Cited by 178
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
Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More
Micciancio, D., & Vadhan, S. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45146-4_17 · Cited by 152
Micciancio, D. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2002.1181960 · Cited by 136
Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures
Nguyễn, P. Q., & Regev, O. (2006) · Lecture notes in computer science · doi:10.1007/11761679_17 · Cited by 130
Self-citationMulti-bit Cryptosystems Based on Lattice Problems
Kawachi, A., Tanaka, K., & Xagawa, K. (2007) · Springer eBooks · doi:10.1007/978-3-540-71677-8_21 · Cited by 99
Immunizing Encryption Schemes from Decryption Errors
Dwork, C., Naor, M., & Reingold, O. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24676-3_21 · Cited by 88
Tensor-based hardness of the shortest vector problem to within almost polynomial factors
Haviv, I., & Regev, O. (2007) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1250790.1250859 · Cited by 88
Self-citationAn improved worst-case to average-case connection for lattice problems
Cai, J., & Nerurkar, A. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646135 · Cited by 85
Lattices that admit logarithmic worst-case to average-case connection factors
Peikert, C., & Rosen, A. (2007) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1250790.1250860 · Cited by 69
Cryptographic Hardness for Learning Intersections of Halfspaces
Klivans, A. R., & Sherstov, A. A. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.24 · Cited by 68
Cryptanalysis of the Ajtai-Dwork cryptosystem
Nguyễn, P. Q., & Stern, J. (1998) · Lecture notes in computer science · doi:10.1007/bfb0055731 · Cited by 57
Hypercubic Lattice Reduction and Analysis of GGH and NTRU Signatures
Szydlo, M. (2003) · Lecture notes in computer science · doi:10.1007/3-540-39200-9_27 · Cited by 55
Representing hard lattices with O(n log n) bits
Ajtai, M. (2005) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1060590.1060604 · Cited by 39
Improved cryptographic hash functions with worst-case/average-case connection
Micciancio, D. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.509995 · Cited by 30
A Faster Lattice Reduction Method Using Quantum Search
Ludwig, C. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-24587-2_22 · Cited by 27
Cryptographic Functions from Worst-Case Complexity Assumptions
Micciancio, D. (2009) · Information security and cryptography · doi:10.1007/978-3-642-02295-1_13 · Cited by 15
Cited by
Efficient Fully Homomorphic Encryption from (Standard) LWE
Brakerski, Z., & Vaikuntanathan, V. (2011) · 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.12 · Cited by 1,449
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
Multiparty Computation from Somewhat Homomorphic Encryption
Damgård, I., Pastro, V., Smart, N., & Zakarias, S. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-32009-5_38 · Cited by 1,331
Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
Micciancio, D., & Peikert, C. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-29011-4_41 · Cited by 1,224
Can homomorphic encryption be practical?
Naehrig, M., Lauter, K., & Vaikuntanathan, V. (2011) · Proceedings of the 3rd ACM workshop on Cloud computing security workshop · doi:10.1145/2046660.2046682 · Cited by 1,004
Metadata
- Authors
- Regev, O.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2006
- Pages
- 131-141
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W1761303171
- Cited by
- 485
- References
- 59
- FWCI
- 7.44
- Type
- conference paper
- Language
- en
- Open access
- closed
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.