Abstract
Fix positive integers B and w. Let C be a linear code over F 2 of length Bw. The 2-regular-decoding problem is to find a nonzero codeword consisting of w length-B blocks, each of which has Hamming weight 0 or 2. This problem appears in attacks on the FSB (fast syndrome-based) hash function and related proposals. This problem differs from the usual information-set-decoding problems in that (1) the target codeword is required to have a very regular structure and (2) the target weight can be rather high, so that there are many possible codewords of that weight.
Augot, Finiasz, and Sendrier, in the paper that introduced FSB, presented a variant of information-set decoding tuned for 2-regular decoding. This paper improves the Augot–Finiasz–Sendrier algorithm in a way that is analogous to Stern’s improvement upon basic information-set decoding. The resulting algorithm achieves an exponential speedup over the previous algorithm.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Augot, D., Finiasz, M., Gaborit, P., Manuel, S., Sendrier, N.: SHA-3 proposal: FSB (2008), http://www-rocq.inria.fr/secret/CBCrypto/fsbdoc.pdf , Citations in this document: §1, §1, §1, §5, §5, §5, §5
Augot, D., Finiasz, M., Sendrier, N.: A fast provably secure cryptographic hash function (2003), http://eprint.iacr.org/2003/230 , Citations in this document: §1, §1, §1, §2, §3, §3, §3, §3, §3, §3, §4
Augot, D., Finiasz, M., Sendrier, N.: A family of fast syndrome based cryptographic hash functions. In: Mycrypt 2005 [13], pp. 64–83 (2005), Citations in this document: §1, §1, §3
Bernstein, D.J., Lange, T., Niederhagen, R., Peters, C., Schwabe, P.: FSBday: implementing Wagner’s generalized birthday attack against the SHA-3 round-1 candidate FSB. In: Indocrypt 2009 [23], pp. 18–38 (2009), http://eprint.iacr.org/2009/292 , Citations in this document: §1
Bernstein, D.J., Lange, T., Peters, C.: Attacking and defending the McEliece cryptosystem. In: PQCrypto 2008 [9], pp. 31–46 (2008), http://eprint.iacr.org/2008/318 , Citations in this document: §2, §4, §4
Bernstein, D.J., Lange, T., Peters, C.: Ball-collision decoding (2010), http://eprint.iacr.org/2010/585 , Citations in this document: §2, §4
Bernstein, D.J., Lange, T., Peters, C., Schwabe, P.: Really fast syndrome-based hashing (2011), http://eprint.iacr.org/2011/074 , Citations in this document: §1, §1, §5
Bernstein, D.J., Lange, T., Peters, C., van Tilborg, H.: Explicit bounds for generic decoding algorithms for code-based cryptography. In: WCC 2009, pp. 168–180 (2009), Citations in this document: §4
Buchmann, J., Ding, J. (eds.): PQCrypto 2008. LNCS, vol. 5299. Springer, Heidelberg (2008) See [5], [14]
Canteaut, A., Chabaud, F.: A new algorithm for finding minimum-weight words in a linear code: application to McEliece’s cryptosystem and to narrow-sense BCH codes of length 511. IEEE Transactions on Information Theory 44, 367–378 (1998), ftp://ftp.inria.fr/INRIA/tech-reports/RR/RR-2685.ps.gz , MR 98m:94043, Citations in this document: §4
Carleial, A.B., Hellman, M.E.: A note on Wyner’s wiretap channel. IEEE Transactions on Information Theory 23, 387–390 (1977), ISSN 0018-9448, Citations in this document: §4
Wolfmann, J., Cohen, G. (eds.): Coding Theory 1988. LNCS, vol. 388. Springer, Heidelberg (1989), See [24]
Dawson, E., Vaudenay, S. (eds.): Mycrypt 2005. LNCS, vol. 3715. Springer, Heidelberg (2005), See [3]
Finiasz, M.: Syndrome based collision resistant hashing. In: PQCrypto 2008 [9], pp. 137–147 (2008), Citations in this document: §1
Finiasz, M., Gaborit, P., Sendrier, N.: Improved fast syndrome based cryptographic hash functions. In: Proceedings of ECRYPT Hash Workshop 2007 (2007), http://www-roc.inria.fr/secret/Matthieu.Finiasz/research/2007/finiasz-gaborit-sendrier-ecrypt-hash-workshop07.pdf , Citations in this document: §1, §1
Finiasz, M., Sendrier, N.: Security bounds for the design of code-based cryptosystems. In: Asiacrypt 2009 [20] (2009), http://eprint.iacr.org/2009/414 , Citations in this document: §2, §4
Günther, C.G. (ed.): EUROCRYPT 1988. LNCS, vol. 330. Springer, Heidelberg (1988), MR 90a:94002, See [18]
Lee, P.J., Brickell, E.F.: An observation on the security of McEliece’s public-key cryptosystem. In: Eurocrypt 1988 [17], pp. 275–280 (1988), http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/E88/275.PDF , MR 0994669, Citations in this document: §2, §4
Leon, J.S.: A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Transactions on Information Theory 34, 1354–1359 (1988), MR 89k:94072, Citations in this document: §2
Matsui, M. (ed.): ASIACRYPT 2009. LNCS, vol. 5912. Springer, Heidelberg (2009), See [16]
McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. JPL DSN Progress Report, 114–116 (1978), http://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF , Citations in this document: §2
Prange, E.: The use of information sets in decoding cyclic codes. IRE Transactions on Information Theory IT-8, S5–S9 (1962), Citations in this document: §2
Roy, B., Sendrier, N. (eds.): INDOCRYPT 2009. LNCS, vol. 5922. Springer, Heidelberg (2009), See [4]
Stern, J.: A method for finding codewords of small weight. In: [12], pp. 106–113 (1989), Citations in this document: §2, §4
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bernstein, D.J., Lange, T., Peters, C., Schwabe, P. (2011). Faster 2-Regular Information-Set Decoding. In: Chee, Y.M., et al. Coding and Cryptology. IWCC 2011. Lecture Notes in Computer Science, vol 6639. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20901-7_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-20901-7_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20900-0
Online ISBN: 978-3-642-20901-7
eBook Packages: Computer ScienceComputer Science (R0)