{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,26]],"date-time":"2025-04-26T05:46:27Z","timestamp":1745646387568,"version":"3.37.3"},"reference-count":32,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2021,5,14]],"date-time":"2021-05-14T00:00:00Z","timestamp":1620950400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2020YFA0309705","2018YFA0704701"],"award-info":[{"award-number":["2020YFA0309705","2018YFA0704701"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61872236","61971192"],"award-info":[{"award-number":["61872236","61971192"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,8,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The Learning Parity with Noise (LPN) problem represents the average-case analogue of the NP-Complete problem \u201cdecoding linear codes\u201d, and it has been extensively studied in learning theory, coding theory and cryptography with applications to quantum-resistant cryptographic schemes. However, LPN also suffers from large public key size which is the common drawback that hinders code-based cryptography from being practical. In this paper, we study a sparse variant of LPN whose public matrix consists of sparse vectors instead of following uniform distribution. We show a win\u2013win argument that at least one of the following assumption is true: (i) either the hardness of sparse LPN is implied by that of the standard LPN under the same noise rate; (ii) or there exists new black-box constructions of public-key encryption schemes and oblivious transfer protocols from standard LPN. Since the second assumption relies on the infeasible noise regimes for LPN-based public-key cryptography, we believe that the first assumption is more likely to hold, i.e. sparse LPN is as hard as standard LPN. Finally, we give a (heuristic) method to further compress the sparse public matrix by evaluating pseudorandom functions with keys made public, whose security again resorts to the aforementioned win\u2013win technique.<\/jats:p>","DOI":"10.1093\/comjnl\/bxab027","type":"journal-article","created":{"date-parts":[[2021,5,9]],"date-time":"2021-05-09T11:07:57Z","timestamp":1620558477000},"page":"1939-1947","source":"Crossref","is-referenced-by-count":1,"title":["On the Hardness of Sparsely Learning Parity with Noise"],"prefix":"10.1093","volume":"65","author":[{"given":"Di","family":"Yan","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering , Shanghai Jiao Tong University, Shanghai 200240, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hanlin","family":"Liu","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering , Shanghai Jiao Tong University, Shanghai 200240, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuoyao","family":"Zhao","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering , Shanghai Jiao Tong University, Shanghai 200240, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu","family":"Yu","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering , Shanghai Jiao Tong University, Shanghai 200240, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,5,14]]},"reference":[{"key":"2022081612371190000_ref1","first-page":"114","article-title":"A public-key cryptosystem based on algebraic coding theory","volume":"4244","author":"McEliece","year":"1978","journal-title":"Coding Thv"},{"key":"2022081612371190000_ref2","first-page":"99","volume-title":"Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22\u201324, 1996","author":"Ajtai","year":"1996"},{"key":"2022081612371190000_ref3","first-page":"298","volume-title":"44th Symposium on Foundations of Computer Science (FOCS 2003), 11\u201314 October 2003, Cambridge, MA, USA, Proceedings","author":"Alekhnovich","year":"2003"},{"key":"2022081612371190000_ref4","first-page":"485","volume-title":"Advances in Cryptology - ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2\u20136, 2012. Proceedings","author":"D\u00f6ttling","year":"2012"},{"key":"2022081612371190000_ref5","first-page":"1","volume-title":"Public-Key Cryptography - PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26\u201328, 2014. Proceedings","author":"Kiltz","year":"2014"},{"key":"2022081612371190000_ref6","first-page":"214","volume-title":"Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14\u201318, 2016, Proceedings, Part I","author":"Yu","year":"2016"},{"key":"2022081612371190000_ref7","first-page":"3","volume-title":"Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8\u201312, 2019, Proceedings, Part II","author":"Yu","year":"2019"},{"key":"2022081612371190000_ref8","first-page":"619","volume-title":"Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19\u201323, 2019, Proceedings, Part III","author":"Brakerski","year":"2019"},{"key":"2022081612371190000_ref9","first-page":"84","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22\u201324, 2005","author":"Regev","year":"2005"},{"key":"2022081612371190000_ref10","first-page":"361","volume-title":"Advances in Cryptology - EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13\u201317, 2008. Proceedings","author":"Gilbert","year":"2008"},{"key":"2022081612371190000_ref11","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1007\/978-3-642-34047-5_20","volume-title":"Fast Software Encryption - 19th International Workshop, FSE 2012, Washington, DC, USA, March 19\u201321, 2012. Revised Selected Papers","author":"Heyse","year":"2012"},{"key":"2022081612371190000_ref12","first-page":"1","volume-title":"Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco \/ French Riviera, May 30\u2013June 3, 2010. Proceedings","author":"Lyubashevsky","year":"2010"},{"key":"2022081612371190000_ref13","first-page":"92","volume-title":"Advances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19\u201323, 2007, Proceedings","author":"Applebaum","year":"2007"},{"key":"2022081612371190000_ref14","first-page":"278","volume-title":"Advances in Cryptology - CRYPTO \u201893, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22\u201326, 1993, Proceedings","author":"Blum","year":"1993"},{"key":"2022081612371190000_ref15","first-page":"73","volume-title":"Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28\u2013June 1, 2006, Proceedings","author":"Katz","year":"2006"},{"key":"2022081612371190000_ref16","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","article-title":"On the inherent intractability of certain coding problems (corresp.)","volume":"24","author":"Berlekamp","year":"1978","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2022081612371190000_ref17","first-page":"563","volume-title":"47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21\u201324 October 2006, Berkeley, California, USA, Proceedings","author":"Feldman","year":"2006"},{"key":"2022081612371190000_ref18","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1145\/792538.792543","article-title":"Noise-tolerant learning, the parity problem, and the statistical query model","volume":"50","author":"Blum","year":"2003","journal-title":"J. ACM"},{"key":"2022081612371190000_ref19","first-page":"378","volume-title":"Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th International Workshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22\u201324, 2005, Proceedings","author":"Lyubashevsky","year":"2005"},{"key":"2022081612371190000_ref20","first-page":"107","volume-title":"Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4\u20138, 2011. Proceedings","author":"May","year":"2011"},{"key":"2022081612371190000_ref21","first-page":"520","volume-title":"Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15\u201319, 2012. Proceedings","author":"Becker","year":"2012"},{"key":"2022081612371190000_ref22","first-page":"743","volume-title":"Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14\u201318, 2011. Proceedings","author":"Bernstein","year":"2011"},{"key":"2022081612371190000_ref23","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1109\/18.651067","article-title":"A new algorithm for finding minimum-weight words in a linear code: Application to mceliece\u2019s cryptosystem and to narrow-sense BCH codes of length 511","volume":"44","author":"Canteaut","year":"1998","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2022081612371190000_ref24","first-page":"377","article-title":"Improved generalized birthday attack","volume":"2011","author":"Kirchner","year":"2011","journal-title":"IACR Cryptology ePrint Archive"},{"key":"2022081612371190000_ref25","first-page":"106","volume-title":"A method for finding codewords of small weight. Coding Theory and Applications, 3rd International Colloquium, Toulon, France, November 2\u20134, 1988, Proceedings","author":"Stern","year":"1988"},{"key":"2022081612371190000_ref26","first-page":"870","article-title":"Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN","volume":"2020","author":"Yu","year":"2020","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"2022081612371190000_ref27","first-page":"171","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5\u20138 June 2010","author":"Applebaum","year":"2010"},{"key":"2022081612371190000_ref28","first-page":"986","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6\u20139, 2019","author":"Bogdanov","year":"2019"},{"key":"2022081612371190000_ref29","first-page":"465","volume-title":"Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14\u201318, 2011. Proceedings","author":"Micciancio","year":"2011"},{"key":"2022081612371190000_ref30","first-page":"1","volume-title":"Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14\u201318, 2011. Proceedings","author":"Barak","year":"2011"},{"key":"2022081612371190000_ref31","first-page":"664","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22\u201324, 2005","author":"Holenstein","year":"2005"},{"volume-title":"Strengthening key agreement using hardcore sets","year":"2006","author":"Holenstein","key":"2022081612371190000_ref32"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/65\/8\/1939\/45329657\/bxab027.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/65\/8\/1939\/45329657\/bxab027.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T12:38:51Z","timestamp":1660653531000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/65\/8\/1939\/6275472"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,14]]},"references-count":32,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,5,14]]},"published-print":{"date-parts":[[2022,8,11]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxab027","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2022,8]]},"published":{"date-parts":[[2021,5,14]]}}}