Secure PRNGs from Specialized Polynomial Maps over Any F q .
Feng-Hao Liu, Chi-Jen Lu, Bo‐Yin Yang, Jíntai Ding · 2007
Abstract. Berbain, Gilbert, and Patarin presented QUAD, a pseudo random number generator (PRNG) at Eurocrypt 2006. QUAD (as PRNG and stream cipher) may be proved secure based on an interesting hardness assumption about the one-wayness of multivariate quadratic polynomial systems over F2. The original BGP proof only worked for F2 and left a gap to general Fq. We show that the result can be generalized to any arbitrary finite field Fq, and thus produces a stream cipher with alphabets in Fq. Further, we generalize the underlying hardness assumption to specialized systems in Fq (including F2) that can be evaluated more efficiently. Barring breakthroughs in the current state-of-the-art for system-solving, a rough implementation of a provably secure instance of our new PRNG is twice as fast and takes 1/10 the storage of an instance of QUAD with the same level of provable security. Recent results on specialization on security are also examined. And we conclude that our ideas are consistent with these new developments and complement them. This gives a clue that we may build secure primitives based on specialized polynomial maps which are more efficient.