Faster 2-regular information-set decoding. (English) Zbl 1272.94096
Chee, Yeow Meng (ed.) et al., Coding and cryptology. Third international workshop, IWCC 2011, Qingdao, China, May 30 – June 3, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20900-0/pbk). Lecture Notes in Computer Science 6639, 81-98 (2011).
Summary: Fix positive integers \(B\) and \(w\). Let \(C\) be a linear code over \(\mathbb 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.
In the paper that introduced FSB [Lect. Notes Comput. Sci. 3715, 64–83 (2005; Zbl 1126.94320)], D. Augot et al. 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.
For the entire collection see [Zbl 1214.94002].
In the paper that introduced FSB [Lect. Notes Comput. Sci. 3715, 64–83 (2005; Zbl 1126.94320)], D. Augot et al. 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.
For the entire collection see [Zbl 1214.94002].
Citations:
Zbl 1126.94320Software:
McElieceReferences:
| [1] | 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 |
| [2] | 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 |
| [3] | 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 · Zbl 1126.94320 · doi:10.1007/11554868_6 |
| [4] | 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 · Zbl 1248.94055 |
| [5] | 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 · Zbl 1177.94128 |
| [6] | Bernstein, D.J., Lange, T., Peters, C.: Ball-collision decoding (2010), http://eprint.iacr.org/2010/585 , Citations in this document: §2, §4 |
| [7] | 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 · Zbl 1280.94039 |
| [8] | 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 |
| [9] | Buchmann, J., Ding, J. (eds.): PQCrypto 2008. LNCS, vol. 5299. Springer, Heidelberg (2008) See [5], [14] · Zbl 1147.94002 |
| [10] | 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 · Zbl 1053.94558 · doi:10.1109/18.651067 |
| [11] | 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 · Zbl 0353.94025 |
| [12] | Wolfmann, J., Cohen, G. (eds.): Coding Theory 1988. LNCS, vol. 388. Springer, Heidelberg (1989), See [24] · Zbl 0652.01018 |
| [13] | Dawson, E., Vaudenay, S. (eds.): Mycrypt 2005. LNCS, vol. 3715. Springer, Heidelberg (2005), See [3] · Zbl 1089.94001 |
| [14] | Finiasz, M.: Syndrome based collision resistant hashing. In: PQCrypto 2008 [9], pp. 137–147 (2008), Citations in this document: §1 · Zbl 1177.94144 · doi:10.1007/978-3-540-88403-3_10 |
| [15] | 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 |
| [16] | 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 · Zbl 1267.94058 |
| [17] | Günther, C.G. (ed.): EUROCRYPT 1988. LNCS, vol. 330. Springer, Heidelberg (1988), MR 90a:94002, See [18] |
| [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 · Zbl 0655.94006 |
| [19] | 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 · Zbl 0666.94017 · doi:10.1109/18.21270 |
| [20] | Matsui, M. (ed.): ASIACRYPT 2009. LNCS, vol. 5912. Springer, Heidelberg (2009), See [16] · Zbl 1177.94014 |
| [21] | 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 |
| [22] | 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 |
| [23] | Roy, B., Sendrier, N. (eds.): INDOCRYPT 2009. LNCS, vol. 5922. Springer, Heidelberg (2009), See [4] · Zbl 1178.94007 |
| [24] | Stern, J.: A method for finding codewords of small weight. In: [12], pp. 106–113 (1989), Citations in this document: §2, §4 · Zbl 0678.94006 · doi:10.1007/BFb0019850 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
