絡密碼學在FPGA上有效率的實作

An efficient implementation of lattice-­based cryptography on FPGA

林怡慧(Yi-Hui Lin)

指導教授 ： 鄭振牟

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

https://doi.org/10.6342/NTU201903039

摘要

由於量子電腦的迅速發展，後量子密碼學變得越來越重要，而絡密碼學是後量子密碼學中重要的演算法之一，所以我們在硬體上以有效率的方式實作了一個在絡密碼學中非常有名的演算法 ──NewHope，在這個演算法中有三個主要的部份，分別是 Key generation、Encapsulation、和 Decapsulation，Key generation 使用了 10956 個 LUTs、9822 個 FFs、18 個 BRAMs 和 16 個 DSPs，Encapsulation 使用了 14171 個 LUTs、14218 個 FFs、20 個 BRAMs 和 16 個 DSPs，Decapsulation 使用了 9103 個 LUTs、6997 個 FFs、16 個 BRAMs 和 18 個 DSPs，他們所需要的運算時間分別為 22.144 微秒、36.968 微秒，和 15.176 微秒，而我們面積和時間的乘積大約是 [4] 的 3 倍。

關鍵字

絡密碼學 ； FPGA

並列摘要

The development of quantum computers is faster and faster. Therefore, post-quantum cryptography is more and more important. Lattice-based cryptography is an important algorithm for post-quantum cryptography, so we implement NewHope, one of the famous algorithms in lattice-based cryptography, on FPGA in an efficient way. There are three main parts for NewHope. One is Key generation, another is Encapsulation, and the other is Decapsulation. The usage of LUTs is 10956, 14171, 9103, FFs is 9822, 14218, 6997, BRAMs is 18, 20, 16, and DSPs is 16, 16, 18 for Key generation, Encapsulation and Decapsulation. The timing consumption is 22.144 µs, 36.968 µs, and 15.176 µs for Key generation, Encapsulation, and Decapsulation. It is about 3 times area-time product better than [4].

並列關鍵字

Lattice-­based cryptography ； FPGA

參考文獻

[1] Alkim, Erdem, et al. “Post-quantum key exchange—a new hope.” 25th Security Symposium (Security 16). 2016.

[2] Alkim, Erdem, et al. “Algorithm Specifications and Supporting Documentation.”

[3] Oder, Tobias, and Tim Güneysu. “Implementing the NewHope-­Simple key exchange on low­-cost FPGAs.” Progress in Cryptology–LATINCRYPT 2017 (2017).

[4] Kuo, Po-­Chun, et al. High performance post­-quantum key exchange on FPGAs. Cryptology ePrint Archive, Report 2017/690.(2017). https://eprint.iacr.org/2017/690, 2017.

[5] Dworkin, Morris J. SHA-­3 standard: Permutation-­based hash and extendable-output functions. No. Federal Inf. Process. Stds.(NIST FIPS)-­202. 2015.