基於橢圓曲線之非互動及指定驗證者零知識值域證明

Non-Interactive and Designated Verifier Zero-Knowledge Range Proof Based on Elliptic Curve

陳庭軒(Chen Ting-Hsuan)

指導教授 ： 左瑞麟

國立政治大學/理學院/資訊科學系/碩士(2021年)

https://doi.org/10.6814/NCCU202101402

摘要

零知識值域證明（zero-knowledge range proof，ZKRP）是一種特殊的零知識 證明（zero-knowledge proof，ZKP），此種證明可以使得證明者（prover）說服驗 證者（verifier），一個特定的秘密數值介於某一個範圍內，但不會洩漏該秘密數 值，即驗證者無法得知此秘密數值實際之大小。本篇提出了一種有效率的非交互 式零知識值域證明方案。透過橢圓曲線的應用，本篇方案在相同等級的安全強度 下具有較短的執行時間、較小的金鑰長度和較小的證明大小，若將本篇 ZKRP 方 案應用至區塊鏈，可降低區塊鏈上加密貨幣的交易成本。此外，本篇基於原先的 零知識值域證明方案提出了一種指定驗證者（designated verifier）的零知識值域 證明方案和另一種強指定驗證者（strong designated verifier）的零知識值域證明方 案，此兩種方案在產生證明的過程中不需額外增加任何的計算步驟。其中，指定 驗證者的方案僅被指定的驗證者能夠驗證此種方案產生的證明，且該驗證者無法 說服任何第三方驗證之結果；而強指定驗證者的方案則是可以令任何第三方皆無 法驗證此種方案產生的證明。上述的零知識值域證明方案皆可靈活運用，換言之， 可以根據秘密值的機密性來選擇合適的方案。另外，本篇提出的方案協定亦通過 嚴謹且完整的安全性證明，不失其應有的安全性。

關鍵字

區塊鏈 ； 零知識值域證明 ； 橢圓曲線 ； 承諾方案 ； 指定驗證者證明

並列摘要

Zero-knowledge range proof (ZKRP) is a kind of particular zero-knowledge proof which allows a prover to convince a verifier that a secret value is in a specified range without revealing the actual value. In this thesis, we propose an efficient non-interactive ZKRP scheme based on elliptic curve. By applying the elliptic curve, our scheme has a shorter execution time, a smaller key size and a smaller proof size at the same level of the security strength compared to existing ZKRP schemes. If we apply our ZKRP scheme to the blockchain, the transaction cost of the cryptocurrency on the blockchain can be reduced. In addition, we propose a designated verifier ZKRP scheme and a strong designated verifier ZKRP scheme based on original ZKRP scheme without adding any extra computation steps during producing proofs. The designated verifier ZKRP scheme allows the only designated verifier to be able to verify the proof, and the verifier cannot convince any other third party of the verification result; the strong designated verifier ZKRP scheme makes any third party cannot verify the proof. Besides, these ZKRP schemes can be optional and flexible: we can choose a suitable scheme to produce a ZKRP proof according to the confidentiality of the secret value. Furthermore, we argue the security proofs of our schemes completely and rigorously so that our schemes can satisfy necessary security properties.

並列關鍵字

Blockchain ； Zero-knowledge range proof ； Elliptic curve ； Commitment scheme ； Designated verifier proof

參考文獻

[1] F. Boudot. Efficient proofs that a committed number lies in an interval. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 431–444. Springer, 2000.

[2] V. Buterin. Ethereum white paper. In GitHub repository, 2013.

[3] B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell. Bulletproofs: Efficient range proofs for confidential transactions. Technical report, Cryptology ePrint Archive, Report 2017/1066, 2017. https://eprint. iacr. org/2017/1066, 2017.

[4] E. Barker, W. Barker, W. Burr, W. Polk, and M. Smid. Recommendation for key management part 1: General (revision 3). In NIST Special Publication 800-57, pages 1–147. July, 2012.

[5] E. Barker, D. Johnson, and M. Smid. Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography. In Special Publication 800-56A, National Institute of Standards and Technology, Gaithersburg, MD, March, 2007.