{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,19]],"date-time":"2022-08-19T18:31:28Z","timestamp":1660933888658},"reference-count":98,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2020,7,21]],"date-time":"2020-07-21T00:00:00Z","timestamp":1595289600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004497","name":"Onderzoeksraad, KU Leuven","doi-asserted-by":"publisher","award":["C14\/18\/067","STG\/17\/019"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7,21]]},"abstract":"Abstract<\/jats:title>We introduce a general framework encompassing the main hard problems emerging in lattice-based cryptography, which naturally includes the recently proposed Mersenne prime cryptosystem, but also problems coming from code-based cryptography. The framework allows to easily instantiate new hard problems and to automatically construct plausibly post-quantum secure primitives from them. As a first basic application, we introduce two new hard problems and the corresponding encryption schemes. Concretely, we study generalisations of hard problems such as SIS, LWE and NTRU to free modules over quotients of \u2124[X<\/jats:italic>] by ideals of the form (f<\/jats:italic>,g<\/jats:italic>), wheref<\/jats:italic>is a monic polynomial andg<\/jats:italic>\u2208 \u2124[X<\/jats:italic>] is a ciphertext modulus coprime tof<\/jats:italic>. For trivial modules (i.e. of rank one), the casef<\/jats:italic>=Xn<\/jats:sup><\/jats:italic>+ 1 andg<\/jats:italic>=q<\/jats:italic>\u2208 \u2124>1<\/jats:sub>corresponds to ring-LWE, ring-SIS and NTRU, while the choicesf<\/jats:italic>=Xn<\/jats:sup><\/jats:italic>\u2013 1 andg<\/jats:italic>=X<\/jats:italic>\u2013 2 essentially cover the recently proposed Mersenne prime cryptosystems. At the other extreme, when considering modules of large rank and letting deg(f<\/jats:italic>) = 1, one recovers the framework of LWE and SIS.<\/jats:p>","DOI":"10.1515\/jmc-2019-0032","type":"journal-article","created":{"date-parts":[[2019,11,8]],"date-time":"2019-11-08T09:06:11Z","timestamp":1573203971000},"page":"202-217","source":"Crossref","is-referenced-by-count":2,"title":["A framework for cryptographic problems from linear algebra"],"prefix":"10.1515","volume":"14","author":[{"given":"Carl","family":"Bootland","sequence":"first","affiliation":[{"name":"ESAT\/COSIC, KU Leuven, Kasteelpark Arenberg 10, 3000Leuven, Belgium"}]},{"given":"Wouter","family":"Castryck","sequence":"additional","affiliation":[{"name":"Department of Mathematics, KU Leuven, Celestijnenlaan 200B, 3000Leuven, Belgium"}]},{"given":"Alan","family":"Szepieniec","sequence":"additional","affiliation":[{"name":"ESAT\/COSIC, KU Leuven, Kasteelpark Arenberg 10, 3000Leuven, Belgium"}]},{"given":"Frederik","family":"Vercauteren","sequence":"additional","affiliation":[{"name":"ESAT\/COSIC, KU Leuven, Kasteelpark Arenberg 10, 3000Leuven, Belgium"}]}],"member":"374","reference":[{"key":"ref371","doi-asserted-by":"crossref","first-page":"35283","DOI":"10.1109\/ACCESS.2018.2846798","article-title":"Oblivious transfer based on NTRUEncrypt","volume":"6","year":"2018","journal-title":"IEEE Access"},{"key":"ref341","first-page":"1","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2010","year":"2010"},{"key":"ref201","article-title":"Somewhat practical fully homomorphic encryption","year":"2012","journal-title":"Preprint"},{"key":"ref981","first-page":"617","volume-title":"Advances in Cryptology\u2014ASIACRYPT 2009","year":"2009"},{"key":"ref411","first-page":"1","volume-title":"16th IEEE International Conference on Networks","year":"2008"},{"key":"ref101","doi-asserted-by":"crossref","first-page":"1006","volume-title":"Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security","year":"2016","DOI":"10.1145\/2976749.2978425"},{"key":"ref921","first-page":"1","volume-title":"16th IEEE International Conference on Networks","year":"2008"},{"key":"ref141","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1112\/S1461157016000280","article-title":"On error distributions in ring-based LWE","volume":"19","year":"2016","journal-title":"LMS J. Comput. Math."},{"key":"ref291","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/s10623-014-9938-4","article-title":"Worst-case to average-case reductions for module lattices","volume":"75","year":"2015","journal-title":"Des. Codes Cryptogr."},{"key":"ref511","article-title":"A new public-key cryptosystem via Mersenne numbers","year":"2017","journal-title":"Preprint"},{"key":"ref801","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/s10623-014-9938-4","article-title":"Worst-case to average-case reductions for module lattices","volume":"75","year":"2015","journal-title":"Des. Codes Cryptogr."},{"key":"ref811","first-page":"107","volume-title":"Public-key Cryptography\u2014PKC 2013","year":"2013"},{"key":"ref41","first-page":"55","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2019","year":"2019"},{"key":"ref911","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1090\/S0002-9939-1983-0715856-2","article-title":"On resultants","volume":"89","year":"1983","journal-title":"Proc. Amer. Math. Soc."},{"key":"ref11","first-page":"459","volume-title":"Advances in Cryptology\u2014CRYPTO 2018. Part III","year":"2018"},{"key":"ref81","first-page":"166","volume-title":"Progress in Cryptology\u2014LATINCRYPT 2017","year":"2019"},{"key":"ref561","first-page":"153","volume-title":"Advances in Cryptology\u2014CRYPTO 2016. Part I","year":"2016"},{"key":"ref581","first-page":"235","volume-title":"Selected Areas in Cryptography\u2014SAC 2017","year":"2018"},{"key":"ref681","first-page":"232","volume-title":"Progress in Cryptology\u2014INDOCRYPT 2005","year":"2005"},{"key":"ref851","first-page":"1","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2010","year":"2010"},{"key":"ref421","first-page":"159","article-title":"Knapsack-type cryptosystems and algebraic coding theory","volume":"15","year":"1986","journal-title":"Probl. Control Inf. Theory"},{"key":"ref611","doi-asserted-by":"crossref","first-page":"1006","volume-title":"Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security","year":"2016","DOI":"10.1145\/2976749.2978425"},{"key":"ref991","year":"2018","journal-title":"Ramstake"},{"key":"ref211","first-page":"169","volume-title":"Proceedings of the 2009 ACM International Symposium on Theory of Computing\u2014STOC\u201909","year":"2009"},{"key":"ref831","first-page":"738","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2012","year":"2012"},{"key":"ref901","article-title":"On the hardness of learning with errors with binary secrets","volume":"14","year":"2018","journal-title":"Theory Comput."},{"key":"ref881","doi-asserted-by":"crossref","first-page":"35283","DOI":"10.1109\/ACCESS.2018.2846798","article-title":"Oblivious transfer based on NTRUEncrypt","volume":"6","year":"2018","journal-title":"IEEE Access"},{"key":"ref671","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1112\/S1461157016000371","article-title":"An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero","volume":"19","year":"2016","journal-title":"LMS J. Comput. Math."},{"key":"ref731","first-page":"197","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing\u2014STOC\u201908","year":"2008"},{"key":"ref451","first-page":"84","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing\u2014STOC\u201905","year":"2005"},{"key":"ref931","first-page":"159","article-title":"Knapsack-type cryptosystems and algebraic coding theory","volume":"15","year":"1986","journal-title":"Probl. Control Inf. Theory"},{"key":"ref641","first-page":"575","volume-title":"Proceedings of the 2013 ACM Symposium on Theory of Computing\u2014STOC\u201913","year":"2013"},{"key":"ref971","article-title":"Reproducible codes and cryptographic applications","year":"2018","journal-title":"Preprint"},{"key":"ref781","article-title":"A signature scheme from learning with truncation","year":"2017","journal-title":"Preprint"},{"key":"ref51","first-page":"153","volume-title":"Advances in Cryptology\u2014CRYPTO 2016. Part I","year":"2016"},{"key":"ref631","article-title":"(Leveled) fully homomorphic encryption without bootstrapping","volume":"6","year":"2014","journal-title":"ACM Trans. Comput. Theory"},{"key":"ref171","first-page":"232","volume-title":"Progress in Cryptology\u2014INDOCRYPT 2005","year":"2005"},{"key":"ref21","first-page":"99","volume-title":"Proceedings of the 28th Annual ACM Symposium on the Theory of Computing","year":"1996"},{"key":"ref311","first-page":"1219","volume-title":"Proceedings of the 2012 ACM Symposium on Theory of Computing\u2014STOC\u201912","year":"2012"},{"key":"ref331","first-page":"144","volume-title":"Automata, Languages and Programming. Part II","year":"2006"},{"key":"ref281","first-page":"3","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2017. Part I","year":"2017"},{"key":"ref231","article-title":"Integer version of ring-LWE and its applications","year":"2017","journal-title":"Preprint"},{"key":"ref01","article-title":"A new public-key cryptosystem via Mersenne numbers","year":"2017","journal-title":"Preprint"},{"key":"ref61","first-page":"327","volume-title":"Proceedings of the 25th USENIX Security Symposium","year":"2016"},{"key":"ref71","first-page":"235","volume-title":"Selected Areas in Cryptography\u2014SAC 2017","year":"2018"},{"key":"ref381","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s00037-007-0234-9","article-title":"Generalized compact knapsacks, cyclic lattices, and efficient one-way functions","volume":"16","year":"2007","journal-title":"Comput. Complexity"},{"key":"ref161","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1112\/S1461157016000371","article-title":"An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero","volume":"19","year":"2016","journal-title":"LMS J. Comput. Math."},{"key":"ref761","article-title":"NTRU: A new high speed public key cryptosystem","year":"1996","journal-title":"Preprint"},{"key":"ref251","article-title":"NTRU: A new high speed public key cryptosystem","year":"1996","journal-title":"Preprint"},{"key":"ref471","first-page":"617","volume-title":"Advances in Cryptology\u2014ASIACRYPT 2009","year":"2009"},{"key":"ref541","first-page":"44","volume-title":"Progress in Cryptology\u2014AFRICACRYPT 2016","year":"2016"},{"key":"ref861","first-page":"1","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2010","year":"2010"},{"key":"ref301","first-page":"107","volume-title":"Public-key Cryptography\u2014PKC 2013","year":"2013"},{"key":"ref751","journal-title":"Miscellaneous"},{"key":"ref191","first-page":"22","volume-title":"Advances in Cryptology\u2014ASIACRYPT 2014. Part II","year":"2014"},{"key":"ref841","first-page":"144","volume-title":"Automata, Languages and Programming. Part II","year":"2006"},{"key":"ref461","article-title":"Reproducible codes and cryptographic applications","year":"2018","journal-title":"Preprint"},{"key":"ref521","first-page":"459","volume-title":"Advances in Cryptology\u2014CRYPTO 2018. Part III","year":"2018"},{"key":"ref941","first-page":"554","volume-title":"Advances in Cryptology\u2014CRYPTO 2008","year":"2008"},{"key":"ref431","first-page":"554","volume-title":"Advances in Cryptology\u2014CRYPTO 2008","year":"2008"},{"key":"ref481","year":"2018","journal-title":"Ramstake"},{"key":"ref691","article-title":"A simple provably secure key exchange scheme based on the learning with errors problem","year":"2012","journal-title":"Preprint"},{"key":"ref771","first-page":"267","volume-title":"Algorithmic Number Theory","year":"1998"},{"key":"ref401","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1090\/S0002-9939-1983-0715856-2","article-title":"On resultants","volume":"89","year":"1983","journal-title":"Proc. Amer. Math. Soc."},{"key":"ref241","journal-title":"Miscellaneous"},{"key":"ref591","first-page":"166","volume-title":"Progress in Cryptology\u2014LATINCRYPT 2017","year":"2019"},{"key":"ref601","article-title":"Efficiently processing complex-valued data in homomorphic encryption","year":"2018","journal-title":"Preprint"},{"key":"ref621","first-page":"370","volume-title":"Theory of Cryptography. Part II","year":"2018"},{"key":"ref91","article-title":"Efficiently processing complex-valued data in homomorphic encryption","year":"2018","journal-title":"Preprint"},{"key":"ref441","first-page":"S5","article-title":"The use of information sets in decoding cyclic codes","volume":"IT-8","year":"1962","journal-title":"IRE Trans."},{"key":"ref391","article-title":"On the hardness of learning with errors with binary secrets","volume":"14","year":"2018","journal-title":"Theory Comput."},{"key":"ref651","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1112\/S1461157016000280","article-title":"On error distributions in ring-based LWE","volume":"19","year":"2016","journal-title":"LMS J. Comput. Math."},{"key":"ref661","first-page":"116","volume-title":"Topics in Cryptology\u2014CT-RSA 2018","year":"2018"},{"key":"ref131","first-page":"575","volume-title":"Proceedings of the 2013 ACM Symposium on Theory of Computing\u2014STOC\u201913","year":"2013"},{"key":"ref31","first-page":"44","volume-title":"Progress in Cryptology\u2014AFRICACRYPT 2016","year":"2016"},{"key":"ref721","first-page":"169","volume-title":"Proceedings of the 2009 ACM International Symposium on Theory of Computing\u2014STOC\u201909","year":"2009"},{"key":"ref701","first-page":"22","volume-title":"Advances in Cryptology\u2014ASIACRYPT 2014. Part II","year":"2014"},{"key":"ref711","article-title":"Somewhat practical fully homomorphic encryption","year":"2012","journal-title":"Preprint"},{"key":"ref551","first-page":"55","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2019","year":"2019"},{"key":"ref111","first-page":"370","volume-title":"Theory of Cryptography. Part II","year":"2018"},{"key":"ref261","first-page":"267","volume-title":"Algorithmic Number Theory","year":"1998"},{"key":"ref151","first-page":"116","volume-title":"Topics in Cryptology\u2014CT-RSA 2018","year":"2018"},{"key":"ref271","article-title":"A signature scheme from learning with truncation","year":"2017","journal-title":"Preprint"},{"key":"ref321","first-page":"738","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2012","year":"2012"},{"key":"ref571","first-page":"327","volume-title":"Proceedings of the 25th USENIX Security Symposium","year":"2016"},{"key":"ref871","first-page":"114","article-title":"A public-key cryptosystem based on algebraic coding theory","volume":"42\u201344","year":"1978","journal-title":"JPL DSN Progress Report"},{"key":"ref951","first-page":"S5","article-title":"The use of information sets in decoding cyclic codes","volume":"IT-8","year":"1962","journal-title":"IRE Trans."},{"key":"ref361","first-page":"114","article-title":"A public-key cryptosystem based on algebraic coding theory","volume":"42\u201344","year":"1978","journal-title":"JPL DSN Progress Report"},{"key":"ref181","article-title":"A simple provably secure key exchange scheme based on the learning with errors problem","year":"2012","journal-title":"Preprint"},{"key":"ref351","first-page":"1","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2010","year":"2010"},{"key":"ref741","article-title":"Integer version of ring-LWE and its applications","year":"2017","journal-title":"Preprint"},{"key":"ref221","first-page":"197","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing\u2014STOC\u201908","year":"2008"},{"key":"ref531","first-page":"99","volume-title":"Proceedings of the 28th Annual ACM Symposium on the Theory of Computing","year":"1996"},{"key":"ref791","first-page":"3","volume-title":"Advances in Cryptology\u2014EUROCRYPT 2017. Part I","year":"2017"},{"key":"ref821","first-page":"1219","volume-title":"Proceedings of the 2012 ACM Symposium on Theory of Computing\u2014STOC\u201912","year":"2012"},{"key":"ref961","first-page":"84","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing\u2014STOC\u201905","year":"2005"},{"key":"ref121","article-title":"(Leveled) fully homomorphic encryption without bootstrapping","volume":"6","year":"2014","journal-title":"ACM Trans. Comput. Theory"},{"key":"ref891","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s00037-007-0234-9","article-title":"Generalized compact knapsacks, cyclic lattices, and efficient one-way functions","volume":"16","year":"2007","journal-title":"Comput. Complexity"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/jmc\/14\/1\/article-p202.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2019-0032\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,22]],"date-time":"2021-04-22T01:17:54Z","timestamp":1619054274000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/jmc-2019-0032\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,21]]},"references-count":98,"journal-issue":{"issue":"1"},"URL":"http:\/\/dx.doi.org\/10.1515\/jmc-2019-0032","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"value":"1862-2984","type":"electronic"},{"value":"1862-2976","type":"print"}],"subject":["Applied Mathematics","Computational Mathematics","Computer Science Applications"],"published":{"date-parts":[[2020,7,21]]}}}