{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:49:05Z","timestamp":1767340145152},"reference-count":66,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s00145-020-09365-w","type":"journal-article","created":{"date-parts":[[2021,1,6]],"date-time":"2021-01-06T02:02:59Z","timestamp":1609898579000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Toward Non-interactive Zero-Knowledge Proofs for NP from LWE"],"prefix":"10.1007","volume":"34","author":[{"given":"Ron D.","family":"Rothblum","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Sealfon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katerina","family":"Sotiraki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,1,6]]},"reference":[{"key":"9365_CR1","doi-asserted-by":"crossref","unstructured":"B. Applebaum, D. Cash, C. Peikert, and A. Sahai. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In CRYPTO, 2009.","DOI":"10.1007\/978-3-642-03356-8_35"},{"key":"9365_CR2","volume-title":"David Mandell Freeman, and Vinod Vaikuntanathan","author":"S Agrawal","year":"2011","unstructured":"S. Agrawal, D.M. Freeman, and V. Vaikuntanathan. Functional encryption for inner product predicates from learning with errors. In ASIACRYPT, 2011."},{"key":"9365_CR3","unstructured":"N. Alamati, C. Peikert, and N. Stephens-Davidowitz. New (and old) proof systems for lattice problems. Cryptology ePrint Archive, Report 2017\/1226, 2017."},{"issue":"6","key":"9365_CR4","doi-asserted-by":"publisher","first-page":"1084","DOI":"10.1137\/0220068","volume":"20","author":"M Blum","year":"1991","unstructured":"M. Blum, A. De\u00a0Santis, S. Micali, and G. Persiano. Noninteractive zero-knowledge. SIAM Journal on Computing, 20(6):1084\u20131118, 1991.","journal-title":"SIAM Journal on Computing"},{"key":"9365_CR5","doi-asserted-by":"crossref","unstructured":"M. Blum, P. Feldman, and S. Micali. Non-interactive zero-knowledge and its applications (extended abstract). In STOC, 1988.","DOI":"10.1145\/62212.62222"},{"key":"9365_CR6","volume-title":"Ring signatures: Stronger definitions, and constructions without random oracles","author":"A Bender","year":"2006","unstructured":"A. Bender, J. Katz, and R. Morselli. Ring signatures: Stronger definitions, and constructions without random oracles. In TCC. Springer, 2006."},{"key":"9365_CR7","doi-asserted-by":"crossref","unstructured":"M. Bellare, D. Micciancio, and B. Warinschi. Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions. In EUROCRYPT, 2003.","DOI":"10.1007\/3-540-39200-9_38"},{"key":"9365_CR8","doi-asserted-by":"crossref","unstructured":"N. Bitansky and O. Paneth. Zaps and non-interactive witness indistinguishability from indistinguishability obfuscation. In TCC, 2015.","DOI":"10.1007\/978-3-662-46497-7_16"},{"key":"9365_CR9","doi-asserted-by":"crossref","unstructured":"M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In CCS, 1993.","DOI":"10.1145\/168588.168596"},{"key":"9365_CR10","first-page":"114","volume":"2017","author":"I Berman","year":"2017","unstructured":"I. Berman, R.D. Rothblum, and V. Vaikuntanathan. Zero-knowledge proofs of proximity. IACR Cryptology ePrint Archive, 2017:114, 2017.","journal-title":"IACR Cryptology ePrint Archive"},{"issue":"2","key":"9365_CR11","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1137\/120868669","volume":"43","author":"Z Brakerski","year":"2014","unstructured":"Z. Brakerski and V. Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. SIAM J. Comput., 43(2):831\u2013871, 2014.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9365_CR12","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/BF00208000","volume":"9","author":"M Bellare","year":"1996","unstructured":"M. Bellare and M. Yung. Certifying permutations: Noninteractive zero-knowledge based on any trapdoor permutation. J. Cryptology, 9(3):149\u2013166, 1996.","journal-title":"J. Cryptology"},{"key":"9365_CR13","doi-asserted-by":"crossref","unstructured":"R. Canetti, Y. Chen, J. Holmgren, A. Lombardi, G.N. Rothblum, R.D. Rothblum, and D. Wichs. Fiat-Shamir: from practice to theory. In STOC, 2019.","DOI":"10.1145\/3313276.3316380"},{"key":"9365_CR14","doi-asserted-by":"crossref","unstructured":"R. Canetti, Y. Chen, L. Reyzin, and R.D. Rothblum. Fiat-Shamir and correlation intractability from strong kdm-secure encryption. Cryptology ePrint Archive, Report 2018\/131, 2018.","DOI":"10.1007\/978-3-319-78381-9_4"},{"issue":"4","key":"9365_CR15","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1145\/1008731.1008734","volume":"51","author":"R Canetti","year":"2004","unstructured":"R. Canetti, O. Goldreich, and S. Halevi. The random oracle methodology, revisited. J. ACM, 51(4):557\u2013594, 2004.","journal-title":"J. ACM"},{"key":"9365_CR16","doi-asserted-by":"crossref","unstructured":"G. Couteau and D. Hofheinz. Designated-verifier pseudorandom generators, and their applications. In EUROCRYPT, 2019.","DOI":"10.1007\/978-3-030-17656-3_20"},{"key":"9365_CR17","first-page":"631","volume":"2017","author":"R Canetti","year":"2017","unstructured":"R. Canetti and A. Lichtenberg. Certifying trapdoor permutations, revisited. IACR Cryptology ePrint Archive, 2017:631, 2017.","journal-title":"IACR Cryptology ePrint Archive"},{"issue":"4","key":"9365_CR18","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1137\/S0036144503429856","volume":"45","author":"D Dolev","year":"2003","unstructured":"D. Dolev, C. Dwork, and M. Naor. Nonmalleable cryptography. SIAM Review, 45(4):727\u2013784, 2003.","journal-title":"SIAM Review"},{"issue":"6","key":"9365_CR19","doi-asserted-by":"publisher","first-page":"1513","DOI":"10.1137\/S0097539703426817","volume":"36","author":"C Dwork","year":"2007","unstructured":"C. Dwork and M. Naor. Zaps and their applications. SIAM J. Comput., 36(6):1513\u20131543, 2007.","journal-title":"SIAM J. Comput."},{"key":"9365_CR20","doi-asserted-by":"crossref","unstructured":"R. del Pino and V. Lyubashevsky. Amortization with fewer equations for proving knowledge of small secrets. In CRYPTO, 2017.","DOI":"10.1007\/978-3-319-63697-9_13"},{"issue":"1","key":"9365_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539792230010","volume":"29","author":"U Feige","year":"1999","unstructured":"U. Feige, D. Lapidot, and A. Shamir. Multiple noninteractive zero knowledge proofs under general assumptions. SIAM J. Comput., 29(1):1\u201328, 1999.","journal-title":"SIAM J. Comput."},{"key":"9365_CR22","unstructured":"A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In CRYPTO, 1986."},{"issue":"3","key":"9365_CR23","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1006\/jcss.1999.1686","volume":"60","author":"O Goldreich","year":"2000","unstructured":"O. Goldreich and S. Goldwasser. On the limits of nonapproximability of lattice problems. J. Comput. Syst. Sci., 60(3):540\u2013563, 2000.","journal-title":"J. Comput. Syst. Sci."},{"key":"9365_CR24","unstructured":"S. Goldwasser and Y.T. Kalai. On the (in)security of the fiat-shamir paradigm. In FOCS, 2003."},{"key":"9365_CR25","doi-asserted-by":"crossref","unstructured":"S. Goldwasser and D. Kharchenko. Proof of plaintext knowledge for the ajtai-dwork cryptosystem. In TCC, 2005.","DOI":"10.1007\/978-3-540-30576-7_29"},{"key":"9365_CR26","unstructured":"Y. Gertner, S. Kannan, T. Malkin, O. Reingold, and M. Viswanathan. The relationship between public key encryption and oblivious transfer. In FOCS, 2000."},{"key":"9365_CR27","volume-title":"Raluca Ada Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich","author":"S Goldwasser","year":"2013","unstructured":"S. Goldwasser, Y. Kalai, R.A. Popa, V. Vaikuntanathan, and N. Zeldovich. Reusable garbled circuits and succinct functional encryption. In STOC, 2013."},{"key":"9365_CR28","first-page":"274","volume":"2017","author":"R Goyal","year":"2017","unstructured":"R. Goyal, V. Koppula, and B. Waters. Lockable obfuscation. IACR Cryptology ePrint Archive, 2017:274, 2017.","journal-title":"Lockable obfuscation. IACR Cryptology ePrint Archive"},{"issue":"2","key":"9365_CR29","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S Goldwasser","year":"1984","unstructured":"S. Goldwasser and S. Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270\u2013299, 1984.","journal-title":"J. Comput. Syst. Sci."},{"key":"9365_CR30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891","volume-title":"The Foundations of Cryptography -","author":"O Goldreich","year":"2001","unstructured":"O. Goldreich. The Foundations of Cryptography - Volume 1, Basic Techniques. Cambridge University Press, 2001."},{"key":"9365_CR31","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721656","volume-title":"The Foundations of Cryptography -","author":"O Goldreich","year":"2004","unstructured":"O. Goldreich. The Foundations of Cryptography - Volume 2, Basic Applications. Cambridge University Press, 2004."},{"key":"9365_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22670-0_28","volume-title":"Basing non-interactive zero-knowledge on (enhanced) trapdoor permutations: The state of the art","author":"O Goldreich","year":"2011","unstructured":"O. Goldreich. Basing non-interactive zero-knowledge on (enhanced) trapdoor permutations: The state of the art. In Studies in Complexity and Cryptography. Springer Berlin Heidelberg, 2011."},{"key":"9365_CR33","doi-asserted-by":"crossref","unstructured":"J. Groth, R. Ostrovsky, and A. Sahai. New techniques for noninteractive zero-knowledge. J. ACM, 59(3):11:1\u201311:35, 2012.","DOI":"10.1145\/2220357.2220358"},{"issue":"3","key":"9365_CR34","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1007\/s00145-012-9131-8","volume":"26","author":"O Goldreich","year":"2013","unstructured":"O. Goldreich and R.D. Rothblum. Enhancements of trapdoor permutations. J. Cryptology, 26(3):484\u2013512, 2013.","journal-title":"J. Cryptology"},{"key":"9365_CR35","doi-asserted-by":"crossref","unstructured":"J. Groth. Short pairing-based non-interactive zero-knowledge arguments. In ASIACRYPT, 2010.","DOI":"10.1007\/978-3-642-17455-1_13"},{"key":"9365_CR36","unstructured":"J. Groth and A. Sahai. Efficient non-interactive proof systems for bilinear groups. In EUROCRYPT, 2008."},{"key":"9365_CR37","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48000-7_25","volume-title":"Predicate encryption for circuits from lwe","author":"S Gorbunov","year":"2015","unstructured":"S. Gorbunov, V. Vaikuntanathan, and H. Wee. Predicate encryption for circuits from lwe. In CRYPTO. Springer, 2015."},{"key":"9365_CR38","doi-asserted-by":"crossref","unstructured":"S. Katsumata, R. Nishimaki, S. Yamada, and T. Yamakawa. Designated verifier\/prover and preprocessing nizks from diffie-hellman assumptions. In EUROCRYPT, 2019.","DOI":"10.1007\/978-3-030-17656-3_22"},{"key":"9365_CR39","doi-asserted-by":"crossref","unstructured":"Y.T. Kalai, G.N. Rothblum, and R.D. Rothblum. From obfuscation to the security of fiat-shamir for proofs. In CRYPTO, 2017.","DOI":"10.1007\/978-3-319-63715-0_8"},{"key":"9365_CR40","doi-asserted-by":"crossref","unstructured":"A. Kawachi, K. Tanaka, and K. Xagawa. Concurrently secure identification schemes based on the worst-case hardness of lattice problems. In ASIACRYPT, 2008.","DOI":"10.1007\/978-3-540-89255-7_23"},{"key":"9365_CR41","doi-asserted-by":"crossref","unstructured":"S. Kim and D.J. Wu. Multi-theorem preprocessing nizks from lattices. In CRYPTO, 2018.","DOI":"10.1007\/978-3-319-96881-0_25"},{"key":"9365_CR42","doi-asserted-by":"crossref","unstructured":"B. Libert, S. Ling, F. Mouhartem, K. Nguyen, and H. Wang. Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions. In ASIACRYPT, 2016.","DOI":"10.1007\/978-3-662-53890-6_13"},{"key":"9365_CR43","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky and D. Micciancio. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In CRYPTO, 2009.","DOI":"10.1007\/978-3-642-03356-8_34"},{"key":"9365_CR44","doi-asserted-by":"crossref","unstructured":"S. Ling, K. Nguyen, D. Stehl\u00e9, and H. Wang. Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications. In PKC, 2013.","DOI":"10.1007\/978-3-642-36362-7_8"},{"key":"9365_CR45","first-page":"242","volume":"2019","author":"A Lombardi","year":"2019","unstructured":"A. Lombardi, W. Quach, R.D. Rothblum, D. Wichs, and D.J. Wu. New constructions of reusable designated-verifier nizks. IACR Cryptology ePrint Archive, 2019:242, 2019.","journal-title":"IACR Cryptology ePrint Archive"},{"key":"9365_CR46","unstructured":"V. Lyubashevsky. Lattice-based identification schemes secure under active attacks. In PKC, 2008."},{"key":"9365_CR47","doi-asserted-by":"crossref","unstructured":"D. Micciancio and S. Vadhan. Statistical zero-knowledge proofs with efficient provers: Lattice problems and more. CRYPTO, 2003.","DOI":"10.1007\/978-3-540-45146-4_17"},{"key":"9365_CR48","doi-asserted-by":"crossref","unstructured":"P. Mukherjee and D. Wichs. Two round multiparty computation via multi-key FHE. In EUROCRYPT, 2016.","DOI":"10.1007\/978-3-662-49896-5_26"},{"key":"9365_CR49","doi-asserted-by":"crossref","unstructured":"M. Naor. On cryptographic assumptions and challenges. In CRYPTO, 2003.","DOI":"10.1007\/978-3-540-45146-4_6"},{"key":"9365_CR50","doi-asserted-by":"crossref","unstructured":"M. Naor and M. Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In STOC, 1990.","DOI":"10.1145\/100216.100273"},{"key":"9365_CR51","doi-asserted-by":"crossref","unstructured":"C. Peikert. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In STOC, 2009.","DOI":"10.1145\/1536414.1536461"},{"key":"9365_CR52","first-page":"158","volume":"2019","author":"C Peikert","year":"2019","unstructured":"C. Peikert and S. Shiehian. Noninteractive zero knowledge for NP from (plain) learning with errors. IACR Cryptology ePrint Archive, 2019:158, 2019.","journal-title":"IACR Cryptology ePrint Archive"},{"key":"9365_CR53","unstructured":"C. Peikert and V. Vaikuntanathan. Noninteractive statistical zero-knowledge proofs for lattice problems. In CRYPTO, 2008."},{"key":"9365_CR54","unstructured":"C. Peikert, V. Vaikuntanathan, and B. Waters. A framework for efficient and composable oblivious transfer. In CRYPTO, 2008."},{"key":"9365_CR55","doi-asserted-by":"crossref","unstructured":"C. Peikert and B. Waters. Lossy trapdoor functions and their applications. In STOC, 2008.","DOI":"10.1145\/1374376.1374406"},{"key":"9365_CR56","doi-asserted-by":"crossref","unstructured":"W. Quach, R.D. Rothblum, and D. Wichs. Reusable designated-verifier nizks for all NP from CDH. In EUROCRYPT, 2019.","DOI":"10.1007\/978-3-030-17656-3_21"},{"key":"9365_CR57","volume-title":"Digitalized Signatures and Public-key Functions as Intractable as Factorization","author":"MO Rabin","year":"1979","unstructured":"M.O. Rabin. Digitalized Signatures and Public-key Functions as Intractable as Factorization. Laboratory for Computer Science. Massachusetts Institute of Technology, Laboratory for Computer Science, 1979."},{"key":"9365_CR58","doi-asserted-by":"crossref","unstructured":"O. Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):34:1\u201334:40, 2009.","DOI":"10.1145\/1568318.1568324"},{"key":"9365_CR59","doi-asserted-by":"crossref","unstructured":"R.D. Rothblum, A. Sealfon, and K. Sotiraki. Towards non-interactive zero-knowledge for np from lwe. In D. Lin and K. Sako, editors, Public-Key Cryptography \u2013 PKC 2019, pages 472\u2013503, Cham, 2019. Springer International Publishing.","DOI":"10.1007\/978-3-030-17259-6_16"},{"key":"9365_CR60","unstructured":"A. Sahai. Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In FOCS, 1999."},{"issue":"2","key":"9365_CR61","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1137\/S0036144598347011","volume":"41","author":"PW Shor","year":"1999","unstructured":"P.W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review, 41(2):303\u2013332, 1999.","journal-title":"SIAM Review"},{"issue":"6","key":"9365_CR62","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1109\/18.556672","volume":"42","author":"J Stern","year":"1996","unstructured":"J. Stern. A new paradigm for public key identification. IEEE Trans. Information Theory, 42(6):1757\u20131768, 1996.","journal-title":"IEEE Trans. Information Theory"},{"key":"9365_CR63","doi-asserted-by":"crossref","unstructured":"A. Sahai and B. Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In STOC, 2014.","DOI":"10.1145\/2591796.2591825"},{"key":"9365_CR64","unstructured":"S.P. Vadhan. A Study of Statistical Zero-Knowledge Proofs. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 1999."},{"key":"9365_CR65","unstructured":"J. Von Neumann. Various techniques used in connection with random digits, paper no. 13 in \u201cMonte Carlo method\u201d. NBS Applied Mathematics Series, 1961."},{"key":"9365_CR66","first-page":"276","volume":"2017","author":"D Wichs","year":"2017","unstructured":"D. Wichs and G. Zirdelis. Obfuscating compute-and-compare programs under LWE. IACR Cryptology ePrint Archive, 2017:276, 2017.","journal-title":"IACR Cryptology ePrint Archive"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-020-09365-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-020-09365-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-020-09365-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,8]],"date-time":"2021-02-08T21:27:33Z","timestamp":1612819653000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-020-09365-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":66,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["9365"],"URL":"https:\/\/doi.org\/10.1007\/s00145-020-09365-w","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]},"assertion":[{"value":"15 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"3"}}