Aarhus University Seal

Property-Preserving Hash Functions for Hamming Distance from Standard Assumptions

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Nils Fleischhacker, Ruhr University Bochum
  • ,
  • Kasper Green Larsen
  • Mark Simkin, Ethereum Foundation

Property-preserving hash functions allow for compressing long inputs x0 and x1 into short hashes h(x0) and h(x1) in a manner that allows for computing a predicate P(x0, x1) given only the two hash values without having access to the original data. Such hash functions are said to be adversarially robust if an adversary that gets to pick x0 and x1 after the hash function has been sampled, cannot find inputs for which the predicate evaluated on the hash values outputs the incorrect result. In this work we construct robust property-preserving hash functions for the hamming-distance predicate which distinguishes inputs with a hamming distance at least some threshold t from those with distance less than t. The security of the construction is based on standard lattice hardness assumptions. Our construction has several advantages over the best known previous construction by Fleischhacker and Simkin (Eurocrypt 2021). Our construction relies on a single well-studied hardness assumption from lattice cryptography whereas the previous work relied on a newly introduced family of computational hardness assumptions. In terms of computational effort, our construction only requires a small number of modular additions per input bit, whereas the work of Fleischhacker and Simkin required several exponentiations per bit as well as the interpolation and evaluation of high-degree polynomials over large fields. An additional benefit of our construction is that the description of the hash function can be compressed to λ bits assuming a random oracle. Previous work has descriptions of length O(ℓλ) bits for input bit-length ℓ. We prove a lower bound on the output size of any property-preserving hash function for the hamming distance predicate. The bound shows that the size of our hash value is not far from optimal.

Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2022 : 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2022, Proceedings
EditorsOrr Dunkelman, Stefan Dziembowski
Number of pages18
PublisherSpringer
Publication yearMay 2022
Pages764-781
ISBN (print)9783031070846
ISBN (Electronic)978-3-031-07085-3
DOIs
Publication statusPublished - May 2022
Event41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022 - Trondheim, Norway
Duration: 30 May 20223 Jun 2022

Conference

Conference41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022
LandNorway
ByTrondheim
Periode30/05/202203/06/2022
SeriesLecture Notes in Computer Science (LNCS)
Volume13276
ISSN0302-9743

Bibliographical note

Publisher Copyright:
© 2022, International Association for Cryptologic Research.

See relations at Aarhus University Citationformats

ID: 276791406