Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Multivariate Cryptography, QUAD Stream Cipher, Partially Circulant Polynomials, Linear Recurring Sequences

Publication Info: no published elsewhere

Date: received 8 May 2013

Contact author: apetzoldt at cdc informatik tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20130513:115913 (All versions of this report)

Short URL: ia.cr/2013/263

Discussion forum: Show discussion | Start new discussion