後量子區塊鏈雜湊數位簽章之研究

A Study on Hash-Based Signatures in Post-Quantum Block Chains

蕭世謙(Alexander Chane Shiau)

指導教授 ： 鄭振牟

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

https://doi.org/10.6342/NTU202003813

摘要

橢圓曲線數位簽章是目前區塊鏈和密碼學貨幣上最廣為使用的數位簽章。然而，隨著大型量子計算機的發展，在不久的將來有必要轉換到後量子數位簽章。在一干可能抗量子的演算法中，乍看之下，雜湊函數數位簽章由於其簽章較大，似乎並不適合在區塊鏈上使用，然而雜湊函數數位簽章擁有很高的安全保證，並且對其安全性文獻上也已有充分的研究和理解。因此，我們在本研究中將重點放在雜湊函數數位簽章上。在本文中，我們首先討論了雜湊函數數位簽章直接使用於後量子區塊鏈時的某些缺點，然後提出了一個二階段的新方法，該方法使用雜湊函數一次性簽章對每次的交易進行簽章，但是需要修改區塊鏈協議。第一階段中我們以依序廣播一系列「空無交易」來替代傳統的交易廣播，直到某位礦工成功地將交易放到區塊鏈上為止。第二階段中我們提出一個將系列「空無交易」壓縮成只有兩個交易的方法以降低儲存需求和未來所需的的驗証時間。

關鍵字

區塊鏈 ； 後量子密碼學 ； 一次性簽章 ； 雜湊函數數位簽章 ； 比特幣

並列摘要

Elliptic curve signature schemes are currently still widely used in block chains and crypto-currency; however, with the advent of large-scale quantum computers, it would be necessary to switch to post-quantum signature schemes in the near future. Among potential candidates for quantum resistant algorithms, hash-based signatures at first glance may seem relatively unsuitable for use in block chains due to their large signature size, and yet they boast high security guarantees and their security is well studied and understood. With these advantages, we focus on hash-based signatures in this study. In this thesis, we first discuss certain drawbacks of hash-based signatures when used as they are in post-quantum block chains and then propose a two-stage approach that uses a hash-based one-time signature (OTS) scheme to sign a transaction but requires modifying the block chain protocol. In the first stage, we replace the conventional transaction broadcast by broadcasting a series of "null transaction lists" sequentially until the broadcasted transaction has been successfully added to the block chain by a miner. We further propose compressing the final null transaction list to a list of only two transactions in the second stage to reduce the overhead of the storage requirement and future verification time.

並列關鍵字

Block Chain ； Post-Quantum Cryptography ； One-Time Signature ； Hash-based Signature ； Bitcoin

參考文獻

[1] S. Nakamoto et al., “Bitcoin: A peer-to-­peer electronic cash system.(2008),” 2008.

[2] P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994, pp. 124–134.

[3] A. Kuznetsov, I. Svatovskij, N. Kiyan, and A. Pushkar’ov, “Code-based public­key cryptosystems for the post-quantum period,” in 2017 4th International ScientificPractical Conference Problems of Infocommunications. Science and Technology (PIC S T). IEEE, 2017, pp. 125–130.

[4] O. Regev, “New lattice-based cryptographic constructions,” Journal of the ACM (JACM), vol. 51, no. 6, pp. 899–942, 2004.

[5] O. Regev, “Quantum computation and lattice problems,” SIAM Journal on Computing, vol. 33, no. 3, pp. 738–760, 2004.