Welcome to the resource topic for 2020/1378
Title:
Correlation-Intractable Hash Functions via Shift-Hiding
Authors: Alex Lombardi, Vinod Vaikuntanathan
Abstract:A hash function family \mathcal{H} is correlation intractable for a t-input relation \mathcal{R} if, given a random function h chosen from \mathcal{H}, it is hard to find x_1,\ldots,x_t such that \mathcal{R}(x_1,\ldots,x_t,h(x_1),\ldots,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.
ePrint: https://eprint.iacr.org/2020/1378
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .