When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-10155
Go to the corresponding Portal

Arditti, David ; Berbain, Cme ; Billet, Olivier ; Gilbert, Henri ; Patarin, Jacques

QUAD: Overview and Recent Developments

07021.GilbertHenri.Paper.1015.pdf (0.3 MB)


We give an outline of the specification and provable security features of the QUAD stream cipher proposed at Eurocrypt 2006. The cipher relies on the iteration of a multivariate system of quadratic equations over a finite field, typically GF(2) or a small extension. In the binary case, the security of the keystream generation can be related, in the concrete security model, to the conjectured intractability of the MQ problem of solving a random system of m equations in n unknowns. We show that this security reduction can be extended to incorporate the key and IV setup and provide a security argument related to the whole stream cipher.We also briefly address software and hardware performance issues and show that if one is willing to pseudorandomly generate the systems of quadratic polynomials underlying the cipher, this leads to suprisingly inexpensive hardware implementations of QUAD.

BibTeX - Entry

  author =	{David Arditti and C{\^o}me Berbain and Olivier Billet and Henri Gilbert and Jacques Patarin},
  title =	{QUAD: Overview and Recent Developments},
  booktitle =	{Symmetric Cryptography},
  year =	{2007},
  editor =	{Eli Biham and Helena Handschuh and Stefan Lucks and Vincent Rijmen},
  number =	{07021},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: MQ problem, stream cipher, provable security, Gr{\"o}bner basis}

Keywords: MQ problem, stream cipher, provable security, Gröbner basis
Seminar: 07021 - Symmetric Cryptography
Issue Date: 2007
Date of publication: 06.06.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI