Publications-Theses
Article View/Open
Publication Export
-
題名 非互動零知識值域證明及其應用
Non-Interactive Zero-Knowledge Range Proof and Its Applications作者 蔡亞哲
Tsai, Ya-Che貢獻者 左瑞麟
Tso, Ray-Lin
蔡亞哲
Tsai, Ya-Che關鍵詞 區塊鏈
承諾方案
非交互式零知識
隱私保護
範圍證明
Blockchain
Commitment scheme
Non-interactive zero-knowledge
Privacy protection
Range proof日期 2019 上傳時間 3-Oct-2019 17:18:32 (UTC+8) 摘要 區塊鏈是中本聰於2008年推出的第一個分散式加密貨幣比特幣的核心技術。從那時起，區塊鏈技術有了革命性的進步。特別是在最近的區塊鏈平台中，如以太坊已可提供通用可執行的腳本，即智能合約。可用於在付款之外的許多領域開發分散式應用程式。然而，區塊鏈數據的透明度引起了許多需要高隱私級別的應用程序的擔憂。因此，許多隱私增強技術已應用於分散式應用程式開發，包括零知識證明。本文重點介紹一種特殊的零知識證明，稱為零知識值域證明，目前已應用於基於區塊鏈的銀行支付。 零知識值域證明允許用戶說服其他人，其秘密值實際上位於一個區間內，而不會洩露任何有關該秘密的訊息。這裡我們介紹一種新的零知識值域證明，並具有以下顯著特徵：(1)非交互式：在證明期間，用戶和驗證者之間不需要通信。(2)範圍靈活性：除了它們是自然數之外，對值域的下限和上限沒有限制。 (3) 效率：我們的方案與Pang等人的方案相比有所改進，實現了更好的安全性，並且比他們的計劃更有效率。(4)安全性:基於離散對數問題，因數分解問題，我們在隨機圖靈機模型中嚴格證明了該方案的安全性。我們相信我們的新零知識值域證明可以有利於發分散式應用程式開發，並可以將應用程序範圍擴展到更多場景。
Blockchain is the core technology underlying the first decentralized cryptocurrency, Bitcoin, introduced by Nakamoto in 2008. Since then, blockchain technology has many more advancements that are being developed and experimented.In particular, recent blockchain platforms such as Ethereum offer general and executable scripts, namely smart contracts, that can be employed to develop decentralized applications (DApps) in many domains beyond payment. However, the transparency of blockchain data raises concerns for many applications that require a high privacy level. Therefore, many privacy enhancing technologies have been applied to DApp development, including zero-knowledge proof (ZKP). This paper focuses on a particular kind of ZKP, called zero-knowledge range proof (ZKRP), that has been applied in blockchain-based payments for banks. ZKRP allows a user to convince other people that a secret value lies within an interval without revealing any information about the secret. Here we introduce a new ZKRP which has the following remarkable features: (1) Non-interactive: No communication is required between a user and a verifier during the proof. (2) Range-flexibility: There is no limitation on the lower bound and the upper bound of the range except that they are natural numbers. (3) Efficiency: Our scheme is modified from that of Pang et al. (2010), yet achieves better security and is more efficient than their scheme. (4) Security: the security of the proposed scheme is rigorously proved in the random oracle model based on the hardness assumptions of the discrete logarithm problem, the integer factorization problem, etc. We believe our new ZKRP can be beneficial to the development of DApps and can extend the application scope to more scenarios.參考文獻 [1] S. Agrawal, C. Ganesh, and P. Mohassel. Non-interactive zero-knowledge proofsfor composite statements. In Annual International Cryptology Conference, pages643–673. Springer, 2018.[2] 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.[3] F. Boudot and J. Traoré. Efficient publicly verifiable secret sharing schemes withfast or delayed recovery. In International Conference on Information and Communications Security, pages 87–102. Springer, 1999.[4] B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell. Bulletproofs:Efficient range proofs for confidential transactions. Technical report, CryptologyePrint Archive, Report 2017/1066, 2017. https://eprint. iacr. org/2017/1066, 2017.[5] B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell. Bulletproofs:Short proofs for confidential transactions and more. In Bulletproofs: Short Proofsfor Confidential Transactions and More, page 0. IEEE, 2018.[6] R. Chaabouni, H. Lipmaa, and B. Zhang. A non-interactive range proof with constantcommunication. In International Conference on Financial Cryptography and DataSecurity, pages 179–199. Springer, 2012.[7] E. Fujisaki and T. Okamoto. Statistical zero knowledge protocols to prove modularpolynomial relations. In Annual International Cryptology Conference, pages 16–30.Springer, 1997.[8] O. Goldreich. Foundations of Cryptography: Volume 1, Basic Tools. CambridgeUniversity Press, 2010.[9] J. Groth. Non-interactive zero-knowledge arguments for voting. In International Conference on Applied Cryptography and Network Security, pages 467–482.Springer, 2005.[10] A. Hahn, R. Singh, C.-C. Liu, and S. Chen. Smart contract-based campus demonstration of decentralized transactive energy auctions. In Power & Energy Society Innovative Smart Grid Technologies Conference (ISGT), 2017 IEEE, pages 1–5. IEEE,2017.[11] T. Koens, C. Ramaekers, and C. Van Wijk. Efficient zero-knowledge range proofsin ethereum. Technical report, Technical Report, 2018.[12] A. Kosba, A. Miller, E. Shi, Z. Wen, and C. Papamanthou. Hawk: The blockchainmodel of cryptography and privacy-preserving smart contracts. In 2016 IEEE symposium on security and privacy (SP), pages 839–858. IEEE, 2016.[13] K. Li, R. Yang, M. H. Au, and Q. Xu. Practical range proof for cryptocurrencymonero with provable security. In International Conference on Information andCommunications Security, pages 255–262. Springer, 2017.[14] Y. Lindell. How to simulate it–a tutorial on the simulation proof technique. InTutorials on the Foundations of Cryptography, pages 277–346. Springer, 2017.[15] 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.[16] H. Lipmaa. Progression-free sets and sublinear pairing-based non-interactive zeroknowledge arguments. In Theory of Cryptography Conference, pages 169–189.Springer, 2012.[17] P. McCorry, S. F. Shahandashti, and F. Hao. A smart contract for boardroom votingwith maximum voter privacy. In International Conference on Financial Cryptography and Data Security, pages 357–375. Springer, 2017.[18] I. Miers, C. Garman, M. Green, and A. D. Rubin. Zerocoin: Anonymous distributede-cash from bitcoin. In Security and Privacy (SP), 2013 IEEE Symposium on, pages397–411. IEEE, 2013.[19] K. Peng. A general, flexible and efficient proof of inclusion and exclusion. In Cryptographers’ Track at the RSA Conference, pages 33–48. Springer, 2011.[20] K. Peng and F. Bao. Batch range proof for practical small ranges. In InternationalConference on Cryptology in Africa, pages 114–130. Springer, 2010.[21] K. Peng and F. Bao. An efficient range proof scheme. In Social Computing (SocialCom), 2010 IEEE Second International Conference on, pages 826–833. IEEE,2010.[22] K. Peng, C. Boyd, and E. Dawson. Batch zero-knowledge proof and verification andits applications. ACM Transactions on Information and System Security (TISSEC),10(2):6, 2007.[23] K. Peng and L. Yi. Studying a range proof technique— exception and optimisation. InInternational Conference on Cryptology in Africa, pages 328–341. Springer, 2013.[24] E. B. Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, and M. Virza.Zerocash: Decentralized anonymous payments from bitcoin. In 2014 IEEE Symposium on Security and Privacy (SP), pages 459–474. IEEE, 2014.[25] C.-P. Schnorr. Efficient identification and signatures for smart cards. In Conferenceon the Theory and Application of Cryptology, pages 239–252. Springer, 1989.[26] T. H. Yuen, Q. Huang, Y. Mu, W. Susilo, D. S. Wong, and G. Yang. Efficient noninteractive range proof. In International Computing and Combinatorics Conference,pages 138–147. Springer, 2009. 描述 碩士
國立政治大學
資訊科學系
106753028資料來源 http://thesis.lib.nccu.edu.tw/record/#G0106753028 資料類型 thesis dc.contributor.advisor 左瑞麟 zh_TW dc.contributor.advisor Tso, Ray-Lin en_US dc.contributor.author (Authors) 蔡亞哲 zh_TW dc.contributor.author (Authors) Tsai, Ya-Che en_US dc.creator (作者) 蔡亞哲 zh_TW dc.creator (作者) Tsai, Ya-Che en_US dc.date (日期) 2019 en_US dc.date.accessioned 3-Oct-2019 17:18:32 (UTC+8) - dc.date.available 3-Oct-2019 17:18:32 (UTC+8) - dc.date.issued (上傳時間) 3-Oct-2019 17:18:32 (UTC+8) - dc.identifier (Other Identifiers) G0106753028 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/126584 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學系 zh_TW dc.description (描述) 106753028 zh_TW dc.description.abstract (摘要) 區塊鏈是中本聰於2008年推出的第一個分散式加密貨幣比特幣的核心技術。從那時起，區塊鏈技術有了革命性的進步。特別是在最近的區塊鏈平台中，如以太坊已可提供通用可執行的腳本，即智能合約。可用於在付款之外的許多領域開發分散式應用程式。然而，區塊鏈數據的透明度引起了許多需要高隱私級別的應用程序的擔憂。因此，許多隱私增強技術已應用於分散式應用程式開發，包括零知識證明。本文重點介紹一種特殊的零知識證明，稱為零知識值域證明，目前已應用於基於區塊鏈的銀行支付。 零知識值域證明允許用戶說服其他人，其秘密值實際上位於一個區間內，而不會洩露任何有關該秘密的訊息。這裡我們介紹一種新的零知識值域證明，並具有以下顯著特徵：(1)非交互式：在證明期間，用戶和驗證者之間不需要通信。(2)範圍靈活性：除了它們是自然數之外，對值域的下限和上限沒有限制。 (3) 效率：我們的方案與Pang等人的方案相比有所改進，實現了更好的安全性，並且比他們的計劃更有效率。(4)安全性:基於離散對數問題，因數分解問題，我們在隨機圖靈機模型中嚴格證明了該方案的安全性。我們相信我們的新零知識值域證明可以有利於發分散式應用程式開發，並可以將應用程序範圍擴展到更多場景。 zh_TW dc.description.abstract (摘要) Blockchain is the core technology underlying the first decentralized cryptocurrency, Bitcoin, introduced by Nakamoto in 2008. Since then, blockchain technology has many more advancements that are being developed and experimented.In particular, recent blockchain platforms such as Ethereum offer general and executable scripts, namely smart contracts, that can be employed to develop decentralized applications (DApps) in many domains beyond payment. However, the transparency of blockchain data raises concerns for many applications that require a high privacy level. Therefore, many privacy enhancing technologies have been applied to DApp development, including zero-knowledge proof (ZKP). This paper focuses on a particular kind of ZKP, called zero-knowledge range proof (ZKRP), that has been applied in blockchain-based payments for banks. ZKRP allows a user to convince other people that a secret value lies within an interval without revealing any information about the secret. Here we introduce a new ZKRP which has the following remarkable features: (1) Non-interactive: No communication is required between a user and a verifier during the proof. (2) Range-flexibility: There is no limitation on the lower bound and the upper bound of the range except that they are natural numbers. (3) Efficiency: Our scheme is modified from that of Pang et al. (2010), yet achieves better security and is more efficient than their scheme. (4) Security: the security of the proposed scheme is rigorously proved in the random oracle model based on the hardness assumptions of the discrete logarithm problem, the integer factorization problem, etc. We believe our new ZKRP can be beneficial to the development of DApps and can extend the application scope to more scenarios. en_US dc.description.tableofcontents 1 Introduction p11.1 Contribution p41.2 Organization p42 Preliminaries p52.1 Notation p52.2 Non-Interactive Zero-Knowledge p52.3 Fujisaki-Okamoto commitment p62.4 The Discrete Logarithm problem p72.5 The Integer Factorization problem p72.6 The Secret Order Principle p82.7 LR-Security Game p82.8 Knowledge of Discrete Logarithm in a Cyclic Group with a Secret Order( KDLCGSO ) p92.9 Two Commitments Hide the Same Secret Proof (EL Proof) p102.10 Committed Number is a Square Proof (SQR Proof) p113 Non-Interactive Zero-Knowledge Range Proof p134 The New Non-interactive ZKRP Protocol p165 Security Description p215.1 Correctness p215.2 Soundness p225.3 Zero-Knowledge p 266 Efficiency of Our Scheme p507 Conclusions p52Reference p53 zh_TW dc.format.extent 1647112 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0106753028 en_US dc.subject (關鍵詞) 區塊鏈 zh_TW dc.subject (關鍵詞) 承諾方案 zh_TW dc.subject (關鍵詞) 非交互式零知識 zh_TW dc.subject (關鍵詞) 隱私保護 zh_TW dc.subject (關鍵詞) 範圍證明 zh_TW dc.subject (關鍵詞) Blockchain en_US dc.subject (關鍵詞) Commitment scheme en_US dc.subject (關鍵詞) Non-interactive zero-knowledge en_US dc.subject (關鍵詞) Privacy protection en_US dc.subject (關鍵詞) Range proof en_US dc.title (題名) 非互動零知識值域證明及其應用 zh_TW dc.title (題名) Non-Interactive Zero-Knowledge Range Proof and Its Applications en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] S. Agrawal, C. Ganesh, and P. Mohassel. Non-interactive zero-knowledge proofsfor composite statements. In Annual International Cryptology Conference, pages643–673. Springer, 2018.[2] 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.[3] F. Boudot and J. Traoré. Efficient publicly verifiable secret sharing schemes withfast or delayed recovery. In International Conference on Information and Communications Security, pages 87–102. Springer, 1999.[4] B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell. Bulletproofs:Efficient range proofs for confidential transactions. Technical report, CryptologyePrint Archive, Report 2017/1066, 2017. https://eprint. iacr. org/2017/1066, 2017.[5] B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell. Bulletproofs:Short proofs for confidential transactions and more. In Bulletproofs: Short Proofsfor Confidential Transactions and More, page 0. IEEE, 2018.[6] R. Chaabouni, H. Lipmaa, and B. Zhang. A non-interactive range proof with constantcommunication. In International Conference on Financial Cryptography and DataSecurity, pages 179–199. Springer, 2012.[7] E. Fujisaki and T. Okamoto. Statistical zero knowledge protocols to prove modularpolynomial relations. In Annual International Cryptology Conference, pages 16–30.Springer, 1997.[8] O. Goldreich. Foundations of Cryptography: Volume 1, Basic Tools. CambridgeUniversity Press, 2010.[9] J. Groth. Non-interactive zero-knowledge arguments for voting. In International Conference on Applied Cryptography and Network Security, pages 467–482.Springer, 2005.[10] A. Hahn, R. Singh, C.-C. Liu, and S. Chen. Smart contract-based campus demonstration of decentralized transactive energy auctions. In Power & Energy Society Innovative Smart Grid Technologies Conference (ISGT), 2017 IEEE, pages 1–5. IEEE,2017.[11] T. Koens, C. Ramaekers, and C. Van Wijk. Efficient zero-knowledge range proofsin ethereum. Technical report, Technical Report, 2018.[12] A. Kosba, A. Miller, E. Shi, Z. Wen, and C. Papamanthou. Hawk: The blockchainmodel of cryptography and privacy-preserving smart contracts. In 2016 IEEE symposium on security and privacy (SP), pages 839–858. IEEE, 2016.[13] K. Li, R. Yang, M. H. Au, and Q. Xu. Practical range proof for cryptocurrencymonero with provable security. In International Conference on Information andCommunications Security, pages 255–262. Springer, 2017.[14] Y. Lindell. How to simulate it–a tutorial on the simulation proof technique. InTutorials on the Foundations of Cryptography, pages 277–346. Springer, 2017.[15] 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.[16] H. Lipmaa. Progression-free sets and sublinear pairing-based non-interactive zeroknowledge arguments. In Theory of Cryptography Conference, pages 169–189.Springer, 2012.[17] P. McCorry, S. F. Shahandashti, and F. Hao. A smart contract for boardroom votingwith maximum voter privacy. In International Conference on Financial Cryptography and Data Security, pages 357–375. Springer, 2017.[18] I. Miers, C. Garman, M. Green, and A. D. Rubin. Zerocoin: Anonymous distributede-cash from bitcoin. In Security and Privacy (SP), 2013 IEEE Symposium on, pages397–411. IEEE, 2013.[19] K. Peng. A general, flexible and efficient proof of inclusion and exclusion. In Cryptographers’ Track at the RSA Conference, pages 33–48. Springer, 2011.[20] K. Peng and F. Bao. Batch range proof for practical small ranges. In InternationalConference on Cryptology in Africa, pages 114–130. Springer, 2010.[21] K. Peng and F. Bao. An efficient range proof scheme. In Social Computing (SocialCom), 2010 IEEE Second International Conference on, pages 826–833. IEEE,2010.[22] K. Peng, C. Boyd, and E. Dawson. Batch zero-knowledge proof and verification andits applications. ACM Transactions on Information and System Security (TISSEC),10(2):6, 2007.[23] K. Peng and L. Yi. Studying a range proof technique— exception and optimisation. InInternational Conference on Cryptology in Africa, pages 328–341. Springer, 2013.[24] E. B. Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, and M. Virza.Zerocash: Decentralized anonymous payments from bitcoin. In 2014 IEEE Symposium on Security and Privacy (SP), pages 459–474. IEEE, 2014.[25] C.-P. Schnorr. Efficient identification and signatures for smart cards. In Conferenceon the Theory and Application of Cryptology, pages 239–252. Springer, 1989.[26] T. H. Yuen, Q. Huang, Y. Mu, W. Susilo, D. S. Wong, and G. Yang. Efficient noninteractive range proof. In International Computing and Combinatorics Conference,pages 138–147. Springer, 2009. zh_TW dc.identifier.doi (DOI) 10.6814/NCCU201901191 en_US
