Fast exhaustive search for quadratic systems in F_2 on FPGAs

C. Bouillaguet, C.M. Cheng, T. Chou, R.F. Niederhagen, B.Y. Yang

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)


In 2010, Bouillaguet et al. proposed an e¿cient solver for polynomial systems over F2 that trades memory for speed [BCC+10]. As a result, 48 quadratic equations in 48 variables can be solved on a graphics processing unit (GPU) in 21 min. The research question that we would like to answer in this paper is how speci¿cally designed hardware performs on this task. We approach the answer by solving multivariate quadratic systems on recon¿gurable hardware, namely Field-Programmable Gate Arrays (FPGAs). We show that, although the algorithm proposed in [BCC+10] has a better asymptotic time complexity than traditional enumeration algorithms, it does not have a better asymptotic complexity in terms of silicon area. Nevertheless, our FPGA implementation consumes 20–25 times less energy than its GPU counterpart. This is a signi¿cant improvement, not to mention that the monetary cost per unit of computational power for FPGAs is generally much cheaper than that of GPUs.
Original languageEnglish
Title of host publicationSelected Areas in Cryptography - SAC 2013 (20th International Conference, Burnaby BC, Canada, August 14-16, 2013. Revised Selected Papers)
EditorsT. Lange, K. Lauter, P. Lisonek
Place of PublicationBerlin
ISBN (Print)978-3-662-43413-0
Publication statusPublished - 2014
Event20th International Conference on Selected Areas in Cryptography (SAC 2013) - Burnaby, Canada
Duration: 14 Aug 201316 Aug 2013
Conference number: 20

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference20th International Conference on Selected Areas in Cryptography (SAC 2013)
Abbreviated titleSAC 2013


Dive into the research topics of 'Fast exhaustive search for quadratic systems in F_2 on FPGAs'. Together they form a unique fingerprint.

Cite this