QUAD (cipher)

In cryptography, the QUAD cipher is a stream cipher which was designed with provable security arguments in mind.

QUAD relies on the iteration of a randomly chosen multivariate quadratic system S=(Q₁, ..., Q_m) 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.

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.

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 2⁴⁰ 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.

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 2⁸⁰.

Yang, Chen, Bernstein and Chen studied the security of the different parameter sets 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 2⁶⁶ Opteron cycles, and to break the underlying hard problem in approximately 2⁴⁵ cycles, which was carried out successfully. However, according to this paper, it would take about 2¹¹⁰ to solve an instance of the QUAD(2,160,160) version recommended by the authors of QUAD using XL-Wiedemann.