Paper 2023/925

Homomorphic Indistinguishability Obfuscation and its Applications

Abstract

In this work, we propose the notion of homomorphic indistinguishability obfuscation ($\mathsf{HiO}$) and present a construction based on subexponentially-secure $\mathsf{iO}$ and one-way functions. An $\mathsf{HiO}$ scheme allows us to convert an obfuscation of circuit $C$ to an obfuscation of $C'\circ C$, and this can be performed obliviously (that is, without knowing the circuit $C$). A naive solution would be to obfuscate $C' \circ \mathsf{iO}(C)$. However, if we do this for $k$ hops, then the size of the final obfuscation is exponential in $k$. $\mathsf{HiO}$ ensures that the size of the final obfuscation remains polynomial after repeated compositions. As an application, we show how to build function-hiding hierarchical multi-input functional encryption and homomorphic witness encryption using $\mathsf{HiO}$.