The DOI matches its Crossref record; 84 of the 84 references it cites were found in a registry or an index.
The Two Faces of Lattices in Cryptology
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
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1983) · Communications of the ACM · doi:10.1145/357980.358017 · Cited by 13,012
Handbook of applied cryptography
(1997) · Choice Reviews Online · doi:10.5860/choice.34-4512 · Cited by 10,357
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
Geometric Algorithms and Combinatorial Optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1988) · Algorithms and Combinatorics · doi:10.1007/978-3-642-97881-4 · Cited by 3,431
Sphere Packings, Lattices and Groups.
Coxeter, H. S. M., Conway, J. H., & Sloane, N. J. A. (1989) · The American Mathematical Monthly · doi:10.2307/2323992 · Cited by 3,377
A Course in Computational Algebraic Number Theory
Cohen, H. (1993) · Graduate Texts in Mathematics · doi:10.1007/978-3-662-02945-9 · Cited by 2,567
Sphere Packings, Lattices and Groups
Conway, J. H., & Sloane, N. J. A. (1999) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-1-4757-6568-7 · Cited by 2,223
NTRU: 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
Lattice basis reduction: Improved practical algorithms and solving subset sum problems
Schnorr, C. P., & Euchner, M. (1994) · Mathematical Programming · doi:10.1007/bf01581144 · Cited by 1,427
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
Milnor, J., & Husemoller, D. H. (1973) · Springer eBooks · doi:10.1007/978-3-642-88330-9 · Cited by 1,074
On Lovász’ lattice reduction and the nearest lattice point problem
Babai, L. (1986) · Combinatorica · doi:10.1007/bf02579403 · Cited by 938
Bellare, M., & Rogaway, P. (1995) · Lecture Notes in Computer Science · doi:10.1007/bfb0053428 · Cited by 906
The Decision Diffie-Hellman problem
Boneh, D. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0054851 · Cited by 895
Hiding information and signatures in trapdoor knapsacks
Merkle, R., & Hellman, M. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055927 · Cited by 827
Minkowski's Convex Body Theorem and Integer Programming
Kannan, R. (1987) · Mathematics of Operations Research · doi:10.1287/moor.12.3.415 · Cited by 777
Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities
Coppersmith, D. (1997) · Journal of Cryptology · doi:10.1007/s001459900030 · Cited by 771
Cryptanalysis of short RSA secret exponents
Wiener, M. J. (1990) · IEEE Transactions on Information Theory · doi:10.1109/18.54902 · Cited by 698
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
The development of the number field sieve
(1993) · Lecture Notes in Mathematics · doi:10.1007/bfb0091534 · Cited by 574
TWENTY YEARS OF ATTACKS ON THE RSA CRYPTOSYSTEM
Boneh, D. (1999) · Cited by 568
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
Horadam, K. (2003) · Lecture notes in computer science · doi:10.1007/b93924 · Cited by 524
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
Minkowski, H. (1910) · TIB Hannover · doi:10.14463/gbv:1014770351 · Cited by 432
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
Cryptanalysis of RSA with private key d less than N/sup 0.292/
Boneh, D., & Durfee, G. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.850673 · Cited by 391
An Algorithmic Theory of Numbers, Graphs and Convexity
Lovász, L. (1986) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970203 · Cited by 358
The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations
Arora, S., Babai, L., Stern, J., & Sweedyk, Z. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1472 · Cited by 344
Self-citationShoup, V. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_15 · Cited by 300
Korkine, A., & Zolotareff, G. (1873) · Mathematische Annalen · doi:10.1007/bf01442795 · Cited by 287
Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes
Boneh, D., & Venkatesan, R. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68697-5_11 · Cited by 266
The Shortest Vector Problem in L 2 is NP-hard for Randomized Reductions.Preprint
Ajtai, M. (1997) · Electronic colloquium on computational complexity · Cited by 243
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
Self-citationA knapsack-type public key cryptosystem based on arithmetic in finite fields
Chor, B., & Rivest, R. L. (1988) · IEEE Transactions on Information Theory · doi:10.1109/18.21214 · Cited by 238
Breaking RSA may not be equivalent to factoring: Extended abstract
Boneh, D., & Venkatesan, R. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0054117 · Cited by 235
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
Cryptanalysis of RSA with Private Key d Less than N 0.292
Boneh, D., & Durfee, G. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_1 · Cited by 229
Lattice Attacks on Digital Signature Schemes
Howgrave-Graham, N. A., & Smart, N. P. (2001) · Designs, Codes and Cryptography · doi:10.1023/a:1011214926272 · Cited by 219
Approximate Integer Common Divisors
Howgrave-Graham, N. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44670-2_6 · Cited by 219
Coppersmith, D., & Shamir, A. (1997) · Lecture notes in computer science · doi:10.1007/3-540-69053-0_5 · Cited by 216
RSA-OAEP Is Secure under the RSA Assumption
Fujisaki, E., Okamoto, T., Pointcheval, D., & Stern, J. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_16 · Cited by 206
Self-citationThe rise and fall of knapsack cryptosystems
Odlyzko, A. M. (1991) · Proceedings of Symposia in Applied Mathematics · doi:10.1090/psapm/042/1095552 · Cited by 187
The Insecurity of the Digital Signature Algorithm with Partially Known Nonces
Nguyen, & Shparlinski (2002) · Journal of Cryptology · doi:10.1007/s00145-002-0021-3 · Cited by 176
The Insecurity of the Digital Signature Algorithm with Partially Known Nonces
Shparlinski, I. (2003) · Cryptographic Applications of Analytic Number Theory · doi:10.1007/978-3-0348-8037-4_17 · Cited by 175
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
An Attack on RSA Given a Small Fraction of the Private Key Bits
Boneh, D., Durfee, G., & Frankel, Y. (1998) · Lecture notes in computer science · doi:10.1007/3-540-49649-1_3 · Cited by 172
Solving Simultaneous Modular Equations of Low Degree
Hastad, J. (1988) · SIAM Journal on Computing · doi:10.1137/0217019 · Cited by 170
Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction
Schnorr, C.-P., & Hörner, H. H. (1995) · Lecture notes in computer science · doi:10.1007/3-540-49264-x_1 · Cited by 160
Factorization of a 512-Bit RSA Modulus
Cavallar, S., Dodson, B., Lenstra, A. K., Lioen, W. M., Montgomery, P. L., Murphy, B., teRiele, H. J. J., Aardal, K., Gilchrist, J., Guillerm, G., et al. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45539-6_1 · Cited by 149
Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
Goldreich, O., Micciancio, D., Safra, M., & Seifert, J. (1999) · Information Processing Letters · doi:10.1016/s0020-0190(99)00083-6 · Cited by 146
Cryptanalysis: a survey of recent results
Brickell, E. F., & Odlyzko, A. M. (1988) · Proceedings of the IEEE · doi:10.1109/5.4443 · Cited by 134
Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97
Nguyen, P. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48405-1_18 · Cited by 128
Self-citationAlgorithmic Geometry of Numbers
Kannan, R. (1987) · Annual Review of Computer Science · doi:10.1146/annurev.cs.02.060187.001311 · Cited by 120
Speeding up discrete log and factoring based schemes via precomputations
Boyko, V., Peinado, M., & Venkatesan, R. (1998) · Lecture notes in computer science · doi:10.1007/bfb0054129 · Cited by 118
Reconstructing Truncated Integer Variables Satisfying Linear Congruences
FRIEZE, A. M., Håstad, J., Kannan, R., Lagarias, J. C., & Adi Shamir, Z. (1988) · SIAM Journal on Computing · doi:10.1137/0217016 · Cited by 110
A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem
Adi Shamir, Z. (1982) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1982.5 · Cited by 108
Lattice Reduction in Cryptology: An Update
Nguyễn, P. Q., & Stern, J. (2000) · Lecture notes in computer science · doi:10.1007/10722028_4 · Cited by 106
Self-citationA polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem
Adi Shamir, Z. (1982) · doi:10.1109/sfcs.1982.55 · Cited by 100
Noisy Polynomial Interpolation and Noisy Chinese Remaindering
Bleichenbacher, D., & Nguyễn, P. Q. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45539-6_4 · Cited by 98
Key Recovery and Message Attacks on NTRU-Composite
Gentry, C. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44987-6_12 · Cited by 97
Approximating SVP ∞ to within Almost-Polynomial Factors Is NP-Hard
Dinur, I. (2000) · Lecture notes in computer science · doi:10.1007/3-540-46521-9_22 · Cited by 97
An 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
Why Textbook ElGamal and RSA Encryption Are Insecure
Boneh, D., Joux, A., & Nguyễn, P. Q. (2000) · Lecture notes in computer science · doi:10.1007/3-540-44448-3_3 · Cited by 81
Nguyễn, P. Q., & Stern, J. (1997) · Lecture notes in computer science · doi:10.1007/bfb0052236 · Cited by 80
Self-citationOn the complexity of computing short linearly independent vectors and short bases in a lattice
Blömer, J., & Seifert, J. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301441 · Cited by 70
On the Unpredictability of Bits of the Elliptic Curve Diffie-Hellman Scheme
Boneh, D., & Shparlinski, I. E. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44647-8_12 · Cited by 62
Approximating-CVP to within almost-polynomial factors is NP-hard
Dinur, I., Kindler, G., & Safra, M. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1998.743433 · Cited by 60
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
Self-citationCryptanalysis of the Chor—Rivest Cryptosystem
Vaudenay, S. (2000) · Journal of Cryptology · doi:10.1007/s001450010005 · Cited by 47
On the Security of Diffie-Hellman Bits
Vasco, M. I. G., & Shparlinski, I. E. (2001) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-8295-8_19 · Cited by 45
The Béguin-Quisquater Server-Aided RSA Protocol from Crypto ’95 is not Secure
Nguyen, P., & Stern, J. (1998) · Lecture notes in computer science · doi:10.1007/3-540-49649-1_29 · Cited by 30
Self-citationSquare roots of products of algebraic numbers
Montgomery, P. L. (1994) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/048/1314892 · Cited by 28
Certificates of Recoverability with Scalable Recovery Agent Security
Verheul, E. R. (2000) · Lecture notes in computer science · doi:10.1007/978-3-540-46588-1_18 · Cited by 22
A Montgomery-like square root for the Number Field Sieve
Nguyễn, P. Q. (1998) · Lecture notes in computer science · doi:10.1007/bfb0054859 · Cited by 21
Cited by
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
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
A Decade of Lattice Cryptography
Peikert, C. (2016) · Foundations and TrendsŴ in Theoretical Computer Science · doi:10.1561/0400000074 · Cited by 504
Regev, O. (2006) · Lecture Notes in Computer Science · doi:10.1007/11818175_8 · Cited by 485
Fully Homomorphic Encryption over the Integers with Shorter Public Keys
Coron, J.-S., Mandal, A., Naccache, D., & Tibouchi, M. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-22792-9_28 · Cited by 466
Metadata
- Authors
- Nguyen, P. Q., & Stern, J.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2001
- Pages
- 146-180
- ISSN
- 0302-9743 (ISSN-L)
- OpenAlex
- W2096221836
- Cited by
- 252
- References
- 84
- FWCI
- 5.81
- 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.