zbMATH — the first resource for mathematics

QUAD: A multivariate stream cipher with provable security. (English) Zbl 1173.94415
Summary: We present the stream cipher QUAD and the provable security arguments supporting its conjectured strength for suitable parameter values. QUAD was first proposed at Eurocrypt 2006 by C. Berbain et al. [in: Advances in cryptology – EUROCRYPT 2006. 25th annual international conference on the theory and applications of cryptographic techniques, St. Petersburg, Russia, May 28 – June 1, 2006. Proceedings. Berlin: Springer. Lecture Notes in Computer Science 4004, 109–128 (2006; Zbl 1140.94322)]. It relies on the iteration of a set of multivariate quadratic polynomials over a finite field, typically GF(2) or a small extension. We show that in the binary case, the security of the keystream generation can be related, in the concrete security model, to the conjectured intractability of the MQ problem of solving a random system of \(m\) equations in \(n\) unknowns. We show furthermore that this security reduction can be extended to incorporate the key and \(IV\) setup and provide a security argument related to the whole stream cipher. We also briefly address software and hardware performance issues and show that if one is willing to pseudo-randomly generate the sets of quadratic polynomials underlying the cipher, this leads to surprisingly inexpensive hardware implementations of QUAD.

94A60 Cryptography
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
FGb; Scream; QUAD; eSTREAM; Grain; SNOW
Full Text: DOI
[1] Arditti, D.; Berbain, C.; Billet, O.; Gilbert, H., Compact FPGA implementations of QUAD, ()
[2] Bardet, M., 2004. Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie. Ph.D. Thesis. Université Paris VI
[3] Bellare, M., 1999. The Goldreich-Levin Theorem. Available from URL: http://www-cse.ucsd.edu/users/mihir/courses.html
[4] Berbain, C., 2007. Analyse et conception d’algorithmes de chiffrement à flot. Ph.D. Thesis. Université Paris VII
[5] Berbain, C.; Billet, O.; Gilbert, H., Efficient implementations of multivariate quadratic systems, () · Zbl 1161.94385
[6] Berbain, C.; Gilbert, H., On the security of \(I V\) dependent stream ciphers, () · Zbl 1186.94423
[7] Berbain, C.; Gilbert, H.; Patarin, J., QUAD: A practical stream cipher with provable security, () · Zbl 1140.94322
[8] Blum, L.; Blum, M.; Shub, M., A simple unpredictable pseudo-random number generator, SIAM J. comput., 15, 2, 364-383, (1986) · Zbl 0602.65002
[9] Blum, M.; Micali, S., How to generate cryptographically strong sequences of pseudo-random bits, SIAM J. comput., 13, 4, 850-864, (1984) · Zbl 0547.68046
[10] Boneh, D., Halevi, S., Howgrave-Graham, N., 2001. The modular inversion hidden number problem, In: ASIACRYPT, pp. 36-51 · Zbl 1062.94545
[11] Buchberger, B., 1965. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal (An algorithm for finding the basis elements in the residue class ring modulo a zero dimensional polynomial ideal). Ph.D. Thesis. Mathematical Institute, University of Innsbruck, Austria · Zbl 1245.13020
[12] Cannière, C.D., Preneel, B., 2005. Trivium: Specifications. eSTREAM, ECRYPT Stream Cipher Project, Report 2005/001. Available at: http://www.ecrypt.eu.org/stream
[13] Courtois, N., Goubin, L., Meier, W., Tacier, J.-D., 2002. Solving underdefined systems of multivariate quadratic equations, In: Public Key Cryptography, pp. 211-227 · Zbl 1055.94534
[14] Courtois, N.; Klimov, A.; Patarin, J.; Shamir, A., Efficient algorithms for solving overdefined systems of multivariate polynomial equations, (), 392-407 · Zbl 1082.94514
[15] Courtois, N.; Patarin, J., About the XL algorithm over \(G F(2)\), (), 141-157 · Zbl 1039.94511
[16] Ekdahl, P.; Johansson, T., A new version of the stream cipher SNOW, () · Zbl 1027.68596
[17] Faugère, J.-C., A new efficient algorithm for computing Gröbner bases (F4), J. pure appl. algebra, (1999)
[18] Faugère, J.-C.; Imai, H.; Kawazoe, M.; Sugita, M.; Ars, G., Comparison between XL and Groebner basis algorithms, (), 338-353 · Zbl 1094.94024
[19] Fischer, J.-B., Stern, J., 1996. An Efficient Pseudo-random generator provably as secure as syndrome decoding, In: EUROCRYPT, pp. 245-255 · Zbl 1304.94056
[20] Fraenkel, A.S.; Yesha, Y., Complexity of solving algebraic equations, Inform. process. lett., 10, 4/5, 178-179, (1980) · Zbl 0487.68036
[21] Garey, M.R.; Johnson, D.S., Algebraic equations over \(G F(2)\), (), (Chapter 7.2)
[22] Goldreich, O., The foundations of cryptography — volume 1, (2001), Cambridge University Press
[23] Goldreich, O.; Goldwasser, S.; Micali, S., How to construct random functions, J. ACM, 33, 4, 792-807, (1986) · Zbl 0596.65002
[24] Goldreich, O.; Krawczyk, H., Sparse pseudorandom distributions, (), 113-127
[25] Goldreich, O.; Levin, L.A., A hard-core predicate for all one-way functions, (), 25-32
[26] Goldreich, O., Rubinfeld, R., Sudan, M., 1995. Learning polynomials with queries: The highly noisy case, In: FOCS, pp. 294-303 · Zbl 0938.68642
[27] Goldwasser, S., Bellare, M., 2001. Lecture Notes on Cryptography. Available at: http://www-cse.ucsd.edu/users/mihir/courses.html
[28] Halevi, S.; Coppersmith, D.; Jutla, C.S., Scream: A software-efficient stream cipher, (), 195-209 · Zbl 1045.94519
[29] Håstad, J.; Impagliazzo, R.; Levin, L.A.; Luby, M., A pseudorandom generator from any one-way function, SIAM J. comput., 28, 4, 1364-1396, (1999) · Zbl 0940.68048
[30] Håstad, J., Näslund, M., 2000. BMGL: Synchronous keystream generator with provable security (submitted to Nessie Project)
[31] Hell, M., Johansson, T., Meier, W., 2005. Grain — A stream cipher for constrained environments. ECRYPT Stream Cipher Project Report 2005/001. http://www.ecrypt.eu.org/stream
[32] Impagliazzo, R.; Naor, M., Efficient cryptographic schemes provably as secure as subset sum, J. crypt., 9, 4, 199-216, (1996) · Zbl 0862.94015
[33] Kipnis, A., Patarin, J., Goubin, L., 1999. Unbalanced oil and vinegar signature schemes. In: Stern, J. (Ed.), Advances in Cryptology — EUROCRYPT ’99, vol. 1592. Springer, pp. 206-222 · Zbl 0933.94031
[34] Lidl, R.; Niederreiter, H., Finite fields, (1997), Cambridge University Press
[35] Patarin, J., 1996. Hidden fields equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms. In: Maurer, U.M. (Ed.), Advances in Cryptology — EUROCRYPT’96, vol. 1070. Springer, pp. 33-48 · Zbl 1301.94125
[36] Patarin, J., Goubin, L., 1997. Asymmetric cryptography with S-Boxes, In: ICICS, pp. 369-380 · Zbl 0903.94032
[37] Rivest, R., The RC4 encryption algorithm, (1992), RSA Security Inc.
[38] Shamir, A., 1981. On the generation of cryptographically strong pseudo-random sequences. In: ICALP, pp. 544-550 · Zbl 0462.94017
[39] Steinfeld, R., Pieprzyk, J., Wang, H., 2006. On the provable security of an efficient RSA-based pseudorandom generator, In: ASIACRYPT, pp.194-209 · Zbl 1172.94597
[40] Yang, B.-Y.; Chen, O.C.-H.; Bernstein, D.J.; Chen, J.-M., Analysis of QUAD, ()
[41] Yao, A., 1982. Theory and applications of trapdoor function. In: Foundations of Cryptography FOCS 1982
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.