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

謝辭·····i
摘要·····ii
Abstract·····iii
CONTENTS·····iv
LIST OF FIGURES·····vi
LIST OF TABLES·····vii
1 Introduction ·····1
1.1 Background ·····1
1.2 Motivation·····2
1.3 Contributions·····2
1.4 Organization·····3
2 Preliminaries·····5
2.1 Notations·····5
2.2 Hardness Assumptions·····6
2.3 Elliptic-curve Pedersen Commitment Scheme·····6
2.4 Elliptic-curve Diffie–Hellman Key Exchange (ECDH)·····8
2.5 Trapdoor Commitment Scheme·····9
2.6 Elliptic-curve EL Proof·····11
2.6.1 Definitions and Security Models·····11
2.6.2 EC-EL Proof Protocol·····13
2.6.3 Security Descriptions·····14
2.7 Elliptic-curve SQR Proof·····18
2.7.1 Definitions and Security Models·····19
2.7.2 EC-SQR Proof Protocol·····21
2.7.3 Security Descriptions·····22
2.8 Zero-Knowledge Proof with Commitment Secret (ZKPCS)·····24
3 Non-Interactive EC-ZKRP Scheme·····27
3.1 Definitions and Security Models·····27
3.2 Non-Interactive EC-ZKRP Protocol·····28
3.3 Security Descriptions·····33
3.3.1 Correctness·····33
3.3.2 Soundness·····34
3.3.3 Zero-knowledge·····36
4 Non-Interactive Designated Verifier EC-ZKRP Protocol·····41
4.1 Designated Verifier EC-ZKRP Scheme·····41
4.1.1 Definitions and Security Models·····41
4.1.2 Designated Verifier EC-ZKRP Protocol·····43
4.1.3 Security Description: Designated Verifier·····45
4.2 Strong Designated Verifier EC-ZKRP Scheme·····49
4.2.1 Definitions and Security Models·····49
4.2.2 Strong Designated Verifier EC-ZKRP Protocol·····51
4.2.3 Security Description: Strong Designated Verifier·····53
5 Efficiency Analysis·····57
6 Application Scenarios·····60
7 Conclusions·····62
Reference·····63

[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.
[6] R. Chaabouni, H. Lipmaa, and B. Zhang. A non-interactive range proof with constant communication. In Financial Cryptography and Data Security, A. D. Keromytis, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, pages 179–199. 2012.
[7] P. Chaidos, and G. Couteau. Efficient designated-verifier non-interactive zeroknowledge proofs of knowledge. In Annual International Conference on the Theory and Applications of Cryptographic Techniques pages 193–221. Springer, Cham, April, 2018.
[8] F. Christian and G. Johann. Efficient Implementation of Pedersen Commitments Using Twisted Edwards Curves. In Mobile, Secure, and Programmable Networking - Third International Conference, MSPN 2017, pages 1–17, 2017.
[9] E. Fujisaki and T. Okamoto. Statistical zero knowledge protocols to prove modular polynomial relations. In Annual International Cryptology Conference, pages 16– 30. Springer, 1997.
[10] P. Gallagher. Digital signature standard (DSS). In Federal Information Processing Standards Publications, volume FIPS, 186, 2013.
[11] O. Goldreich, Y. Oren. Definitions and properties of zero-knowledge proof systems. In J. Cryptology 7, pages 1–32, 1994.
[12] D. Hankerson, A. Menezes. Elliptic Curve Discrete Logarithm Problem. In van Tilborg H.C.A., Jajodia S. (eds) Encyclopedia of Cryptography and Security, 2011.
[13] M. Jakobsson, K. Sako, R. Impagliazzo. Designated Verifier Proofs and their 64 Applications. In Eurocrypt’96, Springer LNCS Vol. 1070, pages 142–154, 1996.
[14] S. Katsumata, R. Nishimaki, S. Yamada, and T. Yamakawa. Designated verifier/prover and preprocessing NIZKs from Diffie-Hellman assumptions. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 622–651. Springer, Cham, May, 2019.
[15] T. Koens, C. Ramaekers and C. van Wijk. Efficient Zero-Knowledge Range Proofs in Ethereum. In ING media.
[16] A. Kosba, A. Miller, E. Shi, Z. Wen, and C. Papamanthou. Hawk: The blockchain model of cryptography and privacy-preserving smart contracts. In 2016 IEEE symposium on security and privacy (SP), pages 839–858, 2016.
[17] B. Libert, A. Passelègue, H. Wee, and D. Wu. New constructions of statistical NIZKs: dual-mode DV-NIZKs and more. In Eurocrypt 2020-39th Annual International Conference on the Theory and Applications of Cryptographic Techniques. May, 2020.
[18] H. Lipmaa. On diophantine complexity and statistical zero-knowledge arguments. In International Conference on the Theory and Application of Cryptology and Information Security, pages 398–415, Springer, 2003.
[19] P. McCorry, S. Shahandashti, and F. Hao. A smart contract for boardroom voting with maximum voter privacy. In International Conference on Financial Cryptography and Data Security, pages 357–375. Springer, 2017.
[20] I. Miers, C. Garman, M. Green, and A. D. Rubin. Zerocoin: Anonymous distributed e-cash from bitcoin. In 2013 IEEE Symposium on Security and Privacy, pages 397–411, IEEE, May, 2013.
[21] E. Morais, T. Koens, C. Wijk, and A. Koren. A survey on zero knowledge range proofs and applications. In Nature Switzerland AG 2019, Springer, 2019.
[22] S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system. In Decentralized Business Review, 2008.
[23] T. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In CRYPTO, volume 576 of Lecture Notes in Computer Science, pages 129–140, 1991.
[24] K. Peng and F. Bao. Batch range proof for practical small ranges. In International Conference on Cryptology in Africa, pages 114–130, Springer, 2010.
[25] M. Qu. Sec 2: Recommended elliptic curve domain parameters. In Certicom Res., Mississauga, ON, Canada, Tech. Rep. SEC2-Ver-0.6, 1999.
[26] R. Schoof. Elliptic Curves over Finite Fields and the Computation of Square Roots mod p. In Mathematics of Computation Vol. 44, No. 170, pages 483–494, April, 1985.
[27] N. Van Saberhagen. CryptoNote v 2.0, 2013. 65
[28] Y. Tsai, R. Tso, Z. Liu, and K. Chen. An improved non-interactive zero-knowledge range proof for decentralized applications. In 2019 IEEE International Conference on Decentralized Applications and Infrastructures (DAPPCON), pages 129–134, April 2019.
[29] Y. Wang and A. Kogan. Designing confidentiality-preserving blockchain-based transaction processing systems. In International Journal of Accounting Information Systems, vol. 30, pages 1–18, 2018.
[30] L. Xu, N. Shah, L. Chen, N. Diallo, Z. Gao, Y. Lu, and W. Shi. Enabling the sharing economy: Privacy respecting contract based on public blockchain. In Proceedings of the ACM Workshop on Blockchain, Cryptocurrencies and Contracts, pages 15– 21, 2017.