{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T19:45:29Z","timestamp":1742931929398,"version":"3.40.3"},"publisher-location":"Cham","reference-count":49,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319765808"},{"type":"electronic","value":"9783319765815"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-76581-5_21","type":"book-chapter","created":{"date-parts":[[2018,2,28]],"date-time":"2018-02-28T09:41:20Z","timestamp":1519810880000},"page":"619-643","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["New (and Old) Proof Systems for Lattice Problems"],"prefix":"10.1007","author":[{"given":"Navid","family":"Alamati","sequence":"first","affiliation":[]},{"given":"Chris","family":"Peikert","sequence":"additional","affiliation":[]},{"given":"Noah","family":"Stephens-Davidowitz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,1]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, D., Dadush, D., Regev, O., Stephens-Davidowitz, N.: Solving the shortest vector problem in $$2^n$$ time using discrete Gaussian sampling. In: STOC, pp. 733\u2013742 (2015)","DOI":"10.1145\/2746539.2746606"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Aggarwal, D., Dadush, D., Stephens-Davidowitz, N.: Solving the closest vector problem in $$2^n$$ time - the discrete Gaussian strikes again! In: FOCS, pp. 563\u2013582 (2015)","DOI":"10.1109\/FOCS.2015.41"},{"issue":"5","key":"21_CR3","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1145\/1089023.1089025","volume":"52","author":"D Aharonov","year":"2005","unstructured":"Aharonov, D., Regev, O.: Lattice problems in NP $$\\cap $$ coNP. J. ACM 52(5), 749\u2013765 (2005). Preliminary version in FOCS 2004","journal-title":"J. ACM"},{"key":"21_CR4","first-page":"1","volume":"13","author":"M Ajtai","year":"2004","unstructured":"Ajtai, M.: Generating hard instances of lattice problems. Quaderni di Matematica 13, 1\u201332 (2004). Preliminary version in STOC 1996","journal-title":"Quaderni di Matematica"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"Babai, L.: Trading group theory for randomness. In: STOC, pp. 421\u2013429 (1985)","DOI":"10.1145\/22145.22192"},{"issue":"1","key":"21_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579403","volume":"6","author":"L Babai","year":"1986","unstructured":"Babai, L.: On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1\u201313 (1986). Preliminary version in STACS 1985","journal-title":"Combinatorica"},{"issue":"4","key":"21_CR7","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1007\/BF01445125","volume":"296","author":"W Banaszczyk","year":"1993","unstructured":"Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296(4), 625\u2013635 (1993)","journal-title":"Math. Ann."},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF02574039","volume":"13","author":"W Banaszczyk","year":"1995","unstructured":"Banaszczyk, W.: Inequalites for convex bodies and polar reciprocal lattices in $$\\mathbb{R}^n$$. Discrete Comput. Geom. 13, 217\u2013231 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/0-387-34805-0_19","volume-title":"Advances in Cryptology \u2014 CRYPTO 1989 Proceedings","author":"M Bellare","year":"1990","unstructured":"Bellare, M., Goldwasser, S.: New paradigms for digital signatures and message authentication based on non-interactive zero knowledge proofs. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 194\u2013211. Springer, New York (1990). https:\/\/doi.org\/10.1007\/0-387-34805-0_19"},{"issue":"6","key":"21_CR10","doi-asserted-by":"publisher","first-page":"1084","DOI":"10.1137\/0220068","volume":"20","author":"M Blum","year":"1991","unstructured":"Blum, M., De Santis, A., Micali, S., Persiano, G.: Noninteractive zero-knowledge. SIAM J. Comput. 20(6), 1084\u20131118 (1991). Preliminary version in STOC 1988","journal-title":"SIAM J. Comput."},{"issue":"2","key":"21_CR11","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"RB Boppana","year":"1987","unstructured":"Boppana, R.B., H\u00e5stad, J., Zachos, S.: Does co-NP have short interactive proofs? Inf. Process. Lett. 25(2), 127\u2013132 (1987)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"21_CR12","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/2633600","volume":"6","author":"Z Brakerski","year":"2014","unstructured":"Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. TOCT 6(3), 13 (2014). Preliminary version in ITCS 2012","journal-title":"TOCT"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehl\u00e9, D.: Classical hardness of learning with errors. In: STOC, pp. 575\u2013584 (2013)","DOI":"10.1145\/2488608.2488680"},{"issue":"2","key":"21_CR14","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1137\/120868669","volume":"43","author":"Z Brakerski","year":"2014","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. SIAM J. Comput. 43(2), 831\u2013871 (2014). Preliminary version in FOCS 2011","journal-title":"SIAM J. Comput."},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: FOCS, pp. 136\u2013145 (2001)","DOI":"10.1109\/SFCS.2001.959888"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Chung, K.-M., Dadush, D., Liu, F.-H., Peikert, C.: On the lattice smoothing parameter problem. In: IEEE Conference on Computational Complexity, pp. 230\u2013241 (2013)","DOI":"10.1109\/CCC.2013.31"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Dadush, D., Peikert, C., Vempala, S.: Enumerative lattice algorithms in any norm via M-ellipsoid coverings. In: FOCS, pp. 580\u2013589 (2011)","DOI":"10.1109\/FOCS.2011.31"},{"key":"21_CR18","doi-asserted-by":"crossref","unstructured":"Dadush, D., Regev, O.: Towards strong reverse Minkowski-type inequalities for lattices. In: FOCS, pp. 447\u2013456 (2016)","DOI":"10.1109\/FOCS.2016.55"},{"issue":"6","key":"21_CR19","doi-asserted-by":"publisher","first-page":"1513","DOI":"10.1137\/S0097539703426817","volume":"36","author":"C Dwork","year":"2007","unstructured":"Dwork, C., Naor, M.: Zaps and their applications. SIAM J. Comput. 36(6), 1513\u20131543 (2007)","journal-title":"SIAM J. Comput."},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197\u2013206 (2008)","DOI":"10.1145\/1374376.1374407"},{"issue":"3","key":"21_CR21","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1006\/jcss.1999.1686","volume":"60","author":"O Goldreich","year":"2000","unstructured":"Goldreich, O., Goldwasser, S.: On the limits of nonapproximability of lattice problems. J. Comput. Syst. Sci. 60(3), 540\u2013563 (2000). Preliminary version in STOC 1998","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR22","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC, pp. 218\u2013229 (1987)","DOI":"10.1145\/28395.28420"},{"issue":"3","key":"21_CR23","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1145\/116825.116852","volume":"38","author":"O Goldreich","year":"1991","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 691\u2013729 (1991)","journal-title":"J. ACM"},{"key":"21_CR24","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Sahai, A., Vadhan, S.P.: Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In: STOC, pp. 399\u2013408 (1998)","DOI":"10.1145\/276698.276852"},{"key":"21_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/3-540-48405-1_30","volume-title":"Advances in Cryptology \u2014 CRYPTO 1999","author":"O Goldreich","year":"1999","unstructured":"Goldreich, O., Sahai, A., Vadhan, S.: Can statistical zero knowledge be made non-interactive? or on the relationship of SZK and NISZK. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 467\u2013484. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48405-1_30"},{"issue":"1","key":"21_CR26","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S Goldwasser","year":"1989","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186\u2013208 (1989). Preliminary version in STOC 1985","journal-title":"SIAM J. Comput."},{"issue":"2","key":"21_CR27","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/s00037-005-0193-y","volume":"14","author":"V Guruswami","year":"2005","unstructured":"Guruswami, V., Micciancio, D., Regev, O.: The complexity of the covering radius problem. Comput. Complex. 14(2), 90\u2013121 (2005). Preliminary version in CCC 2004","journal-title":"Comput. Complex."},{"key":"21_CR28","doi-asserted-by":"crossref","unstructured":"Haviv, I., Regev, O.: On the lattice isomorphism problem. In: SODA, pp. 391\u2013404 (2014)","DOI":"10.1137\/1.9781611973402.29"},{"key":"21_CR29","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58, 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"issue":"3","key":"21_CR30","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s001459900042","volume":"11","author":"A Joux","year":"1998","unstructured":"Joux, A., Stern, J.: Lattice reduction: a toolbox for the cryptanalyst. J. Cryptology 11(3), 161\u2013185 (1998)","journal-title":"J. Cryptology"},{"key":"21_CR31","doi-asserted-by":"crossref","unstructured":"Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: STOC, pp. 193\u2013206 (1983)","DOI":"10.1145\/800061.808749"},{"key":"21_CR32","unstructured":"Klein, P.N.: Finding the closest lattice vector when it\u2019s unusually close. In: SODA, pp. 937\u2013941 (2000)"},{"issue":"4","key":"21_CR33","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra Jr., H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515\u2013534 (1982)","journal-title":"Math. Ann."},{"issue":"4","key":"21_CR34","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"21_CR35","series-title":"The Kluwer International Series in Engineering and Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0897-7","volume-title":"Complexity of Lattice Problems: A Cryptographic Perspective","author":"D Micciancio","year":"2002","unstructured":"Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems: A Cryptographic Perspective. The Kluwer International Series in Engineering and Computer Science, vol. 671. Kluwer Academic Publishers, Boston (2002)"},{"key":"21_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1007\/978-3-642-29011-4_41","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"D Micciancio","year":"2012","unstructured":"Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700\u2013718. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29011-4_41"},{"issue":"1","key":"21_CR37","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1137\/S0097539705447360","volume":"37","author":"D Micciancio","year":"2007","unstructured":"Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267\u2013302 (2007). Preliminary version in FOCS 2004","journal-title":"SIAM J. Comput."},{"key":"21_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/978-3-540-45146-4_17","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"D Micciancio","year":"2003","unstructured":"Micciancio, D., Vadhan, S.P.: Statistical zero-knowledge proofs with efficient provers: lattice problems and more. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 282\u2013298. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45146-4_17"},{"key":"21_CR39","doi-asserted-by":"crossref","unstructured":"Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: STOC, pp. 427\u2013437 (1990)","DOI":"10.1145\/100216.100273"},{"key":"21_CR40","doi-asserted-by":"crossref","unstructured":"Nguyen, M.-H., Vadhan, S.P.: Zero knowledge with efficient provers. In: STOC, pp. 287\u2013295 (2006)","DOI":"10.1145\/1132516.1132559"},{"key":"21_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/3-540-44670-2_12","volume-title":"Cryptography and Lattices","author":"PQ Nguyen","year":"2001","unstructured":"Nguyen, P.Q., Stern, J.: The two faces of lattices in cryptology. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 146\u2013180. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44670-2_12"},{"key":"21_CR42","doi-asserted-by":"crossref","unstructured":"Odlyzko, A.M.: The rise and fall of knapsack cryptosystems. In: Pomerance, C. (ed.) Cryptology and Computational Number Theory, Proceedings of Symposia in Applied Mathematics, vol. 42, pp. 75\u201388 (1990)","DOI":"10.1090\/psapm\/042\/1095552"},{"issue":"1","key":"21_CR43","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1006\/jcss.1999.1664","volume":"60","author":"T Okamoto","year":"2000","unstructured":"Okamoto, T.: On relationships between statistical zero-knowledge proofs. J. Comput. Syst. Sci. 60(1), 47\u2013108 (2000). Preliminary version in STOC 1996","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR44","doi-asserted-by":"crossref","unstructured":"Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem. In: STOC, pp. 333\u2013342 (2009)","DOI":"10.1145\/1536414.1536461"},{"key":"21_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1007\/978-3-540-85174-5_30","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"C Peikert","year":"2008","unstructured":"Peikert, C., Vaikuntanathan, V.: Noninteractive statistical zero-knowledge proofs for lattice problems. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 536\u2013553. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-85174-5_30"},{"issue":"6","key":"21_CR46","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1568318.1568324","volume":"56","author":"O Regev","year":"2009","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 1\u201340 (2009). Preliminary version in STOC 2005","journal-title":"J. ACM"},{"key":"21_CR47","doi-asserted-by":"crossref","unstructured":"Regev, O., Stephens-Davidowitz, N.: A reverse Minkowski theorem. In: STOC, pp. 941\u2013953 (2017)","DOI":"10.1145\/3055399.3055434"},{"issue":"2","key":"21_CR48","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1145\/636865.636868","volume":"50","author":"A Sahai","year":"2003","unstructured":"Sahai, A., Vadhan, S.P.: A complete problem for statistical zero knowledge. J. ACM 50(2), 196\u2013249 (2003). Preliminary version in FOCS 1997","journal-title":"J. ACM"},{"key":"21_CR49","unstructured":"Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices, pp. 210\u2013268. Cambridge University Press (2012). http:\/\/www-personal.umich.edu\/~romanv\/papers\/non-asymptotic-rmt-plain.pdf"}],"container-title":["Lecture Notes in Computer Science","Public-Key Cryptography \u2013 PKC 2018"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-76581-5_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,5]],"date-time":"2021-03-05T01:09:05Z","timestamp":1614906545000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-76581-5_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319765808","9783319765815"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-76581-5_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"1 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PKC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"IACR International Workshop on Public Key Cryptography","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rio de Janeiro","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Brazil","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 March 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 March 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"pkc2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/pkc.iacr.org\/2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}