Paper 2020/1378

Multi-Input Correlation-Intractable Hash Functions via Shift-Hiding

Alex Lombardi and 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. Recent works have constructed correlation-intractable hash families for single-input relations from standard cryptographic assumptions. However, the case of multi-input relations (even for $t=2$) is wide open: there are two known constructions, the first of which relies on a very strong ``brute-force-is-best'' type of hardness assumption (Holmgren and Lombardi, FOCS 2018); and the second only achieves the much weaker notion of output intractability (Zhandry, CRYPTO 2016). Our main result is the construction of several multi-input correlation intractable hash families for large classes of interesting input-dependent relations from either the learning with errors (LWE) assumption or from indistinguishability obfuscation. Our constructions follow from a simple and modular approach to constructing correlation-intractable hash functions using shift-hiding shiftable functions (Peikert-Shiehian, PKC 2018). This approach also gives an alternative framework (as compared to Peikert-Shiehian, CRYPTO 2019) for achieving single-input correlation intractability (and NIZKs for NP) based on LWE.