Syndrome based collision resistant hashing. (English) Zbl 1177.94144
Buchmann, Johannes (ed.) et al., Post-quantum cryptography. Second international workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17–19, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-88402-6/pbk). Lecture Notes in Computer Science 5299, 137-147 (2008).
Summary: Hash functions are a hot topic at the moment in cryptography. Many proposals are going to be made for SHA-3, and among them, some provably collision resistant hash functions might also be proposed. These do not really compete with “standard” designs as they are usually much slower and not well suited for constrained environments. However, they present an interesting alternative when speed is not the main objective. As always when dealing with provable security, hard problems are involved, and the fast syndrome-based cryptographic hash function proposed by Augot, Finiasz and Sendrier at Mycrypt 2005 relies on the problem of Syndrome Decoding, a well known “Post Quantum” problem from coding theory. In this article we review the different variants and attacks against it so as to clearly point out which choices are secure and which are not.
For the entire collection see [Zbl 1147.94002].
For the entire collection see [Zbl 1147.94002].
References:
| [1] | Augot, D., Finiasz, M., Sendrier, N.: A family of fast syndrome based cryptographic hash functions. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol. 3715, pp. 64–83. Springer, Heidelberg (2005) · Zbl 1126.94320 · doi:10.1007/11554868_6 |
| [2] | Berbain, C., Gilbert, H., Patarin, J.: QUAD: a practical stream cipher with provable security. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 109–128. Springer, Heidelberg (2006) · Zbl 1140.94322 · doi:10.1007/11761679_8 |
| [3] | Blum, L., Blum, M., Shub, M.: Comparison of two pseudo-random number generators. In: Chaum, D., Rivest, R.L., Sherman, A. (eds.) Crypto 1982, pp. 61–78. Plenum (1983) · Zbl 0543.68031 · doi:10.1007/978-1-4757-0602-4_6 |
| [4] | 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(1), 367–378 (1998) · Zbl 1053.94558 · doi:10.1109/18.651067 |
| [5] | Coron, J.-S., Joux, A.: Cryptanalysis of a provably secure cryptographic hash function. IACR eprint archive (2004), http://eprint.iacr.org/2004/013 |
| [6] | Finiasz, M., Gaborit, P., Sendrier, N.: Improved fast syndrome based cryptographic hash functions. In: Rijmen, V. (ed.) ECRYPT Workshop on Hash Functions (2007) |
| [7] | Fouque, P.-A., Leurent, G.: Cryptanalysis of a hash function based on quasi-cyclic codes. In: Malkin, T. (ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 19–35. Springer, Heidelberg (2008) · Zbl 1159.94360 · doi:10.1007/978-3-540-79263-5_2 |
| [8] | Gaborit, P., Zémor., G.: Asymptotic improvement of the Gilbert-Varshamov bound for linear codes. In: IEEE Conference, ISIT 2006, pp. 287–291 (2006) |
| [9] | Saarinen, M.-J.O.: Linearization attacks against syndrome based hashes. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 1–9. Springer, Heidelberg (2007) · Zbl 1153.94426 · doi:10.1007/978-3-540-77026-8_1 |
| [10] | Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–304. Springer, Heidelberg (2002) · Zbl 1026.94541 · doi:10.1007/3-540-45708-9_19 |
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.
