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

Qian Guo; Thomas Johansson; Erik Mårtensson; Paul Stankovski Wagner

doi:10.3934/amc.2019035

Article Contents

2019, Volume 13, Issue 4: 559-578. Doi: 10.3934/amc.2019035

This issue Previous Article Critical perspectives on provable security: Fifteen years of "another look" papers Next Article Differential uniformity and the associated codes of cryptographic functions

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
^* Corresponding author

Received: September 30, 2018

Published: June 2019

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)

Abstract Full Text(HTML) Figure(3) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 94A60; Secondary: 68P30.

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

Figure 2. The logarithm of the success probability for the different algorithms as a function of $ \sigma $

Download: Full-size image PowerPoint slide

Figure 3. The failure probability for the different algorithms as a function of $ \sigma $

Download: Full-size image PowerPoint slide

Related Papers

Cited by

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.