Paper 2013/263

Speeding up QUAD

Albrecht Petzoldt

Abstract

QUAD is a provable secure stream cipher based on multivariate polynomials which was proposed in 2006 by Berbain, Gilbert and Patarin \cite{BG06}. In this paper we show how to speed up QUAD over GF(256) by a factor of up to 5.8. We get this by using structured systems of polynomials, in particular partially circulant polynomials and polynomials generated by a linear recurring sequence (LRS), instead of random ones. By using this strategy, we can also reduce the system parameter of QUAD by about 99 \verb!%!. We furthermore present experiments, which seem to show that using structured polynomials of this special choice does not influence the security of QUAD.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. no published elsewhere
Keywords
Multivariate CryptographyQUAD Stream CipherPartially Circulant PolynomialsLinear Recurring Sequences
Contact author(s)
apetzoldt @ cdc informatik tu-darmstadt de
History
2013-05-13: received
Short URL
https://ia.cr/2013/263
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/263,
      author = {Albrecht Petzoldt},
      title = {Speeding up QUAD},
      howpublished = {Cryptology ePrint Archive, Paper 2013/263},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/263}},
      url = {https://eprint.iacr.org/2013/263}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.