{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:31:29Z","timestamp":1764981089286,"version":"3.46.0"},"reference-count":20,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,8,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>As quantum computing advances rapidly, guaranteeing the security of cryptographic protocols resistant to quantum attacks is paramount. Some leading candidate cryptosystems use the learning with errors (LWE) problem, attractive for its simplicity and hardness guaranteed by reductions from hard computational lattice problems. Its algebraic variants, ring-learning with errors (RLWE) and polynomial learning with errors (PLWE), gain efficiency over standard LWE, but their security remains to be thoroughly investigated. In this work, we consider the \u201csmearing\u201d condition, a condition for attacks on PLWE and RLWE introduced in Elias et al. We expand upon some questions about smearing posed by Elias et al. and show how smearing is related to the coupon collector\u2019s problem. Furthermore, we develop an algorithm for computing probabilities related to smearing. Finally, we present a smearing-based algorithm for solving the PLWE problem.<\/jats:p>","DOI":"10.1515\/jmc-2020-0035","type":"journal-article","created":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T12:53:52Z","timestamp":1660136032000},"page":"215-232","source":"Crossref","is-referenced-by-count":0,"title":["The polynomial learning with errors problem and the smearing condition"],"prefix":"10.1515","volume":"16","author":[{"given":"Liljana","family":"Babinkostova","sequence":"first","affiliation":[{"name":"Department of Mathematics, Boise State University , Boise, ID 83725 , United States"}]},{"given":"Ariana","family":"Chin","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of California , Berkeley, CA , United States"}]},{"given":"Aaron","family":"Kirtland","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Washington University in St Louis McKelvey School of Engineering , WA , United States"}]},{"given":"Vladyslav","family":"Nazarchuk","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Yale University , New Haven , United States"}]},{"given":"Esther","family":"Plotnick","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Harvard University , Cambridge, MA , United States"}]}],"member":"374","published-online":{"date-parts":[[2022,8,10]]},"reference":[{"key":"2025120600292500853_j_jmc-2020-0035_ref_001","doi-asserted-by":"crossref","unstructured":"Albrecht MR, Deo A. Large modulus ring-LWE geq module-LWE. ASIACRYPT 2017. 2017;10624:267\u201396.","DOI":"10.1007\/978-3-319-70694-8_10"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_002","doi-asserted-by":"crossref","unstructured":"Banerjee A, Peikert C, Rosen A. Pseudorandom functions and lattices, Lecture Notes Comput Sci. 2012;7237:719\u201337.","DOI":"10.1007\/978-3-642-29011-4_42"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_003","doi-asserted-by":"crossref","unstructured":"Brakerski Z, Vaikuntanathan V. Fully homomorphic encryption from Ring-LWE and security for key dependent messages. Lecture Notes Comput Sci. 2011;6841:505\u201324.","DOI":"10.1007\/978-3-642-22792-9_29"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_004","doi-asserted-by":"crossref","unstructured":"Chen Y, Case BM, Gao S, Gong G. Error analysis of weak Poly-LWE instances. Cryptography Commun. 2019;11:411\u201326.","DOI":"10.1007\/s12095-018-0301-x"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_005","doi-asserted-by":"crossref","unstructured":"Damg\u00e4rd I, Polychroniadou A, Adaptively R. Secure Multi-Party Computation from LWE. Lecture Notes Comput Sci. 2016;9615:208\u201333.","DOI":"10.1007\/978-3-662-49387-8_9"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_006","doi-asserted-by":"crossref","unstructured":"Galbraith SD. Mathematics of public key cryptography. 1st edition. Cambridge, United Kingdom: Cambridge University Press; 2012.","DOI":"10.1017\/CBO9781139012843"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_007","doi-asserted-by":"crossref","unstructured":"Elias Y, Lauter KE, Ozman E, Stange KE. Provably weak instances of ring-LWE. Lecture Notes Comput Sci. 2015;9215:63\u201392.","DOI":"10.1007\/978-3-662-47989-6_4"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_008","doi-asserted-by":"crossref","unstructured":"Elias Y, Lauter KE, Ozman E, Stange KE. Ring-LWE cryptography for the number theorist. In: Directions in number theory. Association for women in mathematics series. Vol. 3. Cham: Springer; 2016. p. 271\u201390.","DOI":"10.1007\/978-3-319-30976-7_9"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_009","unstructured":"Erd\u00f6s P, R\u00e9nyi A. On a classical problem of probability theory. Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei. 1961;6:215\u201320."},{"key":"2025120600292500853_j_jmc-2020-0035_ref_010","unstructured":"Ferrante M, Saltalamacchia M. The coupon collectoras problem. MATerials MATem\u00e0tics. 2014;2014(2):35. ISSN: 1887-1097."},{"key":"2025120600292500853_j_jmc-2020-0035_ref_011","doi-asserted-by":"crossref","unstructured":"Grover LK. A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC). Pennsylvania; 1996. p. 212\u20139.","DOI":"10.1145\/237814.237866"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_012","doi-asserted-by":"crossref","unstructured":"Hoffstein J, Pipher J, Silverman JH. NTRU: a ring based public key cryptosystem. Lecture Notes Comput Sci. 1998;1423:267\u201388.","DOI":"10.1007\/BFb0054868"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_013","doi-asserted-by":"crossref","unstructured":"Lindner R, Peikert C. Better key sizes (and attacks) for LWE-based encryption. Lecture Notes Comput Sci. 2001;6558:319\u201339.","DOI":"10.1007\/978-3-642-19074-2_21"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_014","doi-asserted-by":"crossref","unstructured":"Regev O. On lattices, learning with errors, random linear codes, and cryptography. JACM. 2009;56(6):84\u201393.","DOI":"10.1145\/1568318.1568324"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_015","doi-asserted-by":"crossref","unstructured":"Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. Lecture Notes Comput Sci. 2010;6110:1\u201325.","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_016","doi-asserted-by":"crossref","unstructured":"Micciancio D, Regev O. Lattice-based cryptography. In: Bernstein DJ, Buchmann J, Dahmen E, (eds). Post-quantum cryptography. Berlin, Heidelberg: Springer; 2009. p. 147\u201391.","DOI":"10.1007\/978-3-540-88702-7_5"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_017","unstructured":"National institute of standards and technology, announcing request for nominations for public-key post-quantum cryptographic algorithms. Federal Register. 2016;81(244):92787\u20138."},{"key":"2025120600292500853_j_jmc-2020-0035_ref_018","doi-asserted-by":"crossref","unstructured":"Peikert C. Lattice cryptography for the internet. In: Mosca M, (eds). Post-quantum cryptography, lecture notes in computer science. Vol 8772. Cham: Springer; 2014.","DOI":"10.1007\/978-3-319-11659-4_12"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_019","doi-asserted-by":"crossref","unstructured":"Shor PW. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput. 1997;26(5):1484\u2013509.","DOI":"10.1137\/S0097539795293172"},{"key":"2025120600292500853_j_jmc-2020-0035_ref_020","doi-asserted-by":"crossref","unstructured":"Wang T, Yu J, Zhang R, Zhang Y. Efficient signature schemes from R-LWE. Trans Internet Inf Syst. 2016;10:3911\u201324.","DOI":"10.3837\/tiis.2016.08.026"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2020-0035\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2020-0035\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:30:00Z","timestamp":1764981000000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2020-0035\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,1]]},"references-count":20,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,2,10]]},"published-print":{"date-parts":[[2022,2,10]]}},"alternative-id":["10.1515\/jmc-2020-0035"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2020-0035","relation":{},"ISSN":["1862-2984"],"issn-type":[{"type":"electronic","value":"1862-2984"}],"subject":[],"published":{"date-parts":[[2022,1,1]]}}}