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

Abstract

零知識值域證明（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.