**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.

**Category / Keywords: **foundations / Correlation Intractability

**Date: **received 2 Nov 2020, last revised 2 Nov 2020

**Contact author: **alexjl at mit edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20201110:123024 (All versions of this report)

**Short URL: **ia.cr/2020/1378

[ Cryptology ePrint archive ]