### Property-Preserving Hash Functions and Combinatorial Group Testing

Kazuhiko Minematsu

##### Abstract

Property-preserving hash (PPH) function is a class of hash functions that allows an evaluation of the property of inputs from their hash values. Boyle et al. at ITCS 2019 recently introduced it and considered the robustness of PPH against an adversary who accesses the internal randomness of PPH, and proposed two robust PPH constructions for a weak form of Hamming distance predicate. The second construction received attention for its short hash value, although it relies on an ad-hoc security assumption. The first construction, which is entirely hash-based and based on the classical collision-resistance assumption, has been largely overlooked. We study their first construction and discover its close connection to a seemingly different field of hash/MAC-based (adversarial) error detection using the theory of Combinatorial Group Testing (CGT). We show some consequences of this discovery. In particular, we show that some existing proposals in the field of CGT-based error detection can be converted into a PPH for the Hamming distance property, and they immediately improve and generalize Boyle et al.'s hash-based PPH proposal. We also show that the idea of Boyle et al. is useful in the context of a variant of CGT problem.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. ITC 2022
Keywords
Hash functionProperty-Preserving HashCombinatorial Group TestingProvable Security
Contact author(s)
k-minematsu @ nec com
History
Short URL
https://ia.cr/2022/478

CC BY

BibTeX

@misc{cryptoeprint:2022/478,
author = {Kazuhiko Minematsu},
title = {Property-Preserving Hash Functions and Combinatorial Group Testing},
howpublished = {Cryptology ePrint Archive, Paper 2022/478},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/478}},
url = {https://eprint.iacr.org/2022/478}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.