cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...

, the QUAD, cipher is a relatively new

stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream ( keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...

, 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. 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 In cryptography, security level is a measure of the strength that a cryptographic primitive — such as a cipher or hash function — achieves. Security level is usually expressed as a number of "bits of security" (also security strength ...

of about 2⁸⁰. 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 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. 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 F_q").

References

* * * * * * {{Cryptography navbox , stream Stream ciphers Multivariate cryptography