QUAD (cipher) - Discussion On Parameters

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 280.

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 266 Opteron cycles, and to break the underlying hard problem in approximately 245 cycles, which was carried out successfully. However, according to this paper, it would take about 2110 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 not sufficient to get a contradiction with 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").