Computer Science ›› 2022, Vol. 49 ›› Issue (10): 335-343.doi: 10.11896/jsjkx.210900044

• Information Security • Previous Articles     Next Articles

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).

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

CLC Number: 

  • 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] LU Chen-yang, DENG Su, MA Wu-bin, WU Ya-hui, ZHOU Hao-hao. Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients [J]. Computer Science, 2022, 49(9): 183-193.
[2] WANG Zi-kai, ZHU Jian, ZHANG Bo-jun, HU Kai. Research and Implementation of Parallel Method in Blockchain and Smart Contract [J]. Computer Science, 2022, 49(9): 312-317.
[3] ZHOU Hang, JIANG He, ZHAO Yan, XIE Xiang-peng. Study on Optimal Scheduling of Power Blockchain System for Consensus Transaction ofEach Unit [J]. Computer Science, 2022, 49(6A): 771-776.
[4] LI Bo, XIANG Hai-yun, ZHANG Yu-xiang, LIAO Hao-de. Application Research of PBFT Optimization Algorithm for Food Traceability Scenarios [J]. Computer Science, 2022, 49(6A): 723-728.
[5] FU Li-yu, LU Ge-hao, WU Yi-ming, LUO Ya-ling. Overview of Research and Development of Blockchain Technology [J]. Computer Science, 2022, 49(6A): 447-461.
[6] GAO Jian-bo, ZHANG Jia-shuo, LI Qing-shan, CHEN Zhong. RegLang:A Smart Contract Programming Language for Regulation [J]. Computer Science, 2022, 49(6A): 462-468.
[7] MAO Dian-hui, HUANG Hui-yu, ZHAO Shuang. Study on Automatic Synthetic News Detection Method Complying with Regulatory Compliance [J]. Computer Science, 2022, 49(6A): 523-530.
[8] WANG Si-ming, TAN Bei-hai, YU Rong. Blockchain Sharding and Incentive Mechanism for 6G Dependable Intelligence [J]. Computer Science, 2022, 49(6): 32-38.
[9] SUN Hao, MAO Han-yu, ZHANG Yan-feng, YU Ge, XU Shi-cheng, HE Guang-yu. Development and Application of Blockchain Cross-chain Technology [J]. Computer Science, 2022, 49(5): 287-295.
[10] YANG Zhen, HUANG Song, ZHENG Chang-you. Study on Crowdsourced Testing Intellectual Property Protection Technology Based on Blockchain and Improved CP-ABE [J]. Computer Science, 2022, 49(5): 325-332.
[11] REN Chang, ZHAO Hong, JIANG Hua. Quantum Secured-Byzantine Fault Tolerance Blockchain Consensus Mechanism [J]. Computer Science, 2022, 49(5): 333-340.
[12] FENG Liao-liao, DING Yan, LIU Kun-lin, MA Ke-lin, CHANG Jun-sheng. Research Advance on BFT Consensus Algorithms [J]. Computer Science, 2022, 49(4): 329-339.
[13] WANG Mei-shan, YAO Lan, GAO Fu-xiang, XU Jun-can. Study on Differential Privacy Protection for Medical Set-Valued Data [J]. Computer Science, 2022, 49(4): 362-368.
[14] WANG Xin, ZHOU Ze-bao, YU Yun, CHEN Yu-xu, REN Hao-wen, JIANG Yi-bo, SUN Ling-yun. Reliable Incentive Mechanism for Federated Learning of Electric Metering Data [J]. Computer Science, 2022, 49(3): 31-38.
[15] ZHANG Ying-li, MA Jia-li, LIU Zi-ang, LIU Xin, ZHOU Rui. Overview of Vulnerability Detection Methods for Ethereum Solidity Smart Contracts [J]. Computer Science, 2022, 49(3): 52-61.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!