Stream Cipher Designs Based on NP-hard Problems

In public key cryptography, the general idea is to design ciphers based difficult problems that take very long time to solve. These systems utilize a private and a public key, where the public key is used to encrypt messages and the private key is used for decryption. The security of these cryptosystems is based on the fact that the private key can be computed from the public key only by solving a NP-hard problem. As examples, RSA and Rabin cryptosystems based on integer factorization, and Diffie-Hellman, ElGamal systems based on discrete logarithm problem can be given.

The same idea may be used to design stream ciphers. However, generating fast stream ciphers using this approach is a challenge. The cipher QUAD, introduced by Berbain et al. is based on the iteration of multivariate quadratic system of m equations and n100) when the quadratic equations are random.

QUAD uses three fixed and publicly known multivariate system of quadratic equations, S, S_0 and S_1. S=(Q_1,\ldots,Q_{kn}) consists of kn randomly chosen equations with n variables over GF(q). S_0 and S_1 are smaller systems with n equations and $ variables. These two systems are only used during the initialization of the cipher where the internal state (x_1,\ldots,x_n), n-tuple of GF(q) values, is generated using key and IV.

Keystream generation phase of QUAD is iterative and in each iteration
the following steps are performed;

Compute S(x)=(Q_1(x),\ldots,Q_{kn}(x)) where x is the current internal state,
Output (Q_{n}(x),\ldots,Q_{kn}(x)),
Update the internal state as x=(Q_{1}(x),\ldots,Q_{n}(x)).

Analysis of different instances of QUAD(q,n,r) are given in the FSE 2007 paper by Yang et al., where q is the field size, n is the number of variables and r is the number of outputs per round. In particular, the instance of QUAD(256,20,20) is broken using XL-Wiedemann in approximately 2^{66} cycles.