# American Institute of Mathematical Sciences

November  2019, 13(4): 559-578. doi: 10.3934/amc.2019035

## Some cryptanalytic and coding-theoretic applications of a soft stern algorithm

 1 Selmer Center, Department of Informatics, University of Bergen, Postboks 7803, N-5020 Bergen, Norway 2 Department of Electrical and Information Technology, Lund University, Box 118, SE-22100 Lund, Sweden

* Corresponding author

Part of the material in this paper was presented at the 2017 IEEE International Symposium on Information Theory (ISIT 2017), Aachen, Germany, June 25-30, 2017

Received  October 2018 Published  June 2019

Fund Project: This work was supported in part by the Swedish Research Council (Grant No. 2015-04528). The first author was also supported in part by the Norwegian Research Council (Grants No. 247742/070)

Using the class of information set decoding algorithms is the best known way of decoding general codes, i.e. codes that admit no special structure, in the Hamming metric. The Stern algorithm is the origin of the most efficient algorithms in this class. We consider the same decoding problem but for a channel with soft information. We give a version of the Stern algorithm for a channel with soft information that includes some novel steps of ordering vectors in lists, based on reliability values. We demonstrate how the algorithm constitutes an improvement in some cryptographic and coding theoretic applications. We also indicate how to extend the algorithm to include multiple iterations and soft output values.

Citation: Qian Guo, Thomas Johansson, Erik Mårtensson, Paul Stankovski Wagner. Some cryptanalytic and coding-theoretic applications of a soft stern algorithm. Advances in Mathematics of Communications, 2019, 13 (4) : 559-578. doi: 10.3934/amc.2019035
##### References:
 [1] M. Baldi, N. Maturo, E. Paolini and F. Chiaraluce, On the use of ordered statistics decoders for low-density parity-check codes in space telecommand links, EURASIP Journal on Wireless Communications and Networking, 2016 (2016), 272. doi: 10.1186/s13638-016-0769-z. Google Scholar [2] M. Baldi, P. Santini and F. Chiaraluce, Soft McEliece: MDPC code-based McEliece cryptosystems with very compact keys through real-valued intentional errors, in IEEE International Symposium on Information Theory ISIT, IEEE, (2016), 795–799. doi: 10.1109/ISIT.2016.7541408. Google Scholar [3] A. Becker, A. Joux, A. May and A. Meurer, Decoding random binary linear codes in $2^{n/20}$: How 1 + 1 = 0 improves information set decoding, in Advances in Cryptology – EUROCRYPT (eds. D. Pointcheval and T. Johansson), Springer, 7237 (2012), 520–536. doi: 10.1007/978-3-642-29011-4_31. Google Scholar [4] S. Belaïd, J.-S. Coron, P.-A. Fouque, B. Gèrard, J.-G. Kammerer and E. Prouff, Improved Side-Channel Analysis of Finite-Field Multiplication, in Cryptographic Hardware and Embedded Systems – CHES (eds. T. Güneysu and H. Handschuh), Springer, (2015), 395–415.Google Scholar [5] S. Belaïd, P.-A. Fouque and B. Gèrard, Side-channel analysis of multiplications in GF($2^{128}$), in Advances in Cryptology – ASIACRYPT (eds. P. Sarkar and T. Iwata), Springer, 8874 (2014), 306–325. doi: 10.1007/978-3-662-45608-8_17. Google Scholar [6] D. J. Bernstein, T. Lange and C. Peters, Smaller decoding exponents: Ball-collision decoding, in Advances in Cryptology – CRYPTO (eds. P. Rogaway), Springer, 6841 (2011), 743–760. doi: 10.1007/978-3-642-22792-9_42. Google Scholar [7] D. J. Bernstein, T. Lange and C. Peters, Attacking and Defending the McEliece Cryptosystem, in International Workshop on Post-Quantum Cryptography – PQCrypto (eds. J. Buchmann and J. Ding), Springer, 5299 (2008), 31–46. doi: 10.1007/978-3-540-88403-3_3. Google Scholar [8] A. Canteaut and F. Chabaud, A new algorithm for finding minimum-weight wordsin a linear code: Application to McEliece's cryptosystem and to narrow-sense BCH codes of length 511, IEEE Transactions on Information Theory, 44 (1998), 367-378. doi: 10.1109/18.651067. Google Scholar [9] D. Chase, A class of algorithms for decoding block codes with channel measurement information, IEEE Transactions on Information theory, 18 (1972), 170-182. doi: 10.1109/tit.1972.1054746. Google Scholar [10] J. Conway and N. Sloane, Soft decoding techniques for codes and lattices, including the Golay code and the Leech lattice, IEEE Transactions on Information Theory, 32 (1986), 41-50. doi: 10.1109/TIT.1986.1057135. Google Scholar [11] I. Dumer, Sort-and-match algorithm for soft-decision decoding, IEEE Transactions on Information Theory, 45 (1999), 2333-2338. doi: 10.1109/18.796373. Google Scholar [12] S. Dziembowski, S. Faust, G. Herold, A. Journault, D. Masny and F. Standaert, Towards sound fresh re-keying with hard (physical) learning problems, in Advances in Cryptology – CRYPTO (eds. M. Robshaw and J. Katz), Springer, 9815 (2016), 272–301. doi: 10.1007/978-3-662-53008-5_10. Google Scholar [13] M. Finiasz and N. Sendrier, Security bounds for the design of code-based cryptosystems, in Advances in Cryptology – ASIACRYPT, (eds. M. Matsui), Springer, (2009), 88–105. doi: 10.1007/978-3-642-10366-7_6. Google Scholar [14] M. P. Fossorier and S. Lin, Soft-decision decoding of linear block codes based on ordered statistics, IEEE Transactions on Information Theory, 41 (1995), 1379-1396. doi: 10.1109/ISIT.1994.394624. Google Scholar [15] D. Gazelle and J. Snyders, Reliability-Based Code-Search Algorithms for Maximum-Likelihood Decoding of Block Codes, IEEE Transactions on Information Theory, 43 (1997), 239-249. doi: 10.1109/18.567691. Google Scholar [16] Q. Guo, T. Johansson, E. Mårtensson and P. Stankovski, Information Set Decoding with Soft Information and some Cryptographic Applications, in IEEE International Symposium on Information Theory – ISIT, IEEE, (2017), 1793–1797. doi: 10.1109/ISIT.2017.8006838. Google Scholar [17] R. Koetter and A. Vardy, Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Transactions on Information Theory, 49 (2003), 2809-2825. doi: 10.1109/TIT.2003.819332. Google Scholar [18] P. J. Lee and E. F. Brickell, An observation on the security of McEliece's public-key cryptosystem, in Workshop on the Theory and Application of Cryptographic Techniques, Springer, 330 (1988), 275–280. doi: 10.1007/3-540-45961-8_25. Google Scholar [19] A. May and I. Ozerov, On computing nearest neighbors with applications to decoding of binary linear codes, in Advances in Cryptology - EUROCRYPT (eds. E. Oswald and M. Fischlin), Springer, 9056 (2015), 203–228. doi: 10.1007/978-3-662-46800-5_9. Google Scholar [20] R. Misoczki, J. P. Tillich, N. Sendrier and P. S. Barreto, MDPC-McEliece: New McEliece variants from moderate density parity-check codes, in IEEE International Symposium on Information Theory – ISIT, IEEE, (2013), 2069–2073. doi: 10.1109/ISIT.2013.6620590. Google Scholar [21] P. Pessl, L. Groot Bruinderink and Y. Yarom, To BLISS-B or not to be: Attacking strongSwan's Implementation of Post-Quantum Signatures, in ACM SIGSAC Conference on Computer and Communications Security – CCS, ACM, (2017), 1843–1855. doi: 10.1145/3133956.3134023. Google Scholar [22] P. Pessl and S. Mangard, Enhancing side-channel analysis of binary-field multiplication with bit reliability, in RSA Conference Cryptographers' Track (CT-RSA) (eds. K. Sako), 9610 (2016), 255–270. doi: 10.1007/978-3-319-29485-8_15. Google Scholar [23] E. Prange, The use of information sets in decoding cyclic codes, IRE Transactions on Information Theory, 8 (1962), 5-9. doi: 10.1109/tit.1962.1057777. Google Scholar [24] The Sage Developers, SageMath, the Sage Mathematics Software System, http://www.sagemath.org, 2018.Google Scholar [25] J. Stern, A method for finding codewords of small weight, in Coding Theory and Applications (eds. G. Cohen and J. Wolfmann), 388 (1988), 106–113. doi: 10.1007/BFb0019850. Google Scholar [26] A. Valembois, Fast soft-decision decoding of linear codes, stochastic resonance in algorithms, in IEEE International Symposium on Information Theory – ISIT, IEEE, (2000), 91. doi: 10.1109/ISIT.2000.866381. Google Scholar [27] A. Valembois and M. Fossorier, Generation of binary vectors that optimize a given weight function with application to soft-decision decoding, in IEEE Information Theory Workshop, IEEE, (2001), 138–140.Google Scholar [28] A. Valembois and M. Fossorier, Box and match techniques applied to soft-decision decoding, IEEE Transactions on Information Theory, 50 (2004), 796-810. doi: 10.1109/TIT.2004.826644. Google Scholar [29] A. J. Viterbi and J. K. Omura, Principles of Digital Communication and Coding, , McGraw-Hill, New York, 1979.Google Scholar [30] Y. Wu and C. N. Hadjicostis, Soft-decision decoding using ordered recodings on the most reliable basis, IEEE Transactions on Information Theory, 53 (2007), 829-836. doi: 10.1109/TIT.2006.889699. Google Scholar

show all references

##### References:
 [1] M. Baldi, N. Maturo, E. Paolini and F. Chiaraluce, On the use of ordered statistics decoders for low-density parity-check codes in space telecommand links, EURASIP Journal on Wireless Communications and Networking, 2016 (2016), 272. doi: 10.1186/s13638-016-0769-z. Google Scholar [2] M. Baldi, P. Santini and F. Chiaraluce, Soft McEliece: MDPC code-based McEliece cryptosystems with very compact keys through real-valued intentional errors, in IEEE International Symposium on Information Theory ISIT, IEEE, (2016), 795–799. doi: 10.1109/ISIT.2016.7541408. Google Scholar [3] A. Becker, A. Joux, A. May and A. Meurer, Decoding random binary linear codes in $2^{n/20}$: How 1 + 1 = 0 improves information set decoding, in Advances in Cryptology – EUROCRYPT (eds. D. Pointcheval and T. Johansson), Springer, 7237 (2012), 520–536. doi: 10.1007/978-3-642-29011-4_31. Google Scholar [4] S. Belaïd, J.-S. Coron, P.-A. Fouque, B. Gèrard, J.-G. Kammerer and E. Prouff, Improved Side-Channel Analysis of Finite-Field Multiplication, in Cryptographic Hardware and Embedded Systems – CHES (eds. T. Güneysu and H. Handschuh), Springer, (2015), 395–415.Google Scholar [5] S. Belaïd, P.-A. Fouque and B. Gèrard, Side-channel analysis of multiplications in GF($2^{128}$), in Advances in Cryptology – ASIACRYPT (eds. P. Sarkar and T. Iwata), Springer, 8874 (2014), 306–325. doi: 10.1007/978-3-662-45608-8_17. Google Scholar [6] D. J. Bernstein, T. Lange and C. Peters, Smaller decoding exponents: Ball-collision decoding, in Advances in Cryptology – CRYPTO (eds. P. Rogaway), Springer, 6841 (2011), 743–760. doi: 10.1007/978-3-642-22792-9_42. Google Scholar [7] D. J. Bernstein, T. Lange and C. Peters, Attacking and Defending the McEliece Cryptosystem, in International Workshop on Post-Quantum Cryptography – PQCrypto (eds. J. Buchmann and J. Ding), Springer, 5299 (2008), 31–46. doi: 10.1007/978-3-540-88403-3_3. Google Scholar [8] A. Canteaut and F. Chabaud, A new algorithm for finding minimum-weight wordsin a linear code: Application to McEliece's cryptosystem and to narrow-sense BCH codes of length 511, IEEE Transactions on Information Theory, 44 (1998), 367-378. doi: 10.1109/18.651067. Google Scholar [9] D. Chase, A class of algorithms for decoding block codes with channel measurement information, IEEE Transactions on Information theory, 18 (1972), 170-182. doi: 10.1109/tit.1972.1054746. Google Scholar [10] J. Conway and N. Sloane, Soft decoding techniques for codes and lattices, including the Golay code and the Leech lattice, IEEE Transactions on Information Theory, 32 (1986), 41-50. doi: 10.1109/TIT.1986.1057135. Google Scholar [11] I. Dumer, Sort-and-match algorithm for soft-decision decoding, IEEE Transactions on Information Theory, 45 (1999), 2333-2338. doi: 10.1109/18.796373. Google Scholar [12] S. Dziembowski, S. Faust, G. Herold, A. Journault, D. Masny and F. Standaert, Towards sound fresh re-keying with hard (physical) learning problems, in Advances in Cryptology – CRYPTO (eds. M. Robshaw and J. Katz), Springer, 9815 (2016), 272–301. doi: 10.1007/978-3-662-53008-5_10. Google Scholar [13] M. Finiasz and N. Sendrier, Security bounds for the design of code-based cryptosystems, in Advances in Cryptology – ASIACRYPT, (eds. M. Matsui), Springer, (2009), 88–105. doi: 10.1007/978-3-642-10366-7_6. Google Scholar [14] M. P. Fossorier and S. Lin, Soft-decision decoding of linear block codes based on ordered statistics, IEEE Transactions on Information Theory, 41 (1995), 1379-1396. doi: 10.1109/ISIT.1994.394624. Google Scholar [15] D. Gazelle and J. Snyders, Reliability-Based Code-Search Algorithms for Maximum-Likelihood Decoding of Block Codes, IEEE Transactions on Information Theory, 43 (1997), 239-249. doi: 10.1109/18.567691. Google Scholar [16] Q. Guo, T. Johansson, E. Mårtensson and P. Stankovski, Information Set Decoding with Soft Information and some Cryptographic Applications, in IEEE International Symposium on Information Theory – ISIT, IEEE, (2017), 1793–1797. doi: 10.1109/ISIT.2017.8006838. Google Scholar [17] R. Koetter and A. Vardy, Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Transactions on Information Theory, 49 (2003), 2809-2825. doi: 10.1109/TIT.2003.819332. Google Scholar [18] P. J. Lee and E. F. Brickell, An observation on the security of McEliece's public-key cryptosystem, in Workshop on the Theory and Application of Cryptographic Techniques, Springer, 330 (1988), 275–280. doi: 10.1007/3-540-45961-8_25. Google Scholar [19] A. May and I. Ozerov, On computing nearest neighbors with applications to decoding of binary linear codes, in Advances in Cryptology - EUROCRYPT (eds. E. Oswald and M. Fischlin), Springer, 9056 (2015), 203–228. doi: 10.1007/978-3-662-46800-5_9. Google Scholar [20] R. Misoczki, J. P. Tillich, N. Sendrier and P. S. Barreto, MDPC-McEliece: New McEliece variants from moderate density parity-check codes, in IEEE International Symposium on Information Theory – ISIT, IEEE, (2013), 2069–2073. doi: 10.1109/ISIT.2013.6620590. Google Scholar [21] P. Pessl, L. Groot Bruinderink and Y. Yarom, To BLISS-B or not to be: Attacking strongSwan's Implementation of Post-Quantum Signatures, in ACM SIGSAC Conference on Computer and Communications Security – CCS, ACM, (2017), 1843–1855. doi: 10.1145/3133956.3134023. Google Scholar [22] P. Pessl and S. Mangard, Enhancing side-channel analysis of binary-field multiplication with bit reliability, in RSA Conference Cryptographers' Track (CT-RSA) (eds. K. Sako), 9610 (2016), 255–270. doi: 10.1007/978-3-319-29485-8_15. Google Scholar [23] E. Prange, The use of information sets in decoding cyclic codes, IRE Transactions on Information Theory, 8 (1962), 5-9. doi: 10.1109/tit.1962.1057777. Google Scholar [24] The Sage Developers, SageMath, the Sage Mathematics Software System, http://www.sagemath.org, 2018.Google Scholar [25] J. Stern, A method for finding codewords of small weight, in Coding Theory and Applications (eds. G. Cohen and J. Wolfmann), 388 (1988), 106–113. doi: 10.1007/BFb0019850. Google Scholar [26] A. Valembois, Fast soft-decision decoding of linear codes, stochastic resonance in algorithms, in IEEE International Symposium on Information Theory – ISIT, IEEE, (2000), 91. doi: 10.1109/ISIT.2000.866381. Google Scholar [27] A. Valembois and M. Fossorier, Generation of binary vectors that optimize a given weight function with application to soft-decision decoding, in IEEE Information Theory Workshop, IEEE, (2001), 138–140.Google Scholar [28] A. Valembois and M. Fossorier, Box and match techniques applied to soft-decision decoding, IEEE Transactions on Information Theory, 50 (2004), 796-810. doi: 10.1109/TIT.2004.826644. Google Scholar [29] A. J. Viterbi and J. K. Omura, Principles of Digital Communication and Coding, , McGraw-Hill, New York, 1979.Google Scholar [30] Y. Wu and C. N. Hadjicostis, Soft-decision decoding using ordered recodings on the most reliable basis, IEEE Transactions on Information Theory, 53 (2007), 829-836. doi: 10.1109/TIT.2006.889699. Google Scholar
An ilustration of what the binary tree in the algorithm for finding the most probable bit patterns looks like in the first six steps
The logarithm of the success probability for the different algorithms as a function of $\sigma$
The failure probability for the different algorithms as a function of $\sigma$
 [1] Claude Carlet, Sylvain Guilley. Complementary dual codes for counter-measures to side-channel attacks. Advances in Mathematics of Communications, 2016, 10 (1) : 131-150. doi: 10.3934/amc.2016.10.131 [2] Guojun Gan, Kun Chen. A soft subspace clustering algorithm with log-transformed distances. Big Data & Information Analytics, 2016, 1 (1) : 93-109. doi: 10.3934/bdia.2016.1.93 [3] Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419 [4] Meng Yu, Jack Xin. Stochastic approximation and a nonlocally weighted soft-constrained recursive algorithm for blind separation of reverberant speech mixtures. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1753-1767. doi: 10.3934/dcds.2010.28.1753 [5] Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179 [6] Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer. The secrecy capacity of the arbitrarily varying wiretap channel under list decoding. Advances in Mathematics of Communications, 2019, 13 (1) : 11-39. doi: 10.3934/amc.2019002 [7] M. Silhavý. Ideally soft nematic elastomers. Networks & Heterogeneous Media, 2007, 2 (2) : 279-311. doi: 10.3934/nhm.2007.2.279 [8] Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007 [9] Jonas Eriksson. A weight-based characterization of the set of correctable error patterns under list-of-2 decoding. Advances in Mathematics of Communications, 2007, 1 (3) : 331-356. doi: 10.3934/amc.2007.1.331 [10] Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443 [11] Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505 [12] Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433 [13] Nicolas Fournier. A new regularization possibility for the Boltzmann equation with soft potentials. Kinetic & Related Models, 2008, 1 (3) : 405-414. doi: 10.3934/krm.2008.1.405 [14] Eva Sincich, Mourad Sini. Local stability for soft obstacles by a single measurement. Inverse Problems & Imaging, 2008, 2 (2) : 301-315. doi: 10.3934/ipi.2008.2.301 [15] Xueyan Wu. An algorithm for reversible information hiding of encrypted medical images in homomorphic encrypted domain. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1441-1455. doi: 10.3934/dcdss.2019099 [16] Weiping Li, Haiyan Wu, Jie Yang. Intelligent recognition algorithm for social network sensitive information based on classification technology. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1385-1398. doi: 10.3934/dcdss.2019095 [17] Xiaohong Zhu, Lihe Zhou, Zili Yang, Joyati Debnath. A new text information extraction algorithm of video image under multimedia environment. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1265-1279. doi: 10.3934/dcdss.2019087 [18] Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385 [19] Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83 [20] Robert F. Bailey, John N. Bray. Decoding the Mathieu group M12. Advances in Mathematics of Communications, 2007, 1 (4) : 477-487. doi: 10.3934/amc.2007.1.477

2018 Impact Factor: 0.879