Basic Search / Detailed Display

Author: 秦昊
Chin, Hao
Thesis Title: 可驗證零知識範圍證明
Authenticated Zero­-Knowledge Range Proof
Advisor: 紀博文
Chi, Po-Wen
Committee: 王銘宏
Wang, Ming-Hung
莊允心
Chuang, Yun-Hsin
Approval Date: 2021/07/30
Degree: 碩士
Master
Department: 資訊工程學系
Department of Computer Science and Information Engineering
Thesis Publication Year: 2021
Academic Year: 109
Language: 英文
Number of pages: 56
Keywords (in Chinese): 零知識證明已認證證明範圍證明
Keywords (in English): Zero­-Knowledge Proof, Authenticated Proof, Range Proof
Research Methods: 主題分析比較研究
DOI URL: http://doi.org/10.6345/NTNU202101078
Thesis Type: Academic thesis/ dissertation
Reference times: Clicks: 79Downloads: 34
Share:
School Collection Retrieve National Library Collection Retrieve Error Report
  • 零知識範圍證明是個很好用的基礎密碼學演算法。零知識範圍證明可以被用 來證明某些想要隱藏的機密在特別的範圍區間之中然而不會洩漏任何跟想要隱藏 的機密有關的資訊,但是剛剛提到的特別的範圍區間是公開資訊,這是一個頗嚴 重的問題,任何人都可以很輕鬆地選一個在範圍區間內的數字並且宣稱此數字是 屬於使用者本身的機密,因為零知識的特性,沒有任何人可以質疑零知識證明的 機密的真偽。為了解決這個嚴重的問題,我們整合零知識證明和簽章演算法,在 證明者產生證明之前,必須先請第三方可信任團體進行和機密相關的簽章,之後 驗證者在驗證零知識範圍證明之前,可以先驗證此簽章是否為證明者本人。我們 堅信著可驗證零知識範圍證明一定會對之後的應用非常的有所幫助。

    Zero-Knowledge range proof is a useful cryptographic primitive. It can be used to show some secret lies in a specific range without leaking the secret itself. The problem is that the range is public information. Everyone can easily pick a number in the range and claim that the number belongs to the user. Because of the zero-knowledge property, no one can challenge the proof generated from a fake number. To solve this problem, we integrate a signature service with the zero-knowledge proof protocol. Before a prover generates a proof, a trusted-third party needs to create some authenticated primitives, which are related to the message, for the proof generation. So a verifier can check if the proof is authenticated before accepting the proof. We believe that proposed Authenticated Zero Knowledge Range Proof can be beneficial to many applications in the world.

    Chapter 1 Introduction 1 1.1 Introduction 1 1.2 Contribution 4 Chapter 2 Preliminaries 6 2.1 Notation 6 2.2 Prime Order Bilinear Group 6 2.3 Composite Order Bilinear Group 7 2.4 Randomizable Signature 7 2.5 Two commitments hide the same secret. (EL Proof) 10 2.6 The commitment hides the square secret. (SQR Proof) 12 2.7 Tsai Non-Interactive ZKRP (NIZKRP) Scheme 14 Chapter 3 Authenticated Zero­-Knowledge Range Proof 18 3.1 Our Idea 18 3.2 Assumptions 21 3.3 Definition 21 3.4 Construction 25 Chapter 4 Security Proof 33 4.1 Correctness 33 4.2 Soundness 35 4.3 Zero-Knowledge 39 Chapter 5 Efficiency Analysis 45 Chapter 6 Conclusion 46 6.1 Future Work 46 References 48 Appendix A — Fujisaki­-Okamoto Commitment 53 Appendix B — Inner Forge and translation problem 55

    [1]  M. Blum, P. Feldman, and S. Micali. Non­interactive zero­knowledge and its appli­ cations. In Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pages 329–349. 2019.
    [2]  D. Boneh, E. Boyle, H. Corrigan­Gibbs, N. Gilboa, and Y. Ishai. Zero­knowledge proofs on secret­shared data via fully linear pcps. In A. Boldyreva and D. Miccian­ cio, editors, Advances in Cryptology – CRYPTO 2019, pages 67–97, Cham, 2019. Springer International Publishing.
    [3]  D. Boneh, E.­J. Goh, and K. Nissim. Evaluating 2­dnf formulas on ciphertexts. In TCC, pages 325–341, 2005.
    [4] F.Boudot.Efficientproofsthatacommittednumberliesinaninterval.InB.Preneel, editor, Advances in Cryptology — EUROCRYPT 2000, pages 431–444. Springer Berlin Heidelberg, 2000.
    [5]  B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell. Bulletproofs: Short proofs for confidential transactions and more. Cryptology ePrint Archive, Report 2017/1066, 2017. https://eprint.iacr.org/2017/1066.
    [6]  B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell. Bulletproofs: Short proofs for confidential transactions and more. In 2018 IEEE Symposium on Security and Privacy (SP), pages 315–334, May 2018.
    [7]  J. Camenisch and A. Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In M. Franklin, editor, Advances in Cryptology – CRYPTO 2004, pages 56–72, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg.
    [8]  R. Chaabouni, H. Lipmaa, and B. Zhang. A non­interactive range proof with con­ stant communication. In A. D. Keromytis, editor, Financial Cryptography and Data Security, pages 179–199, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
    [9]  A. De Santis, S. Micali, and G. Persiano. Non­interactive zero­knowledge proof systems. In C. Pomerance, editor, Advances in Cryptology — CRYPTO ’87, pages 52–72, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg.
    [10]  E. Fujisaki and T. Okamoto. Statistical zero knowledge protocols to prove modular polynomial relations. In B. S. Kaliski, editor, Advances in Cryptology — CRYPTO ’97, pages 16–30, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg.
    [11]  O. Goldreich. Foundations of Cryptography: Basic Tools. Cambridge University Press, USA, 2000.
    [12]  S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interac­ tive proof­systems. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC '85, page 291–304, New York, NY, USA, 1985. Association for Computing Machinery.
    [13]  S.Goldwasser,S.Micali,andR.L.Rivest.Adigitalsignatureschemesecureagainst adaptive chosen­message attacks. SIAM Journal on Computing, 17(2):281–308, 1988.
    [14]  T. Koens and C. Ramaekers. Efficient zero­knowledge range proofs in ethereum. 2017.
    [15]  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, May 2016.
    [16]  P. McCorry, S. Shahandashti, and F. Hao. A smart contract for boardroom voting with maximum voter privacy. 01 2017.
    [17]  D. Pointcheval and O. Sanders. Short randomizable signatures. In K. Sako, edi­tor, Topics in Cryptology ­ CT­RSA 2016, pages 111–126, Cham, 2016. Springer International Publishing.
    [18]  D. Pointcheval and O. Sanders. Reassessing security of randomizable signatures. In N. P. Smart, editor, Topics in Cryptology – CT­RSA 2018, pages 319–338, Cham, 2018. Springer International Publishing.
    [19]  Y. Tao, X. Wang, and R. Zhang. Short zero­knowledge proof of knowledge for lattice­based commitment. In J. Ding and J.­P. Tillich, editors, Post­Quantum Cryptography, pages 268–283, Cham, 2020. Springer International Publishing.
    [20]  Y.C.Tsai,R.Tso,Z.Liu,andK.Chen.Animprovednon­interactivezero­knowledge range proof for decentralized applications. In 2019 IEEE International Conference on Decentralized Applications and Infrastructures (DAPPCON), pages 129–134, April 2019.
    [21]  Y. Wang and A. Kogan. Designing confidentiality­preserving blockchain­based transaction processing systems. International Journal of Accounting Information Systems, 30:1 – 18, 2018. 2017 Research Symposium on Information Integrity & Information Systems Assurance.
    [22]  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.

    下載圖示
    QR CODE