{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T19:59:55Z","timestamp":1770753595095,"version":"3.50.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,9,24]],"date-time":"2022-09-24T00:00:00Z","timestamp":1663977600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,24]],"date-time":"2022-09-24T00:00:00Z","timestamp":1663977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/S021043\/1"],"award-info":[{"award-number":["EP\/S021043\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001381","name":"National Research Foundation Singapore","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cryptogr. Commun."],"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The ring learning with errors (RLWE) problem can be used to construct efficient post-quantum public key encryption schemes. An error distribution, normally a Gaussian-like distribution, is involved in the RLWE problem. In this work we focus on using polar codes to alleviate a natural trade-off present in RLWE public key encryption schemes; namely, we would like a wider error distribution to increase security, but a wider error distribution comes at the cost of an increased probability of decryption error. The motivation of this work is to improve the bit-security level by using wider error distribution while keeping the target decryption failure rate achievable. The approach we proposed in this work is twofold. Firstly, we formulate RLWE public key encryption as a channel model with some noise terms known by the decoder. This makes our approach distinguished from existing research of this kind in the literature which ignores these known terms. Secondly, we design polar codes for the derived channel model. Theoretically and numerically, we show the proposed modeling and polar coding scheme contributes to a considerable bit-security level improvement compared with NewHope, a submission to National Institute of Standards and Technology (NIST), with almost the same parameters. Moreover, polar encoding and decoding support isochronous implementations in the sense that the timings of associated operations are irrelevant to the sensitive information.<\/jats:p>","DOI":"10.1007\/s12095-022-00607-1","type":"journal-article","created":{"date-parts":[[2022,9,24]],"date-time":"2022-09-24T05:02:46Z","timestamp":1663995766000},"page":"397-431","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Polar coding for Ring-LWE-based public key encryption"],"prefix":"10.1007","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5492-4119","authenticated-orcid":false,"given":"Jiabo","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cong","family":"Ling","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,9,24]]},"reference":[{"issue":"3","key":"607_CR1","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1515\/jmc-2015-0016","volume":"9","author":"MR Albrecht","year":"2015","unstructured":"Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol.\u00a09(3), 169\u2013203 (2015)","journal-title":"J Math Cryptol"},{"key":"607_CR2","doi-asserted-by":"crossref","unstructured":"Albrecht, MR, Curtis, BR, Deo, A, Davidson, A, Player, R, Postlethwaite, EW, Virdia, F, Wunderer, T Catalano, D, De Prisco, R (eds.): Estimate All the LWE, NTRU schemes!. Springer International Publishing, Cham (2018)","DOI":"10.1007\/978-3-319-98113-0_19"},{"key":"607_CR3","first-page":"1157","volume":"2016","author":"E Alkim","year":"2016","unstructured":"Alkim, E., Ducas, L., P\u00f6ppelmann, T., Schwabe, P.: NewHope without reconciliation. IACR Cryptology ePrint Archive, 1157 (2016)","journal-title":"IACR Cryptology ePrint Archive"},{"key":"607_CR4","unstructured":"Alkim, E, Ducas, L, P\u00f6ppelmann, T, Schwabe, P: Post-quantum key exchange\u2014a new hope. In: 25th USENIX Security Symposium, pp 327\u201343 (2016b)"},{"issue":"7","key":"607_CR5","doi-asserted-by":"publisher","first-page":"3051","DOI":"10.1109\/TIT.2009.2021379","volume":"55","author":"E Arikan","year":"2009","unstructured":"Arikan, E.: Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Trans. Inf. Theory 55(7), 3051\u201373 (2009)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"12","key":"607_CR6","doi-asserted-by":"publisher","first-page":"2352","DOI":"10.1109\/LCOMM.2013.111113.132103","volume":"17","author":"A Bravo-Santos","year":"2013","unstructured":"Bravo-Santos, A.: Polar codes for the Rayleigh fading channel. IEEE Communications Lett. 17(12), 2352\u201355 (2013)","journal-title":"IEEE Communications Lett."},{"issue":"3","key":"607_CR7","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1109\/18.669123","volume":"44","author":"G Caire","year":"1998","unstructured":"Caire, G., Taricco, G., Biglieri, E.: Bit-interleaved coded modulation. IEEE Trans. Inform. Theory 44(3), 927\u201346 (1998)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"607_CR8","first-page":"782","volume":"2016","author":"E Crockett","year":"2016","unstructured":"Crockett, E., Peikert, C.: Challenges for ring-LWE. IACR Cryptol ePrint Arch, 782 (2016)","journal-title":"IACR Cryptol ePrint Arch"},{"key":"607_CR9","doi-asserted-by":"crossref","unstructured":"D\u2019Anvers, JP, Vercauteren, F, Verbauwhede, I: The impact of error dependencies on ring\/mod-LWE\/LWR based schemes. In: International Conference on Post-Quantum Cryptography. Springer, pp 103\u201315 (2019)","DOI":"10.1007\/978-3-030-25510-7_6"},{"key":"607_CR10","first-page":"688","volume":"2012","author":"J Ding","year":"2012","unstructured":"Ding, J., Xie, X., Lin, X.: A simple provably secure key exchange scheme based on the learning with errors problem. IACR Cryptology EPrint Archive, 688 (2012)","journal-title":"IACR Cryptology EPrint Archive"},{"issue":"5","key":"607_CR11","doi-asserted-by":"publisher","first-page":"1123","DOI":"10.1109\/18.21245","volume":"34","author":"GD Forney","year":"1988","unstructured":"Forney, G.D.: Coset codes. I. Introduction and geometrical classification. IEEE Trans. Inf. Theory 34(5), 1123\u201351 (1988)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"607_CR12","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1109\/18.841165","volume":"46","author":"GD Forney","year":"2000","unstructured":"Forney, G.D., Trott, M.D., Chung, S.Y.: Sphere-bound-achieving coset codes and multilevel coset codes. IEEE Trans. Inf. Theory 46(3), 820\u2013850 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"607_CR13","first-page":"150","volume":"2018","author":"T Fritzmann","year":"2018","unstructured":"Fritzmann, T., P\u00f6ppelmann, T., Sep\u00falveda, M.J.: Analysis of error-correcting codes for lattice-based key exchange. IACR Cryptology ePrint Archive, 150 (2018)","journal-title":"IACR Cryptology ePrint Archive"},{"key":"607_CR14","doi-asserted-by":"crossref","unstructured":"Fujisaki, E, Okamoto, T: Secure integration of asymmetric and symmetric encryption schemes. In: Annual International Cryptology Conference. Springer, pp 537\u201354 (1999)","DOI":"10.1007\/3-540-48405-1_34"},{"key":"607_CR15","doi-asserted-by":"crossref","unstructured":"Howe, J, Prest, T, Ricosset, T, Rossi, M: Isochronous Gaussian Sampling: From Inception to Implementation. In: Ding, J, Tillich, JP (eds.) Post-Quantum Cryptography, pp 53\u201371. Springer International Publishing, Cham (2020)","DOI":"10.1007\/978-3-030-44223-1_4"},{"key":"607_CR16","unstructured":"Kocer, EG.: Circulant, negacyclic and semicirculant matrices with the modified Pell, Jacobsthal and jacobsthal-Lucas numbers. Hacettepe Journal of Mathematics and Statistics 36(2) (2007)"},{"key":"607_CR17","unstructured":"Korada, SB.: Polar Codes for Channel and Source Coding. PhD Thesis Ecole Polytechnique F\u00e9d\u00e9rale De Lausanne. Lausanne, Switzerland (2009)"},{"issue":"12","key":"607_CR18","doi-asserted-by":"publisher","first-page":"4923","DOI":"10.1109\/TCOMM.2016.2613109","volume":"64","author":"C Ling","year":"2016","unstructured":"Ling, C.: Polar codes and polar lattices for independent fading channels. IEEE Trans. Commun. 64(12), 4923\u20134935 (2016)","journal-title":"IEEE Trans. Commun."},{"key":"607_CR19","first-page":"1009","volume":"2018","author":"X Lu","year":"2018","unstructured":"Lu, X., Liu, Y., Zhang, Z., Jia, D., Xue, H., He, J., Li, B., Wang, K., Liu, Z., Yang, H.: LAC: Practical ring-LWE based public-key encryption with byte-level modulus. IACR Cryptol ePrint Arch, 1009 (2018)","journal-title":"IACR Cryptol ePrint Arch"},{"key":"607_CR20","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V, Peikert, C, Regev, O: On ideal lattices and learning with errors over rings. In: Annual international conference on the theory and applications of cryptographic techniques, pp 1\u201323. Springer, (2010)","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"607_CR21","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V, Peikert, C, Regev, O: A toolkit for ring-LWE cryptography. In: Annual international conference on the theory and applications of cryptographic techniques, pp 35\u201354.\u00a0Springer, (2013)","DOI":"10.1007\/978-3-642-38348-9_3"},{"issue":"6","key":"607_CR22","doi-asserted-by":"publisher","first-page":"2756","DOI":"10.1109\/TIT.2009.2018177","volume":"55","author":"A Martinez","year":"2009","unstructured":"Martinez, A., Guillen i Fabregas, A., Caire, G., Willems, F.M.J.: Bit-interleaved coded modulation revisited: a mismatched decoding perspective. IEEE Trans. Inf. Theory 55(6), 2756\u20132765 (2009)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"12","key":"607_CR23","doi-asserted-by":"publisher","first-page":"6698","DOI":"10.1109\/TIT.2016.2616117","volume":"62","author":"M Mondelli","year":"2016","unstructured":"Mondelli, M., Hassani, S.H., Urbanke, R.L.: Unified scaling of polar codes: Error exponent, scaling exponent, moderate deviations, and error floors. IEEE Trans. Inf. Theory 62(12), 6698\u20136712 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"607_CR24","doi-asserted-by":"crossref","unstructured":"Murphy, S, Player, R: \u03b4-Subgaussian random variables in cryptography. In: Jang-Jaccard, J, Guo, F (eds.) Information Security and Privacy, pp 251\u2013268. Springer International Publishing, Cham (2019)","DOI":"10.1007\/978-3-030-21548-4_14"},{"key":"607_CR25","doi-asserted-by":"crossref","unstructured":"Murphy, S, Player, R: Discretisation and product distributions in ring-LWE.\u00a0J. Math. Cryptol.\u00a015(1) (2020)","DOI":"10.1515\/jmc-2020-0073"},{"key":"607_CR26","unstructured":"NIST.: Submission requirements and evaluation criteria for the post-quantum cryptography standardization process. https:\/\/csrc.nist.gov\/CSRC\/media\/Projects\/Post-Quantum-Cryptography\/documents\/call-for-proposals-final-dec-2016.pdf. Accessed 1 Aug\u00a02016"},{"key":"607_CR27","doi-asserted-by":"crossref","unstructured":"Pedarsani, R, Hassani, SH, Tal, I, Telatar, E: On the construction of polar codes. In: 2011 IEEE international symposium on information theory proceedings, pp. 11\u201315 (2011)","DOI":"10.1109\/ISIT.2011.6033724"},{"key":"607_CR28","first-page":"1050","volume":"2016","author":"AV Poppelen","year":"2016","unstructured":"Poppelen, A.V.: Cryptographic decoding of the Leech lattice. IACR Cryptology ePrint Archive, 1050 (2016)","journal-title":"IACR Cryptology ePrint Archive"},{"key":"607_CR29","unstructured":"Prest, T., Ricosset, T., Rossi, M.: Simple, fast and constant-time Gaussian sampling over the integers for Falcon. Tech. rep., Second PQC Standardization Conference. https:\/\/csrc.nist.gov\/Presentations\/2019\/simple-fast-and-constant-time-gaussian. Accessed 23 Aug\u00a02019"},{"key":"607_CR30","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes and cryptography. In: Proceedings of the thirty-seventh annual ACM symposium on theory of computing. ACM, New York, NY, USA, STOC \u201905, pp. 84\u201393 (2005)","DOI":"10.1145\/1060590.1060603"},{"key":"607_CR31","doi-asserted-by":"crossref","unstructured":"Saarinen, MJO.: HILA5: On reliability, reconciliation, and error correction for ring-LWE encryption. In: International conference on selected areas in cryptography. Springer, pp. 192\u2013212 (2017)","DOI":"10.1007\/978-3-319-72565-9_10"},{"key":"607_CR32","doi-asserted-by":"publisher","first-page":"45443","DOI":"10.1109\/ACCESS.2020.2977607","volume":"8","author":"M Song","year":"2020","unstructured":"Song, M., Lee, S., Shin, D., Lee, E., Kim, Y., No, J.: Analysis of error dependencies on newHope. IEEE Access 8, 45443\u201356 (2020)","journal-title":"IEEE Access"},{"key":"607_CR33","doi-asserted-by":"crossref","unstructured":"Stehl\u00e9, D, Steinfeld, R, Tanaka, K, Xagawa, K.: Efficient public key encryption based on ideal lattices. In: International conference on the theory and application of cryptology and information security. Springer, pp. 617\u2013635 (2009)","DOI":"10.1007\/978-3-642-10366-7_36"},{"issue":"10","key":"607_CR34","doi-asserted-by":"publisher","first-page":"6562","DOI":"10.1109\/TIT.2013.2272694","volume":"59","author":"I Tal","year":"2013","unstructured":"Tal, I., Vardy, A.: How to construct polar codes. IEEE Trans. Inf. Theory 59(10), 6562\u20136582 (2013)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"607_CR35","doi-asserted-by":"publisher","first-page":"2213","DOI":"10.1109\/TIT.2015.2410251","volume":"61","author":"I Tal","year":"2015","unstructured":"Tal, I., Vardy, A.: List decoding of polar codes. IEEE Trans. Inf. Theory 61(5), 2213\u20132226 (2015)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"607_CR36","doi-asserted-by":"crossref","unstructured":"Trifonov, P.: Design of polar codes for Rayleigh fading channel. In: 2015 international symposium on wireless communication systems (ISWCS), pp. 331\u2013335 (2015)","DOI":"10.1109\/ISWCS.2015.7454357"},{"issue":"1","key":"607_CR37","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1109\/TC.2019.2940949","volume":"69","author":"RK Zhao","year":"2019","unstructured":"Zhao, R.K., Steinfeld, R., Sakzad, A.: Facct: fast, compact, and constant-time discrete Gaussian sampler over integers. IEEE Trans. Comput.\u00a069(1), 126\u2013137 (2019)","journal-title":"IEEE Trans Comput"}],"container-title":["Cryptography and Communications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-022-00607-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12095-022-00607-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12095-022-00607-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,13]],"date-time":"2023-02-13T16:13:27Z","timestamp":1676304807000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12095-022-00607-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,24]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["607"],"URL":"https:\/\/doi.org\/10.1007\/s12095-022-00607-1","relation":{},"ISSN":["1936-2447","1936-2455"],"issn-type":[{"value":"1936-2447","type":"print"},{"value":"1936-2455","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,24]]},"assertion":[{"value":"9 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of Interests"}}]}}