Paper 2020/606

Ring Key-Homomorphic Weak PRFs and Applications

Navid Alamati and Hart Montgomery and Sikhar Patranabis

Abstract

A weak pseudorandom function $F: K \times X \to Y$ is said to be ring key-homomorphic if, given $F(k_1, x)$ and $F(k_2, x)$, there are efficient algorithms to compute $F(k_1 \oplus k_2, x)$ and $F(k_1 \otimes k_2, x)$ where $\oplus$ and $\otimes$ are the addition and multiplication operations in the ring $K$, respectively. In this work, we initiate the study of ring key-homomorphic weak PRFs (RKHwPRFs). In particular, we show that the following primitives can be constructed from any RKHwPRF: - Multiparty non-interactive key exchange (NIKE) for an arbitrary number of parties. - Indistinguishability obfuscation for all circuits in NC_1. Our proofs are in the standard model, and the proof for our iO scheme is program-independent. Our iO scheme can also be bootstrapped to all polynomial-size circuits using standard techniques. We also consider restricted versions of RKHwPRFs that are structurally weaker than a classic RKHwPRF but suffice for all our constructions. We show how to instantiate these restricted RKHwPRFs from various multilinear maps and associated assumptions. Our framework gives several new results, such as: - The first iO scheme that relies only on SXDH over any asymmetric multilinear map without additional assumptions. - The first iO scheme that relies only on DLIN (or more generally Matrix-DDH) over any (even symmetric) multilinear map without additional assumptions. - The first iO scheme that relies on SXDH over the multilinear map presented by Ma and Zhandry (TCC'18) (the authors only presented a NIKE protocol in their paper). To our knowledge, this candidate multilinear map has not been successfully cryptanalyzed, and the SXDH assumption plausibly holds over it. Our analysis of RKHwPRFs in a sense completes the work initiated by Alamati et al. (EUROCRYPT'19) on building cryptosystems from generic Minicrypt primitives with structure. With our results, almost all of the major known cryptosystems can be built from a weak PRF with either a group or ring homomorphism over either the input space or the key space. Thus, a major contribution of this work is advancing the study of the relationship between structure and cryptography.

Note: Fixed minor typos in Section 9