{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T15:39:09Z","timestamp":1790005149688,"version":"4.0.1"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1643552"],"award-info":[{"award-number":["DMS-1643552"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Appl. Algebra Geometry"],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>The Ring Learning-with-Errors (RLWE) problem shows great promise for postquantum cryptography and homomorphic encryption. We describe a new attack on the nondual search RLWE problem with small error widths, using ring homomorphisms to finite fields and the chi-square statistical test. In particular, we identify a \u201csubfield vulnerability\u201d and give a new attack which finds this vulnerability by mapping to a finite field extension and detecting nonuniformity with respect to the number of elements in the subfield. We use this attack to give examples of vulnerable RLWE instances in Galois number fields. We also extend the well-known search-to-decision reduction result to Galois fields with any unramified prime modulus $q$, regardless of the residue degree $f$ of $q$, and we use this in our attacks. The time complexity of our attack is $O(nq^{2f})$, where $n$ is the degree of $K$ and $f$ is the residue degree of $q$ in $K$. We also show an attack on the nondual (resp., dual) RLWE problem with narrow error distributions in prime cyclotomic rings when the modulus is a ramified prime (resp., any integer). We demonstrate the attacks in practice by finding many vulnerable instances and successfully attacking them. We include the code for all attacks.<\/jats:p>","DOI":"10.1137\/16m1096566","type":"journal-article","created":{"date-parts":[[2017,12,6]],"date-time":"2017-12-06T11:37:18Z","timestamp":1512560238000},"page":"665-682","source":"Crossref","is-referenced-by-count":17,"title":["Attacks on the Search RLWE Problem with Small Errors"],"prefix":"10.1137","volume":"1","author":[{"given":"Hao","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kristin","family":"Lauter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Katherine E.","family":"Stange","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,12,6]]},"reference":[{"key":"atypb1","first-page":"403","author":"Arora S.","year":"2011","journal-title":"Heidelberg"},{"key":"atypb2","first-page":"45","author":"Bos J.W.","year":"2013","journal-title":"Heidelberg"},{"key":"atypb3","first-page":"309","author":"Brakerski Z.","year":"2012","journal-title":"New York"},{"key":"atypb4","first-page":"505","author":"Brakerski Z.","year":"2011","journal-title":"Heidelberg"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/120868669"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1112\/S1461157016000280"},{"key":"atypb7","first-page":"147","author":"Castryck W.","year":"2016","journal-title":"Berlin"},{"key":"atypb8","unstructured":"H. Chen, K.E. Lauter, and K.E. Stange,\n                      Attacks on Search RLWE\n                      , Cryptology ePrint Archive, Report 2015\/971, 2015."},{"key":"atypb9","unstructured":"H. Chen, K.E. Lauter, and K.E. Stange,\n                      Vulnerable Galois RLWE families and improved attacks\n                      , in Selected Areas in Cryptography-SAC 2016, Springer International, Cham, 2016."},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"L. Ducas and A. Durmus,\n                      Ring-LWE in polynomial rings\n                      , in Public Key Cryptography-PKC 2012, Springer, Berlin, Heidelberg, 2012, pp. 34-51.","DOI":"10.1007\/978-3-642-30057-8_3"},{"key":"atypb11","first-page":"183","volume":"2014","author":"Eisentra\u0308ger K.","year":"2014","journal-title":"Selected Areas in Cryptography--SAC"},{"key":"atypb12","first-page":"63","author":"Elias Y.","year":"2015","journal-title":"Heidelberg"},{"key":"atypb13","first-page":"465","author":"Gentry C.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb14","first-page":"197","author":"Gentry C.","year":"2008","journal-title":"New York"},{"key":"atypb15","unstructured":"H. Johnston,\n                      Notes on Galois Modules\n                      , notes accompanying the course Galois Modules, Cambridge, UK, 2011."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-014-9938-4"},{"key":"atypb17","first-page":"1219","author":"Lo\u0301pez-Alt A.","year":"2012","journal-title":"New York"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1145\/2535925"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447360"},{"key":"atypb20","first-page":"147","author":"Micciancio D.","year":"2009","journal-title":"Berlin"},{"key":"atypb21","first-page":"288","author":"Nguyen P.","year":"1999","journal-title":"Berlin"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"C. Peikert,\n                      How (not) to instantiate Ring-LWE\n                      , in Security and Cryptography for Networks (SCN 2016), Springer, Cham, pp. 411-430.","DOI":"10.1007\/978-3-319-44618-9_22"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-3758(03)00149-6"},{"key":"atypb24","first-page":"27","author":"Stehle\u0301 D.","year":"2011","journal-title":"Heidelberg"},{"key":"atypb25","unstructured":"W. Stein et al.\n                      SageMath\n                      , Version \\textup8.0, The Sage Development Team, 2017,http:\/\/www.sagemath.org."}],"container-title":["SIAM Journal on Applied Algebra and Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1096566","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T14:05:16Z","timestamp":1787234716000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1096566"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/16M1096566"],"URL":"https:\/\/doi.org\/10.1137\/16m1096566","relation":{},"ISSN":["2470-6566"],"issn-type":[{"value":"2470-6566","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}