{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T02:27:32Z","timestamp":1749781652455},"reference-count":39,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2020,1,1]]},"DOI":"10.1587\/transfun.2019cip0022","type":"journal-article","created":{"date-parts":[[2019,12,31]],"date-time":"2019-12-31T22:06:04Z","timestamp":1577829964000},"page":"173-182","source":"Crossref","is-referenced-by-count":1,"title":["On the Complexity of the LWR-Solving BKW Algorithm"],"prefix":"10.1587","volume":"E103.A","author":[{"given":"Hiroki","family":"OKADA","sequence":"first","affiliation":[{"name":"KDDI Research, Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Atsushi","family":"TAKAYASU","sequence":"additional","affiliation":[{"name":"The University of Tokyo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhide","family":"FUKUSHIMA","sequence":"additional","affiliation":[{"name":"KDDI Research, Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shinsaku","family":"KIYOMOTO","sequence":"additional","affiliation":[{"name":"KDDI Research, Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tsuyoshi","family":"TAKAGI","sequence":"additional","affiliation":[{"name":"The University of Tokyo"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] H. Okada, A. Takayasu, K. Fukushima, S. Kiyomoto, and T. Takagi, \u201cOn the complexity of the LWR-solving BKW algorithm,\u201d ICISC 2018, pp.196-214, 2019. 10.1007\/978-3-030-12146-4_13","DOI":"10.1007\/978-3-030-12146-4_13"},{"key":"2","unstructured":"[2] National Institute of Standards and Technology, \u201cPost-quantum cryptography,\u201d https:\/\/csrc.nist.gov\/Projects\/Post-Quantum-Cryptography. Accessed: Feb. 27, 2019."},{"key":"3","doi-asserted-by":"crossref","unstructured":"[3] J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J.M. Schanck, P. Schwabe, G. Seiler, and D. Stehle, \u201cCRYSTALS \u2014 Kyber: A CCA-secure module-lattice-based KEM,\u201d EuroS&amp;P 2018, pp.353-367, 2018. 10.1109\/eurosp.2018.00032","DOI":"10.1109\/EuroSP.2018.00032"},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] J. Bos, C. Costello, L. Ducas, I. Mironov, M. Naehrig, V. Nikolaenko, A. Raghunathan, and D. Stebila, \u201cFrodo: Take off the ring! practical, quantum-secure key exchange from LWE,\u201d CCS 2016, pp.1006-1018, 2016. 10.1145\/2976749.2978425","DOI":"10.1145\/2976749.2978425"},{"key":"5","unstructured":"[5] E. Alkim, L. Ducas, T. P\u00f6ppelmann, and P. Schwabe, \u201cPost-quantum key exchange \u2014 A new hope,\u201d USENIX Security Symposium, pp.327-343, 2016."},{"key":"6","unstructured":"[6] R.E. Bansarkhani, \u201cLARA \u2014 A design concept for lattice-based encryption,\u201d Cryptology ePrint Archive, Report 2017\/049, 2017."},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] M.R. Albrecht, E. Orsini, K.G. Paterson, G. Peer, and N.P. Smart, \u201cTightly secure Ring-LWE based key encapsulation with short ciphertexts,\u201d ESORICS 2017, pp.29-46, 2017. 10.1007\/978-3-319-66402-6_4","DOI":"10.1007\/978-3-319-66402-6_4"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] J.H. Cheon, D. Kim, J. Lee, and Y. Song, \u201cLizard: Cut off the tail! a practical post-quantum public-key encryption from LWE and LWR,\u201d SCN 2018, pp.160-177, 2018. 10.1007\/978-3-319-98113-0_9","DOI":"10.1007\/978-3-319-98113-0_9"},{"key":"9","unstructured":"[9] Z. Jin and Y. Zhao, \u201cOptimal key consensus in presence of noise,\u201d CoRR, vol.abs\/1611.06150, 2016."},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] J.P. D&apos;Anvers, A. Karmakar, S.S. Roy, and F. Vercauteren, \u201cSaber: Module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM,\u201d AFRICACRYPT 2018, pp.282-305, 2018. 10.1007\/978-3-319-89339-6_16","DOI":"10.1007\/978-3-319-89339-6_16"},{"key":"11","unstructured":"[11] H. Baan, S. Bhattacharya, O. Garcia-Morchon, R. Rietman, L. Tolhuizen, J.L. Torre-Arce, and Z. Zhang, \u201cRound2: KEM and PKE based on GLWR,\u201d Cryptology ePrint Archive, Report 2017\/1183, 2017."},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] H. Baan, S. Bhattacharya, S. Fluhrer, O. Garcia-Morchon, T. Laarhoven, R. Rietman, M.J.O. Saarinen, L. Tolhuizen, and Z. Zhang, \u201cRound5: Compact and fast post-quantum public-key encryption,\u201d Cryptology ePrint Archive, Report 2019\/090, 2019.","DOI":"10.1007\/978-3-030-25510-7_5"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] O. Regev, \u201cOn lattices, learning with errors, random linear codes, and cryptography,\u201d J. ACM, vol.56, no.6, pp.34:1-34:40, 2009. 10.1145\/1568318.1568324","DOI":"10.1145\/1568318.1568324"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] A. Becker, N. Gama, and A. Joux, \u201cA sieve algorithm based on overlattices,\u201d LMS J. Comput. Math., vol.17, no.A, pp.49-70, 2014. 10.1112\/s1461157014000229","DOI":"10.1112\/S1461157014000229"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] Y. Chen and P.Q. Nguyen, \u201cBKZ 2.0: Better lattice security estimates,\u201d ASIACRYPT 2011, pp.1-20, 2011. 10.1007\/978-3-642-25385-0_1","DOI":"10.1007\/978-3-642-25385-0_1"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] N. Gama, P.Q. Nguyen, and O. Regev, \u201cLattice enumeration using extreme pruning,\u201d EUROCRYPT 2010, pp.257-278, 2010. 10.1007\/978-3-642-13190-5_13","DOI":"10.1007\/978-3-642-13190-5_13"},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] M.R. Albrecht, B.R. Curtis, A. Deo, A. Davidson, R. Player, E.W. Postlethwaite, F. Virdia, and T. Wunderer, \u201cEstimate all the {LWE, NTRU} schemes!,\u201d SCN 2018, pp.351-367, 2018. 10.1007\/978-3-319-98113-0_19","DOI":"10.1007\/978-3-319-98113-0_19"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[18] A. Blum, A. Kalai, and H. Wasserman, \u201cNoise-tolerant learning, the parity problem, and the statistical query model,\u201d J. ACM, vol.50, no.4, pp.506-519, 2003. 10.1145\/792538.792543","DOI":"10.1145\/792538.792543"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] G. Herold, E. Kirshanova, and A. May, \u201cOn the asymptotic complexity of solving LWE,\u201d Des. Codes Cryptogr., vol.86, no.1, pp.55-83, 2018. 10.1007\/s10623-016-0326-0","DOI":"10.1007\/s10623-016-0326-0"},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] Q. Guo, T. Johansson, and P. Stankovski, \u201cCoded-BKW: Solving LWE using lattice codes,\u201d CRYPTO 2015, pp.23-42, 2015. 10.1007\/978-3-662-47989-6_2","DOI":"10.1007\/978-3-662-47989-6_2"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[21] P. Kirchner and P.A. Fouque, \u201cAn improved BKW algorithm for LWE with applications to cryptography and lattices,\u201d CRYPTO 2015, pp.43-62, 2015. 10.1007\/978-3-662-47989-6_3","DOI":"10.1007\/978-3-662-47989-6_3"},{"key":"22","doi-asserted-by":"crossref","unstructured":"[22] T. Laarhoven, \u201cSieving for shortest vectors in lattices using angular locality-sensitive hashing,\u201d CRYPTO 2015, pp.3-22, 2015. 10.1007\/978-3-662-47989-6_1","DOI":"10.1007\/978-3-662-47989-6_1"},{"key":"23","doi-asserted-by":"crossref","unstructured":"[23] A. Banerjee, C. Peikert, and A. Rosen, \u201cPseudorandom functions and lattices,\u201d EUROCRYPT 2012, pp.719-737, 2012. 10.1007\/978-3-642-29011-4_42","DOI":"10.1007\/978-3-642-29011-4_42"},{"key":"24","doi-asserted-by":"publisher","unstructured":"[24] D. Boneh, K. Lewi, H. Montgomery, and A. Raghunathan, \u201cKey homomorphic PRFs and their applications,\u201d CRYPTO 2013, pp.410-428, 2013. 10.1007\/978-3-642-40041-4_23","DOI":"10.1007\/978-3-642-40041-4_23"},{"key":"25","doi-asserted-by":"publisher","unstructured":"[25] J. Alwen, S. Krenn, K. Pietrzak, and D. Wichs, \u201cLearning with rounding, revisited,\u201d CRYPTO 2013, pp.57-74, 2013. 10.1007\/978-3-642-40041-4_4","DOI":"10.1007\/978-3-642-40041-4_4"},{"key":"26","doi-asserted-by":"publisher","unstructured":"[26] M.R. Albrecht, C. Cid, J.C. Faug\u00e8re, R. Fitzpatrick, and L. Perret, \u201cOn the complexity of the BKW algorithm on LWE,\u201d Des. Codes Cryptogr., vol.74, no.2, pp.325-354, 2015. 10.1007\/s10623-013-9864-x","DOI":"10.1007\/s10623-013-9864-x"},{"key":"27","doi-asserted-by":"crossref","unstructured":"[27] A. Duc, F. Tram\u00e8r, and S. Vaudenay, \u201cBetter algorithms for LWE and LWR,\u201d EUROCRYPT 2015, pp.173-202, 2015. 10.1007\/978-3-662-46800-5_8","DOI":"10.1007\/978-3-662-46800-5_8"},{"key":"28","doi-asserted-by":"crossref","unstructured":"[28] V. Lyubashevsky, \u201cThe parity problem in the presence of noise, decoding random linear codes, and the subset sum problem,\u201d Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pp.378-389, 2005. 10.1007\/11538462_32","DOI":"10.1007\/11538462_32"},{"key":"29","doi-asserted-by":"crossref","unstructured":"[29] Q. Guo, T. Johansson, E. M\u00e5rtensson, and P. Stankovski, \u201cCoded-BKW with sieving,\u201d ASIACRYPT 2017, pp.323-346, 2017. 10.1007\/978-3-319-70694-8_12","DOI":"10.1007\/978-3-319-70694-8_12"},{"key":"30","doi-asserted-by":"publisher","unstructured":"[30] M.R. Albrecht, J.C. Faug\u00e8re, R. Fitzpatrick, and L. Perret, \u201cLazy modulus switching for the BKW algorithm on LWE,\u201d PKC 2014, pp.429-445, 2014. 10.1007\/978-3-642-54631-0_25","DOI":"10.1007\/978-3-642-54631-0_25"},{"key":"31","doi-asserted-by":"crossref","unstructured":"[31] R.M. Corless, G.H. Gonnet, D.E. Hare, D.J. Jeffrey, and D.E. Knuth, \u201cOn the Lambert <i>W<\/i> function,\u201d Adv. Comput. Math., vol.5, no.1, pp.329-359, 1996. 10.1007\/bf02124750","DOI":"10.1007\/BF02124750"},{"key":"32","unstructured":"[32] K. Kaminakaya, N. Kunihiro, and A. Takayasu, \u201cBKW algorithm for solving LWE problem,\u201d Symposium on Cryptography and Information Security, SCIS 2016, IEICE, 2016 (in Japanese)."},{"key":"33","doi-asserted-by":"crossref","unstructured":"[33] V. Lyubashevsky, C. Peikert, and O. Regev, \u201cOn ideal lattices and learning with errors over rings,\u201d EUROCRYPT 2010, pp.1-23, 2010. 10.1007\/978-3-642-13190-5_1","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"34","doi-asserted-by":"publisher","unstructured":"[34] A. Langlois and D. Stehl\u00e9, \u201cWorst-case to average-case reductions for module lattices,\u201d Des. Codes Cryptogr., vol.75, no.3, pp.565-599, June 2015. 10.1007\/s10623-014-9938-4","DOI":"10.1007\/s10623-014-9938-4"},{"key":"35","doi-asserted-by":"publisher","unstructured":"[35] S. Bogos, F. Tram\u00e9r, and S. Vaudenay, \u201cOn solving LPN using BKW and variants,\u201d Cryptogr. Commun., vol.8, no.3, pp.331-369, 2016. 10.1007\/s12095-015-0149-2","DOI":"10.1007\/s12095-015-0149-2"},{"key":"36","doi-asserted-by":"crossref","unstructured":"[36] S. Bogos and S. Vaudenay, \u201cOptimization of LPN solving algorithms,\u201d ASIACRYPT 2016, pp.703-728, 2016. 10.1007\/978-3-662-53887-6_26","DOI":"10.1007\/978-3-662-53887-6_26"},{"key":"37","doi-asserted-by":"crossref","unstructured":"[37] B. Zhang, L. Jiao, and M. Wang, \u201cFaster algorithms for solving LPN,\u201d EUROCRYPT 2016, pp.168-195, 2016. 10.1007\/978-3-662-49890-3_7","DOI":"10.1007\/978-3-662-49890-3_7"},{"key":"38","doi-asserted-by":"crossref","unstructured":"[38] S. Devadas, L. Ren, and H. Xiao, \u201cOn iterative collision search for LPN and subset sum,\u201d Theory of Cryptography, pp.729-746, 2017. 10.1007\/978-3-319-70503-3_24","DOI":"10.1007\/978-3-319-70503-3_24"},{"key":"39","doi-asserted-by":"crossref","unstructured":"[39] A. Esser, F. Heuer, R. K\u00fcbler, A. May, and C. Sohler, \u201cDissection-BKW,\u201d CRYPTO 2018, pp.638-666, 2018. 10.1007\/978-3-319-96881-0_22","DOI":"10.1007\/978-3-319-96881-0_22"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E103.A\/1\/E103.A_2019CIP0022\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,6]],"date-time":"2020-01-06T05:25:32Z","timestamp":1578288332000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E103.A\/1\/E103.A_2019CIP0022\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,1]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2019cip0022","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,1]]}}}