Article

Compact FPGA implementations of QUAD

Authors:

David Arditti,

Côme Berbain,

Olivier Billet,

Henri GilbertAuthors Info & Claims

ASIACCS '07: Proceedings of the 2nd ACM symposium on Information, computer and communications security

Pages 347 - 349

https://doi.org/10.1145/1229285.1229323

Published: 20 March 2007 Publication History

Get Access

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.

Digital Library

Google Scholar

[2]

L. Blum, M. Blum, and M. Shub. A Simple Unpredictable Pseudo-Random Number Generator. SIAM J. Comput., 15(2):364--383, 1986.

Digital Library

Google Scholar

[3]

M. Blum and S. Micali. How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits. SIAM J. Comput., 13(4):850--864, 1984.

Digital Library

Google Scholar

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

Google Scholar

[5]

ECRYPT. Web page of the eSTREAM project: http://www.ecrypt.eu.org/stream/.

Google Scholar

[6]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co, 1979.

Digital Library

Google Scholar

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

Digital Library

Google Scholar

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

Google Scholar

Cited By

View all

Elsobky AFarag AKeshk A(2016)Efficient Implementation of McEliece Cryptosystem on Graphic Processing UnitProceedings of the 10th International Conference on Informatics and Systems10.1145/2908446.2908491(247-253)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.1145/2908446.2908491
Hamlet JBrocato R(2015)Throughput-optimized implementations of QUADJournal of Cryptographic Engineering10.1007/s13389-015-0109-y5:4(245-254)Online publication date: 7-Sep-2015
https://doi.org/10.1007/s13389-015-0109-y
Tanaka SCheng CYasuda TSakurai K(2014)Parallelization of QUAD Stream Cipher Using Linear Recurring Sequences on Graphics Processing UnitsProceedings of the 2014 Second International Symposium on Computing and Networking10.1109/CANDAR.2014.85(543-548)Online publication date: 10-Dec-2014
https://dl.acm.org/doi/10.1109/CANDAR.2014.85
Show More Cited By

Index Terms

Compact FPGA implementations of QUAD

Recommendations

High Performance Single-Chip FPGA Rijndael Algorithm Implementations
CHES '01: Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems

This paper describes high performance single-chip FPGA implementations of the new Advanced Encryption Standard (AES) algorithm, Rijndael. The designs are implemented on the Virtex-E FPGA family of devices. FPGAs have proven to be very effective in ...
Rijndael FPGA Implementations Utilising Look-Up Tables

This paper presents single-chip FPGA Rijndael algorithm implementations of the Advanced Encryption Standard (AES) algorithm, Rijndael. In particular, the designs utilise look-up tables to implement the entire Rijndael Round function. A comparison is ...
Compact FPGA implementations of the five SHA-3 finalists
CARDIS'11: Proceedings of the 10th IFIP WG 8.8/11.2 international conference on Smart Card Research and Advanced Applications

Allowing good performances on different platforms is an important criteria for the selection of the future sha-3 standard. In this paper, we consider the compact implementations of blake, Grøstl, jh, Keccak and Skein on recent fpga devices. Our results ...

Comments

Information & Contributors

Information

Published In

ASIACCS '07: Proceedings of the 2nd ACM symposium on Information, computer and communications security

March 2007

323 pages

ISBN:1595935746

DOI:10.1145/1229285

Editors:
Robert Deng,
Pierangela Samarati,
General Chairs:
Feng Bao
I2R, Singapore
,
Steven Miller
SMU, Singapore

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 March 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

Asia CCS07

Sponsor:

SIGSAC

Asia CCS07: Asia CCS'07 ACM Symposium on Information, Computer and Communications Security

March 20 - 22, 2007

Singapore

Acceptance Rates

ASIACCS '07 Paper Acceptance Rate 33 of 180 submissions, 18%;

Overall Acceptance Rate 418 of 2,322 submissions, 18%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
338
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Elsobky AFarag AKeshk A(2016)Efficient Implementation of McEliece Cryptosystem on Graphic Processing UnitProceedings of the 10th International Conference on Informatics and Systems10.1145/2908446.2908491(247-253)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.1145/2908446.2908491
Hamlet JBrocato R(2015)Throughput-optimized implementations of QUADJournal of Cryptographic Engineering10.1007/s13389-015-0109-y5:4(245-254)Online publication date: 7-Sep-2015
https://doi.org/10.1007/s13389-015-0109-y
Tanaka SCheng CYasuda TSakurai K(2014)Parallelization of QUAD Stream Cipher Using Linear Recurring Sequences on Graphics Processing UnitsProceedings of the 2014 Second International Symposium on Computing and Networking10.1109/CANDAR.2014.85(543-548)Online publication date: 10-Dec-2014
https://dl.acm.org/doi/10.1109/CANDAR.2014.85
Sakumoto K(2012)Public-Key identification schemes based on multivariate cubic polynomialsProceedings of the 15th international conference on Practice and Theory in Public Key Cryptography10.1007/978-3-642-30057-8_11(172-189)Online publication date: 21-May-2012
https://dl.acm.org/doi/10.1007/978-3-642-30057-8_11
Sakumoto KShirai THiwatari H(2011)Public-key identification schemes based on multivariate quadratic polynomialsProceedings of the 31st annual conference on Advances in cryptology10.5555/2033036.2033090(706-723)Online publication date: 14-Aug-2011
https://dl.acm.org/doi/10.5555/2033036.2033090
Sakumoto KShirai THiwatari H(2011)Public-Key Identification Schemes Based on Multivariate Quadratic PolynomialsAdvances in Cryptology – CRYPTO 201110.1007/978-3-642-22792-9_40(706-723)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22792-9_40
Billet OEtrog JGilbert H(2010)Lightweight privacy preserving authentication for RFID using a stream cipherProceedings of the 17th international conference on Fast software encryption10.5555/1876089.1876095(55-74)Online publication date: 7-Feb-2010
https://dl.acm.org/doi/10.5555/1876089.1876095
Berbain CBillet OEtrog JGilbert HAl-Shaer EJha SKeromytis A(2009)An efficient forward private RFID protocolProceedings of the 16th ACM conference on Computer and communications security10.1145/1653662.1653669(43-53)Online publication date: 9-Nov-2009
https://dl.acm.org/doi/10.1145/1653662.1653669
Berbain CGilbert HPatarin J(2009)QUADJournal of Symbolic Computation10.1016/j.jsc.2008.10.00444:12(1703-1723)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1016/j.jsc.2008.10.004

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

High Performance Single-Chip FPGA Rijndael Algorithm Implementations

Rijndael FPGA Implementations Utilising Look-Up Tables

Compact FPGA implementations of the five SHA-3 finalists

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations