{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T16:03:29Z","timestamp":1783008209010,"version":"3.54.5"},"reference-count":25,"publisher":"International Association for Cryptologic Research","issue":"3","license":[{"start":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T00:00:00Z","timestamp":1751846400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Research Council of Finland","doi-asserted-by":"publisher","award":["358951"],"award-info":[{"award-number":["358951"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Research Council of Finland","doi-asserted-by":"publisher","award":["358950"],"award-info":[{"award-number":["358950"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,9,2]]},"abstract":"<jats:p>The Learning with Errors (LWE) problem asks to distinguish noisy samples s^T A + e^T mod q from uniformly random values given the random matrix A. In this work, we show that a variant called Leaky LWE, where the distinguisher receives additionally noisy leakages (s^T, e^T) L + f^T of the LWE secret s and error e for low-norm matrix L chosen adaptively by the distinguisher after seeing A, is not easier than the standard LWE of the same dimensions up to polynomial losses in the noise level and the modulus. More generally, we show that the Leaky LWE problem is hard even if the public matrix A is structured and\/or hinted and if the non-leaky parts of the secret and error do not follow Gaussian distributions, as long as the corresponding LWE problem without leakage is hard.<\/jats:p>\n                  <jats:p>Our reduction from LWE to Leaky LWE unifies and extends prior results on the Error-Leakage LWE problem [D\u00f6ttling-Kolonelos-Lai-Lin-Malavolta-Rahimi, EUROCRYPT'23], where L only acts on the error e and the Hint-MLWE problem [Kim-Lee-Seo-Song, CRYPTO'23], where L is restricted to concatenations of random Gaussian scalar matrices not controlled by the distinguisher. Previously, the Hint-MLWE and Error-Leakage LWE assumptions were used as computational replacements of the statistical noise flooding technique in security proofs which led to improved parameters in lattice-based cryptographic constructions such as zero-knowledge proofs, threshold signatures and registration-based encryption. We provide lemmas which abstract out such computational arguments based on Leaky LWE.<\/jats:p>","DOI":"10.62056\/ah89ksuc2","type":"journal-article","created":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T18:49:52Z","timestamp":1759776592000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":3,"title":["Leaky LWE: Learning with Errors with Semi-Adaptive Secret- and Error-Leakage"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9126-1887","authenticated-orcid":false,"given":"Russell","family":"Lai","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/020hwjq30","id-type":"ROR","asserted-by":"publisher"}],"name":"Aalto University","place":["Finland"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-2682-8107","authenticated-orcid":false,"given":"Monisha","family":"Swarnakar","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/020hwjq30","id-type":"ROR","asserted-by":"publisher"}],"name":"Aalto University","place":["Finland"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8905-1207","authenticated-orcid":false,"given":"Ivy","family":"Woo","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/020hwjq30","id-type":"ROR","asserted-by":"publisher"}],"name":"Aalto University","place":["Finland"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2025,10,6]]},"reference":[{"key":"ref1:STOC:Regev05","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/1060590.1060603","article-title":"On lattices, learning with errors, random linear codes, and\n  cryptography","author":"Oded Regev","year":"2005"},{"key":"ref2:AC:SSTX09","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/978-3-642-10366-7_36","article-title":"Efficient Public Key Encryption Based on Ideal Lattices","volume":"5912","author":"Damien Stehl\u00e9","year":"2009"},{"key":"ref3:EC:LyuPeiReg10","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-13190-5_1","article-title":"On Ideal Lattices and Learning with Errors over Rings","volume":"6110","author":"Vadim Lyubashevsky","year":"2010"},{"key":"ref4:BGV14","doi-asserted-by":"publisher","DOI":"10.1145\/2633600","article-title":"(Leveled) Fully Homomorphic Encryption without\n  Bootstrapping","volume":"6","author":"Zvika Brakerski","year":"2014","journal-title":"ACM Trans. Comput. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/1942-3454","issn-type":"electronic"},{"key":"ref5:DCC:LanSte15","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/s10623-014-9938-4","article-title":"Worst-case to average-case reductions for module lattices","volume":"75","author":"Adeline Langlois","year":"2015","journal-title":"DCC"},{"key":"ref6:EC:DKLLMR23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/978-3-031-30620-4_14","article-title":"Efficient Laconic Cryptography from Learning with Errors","volume":"14006","author":"Nico D\u00f6ttling","year":"2023"},{"key":"ref7:C:KLSS23b","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/978-3-031-38554-4_18","article-title":"Toward Practical Lattice-Based Proof of Knowledge from\n  Hint-MLWE","volume":"14085","author":"Duhyeong Kim","year":"2023"},{"key":"ref8:EC:DKMMPS24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-031-58723-8_8","article-title":"Threshold Raccoon: Practical Threshold Signatures from\n  Standard Lattice Assumptions","volume":"14652","author":"Rafa\u00ebl Del Pino","year":"2024"},{"key":"ref9:boschini2025ringtail","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1109\/SP61157.2025.00070","article-title":"Ringtail: practical two-round threshold signatures from\n  learning with errors","author":"Cecilia Boschini","year":"2025"},{"key":"ref10:CiC:MicSuh24","doi-asserted-by":"publisher","first-page":"2","DOI":"10.62056\/a0zogy4e-","article-title":"Simulation-Secure Threshold PKE from LWE with Polynomial\n  Modulus","volume":"1","author":"Daniele Micciancio","year":"2024","journal-title":"CiC"},{"key":"ref11:PKC:AlpPei12","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/978-3-642-30057-8_20","article-title":"Circular and KDM Security for Identity-Based Encryption","volume":"7293","author":"Jacob Alperin-Sheriff","year":"2012"},{"key":"ref12:C:AgrLibSte16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/978-3-662-53015-3_12","article-title":"Fully Secure Functional Encryption for Inner Products, from\n  Standard Assumptions","volume":"9816","author":"Shweta Agrawal","year":"2016"},{"key":"ref13:PKC:WanLaiLiu24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-031-57722-2_9","article-title":"Ring\/Module Learning with Errors Under Linear Leakage -\n  Hardness and Applications","volume":"14602","author":"Zhedong Wang","year":"2024"},{"key":"ref14:cryptoeprint:2025\/1472","volume-title":"Hardness of M-LWE with General Distributions and\n  Applications to Leaky Variants","author":"Katharina Boudgoust","year":"2025"},{"key":"ref15:EC:LyuPeiReg13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-642-38348-9_3","article-title":"A Toolkit for Ring-LWE Cryptography","volume":"7881","author":"Vadim Lyubashevsky","year":"2013"},{"key":"ref16:SIAM:HMA","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1137\/090771806","article-title":"Finding structure with randomness: Probabilistic algorithms\n  for constructing approximate matrix decompositions","volume":"53","author":"Nathan Halko","year":"2011","journal-title":"SIAM review"},{"key":"ref17:EC:MicPei12","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1007\/978-3-642-29011-4_41","article-title":"Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller","volume":"7237","author":"Daniele Micciancio","year":"2012"},{"key":"ref18:PKC:GMPW20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/978-3-030-45374-9_21","article-title":"Improved Discrete Gaussian and Subgaussian Analysis for\n  Lattice Cryptography","volume":"12110","author":"Nicholas Genise","year":"2020"},{"key":"ref19:EC:AbrRoySch24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-031-58751-1_11","article-title":"Succinct Homomorphic Secret Sharing","volume":"14656","author":"Damiano Abram","year":"2024"},{"key":"ref20:C:CinLaiMal23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/978-3-031-38545-2_3","article-title":"Lattice-Based Succinct Arguments from Vanishing Polynomials\n  - (Extended Abstract)","volume":"14082","author":"Valerio Cini","year":"2023"},{"key":"ref21:C:LPSS14","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-662-44371-2_18","article-title":"Hardness of k-LWE and Applications in Traitor Tracing","volume":"8616","author":"San Ling","year":"2014"},{"key":"ref22:C:Wee24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/978-3-031-68382-4_6","article-title":"Circuit ABE with\n  $\\textsf{poly}(\\text{depth},\\lambda)$-Sized Ciphertexts and Keys from\n  Lattices","volume":"14922","author":"Hoeteck Wee","year":"2024"},{"key":"ref23:EC:Wee22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-031-07085-3_8","article-title":"Optimal Broadcast Encryption and CP-ABE from Evasive\n  Lattice Assumptions","volume":"13276","author":"Hoeteck Wee","year":"2022"},{"key":"ref24:C:ACLMT22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/978-3-031-15979-4_4","article-title":"Lattice-Based SNARKs: Publicly Verifiable, Preprocessing,\n  and Recursively Composable - (Extended Abstract)","volume":"13508","author":"Martin R. Albrecht","year":"2022"},{"key":"ref25:PKC:DKLW25","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1007\/978-3-031-91820-9_15","article-title":"Lattice-Based Proof-Friendly Signatures from Vanishing Short\n  Integer Solutions","volume":"15674","author":"Adrien Dubois","year":"2025"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T20:23:00Z","timestamp":1759782180000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/3\/21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,6]]},"references-count":25,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2025,10,6]]}},"URL":"https:\/\/doi.org\/10.62056\/ah89ksuc2","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,6]]},"assertion":[{"value":"2025-07-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-3-35"}}