{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T16:37:05Z","timestamp":1770223025073,"version":"3.49.0"},"reference-count":47,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"4","license":[{"start":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T00:00:00Z","timestamp":1626998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,10,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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 \u201ccredential-based\u201d 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.<\/jats:p>","DOI":"10.2478\/popets-2021-0061","type":"journal-article","created":{"date-parts":[[2021,7,24]],"date-time":"2021-07-24T23:17:28Z","timestamp":1627168648000},"page":"76-95","source":"Crossref","is-referenced-by-count":8,"title":["HashWires: Hyperefficient Credential-Based Range Proofs"],"prefix":"10.56553","volume":"2021","author":[{"given":"Konstantinos","family":"Chalkias","sequence":"first","affiliation":[{"name":"Novi \/ Facebook"}]},{"given":"Shir","family":"Cohen","sequence":"additional","affiliation":[{"name":"Novi \/ Facebook \/ Technion"}]},{"given":"Kevin","family":"Lewi","sequence":"additional","affiliation":[{"name":"Novi \/ Facebook"}]},{"given":"Fredric","family":"Moezinia","sequence":"additional","affiliation":[{"name":"Novi \/ Facebook"}]},{"given":"Yolan","family":"Romailler","sequence":"additional","affiliation":[{"name":"Novi \/ Facebook \/ Kudelski Security"}]}],"member":"35752","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"2022060519474103865_j_popets-2021-0061_ref_001","doi-asserted-by":"crossref","unstructured":"[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\u2013151. Springer, 2001.10.1007\/3-540-44987-6_9","DOI":"10.1007\/3-540-44987-6_9"},{"key":"2022060519474103865_j_popets-2021-0061_ref_002","doi-asserted-by":"crossref","unstructured":"[2] Sebastian Angel and Michael Walfish. Verifiable auctions for online ad exchanges. In ACM SIGCOMM, 2013.10.1145\/2486001.2486038","DOI":"10.1145\/2486001.2486038"},{"key":"2022060519474103865_j_popets-2021-0061_ref_003","doi-asserted-by":"crossref","unstructured":"[3] Foteini Baldimtsi and Anna Lysyanskaya. Anonymous credentials light. In Proceedings of the 2013 ACM SIGSAC conference on Computer & Communications Security, 2013.10.1145\/2508859.2516687","DOI":"10.1145\/2508859.2516687"},{"key":"2022060519474103865_j_popets-2021-0061_ref_004","unstructured":"[4] Dan Boneh and Victor Shoup. A graduate course in applied cryptography. 2020."},{"key":"2022060519474103865_j_popets-2021-0061_ref_005","doi-asserted-by":"crossref","unstructured":"[5] Fabrice Boudot. Efficient proofs that a committed number lies in an interval. In EUROCRYPT \u201900, 2000.10.1007\/3-540-45539-6_31","DOI":"10.1007\/3-540-45539-6_31"},{"key":"2022060519474103865_j_popets-2021-0061_ref_006","doi-asserted-by":"crossref","unstructured":"[6] Stefan Brands. Untraceable off-line cash in wallet with observers. In Annual international cryptology conference, pages 302\u2013318. Springer, 1993.10.1007\/3-540-48329-2_26","DOI":"10.1007\/3-540-48329-2_26"},{"key":"2022060519474103865_j_popets-2021-0061_ref_007","unstructured":"[7] Stefan Brands and David Chaum. Distance-bounding protocols. In EUROCRYPT, 1993."},{"key":"2022060519474103865_j_popets-2021-0061_ref_008","unstructured":"[8] William J Buchanan. Zero-knowledge proof: Proving age with hash chains. Asecuritysite: https:\/\/asecuritysite.com\/encryption\/age, 2021."},{"key":"2022060519474103865_j_popets-2021-0061_ref_009","doi-asserted-by":"crossref","unstructured":"[9] Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas H\u00fclsing, and Markus R\u00fcckert. On the security of the winter-nitz one-time signature scheme. In AFRICACRYPT, 2011.10.1007\/978-3-642-21969-6_23","DOI":"10.1007\/978-3-642-21969-6_23"},{"key":"2022060519474103865_j_popets-2021-0061_ref_010","doi-asserted-by":"crossref","unstructured":"[10] Benedikt B\u00fcnz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Gregory Maxwell. Bulletproofs: Short proofs for confidential transactions and more. In IEEE S&P, 2018.10.1109\/SP.2018.00020","DOI":"10.1109\/SP.2018.00020"},{"key":"2022060519474103865_j_popets-2021-0061_ref_011","doi-asserted-by":"crossref","unstructured":"[11] Jan Camenisch, Rafik Chaabouni, et al. Efficient protocols for set membership and range proofs. In ASIACRYPT, 2008.10.1007\/978-3-540-89255-7_15","DOI":"10.1007\/978-3-540-89255-7_15"},{"key":"2022060519474103865_j_popets-2021-0061_ref_012","doi-asserted-by":"crossref","unstructured":"[12] Jan Camenisch and Anna Lysyanskaya. An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In EUROCRYPT, 2001.10.1007\/3-540-44987-6_7","DOI":"10.1007\/3-540-44987-6_7"},{"key":"2022060519474103865_j_popets-2021-0061_ref_013","doi-asserted-by":"crossref","unstructured":"[13] Srdjan \u010capkun, Mario \u010cagalj, and Mani Srivastava. Secure localization with hidden and mobile base stations. In in Proceedings of IEEE INFOCOM. Citeseer, 2006.10.1109\/INFOCOM.2006.302","DOI":"10.1109\/INFOCOM.2006.302"},{"key":"2022060519474103865_j_popets-2021-0061_ref_014","unstructured":"[14] Konstantinos Chalkias. Secure cryptographic protocols and applications based on bilinear pairings. 2010."},{"key":"2022060519474103865_j_popets-2021-0061_ref_015","unstructured":"[15] Konstantinos Chalkias, Kevin Lewi, Payman Mohassel, and Valeria Nikolaenko. Distributed auditing proofs of liabilities. ZKProof, 2020."},{"key":"2022060519474103865_j_popets-2021-0061_ref_016","doi-asserted-by":"crossref","unstructured":"[16] Nishanth Chandran, Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky. Position based cryptography. In Annual International Cryptology Conference, 2009.10.1007\/978-3-642-03356-8_23","DOI":"10.1007\/978-3-642-03356-8_23"},{"key":"2022060519474103865_j_popets-2021-0061_ref_017","unstructured":"[17] David Chaum, Ronald L. Rivest, and Alan T. Sherman, editors. CRYPTO\u201982. Plenum Press, New York, USA, 1982."},{"key":"2022060519474103865_j_popets-2021-0061_ref_018","doi-asserted-by":"crossref","unstructured":"[18] Gaby G Dagher, Benedikt B\u00fcnz, Joseph Bonneau, Jeremy Clark, and Dan Boneh. Provisions: Privacy-preserving proofs of solvency for bitcoin exchanges. In ACM CCS, 2015.10.1145\/2810103.2813674","DOI":"10.1145\/2810103.2813674"},{"key":"2022060519474103865_j_popets-2021-0061_ref_019","doi-asserted-by":"crossref","unstructured":"[19] Ivan Damg\u00e5rd. Practical and provably secure release of a secret and exchange of signatures. J. Cryptol., 1995.10.1007\/BF00191356","DOI":"10.1007\/BF00191356"},{"key":"2022060519474103865_j_popets-2021-0061_ref_020","unstructured":"[20] Ankur Shah Delight. Zero knowledge proof of age using hash chains, 2017."},{"key":"2022060519474103865_j_popets-2021-0061_ref_021","doi-asserted-by":"crossref","unstructured":"[21] David Derler, Christian Hanser, and Daniel Slamanig. Revisiting cryptographic accumulators, additional properties and relations to other primitives. In CT-RSA, 2015.10.1007\/978-3-319-16715-2_7","DOI":"10.1007\/978-3-319-16715-2_7"},{"key":"2022060519474103865_j_popets-2021-0061_ref_022","doi-asserted-by":"crossref","unstructured":"[22] Chris Dods, Nigel P Smart, and Martijn Stam. Hash based digital signature schemes. In IMA International Conference on Cryptography and Coding, pages 96\u2013115. Springer, 2005.10.1007\/11586821_8","DOI":"10.1007\/11586821_8"},{"key":"2022060519474103865_j_popets-2021-0061_ref_023","unstructured":"[23] Novi Financial. Hashwires rust implementation. https:\/\/github.com\/novifinancial\/hashwires, 2021."},{"key":"2022060519474103865_j_popets-2021-0061_ref_024","doi-asserted-by":"crossref","unstructured":"[24] Eiichiro Fujisaki and Tatsuaki Okamoto. Statistical zero knowledge protocols to prove modular polynomial relations. In CRYPTO \u201997, volume 1294, pages 16\u201330. Springer, 1997.10.1007\/BFb0052225","DOI":"10.1007\/BFb0052225"},{"key":"2022060519474103865_j_popets-2021-0061_ref_025","doi-asserted-by":"crossref","unstructured":"[25] Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. J. ACM, 33(4):792\u2013807, 1986.10.1145\/6490.6503","DOI":"10.1145\/6490.6503"},{"key":"2022060519474103865_j_popets-2021-0061_ref_026","doi-asserted-by":"crossref","unstructured":"[26] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. In SIAM Journal on computing 18.1, pages 186\u2013208, 1989.10.1137\/0218012","DOI":"10.1137\/0218012"},{"key":"2022060519474103865_j_popets-2021-0061_ref_027","unstructured":"[27] Matthew Green. Winternitz checksum. https:\/\/blog.cryptographyengineering.com\/winternitz-checksum, 2021."},{"key":"2022060519474103865_j_popets-2021-0061_ref_028","doi-asserted-by":"crossref","unstructured":"[28] Jens Groth. On the size of pairing-based non-interactive arguments. In EUROCRYPT \u201916. Springer, 2016.10.1007\/978-3-662-49896-5_11","DOI":"10.1007\/978-3-662-49896-5_11"},{"key":"2022060519474103865_j_popets-2021-0061_ref_029","unstructured":"[29] Hudson Jameson. Which cryptographic hash function does ethereum use? https:\/\/ethereum.stackexchange.com\/questions\/550, 2016."},{"key":"2022060519474103865_j_popets-2021-0061_ref_030","unstructured":"[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."},{"key":"2022060519474103865_j_popets-2021-0061_ref_031","unstructured":"[31] Gregory Maxwell, 2016. https:\/\/people.xiph.org\/~greg\/confidential_values.txt."},{"key":"2022060519474103865_j_popets-2021-0061_ref_032","doi-asserted-by":"crossref","unstructured":"[32] Ralph C Merkle. A certified digital signature. In CRYPTO, pages 218\u2013238. Springer, 1989.10.1007\/0-387-34805-0_21","DOI":"10.1007\/0-387-34805-0_21"},{"key":"2022060519474103865_j_popets-2021-0061_ref_033","doi-asserted-by":"crossref","unstructured":"[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.","DOI":"10.1007\/s42452-019-0989-z"},{"key":"2022060519474103865_j_popets-2021-0061_ref_034","unstructured":"[34] Arvind Narayanan, Narendran Thiagarajan, Mugdha Lakhani, Michael Hamburg, Dan Boneh, et al. Location privacy via private proximity testing. In NDSS, 2011."},{"key":"2022060519474103865_j_popets-2021-0061_ref_035","unstructured":"[35] Diem open-source contributors. Diem blockchain hash function support. https:\/\/github.com\/diem\/diem, 2021."},{"key":"2022060519474103865_j_popets-2021-0061_ref_036","unstructured":"[36] Andrew Poelstra. Mimblewimble. 2016."},{"key":"2022060519474103865_j_popets-2021-0061_ref_037","doi-asserted-by":"crossref","unstructured":"[37] Ronald L Rivest and Adi Shamir. Payword and micromint: Two simple micropayment schemes. In International workshop on security protocols. Springer, 1996.10.1007\/3-540-62494-5_6","DOI":"10.1007\/3-540-62494-5_6"},{"key":"2022060519474103865_j_popets-2021-0061_ref_038","doi-asserted-by":"crossref","unstructured":"[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\u201310, 2003.10.1145\/941311.941313","DOI":"10.1145\/941311.941313"},{"key":"2022060519474103865_j_popets-2021-0061_ref_039","unstructured":"[39] Dave Singelee and Bart Preneel. Location verification using secure distance bounding protocols. In Mobile Adhoc and Sensor Systems Conference, 2005."},{"key":"2022060519474103865_j_popets-2021-0061_ref_040","unstructured":"[40] Henry de Valence. Accelerating edwards curve arithmetic with parallel formulas. https:\/\/medium.com\/@hdevalence\/accelerating-edwards-curve-arithmetic-with-parallel-formulas-ac12cf5015be, 2018."},{"key":"2022060519474103865_j_popets-2021-0061_ref_041","doi-asserted-by":"crossref","unstructured":"[41] William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 1961.10.1111\/j.1540-6261.1961.tb02789.x","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"},{"key":"2022060519474103865_j_popets-2021-0061_ref_042","doi-asserted-by":"crossref","unstructured":"[42] Adnan Vora and Mikhail Nesterenko. Secure location verification using radio broadcast. IEEE Transactions on Dependable and Secure Computing, 3(4):377\u2013385, 2006.10.1109\/TDSC.2006.57","DOI":"10.1109\/TDSC.2006.57"},{"key":"2022060519474103865_j_popets-2021-0061_ref_043","unstructured":"[43] Gavin Wood et al. Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper, 151(2014):1\u201332, 2014."},{"key":"2022060519474103865_j_popets-2021-0061_ref_044","unstructured":"[44] Ching-Nung Yang and Hsu-Tun Teng. An efficient method for finding minimum hash chain of multi-payword chains in micropayment. In CEC \u201903, pages 45\u201348. IEEE, 2003."},{"key":"2022060519474103865_j_popets-2021-0061_ref_045","doi-asserted-by":"crossref","unstructured":"[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\u2013806, 2018.","DOI":"10.1016\/j.future.2017.05.035"},{"key":"2022060519474103865_j_popets-2021-0061_ref_046","doi-asserted-by":"crossref","unstructured":"[46] Mingwu Zhang and Tsuyoshi Takagi. Geoenc: Geometric area based keys and policies in functional encryption systems. In ASICP, 2011.10.1007\/978-3-642-22497-3_16","DOI":"10.1007\/978-3-642-22497-3_16"},{"key":"2022060519474103865_j_popets-2021-0061_ref_047","doi-asserted-by":"crossref","unstructured":"[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.10.1109\/JSAC.2005.863855","DOI":"10.1109\/JSAC.2005.863855"}],"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.sciendo.com\/pdf\/10.2478\/popets-2021-0061","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T16:31:39Z","timestamp":1658334699000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2021\/popets-2021-0061.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,23]]},"references-count":47,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,7,23]]},"published-print":{"date-parts":[[2021,10,1]]}},"alternative-id":["10.2478\/popets-2021-0061"],"URL":"https:\/\/doi.org\/10.2478\/popets-2021-0061","relation":{},"ISSN":["2299-0984"],"issn-type":[{"value":"2299-0984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,23]]}}}