The DOI matches its Crossref record.
A public-key cryptosystem with worst-case/average-case equivalence
Abstract
We present a probabilistic public key cryptosystem which is secure unless the worst case of the following lattice problem can be solved in polynomial time: "Find the shortest nonzero vector in an n dimensional lattice L where the shortest vector v is unique in the sense that any other vector whose length is at most nckvk is parallel to v."
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
Cited by
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
“On the other hand, one may prefer to generateJ according to a “nice” average-case distribution that permits a worstcase / average-case reduction [1, 2 , 53].”
BackgroundTrapdoors 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. (2009) · Journal of the ACM · doi:10.1145/1568318.1568324 · Cited by 2,315
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
Closest point search in lattices
Agrell, E., Eriksson, T., Vardy, A., & Zeger, K. (2002) · IEEE Transactions on Information Theory · doi:10.1109/tit.2002.800499 · Cited by 1,412
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
CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM
Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., & Stehle, D. (2018) · 2018 IEEE European Symposium on Security and Privacy (EuroS&P) · doi:10.1109/eurosp.2018.00032 · Cited by 1,192
“The first lattice-based encryption scheme was proposed by Ajtai and Dwork [1].”
MethodOn-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption
López-Alt, A., Tromer, E., & Vaikuntanathan, V. (2012) · Proceedings of the forty-fourth annual ACM symposium on Theory of computing · doi:10.1145/2213977.2214086 · Cited by 910
Public-key cryptosystems from the worst-case shortest vector problem: extended abstract
Peikert, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536461 · Cited by 813
Dolev, D., Dwork, C., & Naor, M. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795291562 · Cited by 746
Self-citationBetter Key Sizes (and Attacks) for LWE-Based Encryption
Lindner, R., & Peikert, C. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-19074-2_21 · Cited by 688
A 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
A new public-key cryptosystem as secure as factoring
Okamoto, T., & Uchiyama, S. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0054135 · Cited by 673
Lossy Trapdoor Functions and Their Applications
Peikert, C., & Waters, B. (2011) · SIAM Journal on Computing · doi:10.1137/080733954 · Cited by 649
Classical hardness of learning with errors
Brakerski, Z., Langlois, A., Peikert, C., Regev, O., & Stehlé, D. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488680 · Cited by 627
Micciancio, D., & Regev, O. (2009) · Post-Quantum Cryptography · doi:10.1007/978-3-540-88702-7_5 · Cited by 615
Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures
Lyubashevsky, V. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-10366-7_35 · Cited by 558
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
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
A Survey of Homomorphic Encryption for Nonspecialists
Fontaine, C., & Galand, F. (2007) · EURASIP Journal on Information Security · doi:10.1155/2007/13801 · Cited by 438
Gama, N., & Nguyen, P. Q. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78967-3_3 · Cited by 413
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
Self-citationGenerating Hard Instances of the Short Basis Problem
Ajtai, M. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48523-6_1 · Cited by 396
Self-citationEfficient Public Key Encryption Based on Ideal Lattices: (Extended Abstract)
Stehlé, D., Steinfeld, R., Tanaka, K., & Xagawa, K. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-10366-7_36 · Cited by 369
The impact of quantum computing on present cryptography
Mavroeidis, V., Vishi, K., D., M., & Jøsang, A. (2018) · International Journal of Advanced Computer Science and Applications · doi:10.14569/ijacsa.2018.090354 · Cited by 361
On Cryptographic Assumptions and Challenges
Naor, M. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45146-4_6 · Cited by 360
Quantum Computing since Democritus
Aaronson, S. (2013) · Cambridge University Press eBooks · doi:10.1017/cbo9780511979309 · Cited by 352
Canetti, R., Dwork, C., Naor, M., & Ostrovsky, R. (1997) · Lecture Notes in Computer Science · doi:10.1007/bfb0052229 · Cited by 348
Self-citationQuantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344
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
Lattice-based FHE as secure as PKE
Brakerski, Z., & Vaikuntanathan, V. (2014) · Proceedings of the 5th conference on Innovations in theoretical computer science · doi:10.1145/2554797.2554799 · Cited by 266
A Decade of Lattice Cryptography
Peikert, C. (2016) · now publishers, Inc. eBooks · doi:10.1561/9781680831139 · Cited by 256
The Learning with Errors Problem (Invited Survey)
Regev, O. (2010) · 2010 IEEE 25th Annual Conference on Computational Complexity · doi:10.1109/ccc.2010.26 · Cited by 255
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
Homomorphic Encryption for Machine Learning in Medicine and Bioinformatics
Wood, A., Najarian, K., & Kahrobaei, D. (2021) · ACM Computing Surveys · doi:10.1145/3394658 · Cited by 179
Quantum resistant public key cryptography: a survey
Perlner, R. A., & Cooper, D. A. (2009) · Proceedings of the 8th Symposium on Identity and Trust on the Internet · doi:10.1145/1527017.1527028 · Cited by 137
“[2] M. Ajtai and C. Dwork.”
MethodEfficient Encryption From Random Quasi-Cyclic Codes
Aguilar-Melchor, C., Blazy, O., Deneuville, J.-C., Gaborit, P., & Zemor, G. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2018.2804444 · Cited by 122
Post Quantum Cryptography: A Review of Techniques, Challenges and Standardizations
Bavdekar, R., Jayant Chopde, E., Agrawal, A., Bhatia, A., & Tiwari, K. (2023) · 2023 International Conference on Information Networking (ICOIN) · doi:10.1109/icoin56518.2023.10048976 · Cited by 108
Quantum proofs for classical theorems
(2011) · Theory of Computing · doi:10.4086/toc.gs.2011.002 · Cited by 41
Fujiwara, M., Waseda, A., Nojima, R., Moriai, S., Ogata, W., & Sasaki, M. (2016) · Scientific Reports · doi:10.1038/srep28988 · Cited by 35
Chaudhary, D., Santhi, P., Durgarao, M. S. P., Padmavathi, A., Mehedi Hassan, M., & Fahad Alkhamees, B. (2024) · IEEE Access · doi:10.1109/access.2024.3434691 · Cited by 21
Metadata
- Authors
- Ajtai, M., & Dwork, C.
- Venue
- Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97
- Publisher
- ACM Press
- Published
- 1997
- Volume
- 3
- Pages
- 284-293
- OpenAlex
- W1263653547
- Cited by
- 642
- References
- 0
- FWCI
- 11.48
- 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.