{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:58:03Z","timestamp":1764997083586},"reference-count":22,"publisher":"Wiley","issue":"A","license":[{"start":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T00:00:00Z","timestamp":1472169600000},"content-version":"unspecified","delay-in-days":238,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["LMS J. Comput. Math."],"published-print":{"date-parts":[[2016]]},"abstract":"Since its introduction in 2010 by Lyubashevsky, Peikert and Regev, the ring learning with errors problem (ring-LWE) has become a popular building block for cryptographic primitives, due to its great versatility and its hardness proof consisting of a (quantum) reduction from ideal lattice problems. But, for a given modulus$q$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>and degree$n$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>number field$K$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, generating ring-LWE samples can be perceived as cumbersome, because the secret keys have to be taken from the reduction mod$q$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>of a certain fractional ideal${\\mathcal{O}}_{K}^{\\vee }\\subset K$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>called the codifferent or \u2018dual\u2019, rather than from the ring of integers${\\mathcal{O}}_{K}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>itself. This has led to various non-dual variants of ring-LWE, in which one compensates for the non-duality by scaling up the errors. We give a comparison of these versions, and revisit some unfortunate choices that have been made in the recent literature, one of which is scaling up by${|\\unicode[STIX]{x1D6E5}_{K}|}^{1\/2n}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>with$\\unicode[STIX]{x1D6E5}_{K}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>the discriminant of$K$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. As a main result, we provide, for any$\\unicode[STIX]{x1D700}>0$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, a family of number fields$K$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>for which this variant of ring-LWE can be broken easily as soon as the errors are scaled up by${|\\unicode[STIX]{x1D6E5}_{K}|}^{(1-\\unicode[STIX]{x1D700})\/n}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1112\/s1461157016000280","type":"journal-article","created":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T15:29:40Z","timestamp":1472225380000},"page":"130-145","source":"Crossref","is-referenced-by-count":12,"title":["On error distributions in ring-based LWE"],"prefix":"10.1112","volume":"19","author":[{"given":"Wouter","family":"Castryck","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilia","family":"Iliashenko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frederik","family":"Vercauteren","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2016,8,26]]},"reference":[{"key":"S1461157016000280_r16","article-title":"On ideal lattices and learning with errors over rings","volume":"60","author":"Lyubashevsky","year":"2013","journal-title":"J.\u00a0ACM"},{"key":"S1461157016000280_r14","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0054868"},{"key":"S1461157016000280_r12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172165"},{"key":"S1461157016000280_r2","first-page":"575","volume-title":"ACM Symposium on the Theory of Computing \u2013 STOC \u201913","author":"Brakerski","year":"2013"},{"key":"S1461157016000280_r9","first-page":"85","article-title":"A differential criterion for complete intersections","volume":"48","author":"de Smit","year":"1997","journal-title":"Journ\u00e9es Arithm\u00e9tiques 1995, Collect. Math."},{"key":"S1461157016000280_r10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13051-4_11"},{"key":"S1461157016000280_r4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49890-3_6"},{"key":"S1461157016000280_r21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-0133-2"},{"key":"S1461157016000280_r7","unstructured":"7. E. Crockett and C. Peikert , \u2018 $\\unicode[STIX]{x1D6EC}\\circ \\unicode[STIX]{x1D706}$ : A functional library for lattice cryptography\u2019, Cryptology ePreprint Archive, Report 2015\/1134 2015."},{"key":"S1461157016000280_r13","first-page":"182","volume-title":"EUROCRYPT \u201901","author":"Gentry","year":"2001"},{"key":"S1461157016000280_r11","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/978-3-662-47989-6_4","volume-title":"Advances in cryptology \u2013 CRYPTO \u201915","author":"Elias","year":"2015"},{"key":"S1461157016000280_r20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"S1461157016000280_r15","volume-title":"Notes accompanying the course \u2018Galois Modules\u2019 given in Cambridge","author":"Johnston","year":"2011"},{"key":"S1461157016000280_r3","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.12"},{"key":"S1461157016000280_r5","unstructured":"5. H. Chen , K. Lauter and K. Stange , \u2018Attacks on search RLWE\u2019, Cryptology ePreprint Archive, Report 2015\/971 2015."},{"key":"S1461157016000280_r19","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568324"},{"key":"S1461157016000280_r1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090262"},{"key":"S1461157016000280_r17","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536461"},{"key":"S1461157016000280_r8","volume-title":"Multiplicative number theory","author":"Davenport","year":"2000"},{"key":"S1461157016000280_r18","doi-asserted-by":"crossref","unstructured":"18. C. Peikert , \u2018How (not) to instantiate Ring-LWE\u2019, Cryptology ePrint Archive, Report 2016\/351 2016.","DOI":"10.1007\/978-3-319-44618-9_22"},{"key":"#cr-split#-S1461157016000280_r6.1","unstructured":"4. H. Chen, K. Lauter and K. Stange, 'Vulnerable Galois RLWE families and improved attacks', Proceedings of Selected Areas in Cryptography (SAC 2016, St. John's, Canada), Lecture Notes in Computer Science (Springer, New York, NY, to appear)"},{"key":"#cr-split#-S1461157016000280_r6.2","unstructured":"5. Cryptology ePreprint Archive, Report 2016\/193 2016."}],"container-title":["LMS Journal of Computation and Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1461157016000280","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T00:27:44Z","timestamp":1568334464000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1461157016000280\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"references-count":22,"journal-issue":{"issue":"A","published-print":{"date-parts":[[2016]]}},"alternative-id":["S1461157016000280"],"URL":"https:\/\/doi.org\/10.1112\/s1461157016000280","relation":{},"ISSN":["1461-1570"],"issn-type":[{"value":"1461-1570","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}