License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2022.2
URN: urn:nbn:de:0030-drops-164809
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16480/
Go to the corresponding LIPIcs Volume Portal

Minematsu, Kazuhiko

Property-Preserving Hash Functions and Combinatorial Group Testing

pdf-format:
LIPIcs-ITC-2022-2.pdf (0.9 MB)

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.

BibTeX - Entry

@InProceedings{minematsu:LIPIcs.ITC.2022.2,
  author =	{Minematsu, Kazuhiko},
  title =	{{Property-Preserving Hash Functions and Combinatorial Group Testing}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{2:1--2:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-238-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{230},
  editor =	{Dachman-Soled, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16480},
  URN =		{urn:nbn:de:0030-drops-164809},
  doi =		{10.4230/LIPIcs.ITC.2022.2},
  annote =	{Keywords: Hash function, Property-Preserving Hash, Combinatorial Group Testing, Provable Security}
}

Keywords: Hash function, Property-Preserving Hash, Combinatorial Group Testing, Provable Security
Collection: 3rd Conference on Information-Theoretic Cryptography (ITC 2022)
Issue Date: 2022
Date of publication: 30.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI