Key sizes 80 bits | ||
Designers Côme Berbain, Henri Gilbert and Jacques Patarin First published May 28, 2006 (at Eurocrypt) Structure multivariate system of quadratic equations | ||
In cryptography, the QUAD, cipher is a relatively new stream cipher, which was designed with provable security arguments in mind.
Contents
Description
QUAD relies on the iteration of a randomly chosen multivariate quadratic system S=(Q1, ..., Qm) of m=kn equations in n unknowns over a finite field GF(q). The keystream generation process simply consists in iterating the three following steps in order to produce (k -1) n GF(q) keystream values at each iteration.
QUAD is a modern stream cipher, i.e. it uses a key and an initialisation value (IV) to produce a keystream sequence. A Key and IV setup is also defined which also rely on multivariate quadratic system.
Security
The security of the keystream generation of QUAD is provably reducible to the conjectured intractability of the MQ problem, namely solving a multivariate system of quadratic equations. The first proof was done over field GF(2) for an old-fashioned stream cipher (where the key is the initial state). It was later extended by Berbain and Gilbert in order to take into account the set-up procedure of a modern cipher (with a setup stage deriving the initial state from the key). The security of the whole cipher as a Pseudo Random Function can be related to the conjectured intractability of the MQ problem. The authors also studied the resistance of the cipher against classical attacks.
Parameters recommended
The authors recommend to use a version of QUAD with an 80-bit key, 80-bit IV and an internal state of n = 160 bits. It outputs 160 keystream bits (m = 320) at each iteration until 240 bits of keystream have been produced.
At Eurocrypt 2006, speed reports were presented for QUAD instances with 160-bit state and output block over the fields GF(2), GF(16), and GF(256). These speed reports were part of an analysis of "Efficient Implementations of Multivariate Quadratic Systems" which was published by Berbain, Billet, and Gilbert at SAC 2006. This analysis (which also covers several multivariate public-key schemes as well as the QUAD stream cipher) studied in part the impact of changing the size of the field on the performances without considering the security aspect.
Discussion on parameters
The initial security theorem for QUAD is valid for the field GF(2) only, and recommended parameters does not achieve to get a contradiction with the proof of security. The authors of QUAD who gave the security theorem acknowledged that a break of QUAD at their suggested parameters does not contradict the proof-of-security theorems when they proposed the scheme at Eurocrypt 2006. However it seemed that the authors had considered them as sufficient to provide the desired security level of about 280.
Yang, Chen, Bernstein and Chen studied the security of the different parameter sets in the document "Analysis of Quad" and found some of them very insecure. Their paper discusses both theoretical and practical aspects of attacking QUAD and of attacking the underlying hard problem. For example, this paper shows how to use XL-Wiedemann to break the GF(256) instance QUAD (256, 20, 20) in approximately 266 Opteron cycles, and to break the underlying hard problem in approximately 245 cycles, which was carried out successfully. However, according to this paper, it would take about 2110 to solve an instance of the QUAD(2,160,160) version recommended by the authors of QUAD using XL-Wiedemann.
The study by Yang et al. highlighted the fact that security theorems often rely on reductions with a looseness factor, and when this is taken into account, none of the parameter sets of the suggested versions are sufficient for the proof of security. An instance that will be provably secure would be QUAD(2,320,320), that is, twice as wide as originally proposed.
A security theorem can also be proved for GF(q), albeit with a larger looseness factor; this and extensions of QUAD for more efficient implementations is proposed by Liu et al. (see reference "Secure PRNGs from Specialized Polynomial Maps over Any Fq").