Details:
Title  QUAD: A multivariate stream cipher with provable security  Author(s)  Côme Berbain, Henri Gilbert, Jacques Patarin  Type  Article in Journal  Abstract  In this paper 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 Berbain and coworkers [Berbain, C., Gilbert, H., Patarin, J., 2006b. QUAD: A practical stream cipher with provable security. In: Vaudenay, S. (Ed.), Advances in Cryptology — EUROCRYPT 2006. In: Lecture Notes in Computer Science, SpringerVerlag]. 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 I V 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 pseudorandomly generate the sets of quadratic polynomials underlying the cipher, this leads to surprisingly inexpensive hardware implementations of QUAD.  Keywords  MQ problem, Stream cipher, Provable security, Gröbner basis computation  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717108001831 
Language  English  Journal  Journal of Symbolic Computation  Volume  44  Number  12  Pages  1703  1723  Year  2009  Note  Gröbner Bases in Cryptography, Coding Theory, and Algebraic Combinatorics  Edition  0  Translation 
No  Refereed 
No 
