QUAD (cipher)

QUAD
General
Designers	Côme Berbain, Henri Gilbert and Jacques Patarin
First published	May 28, 2006 (at Eurocrypt)
Cipher detail
Key sizes	80 bits
Structure	multivariate system of quadratic equations

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

Description

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.

Compute the kn-tuple of GF(q) values S(x) = (Q₁(x),..., Q_kn(x)) where x is the current value of the internal state;
Output the sequence (Q_n+1(x),..., Q_kn(x)) of (k-1)n GF(q) keystream values
Update the internal state x with the sequence of n GF(q) first generated values (Q₁(x),..., Q_n(x))

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 2⁴⁰ bits of keystream have been produced.^[1]

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.^[2] 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.^[2]

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

Yang, Chen, Bernstein and Chen studied the security of the different parameter sets and found some of them very insecure.^[3] 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.

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.^[3]

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.^[4]

References

^ Côme Berbain; Henri Gilbert; Jacques Patarin. QUAD: A Practical Stream Cipher with Provable Security (PDF). Annual International Conference on the Theory and Applications of Cryptographic Techniques - EUROCRYPT 2006.
^ ^a ^b Côme Berbain; Olivier Billet; Henri Gilbert. Efficient Implementations of Multivariate Quadratic Systems (PDF). International Workshop on Selected Areas in Cryptography - SAC 2006. doi:10.1007/978-3-540-74462-7_13. Retrieved 2008-03-18.
^ ^a ^b Bo-Yin Yang; Owen Chia-Hsin Chen; Daniel J. Bernstein; Jiun-Ming Chen (2007-03-03). Analysis of QUAD (PDF). Fast software encryption: 14th international workshop, FSE 2007. Retrieved 2008-02-05.
^ Michael Feng-Hao Liu; Chi-Jen Lu; Bo-Yin Yang; Jintai Ding (October 23, 2007). Secure PRNGs from Specialized Polynomial Maps over Any F_q (PDF). International Workshop on Post-Quantum Cryptography - PQCrypto 2008.

Côme Berbain; Henri Gilbert. On the Security of IV Dependent Stream Ciphers (PDF). International Workshop on Fast Software Encryption 2007.
Jean-Philippe Aumasson; Willi Meier. Analysis of Multivariate Hash Functions (PDF). 10th International Conference on Information Security and Cryptology.