Welcome to the resource topic for 2013/436
Title:
Fast Exhaustive Search for Quadratic Systems in \mathbb{F}_2 on FPGAs — Extended Version
Authors: Charles Bouillaguet, Chen-Mou Cheng, Tung Chou, Ruben Niederhagen, 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.
ePrint: https://eprint.iacr.org/2013/436
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .