计算机科学 ›› 2022, Vol. 49 ›› Issue (10): 335-343.doi: 10.11896/jsjkx.210900044

• 信息安全 • 上一篇    下一篇

ZKFERP:计算成本恒定的通用高效范围证明方案

李一聪, 周宽久, 王梓仲, 徐琳   

  1. 大连理工大学软件学院 辽宁 大连 116024
  • 收稿日期:2021-09-06 修回日期:2022-03-11 出版日期:2022-10-15 发布日期:2022-10-13
  • 通讯作者: 周宽久(zhoukj@dlut.edu.cn)
  • 作者简介:(17640284112@mail.dlut.edu.cn)
  • 基金资助:
    科技部重点研发计划(2019YFD1101104)

ZKFERP:Universal and Efficient Range Proof Scheme with Constant Computational Cost

LI Yi-cong, ZHOU Kuan-jiu, WANG Zi-zhong, XU Lin   

  1. School of Software,Dalian University of Technology,Dalian,Liaoning 116024,China
  • Received:2021-09-06 Revised:2022-03-11 Online:2022-10-15 Published:2022-10-13
  • About author:LI Yi-cong,born in 1997,postgraduate.His main research interests include blockchain system security and crypto-graphy theory and application.
    ZHOU Kuan-jiu,born in 1966,Ph.D,professor,Ph.D supervisor,is a senior member of China Computer Federation.His main research interests include blockchain theory and technology and trusted software.
  • Supported by:
    Key Research and Development Program Project of Ministry of Science and Technology(2019YFD1101104).

摘要: 区块链去中心化的特性易导致交易层用户隐私泄露,引发信息安全问题。零知识范围证明的目的是在不透露交易数据的同时,机密验证数据属于合法正整数区间,有效解决了区块链隐私保护问题。现有的区块链范围证明方案在证明速度、验证速度及计算成本等方面仍有较大的优化空间;并且,现有方案无法处理浮点数问题,因此限制了范围证明的应用领域。基于此,提出了一种计算成本恒定且浮点数、整数通用的高效范围证明方案——ZKFERP。ZKFERP在Bulletproofs的基础上改进零知识协议,优化证明结构,并设计了一种拉格朗日内积向量生成方法,使见证生成时间恒定,最后利用浮点数范围关系式构造承诺,实现浮点数范围证明。ZKFERP仅依赖于离散对数假设,无需第三方可信。实验结果表明,ZKFERP的通信成本和时间复杂度均恒定,且与已知最先进的范围证明方案相比,ZKFERP的证明时间缩短了40.0%,验证时间缩短了29.8%。

关键词: 区块链, 隐私保护, 零知识证明, 范围证明, 向量内积承诺

Abstract: The decentralization of blockchain can easily lead to the leakage of users’ private data at the transaction layer,which in turn leads to information security issues.The zero-knowledge range proof is designed to confidentially verify that the transaction data belongs to a legal positive integer range without revealing the transaction data.It effectively solves the problem of blockchain privacy leakage.The existing blockchain range proof scheme can still be further optimized in terms of proof speed,verification speed and calculation cost.In addition,the existing solutions cannot handle the floating-point number problem,thus limiting the application fields of range proofs.This paper proposes an efficient range proof scheme with constant computational cost and universal for floating-point numbers and integers,ZKFERP.It improves the zero-knowledge protocol based on Bulletproofs to optimize the proof structure,and a Lagrangian inner product vector generation method is designed to make the witness generation time constant and the commitment is constructed according to the floating-point number range relationship to implement floating-point range proof.ZKFERP only relies on the discrete logarithm assumption,and third-party credibility is not required.The communication cost and time complexity of ZKFERP are constant.Experimental results show that,compared with the most advanced known range proof scheme,ZKFERP’s proof speed is increased by 40.0%,and the verification speed is increased by 29.8%.

Key words: Blockchain, Privacy protection, Zero-knowledge proof, Range proof, Vector inner product commitment

中图分类号: 

  • TP399
[1]NAKAMOTO S.Bitcoin:A Peer-to-Peer Electronic Cash Sys-tem[J].Decentralized Business Review,2008,1:2012.
[2]BONNEAU J,MILLER A,CLARK J,et al.Research Perspectives and Challenges for Bitcoin and Cryptocurrencies[C]//2015 IEEE Symposium on Security and Privacy.San Jose:IEEE,2015:104-121.
[3]LIU M D,CHEN Z N,SHI Y J,et al.Research progress of blockchain in data security[J].Chinese Journal of Computer,2021,44(1):1-27.
[4]GOLDREICH O,OREN Y.Definitions and properties of zero-knowledge proof system[J].Journal of Cryptology,1994,7(1):1-32.
[5]NOETHER S,MACKENZIE A.Ring confidential transactions[J].Ledger,2016,1:1-18.
[6]BLUM M.Coin flipping by telephone a protocol for solving impossible problems[J].ACM SIGACT News,1983,15(1):23-27.
[7]MAXWELL G,POELSTRA A.Borromean ring signatures[J].Accessed,2015,8:2019.
[8]PEDERSEN T P.Non-interactive and information-theoretic secure verifiable secret sharing[C]//Annual International Cryptology Conference.Springer:Berlin,1991:129-140.
[9]NOETHER S.Ring signature confidential transactions for Mo-nero[J].IACR Cryptology ePrint Achieve,2016,1:1-18.
[10]SUN S F,AU M H,LIU J K,et al.RingCT 2.0:A Compact Accumulator-Based(Linkable Ring Signature) Protocol for Blockchain Cryptocurrency Monero[C]//European Symposium on Research in Computer Security.Cham:Springer,2017:456-474.
[11]WOOD G.Ethereum:A secure decentralized transaction ledger[EB/OL].http://gavwood.com/paper.pdf.
[12]MCCORRY P,SHAHANDASHTI S F,HAO F.A Smart Contract for Boardroom Voting with Maximum Voter Privacy[C]//International Conference on Financial Cryptography and Data Security.Cham:Springer,2017:357-375.
[13]CAMPANELLI M,GENNARO R,GOLDFEDER S,et al.Zeroknowledge contingent payments revisited:Attacks and payments for servicesy[C]//Conference on Computer and Communications Security.Dallas,Texas,USA:ACM,2017:229-243.
[14]PARNO B,HOWELL J,GENTRY C,et al.Pinocchio:Nearly practical verifiable computation[C]//Proceedings of the 34th IEEE Symposium on Security and Privacy.Berkeley,CA,USA:IEEE,2013:238-252.
[15]BEN-SASSON E,CHIESA A,GENKIN D,et al.SNARKs for C:Verifying program executions succinctly and in zero know-ledge[C]//Annual Cryptology Conference.Berlin:Springer,2013:90-108.
[16]PARNO B,HOWELL J,GENTRY C,et al.Pinocchio:Nearly practical verifiable computation[C]//2013 IEEE Symposium on Security and Privacy.Berkeley,CA,USA:IEEE,2013:238-252.
[17]GROTH J.On the Size of Pairing-Based Non-interactive Arguments[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin:Springer,2016:305-326.
[18]QUESNELLE J.On the linkability of Zcash transactions[J].arXiv:1712.01210,2017.
[19]WAHBY R S,TZIALLA I,SHELAT A,et al. Doubly-efficient zk SNARKs without trusted setup[C]//Proceedings of 2018 IEEE Symposium on Security and Privacy(SP).San Francisco,CA,USA:IEEE,2018:2375-1207.
[20]SETTY S,ANGEL S,LEE J.Verifiable state machines:Proofsthat untrusted services operate correctly[J].ACM SIGOPS Operating Systems Review,2020,54(1):40-46.
[21]BEN-SASSON E,BENTOV I,HORESH Y,et al.Scalable,transparent,and post-quantum secure computational integrity[J].IACR Cryptology ePrint Archive,2018,46:1-83.
[22]MALLER M,BOWE S,KOHLWEISS M,et al.Sonic:Zero-knowledge SNARKs from linear-size universal and updatable structured reference strings[C]//Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Secu-rity.New York:ACM,2019:2111-2128.
[23]GABIZON A,WILLIAMSON Z J,CIOBOTARU O.PLONK:Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge[J].IACR Cryptol.ePrint Arch.,2019,953:1-35.
[24]LIPMAA H.On diophantine complexity and statistical zero-knowledge arguments[C]//International Conference on the Theory and Application of Cryptology and Information Secu-rity.Berlin:Springer,2003:398-415.
[25]GROTH J.Non-interactive zero-knowledge arguments for vo-ting[C]//International Conference on Applied Cryptography and Network Security.Berlin,Heidelberg:Springer,2005:467-482.
[26]BUNZ B,BOOTLE J,BONEH D,et al.Bulletproofs:ShortProofs for Confidential Transactions and More[C]//2018 IEEE Symposium on Security and Privacy.San Francisco,CA,USA:IEEE,2018:315-334.
[27]BOOTLE J,CERULLI A,CHAIDOS P,et al.Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin:Springer,2016:327-357.
[28]DENG C,TANG X,YOU L,et al.Cuproof:A Novel RangeProof with Constant Size[J].IACR Cryptol.ePrint Arch.,2021,13(2):127-137.
[29]FEIGE U,FIAT A,SHAMIR A.Zero knowledge proofs ofidentify[J].Journal of Cryptology,1988,1(2):77-94.
[30]RIVEST R,SHAMIR A,ADLEMAN L.A method for obtaining digital signatures and public-key cryptosystems[J].Communications of the ACM,1978,21(2):120-126.
[31]ALMUHAMMADI S,SUI N T,MCLEOD D.Better privacyand security in e-commerce:using elliptic curve-based zero knowledge proofs[C]//Proceedings IEEE InternationalConfe-rence on e-Commerce Technology.San Diego,CA,USA:IEEE,2004:299-302.
[1] 鲁晨阳, 邓苏, 马武彬, 吴亚辉, 周浩浩.
基于分层抽样优化的面向异构客户端的联邦学习
Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients
计算机科学, 2022, 49(9): 183-193. https://doi.org/10.11896/jsjkx.220500263
[2] 汤凌韬, 王迪, 张鲁飞, 刘盛云.
基于安全多方计算和差分隐私的联邦学习方案
Federated Learning Scheme Based on Secure Multi-party Computation and Differential Privacy
计算机科学, 2022, 49(9): 297-305. https://doi.org/10.11896/jsjkx.210800108
[3] 王子凯, 朱健, 张伯钧, 胡凯.
区块链与智能合约并行方法研究与实现
Research and Implementation of Parallel Method in Blockchain and Smart Contract
计算机科学, 2022, 49(9): 312-317. https://doi.org/10.11896/jsjkx.210800102
[4] 吕由, 吴文渊.
隐私保护线性回归方案与应用
Privacy-preserving Linear Regression Scheme and Its Application
计算机科学, 2022, 49(9): 318-325. https://doi.org/10.11896/jsjkx.220300190
[5] 周航, 姜河, 赵琰, 解相朋.
适用于各单元共识交易的电力区块链系统优化调度研究
Study on Optimal Scheduling of Power Blockchain System for Consensus Transaction ofEach Unit
计算机科学, 2022, 49(6A): 771-776. https://doi.org/10.11896/jsjkx.210600241
[6] 傅丽玉, 陆歌皓, 吴义明, 罗娅玲.
区块链技术的研究及其发展综述
Overview of Research and Development of Blockchain Technology
计算机科学, 2022, 49(6A): 447-461. https://doi.org/10.11896/jsjkx.210600214
[7] 高健博, 张家硕, 李青山, 陈钟.
RegLang:一种面向监管的智能合约编程语言
RegLang:A Smart Contract Programming Language for Regulation
计算机科学, 2022, 49(6A): 462-468. https://doi.org/10.11896/jsjkx.210700016
[8] 毛典辉, 黄晖煜, 赵爽.
符合监管合规性的自动合成新闻检测方法研究
Study on Automatic Synthetic News Detection Method Complying with Regulatory Compliance
计算机科学, 2022, 49(6A): 523-530. https://doi.org/10.11896/jsjkx.210300083
[9] 王健.
基于隐私保护的反向传播神经网络学习算法
Back-propagation Neural Network Learning Algorithm Based on Privacy Preserving
计算机科学, 2022, 49(6A): 575-580. https://doi.org/10.11896/jsjkx.211100155
[10] 李博, 向海昀, 张宇翔, 廖浩德.
面向食品溯源场景的PBFT优化算法应用研究
Application Research of PBFT Optimization Algorithm for Food Traceability Scenarios
计算机科学, 2022, 49(6A): 723-728. https://doi.org/10.11896/jsjkx.210800018
[11] 王思明, 谭北海, 余荣.
面向6G可信可靠智能的区块链分片与激励机制
Blockchain Sharding and Incentive Mechanism for 6G Dependable Intelligence
计算机科学, 2022, 49(6): 32-38. https://doi.org/10.11896/jsjkx.220400004
[12] 孙浩, 毛瀚宇, 张岩峰, 于戈, 徐石成, 何光宇.
区块链跨链技术发展及应用
Development and Application of Blockchain Cross-chain Technology
计算机科学, 2022, 49(5): 287-295. https://doi.org/10.11896/jsjkx.210800132
[13] 李利, 何欣, 韩志杰.
群智感知的隐私保护研究综述
Review of Privacy-preserving Mechanisms in Crowdsensing
计算机科学, 2022, 49(5): 303-310. https://doi.org/10.11896/jsjkx.210400077
[14] 阳真, 黄松, 郑长友.
基于区块链与改进CP-ABE的众测知识产权保护技术研究
Study on Crowdsourced Testing Intellectual Property Protection Technology Based on Blockchain and Improved CP-ABE
计算机科学, 2022, 49(5): 325-332. https://doi.org/10.11896/jsjkx.210900075
[15] 任畅, 赵洪, 蒋华.
一种量子安全拜占庭容错共识机制
Quantum Secured-Byzantine Fault Tolerance Blockchain Consensus Mechanism
计算机科学, 2022, 49(5): 333-340. https://doi.org/10.11896/jsjkx.210400154
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!