TY - GEN
T1 - Fast exhaustive search for quadratic systems in double-struck F2 on FPGAs
AU - Bouillaguet, Charles
AU - Cheng, Chen Mou
AU - Chou, Tung
AU - Niederhagen, Ruben
AU - Yang, Bo Yin
PY - 2014
Y1 - 2014
N2 - In 2010, Bouillaguet et al. proposed an efficient solver for polynomial systems over double-struck 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 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 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 significant improvement, not to mention that the monetary cost per unit of computational power for FPGAs is generally much cheaper than that of GPUs.
AB - In 2010, Bouillaguet et al. proposed an efficient solver for polynomial systems over double-struck 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 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 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 significant improvement, not to mention that the monetary cost per unit of computational power for FPGAs is generally much cheaper than that of GPUs.
KW - Exhaustive search
KW - Field-Programmable Gate Arrays (FPGAs)
KW - Multivariate quadratic polynomials
KW - Parallelization
KW - Solving systems of equations
UR - https://www.scopus.com/pages/publications/84902603142
U2 - 10.1007/978-3-662-43414-7_11
DO - 10.1007/978-3-662-43414-7_11
M3 - 会议稿件
AN - SCOPUS:84902603142
SN - 9783662434130
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 205
EP - 222
BT - Selected Areas in Cryptography, SAC 2013 - 20th International Conference, Revised Selected Papers
PB - Springer Verlag
T2 - 20th International Conference on Selected Areas in Cryptography, SAC 2013
Y2 - 14 August 2013 through 16 August 2013
ER -