1. bookVolume 2021 (2021): Issue 4 (October 2021)
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

HashWires: Hyperefficient Credential-Based Range Proofs

Published Online: 23 Jul 2021
Page range: 76 - 95
Received: 28 Feb 2021
Accepted: 16 Jun 2021
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
Abstract

This paper presents HashWires, a hash-based range proof protocol that is applicable in settings for which there is a trusted third party (typically a credential issuer) that can generate commitments. We refer to these as “credential-based” range proofs (CBRPs). HashWires improves upon hashchain solutions that are typically restricted to micro-payments for small interval ranges, achieving an exponential speedup in proof generation and verification time. Under reasonable assumptions and performance considerations, a Hash-Wires proof can be as small as 305 bytes for 64-bit integers. Although CBRPs are not zero-knowledge and are inherently less flexible than general zero-knowledge range proofs, we provide a number of applications in which a credential issuer can leverage HashWires to provide range proofs for private values, without having to rely on heavyweight cryptographic tools and assumptions.

Keywords

[1] Masayuki Abe. A secure three-move blind signature scheme for polynomially many signatures. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 136–151. Springer, 2001. Search in Google Scholar

[2] Sebastian Angel and Michael Walfish. Verifiable auctions for online ad exchanges. In ACM SIGCOMM, 2013. Search in Google Scholar

[3] Foteini Baldimtsi and Anna Lysyanskaya. Anonymous credentials light. In Proceedings of the 2013 ACM SIGSAC conference on Computer & Communications Security, 2013. Search in Google Scholar

[4] Dan Boneh and Victor Shoup. A graduate course in applied cryptography. 2020. Search in Google Scholar

[5] Fabrice Boudot. Efficient proofs that a committed number lies in an interval. In EUROCRYPT ’00, 2000. Search in Google Scholar

[6] Stefan Brands. Untraceable off-line cash in wallet with observers. In Annual international cryptology conference, pages 302–318. Springer, 1993. Search in Google Scholar

[7] Stefan Brands and David Chaum. Distance-bounding protocols. In EUROCRYPT, 1993. Search in Google Scholar

[8] William J Buchanan. Zero-knowledge proof: Proving age with hash chains. Asecuritysite: https://asecuritysite.com/encryption/age, 2021. Search in Google Scholar

[9] Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas Hülsing, and Markus Rückert. On the security of the winter-nitz one-time signature scheme. In AFRICACRYPT, 2011. Search in Google Scholar

[10] Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Gregory Maxwell. Bulletproofs: Short proofs for confidential transactions and more. In IEEE S&P, 2018. Search in Google Scholar

[11] Jan Camenisch, Rafik Chaabouni, et al. Efficient protocols for set membership and range proofs. In ASIACRYPT, 2008. Search in Google Scholar

[12] Jan Camenisch and Anna Lysyanskaya. An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In EUROCRYPT, 2001. Search in Google Scholar

[13] Srdjan Čapkun, Mario Čagalj, and Mani Srivastava. Secure localization with hidden and mobile base stations. In in Proceedings of IEEE INFOCOM. Citeseer, 2006. Search in Google Scholar

[14] Konstantinos Chalkias. Secure cryptographic protocols and applications based on bilinear pairings. 2010. Search in Google Scholar

[15] Konstantinos Chalkias, Kevin Lewi, Payman Mohassel, and Valeria Nikolaenko. Distributed auditing proofs of liabilities. ZKProof, 2020. Search in Google Scholar

[16] Nishanth Chandran, Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky. Position based cryptography. In Annual International Cryptology Conference, 2009. Search in Google Scholar

[17] David Chaum, Ronald L. Rivest, and Alan T. Sherman, editors. CRYPTO’82. Plenum Press, New York, USA, 1982. Search in Google Scholar

[18] Gaby G Dagher, Benedikt Bünz, Joseph Bonneau, Jeremy Clark, and Dan Boneh. Provisions: Privacy-preserving proofs of solvency for bitcoin exchanges. In ACM CCS, 2015. Search in Google Scholar

[19] Ivan Damgård. Practical and provably secure release of a secret and exchange of signatures. J. Cryptol., 1995. Search in Google Scholar

[20] Ankur Shah Delight. Zero knowledge proof of age using hash chains, 2017. Search in Google Scholar

[21] David Derler, Christian Hanser, and Daniel Slamanig. Revisiting cryptographic accumulators, additional properties and relations to other primitives. In CT-RSA, 2015. Search in Google Scholar

[22] Chris Dods, Nigel P Smart, and Martijn Stam. Hash based digital signature schemes. In IMA International Conference on Cryptography and Coding, pages 96–115. Springer, 2005. Search in Google Scholar

[23] Novi Financial. Hashwires rust implementation. https://github.com/novifinancial/hashwires, 2021. Search in Google Scholar

[24] Eiichiro Fujisaki and Tatsuaki Okamoto. Statistical zero knowledge protocols to prove modular polynomial relations. In CRYPTO ’97, volume 1294, pages 16–30. Springer, 1997. Search in Google Scholar

[25] Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. J. ACM, 33(4):792–807, 1986. Search in Google Scholar

[26] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. In SIAM Journal on computing 18.1, pages 186–208, 1989. Search in Google Scholar

[27] Matthew Green. Winternitz checksum. https://blog.cryptographyengineering.com/winternitz-checksum, 2021. Search in Google Scholar

[28] Jens Groth. On the size of pairing-based non-interactive arguments. In EUROCRYPT ’16. Springer, 2016. Search in Google Scholar

[29] Hudson Jameson. Which cryptographic hash function does ethereum use? https://ethereum.stackexchange.com/questions/550, 2016. Search in Google Scholar

[30] Iuon-Chang Lin, Min-Shiang Hwang, and Chin-Chen Chang. The general pay-word: A micro-payment scheme based on n-dimension one-way hash chain. Des. Codes Cryptogr., 2005. Search in Google Scholar

[31] Gregory Maxwell, 2016. https://people.xiph.org/~greg/confidential_values.txt. Search in Google Scholar

[32] Ralph C Merkle. A certified digital signature. In CRYPTO, pages 218–238. Springer, 1989. Search in Google Scholar

[33] Eduardo Morais, Tommy Koens, Cees van Wijk, and Aleksei Koren. A survey on zero knowledge range proofs and applications. CoRR, abs/1907.06381, 2019. Search in Google Scholar

[34] Arvind Narayanan, Narendran Thiagarajan, Mugdha Lakhani, Michael Hamburg, Dan Boneh, et al. Location privacy via private proximity testing. In NDSS, 2011. Search in Google Scholar

[35] Diem open-source contributors. Diem blockchain hash function support. https://github.com/diem/diem, 2021. Search in Google Scholar

[36] Andrew Poelstra. Mimblewimble. 2016. Search in Google Scholar

[37] Ronald L Rivest and Adi Shamir. Payword and micromint: Two simple micropayment schemes. In International workshop on security protocols. Springer, 1996. Search in Google Scholar

[38] Naveen Sastry, Umesh Shankar, and David Wagner. Secure verification of location claims. In Proceedings of the 2nd ACM workshop on Wireless security, pages 1–10, 2003. Search in Google Scholar

[39] Dave Singelee and Bart Preneel. Location verification using secure distance bounding protocols. In Mobile Adhoc and Sensor Systems Conference, 2005. Search in Google Scholar

[40] Henry de Valence. Accelerating edwards curve arithmetic with parallel formulas. https://medium.com/@hdevalence/accelerating-edwards-curve-arithmetic-with-parallel-formulas-ac12cf5015be, 2018. Search in Google Scholar

[41] William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 1961. Search in Google Scholar

[42] Adnan Vora and Mikhail Nesterenko. Secure location verification using radio broadcast. IEEE Transactions on Dependable and Secure Computing, 3(4):377–385, 2006. Search in Google Scholar

[43] Gavin Wood et al. Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper, 151(2014):1–32, 2014. Search in Google Scholar

[44] Ching-Nung Yang and Hsu-Tun Teng. An efficient method for finding minimum hash chain of multi-payword chains in micropayment. In CEC ’03, pages 45–48. IEEE, 2003. Search in Google Scholar

[45] Rupeng Yang, Qiuliang Xu, Man Ho Au, Zuoxia Yu, Hao Wang, and Lu Zhou. Position based cryptography with location privacy: A step for fog computing. Future Generation Computer Systems, 78:799–806, 2018. Search in Google Scholar

[46] Mingwu Zhang and Tsuyoshi Takagi. Geoenc: Geometric area based keys and policies in functional encryption systems. In ASICP, 2011. Search in Google Scholar

[47] Yanchao Zhang, Wei Liu, Yuguang Fang, and Dapeng Wu. Secure localization and authentication in ultra-wideband sensor networks. IEEE J. Sel. Areas Commun, 2006. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo