Paper 2020/606

Multiparty Noninteractive Key Exchange from Ring Key-Homomorphic Weak PRFs

Abstract

A weak pseudorandom function $F: \mathcal{K} \times \mathcal{X} \rightarrow \mathcal{Y}$ is said to be ring key-homomorphic if, given $F \left(k_{1}, x \right)$ and $F \left(k_{2}, x \right)$, there are efficient algorithms to compute $F \left(k_{1} \oplus k_{2}, x \right)$ and $F \left(k_{1} \otimes k_{2}, x \right)$ where $\oplus$ and $\otimes$ are the addition and multiplication operations in the ring $\mathcal{K}$, respectively. In this work, we initiate the study of ring key-homomorphic weak PRFs (RKHwPRFs). As our main result, we show that any RKHwPRF implies multiparty noninteractive key exchange (NIKE) for an arbitrary number of parties in the standard model. Our analysis of RKHwPRFs in a sense takes a major step towards the goal of building cryptographic primitives from Minicrypt primitives with structure, which has been studied in a recent line of works. With our result, most of the well-known asymmetric cryptographic primitives can be built from a weak PRF with either a group or ring homomorphism over either the input space or the key space.