Paper 2013/436

Fast Exhaustive Search for Quadratic Systems in $\mathbb{F}_2$ on FPGAs --- Extended Version

Charles Bouillaguet, Chen-Mou Cheng, Tung Chou, Ruben Niederhagen, and Bo-Yin Yang

Abstract

In 2010, Bouillaguet et al. proposed an efficient solver for polynomial systems over $\mathbb{F}_2$ that trades memory for speed. As a result, 48 quadratic equations in 48 variables can be solved on a graphics card (GPU) in 21 minutes. The research question that we would like to answer in this paper is how specifically designed hardware performs on this task. We approach the answer by solving multivariate quadratic systems on reconfigurable hardware, namely Field-Programmable Gate Arrays (FPGAs). We show that, although the algorithm proposed by Bouillaguet et al. 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 25 times less energy than their GPU implementation. This is a significant improvement, not to mention that the monetary cost per unit of computational power for FPGAs is generally much cheaper than that of GPUs.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. SAC 2013 (in co-operation with IACR), proceedings published by Springer in the Lecture Notes in Computer Science series
Keywords
multivariate quadratic polynomialssolving systems of equationsexhaustive searchparallelizationField-Programmable Gate Arrays (FPGAs)
Contact author(s)
ruben @ polycephaly org
History
2013-07-17: received
Short URL
https://ia.cr/2013/436
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/436,
      author = {Charles Bouillaguet and Chen-Mou Cheng and Tung Chou and Ruben Niederhagen and Bo-Yin Yang},
      title = {Fast Exhaustive Search for Quadratic Systems in $\mathbb{F}_2$ on {FPGAs} --- Extended Version},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/436},
      year = {2013},
      url = {https://eprint.iacr.org/2013/436}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.