Indistinguishability Obfuscation from Ring Key-Homomorphic Weak PRFs

A weak pseudorandom function F: K x X -> 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 + k_2, x) and F(k_1 . k_{2}, x) where "+" and "." are the addition and multiplication operations in the ring K, respectively. A recent work by Alamati et al. (CT-RSA' 23) initiated the study of ring key-homomorphic weak PRFs (RKHwPRFs) and showed that any RKHwPRF can be used to construct multiparty noninteractive key exchange (NIKE) for an arbitrary number of parties. In this work, we show that any RKHwPRF can, in fact, be used to construct indistinguishability obfuscation (iO) for all circuits in NC1, which in turn can be bootstrapped to all polynomial-size circuits using standard techniques. The proof of security for our iO construction is in the standard model, and our assumptions (including weakenings of RKHwPRFs) are program-independent.

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, notably 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 result in a sense completes the work initiated by Alamati et al. (Eurocrypt' 19, JoC '23) on building cryptosystems from generic Minicrypt primitives with structure. Given our construction of iO from RKHwPRFs, 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.