使用FPGA實作Joux-Vitse雜交式演算法

An FPGA Aided Implementation of Joux-Vitse’s Crossbred Algorithm

林宜臻(Yi-Chen Lin)

指導教授 ： 鄭振牟

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2021年)

https://doi.org/10.6342/NTU202102222

摘要

多變量密碼學屬於後量子密碼學的其中一種。根據系統的多變數二次方程式，解出變數的值。有許多方法可以解這套系統，而其中Joux-Vitse雜交式演算法結合了XL及窮舉的方法，此演算法包含三個階段，分別是XL、窮舉及線性運算。本論文將在原有的GPU實作中加入FPGA的輔助，採用格雷碼窮舉演算法，完成窮舉及線性運算在FPGA上的實作。

關鍵字

多變數多項式系統 ； Joux-Vitse雜交式演算法 ； 格雷碼窮舉演算法 ； 後量子密碼學 ； FPGA實作

並列摘要

Multivariate cryptography is one of the approaches of post-quantum cryptography. According to the multivariate quadratic equations given by the MQ systems, solving the values of the variables. There are many approaches to solving MQ problems, and one of the methods that combines XL and exhaustive search is Joux-Vitse’s crossbred algorithm, which contains three stages, including XL, exhaustive search, and linear system solver. This paper will add the aided FPGA implementation to the original GPU implementation, and use Gray-code enumeration algorithm to complete the implementation of exhaustive search and linear system solver on FPGA.

並列關鍵字

multivariate polynomial systems ； Joux-Vitse’s crossbred algorithm ； Gray-code enumeration algorithm ； post-quantum cryptography ； FPGA implementation

參考文獻

[1] Nicolas Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir, “Efficient algorithms for solving overdefined systems of multivariate polynomial equations,” in Advances in Cryptology - EUROCRYPT 2000, 2000, pp. 392–407.

[2] Antoine Joux and Vanessa Vitse, “A crossbred algorithm for solving boolean polynomial systems,” Cryptology ePrint Archive, Report 2017/372, 2017.

[3] Ruben Niederhagen, Kai-Chun Ning, and Bo-Yin Yang, “Implementing joux-vitse’s crossbred algorithm for solving mq systems over gf(2) on gpus,” Cryptology ePrint Archive, Report 2017/1181, 2017.

[4] Charles Bouillaguet, Chen-Mou Cheng, Tony (Tung) Chou, Ruben Niederhagen, Adi Shamir, and Bo-Yin Yang, “Fast exhaustive search for polynomial systems in 𝑓2,” Cryptology ePrint Archive, Report 2010/313, 2010.

[5] Charles Bouillaguet, Chen-Mou Cheng, Tung Chou, Ruben Niederhagen, and Bo-Yin Yang, “Fast exhaustive search for quadratic systems in 𝐹2 on fpgas — extended version,” Cryptology ePrint Archive, Report 2013/436, 2013.