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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[24]

The Sage Developers, SageMath, the Sage Mathematics Software System, http://www.sagemath.org, 2018.

[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.

[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.

[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.

[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.

[29]

A. J. Viterbi and J. K. Omura, Principles of Digital Communication and Coding, , McGraw-Hill, New York, 1979.

[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.

show all references

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

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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[24]

The Sage Developers, SageMath, the Sage Mathematics Software System, http://www.sagemath.org, 2018.

[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.

[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.

[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.

[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.

[29]

A. J. Viterbi and J. K. Omura, Principles of Digital Communication and Coding, , McGraw-Hill, New York, 1979.

[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.

Figure 1.  An ilustration of what the binary tree in the algorithm for finding the most probable bit patterns looks like in the first six steps
Figure 2.  The logarithm of the success probability for the different algorithms as a function of $ \sigma $
Figure 3.  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]

Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021031

[3]

Anna-Lena Horlemann-Trautmann, Violetta Weger. Information set decoding in the Lee metric with applications to cryptography. Advances in Mathematics of Communications, 2021, 15 (4) : 677-699. doi: 10.3934/amc.2020089

[4]

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

[5]

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

[6]

Meng Yu, Jack Xin. Stochastic approximation and a nonlocally weighted soft-constrained recursive algorithm for blind separation of reverberant speech mixtures. Discrete and Continuous Dynamical Systems, 2010, 28 (4) : 1753-1767. doi: 10.3934/dcds.2010.28.1753

[7]

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

[8]

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

[9]

M. Silhavý. Ideally soft nematic elastomers. Networks and Heterogeneous Media, 2007, 2 (2) : 279-311. doi: 10.3934/nhm.2007.2.279

[10]

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007

[11]

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

[12]

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

[13]

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

[14]

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

[15]

Violetta Weger, Karan Khathuria, Anna-Lena Horlemann, Massimo Battaglioni, Paolo Santini, Edoardo Persichetti. On the hardness of the Lee syndrome decoding problem. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022029

[16]

Nicolas Fournier. A new regularization possibility for the Boltzmann equation with soft potentials. Kinetic and Related Models, 2008, 1 (3) : 405-414. doi: 10.3934/krm.2008.1.405

[17]

Eva Sincich, Mourad Sini. Local stability for soft obstacles by a single measurement. Inverse Problems and Imaging, 2008, 2 (2) : 301-315. doi: 10.3934/ipi.2008.2.301

[18]

Fei Meng, Fang Liu. On the inelastic Boltzmann equation for soft potentials with diffusion. Communications on Pure and Applied Analysis, 2020, 19 (11) : 5197-5217. doi: 10.3934/cpaa.2020233

[19]

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

[20]

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

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (671)
  • HTML views (351)
  • Cited by (1)

[Back to Top]