Compact FPGA implementations of QUAD

ABSTRACT

QUAD [1] is a stream cipher whose provable security relies on the hardness of solving systems of multivariate quadratic equations. This paper explores FPGA implementations of this stream cipher and, more specifically, small area ones. The smallest of our implementations of QUAD requires only 85 slices (2961 GE) on a Virtex 4 Xilinx FPGA, which makes it not only the smallest provably secure stream cipher, but also a very good competitor among conventional stream ciphers: this implementation of QUAD's underlying PRNG results in a 68% improvement over the smallest known AES implementation on FPGA [4].

REFERENCES

• 1: C. Berbain, H. Gilbert, and J. Patarin. QUAD: A Practical Stream Cipher with Provable Security. In S. Vaudenay, editor, Advances in Cryptology -- EUROCRYPT 2006, Lecture Notes in Computer Science. Springer-Verlag, 2006.
• 2: L Blum , M Blum , M Shub, A simple unpredictable pseudo random number generator, SIAM Journal on Computing, v.15 n.2, p.364-383, May 1986 [doi>10.1137/0215025]
• 3: Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
• 4: P. Chodowiec and K. Gaj. Very Compact FPGA Implementation of the AES Algorithm. In C. D. Walter, Çetin Kaya Koç, and C. Paar, editors, Cryptographic Hardware and Embedded Systems -- CHES 2003, volume 2779 of Lecture Notes in Computer Science, pages 319--333. Springer, 2003.
• 5: ECRYPT. Web page of the eSTREAM project: http://www.ecrypt.eu.org/stream/.
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: T. Good and M. Benaissa. Aes on fpga from the fastest to the smallest. In J. R. Rao and B. Sunar, editors, Cryptographic Hardware and Embedded Systems -- CHES 2005, volume 3659 of Lecture Notes in Computer Science, pages 427--440. Springer, 2005.
• 8: T. Good, W. Chelton, and M. Benaissa. Review of Stream Cipher Candidates from a Low Resource Hardware Perspective. Stream Ciphers Revisited -- SASC 2006, Workshop record, 2006.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

  E. Data
  E.4 CODING AND INFORMATION THEORY

General Terms:
Security