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.ITCS.2022.102
URN: urn:nbn:de:0030-drops-156981
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15698/
Go to the corresponding LIPIcs Volume Portal

Lombardi, Alex ; Vaikuntanathan, Vinod

Correlation-Intractable Hash Functions via Shift-Hiding

pdf-format:
LIPIcs-ITCS-2022-102.pdf (0.7 MB)

Abstract

A hash function family ℋ is correlation intractable for a t-input relation ℛ if, given a random function h chosen from ℋ, it is hard to find x_1,…,x_t such that ℛ(x_1,…,x_t,h(x₁),…,h(x_t)) is true. Among other applications, such hash functions are a crucial tool for instantiating the Fiat-Shamir heuristic in the plain model, including the only known NIZK for NP based on the learning with errors (LWE) problem (Peikert and Shiehian, CRYPTO 2019).
We give a conceptually simple and generic construction of single-input CI hash functions from shift-hiding shiftable functions (Peikert and Shiehian, PKC 2018) satisfying an additional one-wayness property. This results in a clean abstract framework for instantiating CI, and also shows that a previously existing function family (PKC 2018) was already CI under the LWE assumption.
In addition, our framework transparently generalizes to other settings, yielding new results:
- We show how to instantiate certain forms of multi-input CI under the LWE assumption. Prior constructions either relied on a very strong "brute-force-is-best" type of hardness assumption (Holmgren and Lombardi, FOCS 2018) or were restricted to "output-only" relations (Zhandry, CRYPTO 2016).
- We construct single-input CI hash functions from indistinguishability obfuscation (iO) and one-way permutations. Prior constructions relied essentially on variants of fully homomorphic encryption that are impossible to construct from such primitives. This result also generalizes to more expressive variants of multi-input CI under iO and additional standard assumptions.

BibTeX - Entry

@InProceedings{lombardi_et_al:LIPIcs.ITCS.2022.102,
  author =	{Lombardi, Alex and Vaikuntanathan, Vinod},
  title =	{{Correlation-Intractable Hash Functions via Shift-Hiding}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{102:1--102:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15698},
  URN =		{urn:nbn:de:0030-drops-156981},
  doi =		{10.4230/LIPIcs.ITCS.2022.102},
  annote =	{Keywords: Cryptographic hash functions, correlation intractability}
}

Keywords: Cryptographic hash functions, correlation intractability
Collection: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Issue Date: 2022
Date of publication: 25.01.2022

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