{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:42:18Z","timestamp":1781077338167,"version":"3.54.1"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031305887","type":"print"},{"value":"9783031305894","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-30589-4_9","type":"book-chapter","created":{"date-parts":[[2023,4,15]],"date-time":"2023-04-15T11:02:07Z","timestamp":1681556527000},"page":"252-281","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Just How Hard Are Rotations of\u00a0$$\\mathbb {Z}^n$$? Algorithms and\u00a0Cryptography with\u00a0the\u00a0Simplest Lattice"],"prefix":"10.1007","author":[{"given":"Huck","family":"Bennett","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Atul","family":"Ganju","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pura","family":"Peetathawatchai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Noah","family":"Stephens-Davidowitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,4,16]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, D., Chen, Y., Kumar, R., Li, Z., Stephens-Davidowitz, N.: Dimension-preserving reductions between SVP and CVP in different $$p$$-norms. In: SODA (2021)","DOI":"10.1137\/1.9781611976465.145"},{"key":"9_CR2","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 (2015)","DOI":"10.1109\/FOCS.2015.41"},{"issue":"10","key":"9_CR3","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1016\/j.ipl.2016.05.003","volume":"116","author":"D Aggarwal","year":"2016","unstructured":"Aggarwal, D., Dubey, C.K.: Improved hardness results for unique shortest vector problem. Inf. Process. Lett. 116(10), 631\u2013637 (2016)","journal-title":"Inf. Process. Lett."},{"key":"9_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/978-3-319-70694-8_11","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2017","author":"MR Albrecht","year":"2017","unstructured":"Albrecht, M.R., G\u00f6pfert, F., Virdia, F., Wunderer, T.: Revisiting the expected cost of solving uSVP and applications to LWE. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 297\u2013322. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70694-8_11"},{"key":"9_CR5","unstructured":"Aono, Y., Espitau, T., Nguyen, P.Q.: Random lattices: theory and practice. https:\/\/espitau.github.io\/bin\/random_lattice.pdf"},{"key":"9_CR6","unstructured":"Bennett, H., Ganju, A., Peetathawatchai, P., Stephens-Davidowitz, N.: Experiments on solving SVP on rotations of $$\\mathbb{Z} ^n$$ (2021). https:\/\/github.com\/poonpura\/Experiments-on-Solving-SVP-on-Rotations-of-Z-n"},{"key":"9_CR7","unstructured":"Bennett, H., Ganju, A., Peetathawatchai, P., Stephens-Davidowitz, N.: Just how hard are rotations of $$\\mathbb{Z} ^n$$? Algorithms and cryptography with the simplest lattice (2021). https:\/\/eprint.iacr.org\/2021\/1548"},{"key":"9_CR8","unstructured":"Bennett, H., Little, R.: Revisiting the BGPS rotations-of-$$\\mathbb{Z} ^n$$ cryptosystem: An implementation, challenges, and attacks. Preprint (2023)"},{"key":"9_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-030-81293-5_17","volume-title":"Post-Quantum Cryptography","author":"TL Blanks","year":"2021","unstructured":"Blanks, T.L., Miller, S.D.: Generating cryptographically-strong random lattice bases and recognizing rotations of $$\\mathbb{Z}^n$$. In: Cheon, J.H., Tillich, J.-P. (eds.) PQCrypto 2021 2021. LNCS, vol. 12841, pp. 319\u2013338. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-81293-5_17"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehl\u00e9, D.: Classical hardness of Learning with Errors. In: STOC (2013)","DOI":"10.1145\/2488608.2488680"},{"key":"9_CR11","doi-asserted-by":"publisher","unstructured":"Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. J. Cryptol. 25(4), 601\u2013639 (2012), preliminary version in EUROCRYPT 2010. https:\/\/doi.org\/10.1007\/978-3-642-13190-5_27","DOI":"10.1007\/978-3-642-13190-5_27"},{"issue":"2","key":"9_CR12","doi-asserted-by":"publisher","first-page":"1244","DOI":"10.1137\/15M1054766","volume":"31","author":"K Chandrasekaran","year":"2017","unstructured":"Chandrasekaran, K., Gandikota, V., Grigorescu, E.: Deciding orthogonality in Construction-A lattices. SIAM J. Discret. Math. 31(2), 1244\u20131262 (2017)","journal-title":"SIAM J. Discret. Math."},{"key":"9_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/978-3-030-56880-1_12","volume-title":"Advances in Cryptology \u2013 CRYPTO 2020","author":"D Dachman-Soled","year":"2020","unstructured":"Dachman-Soled, D., Ducas, L., Gong, H., Rossi, M.: LWE with side information: attacks and concrete security estimation. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 329\u2013358. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-56880-1_12"},{"key":"9_CR14","doi-asserted-by":"publisher","unstructured":"Ducas, L., Postlethwaite, E.W., Pulles, L.N., van Woerden, W.: Hawk: Module LIP makes lattice signatures fast, compact and simple. In: Asiacrypt (2023). https:\/\/doi.org\/10.1007\/978-3-031-22972-5_3","DOI":"10.1007\/978-3-031-22972-5_3"},{"key":"9_CR15","doi-asserted-by":"publisher","unstructured":"Ducas, L., van Woerden, W.: On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography. In: EUROCRYPT (2022). https:\/\/doi.org\/10.1007\/978-3-031-07082-2_23","DOI":"10.1007\/978-3-031-07082-2_23"},{"key":"9_CR16","unstructured":"FPLLL development team: fplll, a lattice reduction library, Version: 5.4.1. https:\/\/github.com\/fplll\/fplll,"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Gei\u00dfler, K., Smart, N.P.: Computing the $$M = U^T U$$ integer matrix decomposition. In: Cryptography and Coding (2003)","DOI":"10.1007\/978-3-540-40974-8_18"},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC (2008)","DOI":"10.1145\/1374376.1374407"},{"key":"9_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/3-540-46035-7_20","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 2002","author":"C Gentry","year":"2002","unstructured":"Gentry, C., Szydlo, M.: Cryptanalysis of the revised NTRU signature scheme. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 299\u2013320. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-46035-7_20"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Haviv, I., Regev, O.: On the lattice isomorphism problem. In: SODA (2014)","DOI":"10.1137\/1.9781611973402.29"},{"key":"9_CR21","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."},{"key":"9_CR22","unstructured":"Hunkenschr\u00f6der, C.: Deciding whether a lattice has an orthonormal basis is in co-NP (2019)"},{"issue":"4","key":"9_CR23","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W., Jr., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515\u2013534 (1982)","journal-title":"Math. Ann."},{"key":"9_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-662-44371-2_16","volume-title":"Advances in Cryptology \u2013 CRYPTO 2014","author":"HW Lenstra","year":"2014","unstructured":"Lenstra, H.W., Silverberg, A.: Revisiting the gentry-Szydlo algorithm. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 280\u2013296. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-44371-2_16"},{"issue":"3","key":"9_CR25","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1007\/s00145-016-9235-7","volume":"30","author":"HW Lenstra","year":"2017","unstructured":"Lenstra, H.W., Silverberg, A.: Lattices with symmetry. J. Cryptol. 30(3), 760\u2013804 (2017)","journal-title":"J. Cryptol."},{"key":"9_CR26","doi-asserted-by":"crossref","unstructured":"Li, J., Nguyen, P.Q.: Approximating the densest sublattice from Rankin\u2019s inequality. LMS J. Comput. Math. 17(A), 92\u2013111 (2014)","DOI":"10.1112\/S1461157014000333"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"Li, J., Nguyen, P.Q.: Computing a lattice basis revisited. In: ISAAC (2019)","DOI":"10.1145\/3326229.3326265"},{"key":"9_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/978-3-642-03356-8_34","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"V Lyubashevsky","year":"2009","unstructured":"Lyubashevsky, V., Micciancio, D.: On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 577\u2013594. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03356-8_34"},{"issue":"1","key":"9_CR29","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)","journal-title":"SIAM J. Comput."},{"key":"9_CR30","doi-asserted-by":"crossref","unstructured":"Micciancio, D., Voulgaris, P.: Faster exponential time algorithms for the Shortest Vector Problem. In: SODA (2010)","DOI":"10.1137\/1.9781611973075.119"},{"key":"9_CR31","unstructured":"Nguyen, P.Q., Pujet, L.: The probability of primitive sets and generators in lattices (2022)"},{"issue":"4","key":"9_CR32","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1561\/0400000074","volume":"10","author":"C Peikert","year":"2016","unstructured":"Peikert, C.: A decade of lattice cryptography. Foundations Trends Theoret. Comput. Sci. 10(4), 283\u2013424 (2016)","journal-title":"Foundations Trends Theoret. Comput. Sci."},{"key":"9_CR33","unstructured":"Regev, O.: LLL algorithm (2004). https:\/\/cims.nyu.edu\/regev\/teaching\/lattices_fall_2004\/ln\/lll.pdf"},{"key":"9_CR34","doi-asserted-by":"crossref","unstructured":"Regev, O., Stephens-Davidowitz, N.: A reverse Minkowski theorem. In: STOC (2017)","DOI":"10.1145\/3055399.3055434"},{"key":"9_CR35","doi-asserted-by":"crossref","unstructured":"Stephens-Davidowitz, N.: Discrete Gaussian sampling reduces to CVP and SVP. In: SODA (2016)","DOI":"10.1137\/1.9781611974331.ch121"},{"key":"9_CR36","unstructured":"Stephens-Davidowitz, N.: Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one. In: APPROX (2016)"},{"key":"9_CR37","unstructured":"Stephens-Davidowitz, N.: Lattice algorithms (2020). https:\/\/www.youtube.com\/watch?v=o4Pl-0Q5-q0, talk as part of the Simons Institute\u2019s semester on lattices"},{"key":"9_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/3-540-39200-9_27","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 2003","author":"M Szydlo","year":"2003","unstructured":"Szydlo, M.: Hypercubic lattice reduction and analysis of GGH and NTRU signatures. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 433\u2013448. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-39200-9_27"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2023"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30589-4_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,15]],"date-time":"2025-04-15T22:04:30Z","timestamp":1744754670000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30589-4_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031305887","9783031305894"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30589-4_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"16 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"EUROCRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lyon","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 April 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 April 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"42","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"eurocrypt2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eurocrypt.iacr.org\/2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"HotCRP","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"415","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"109","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"16","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}