Welcome to the resource topic for 2020/606
Title:
Ring Key-Homomorphic Weak PRFs and Applications
Authors: Navid Alamati, Hart Montgomery, 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.
ePrint: https://eprint.iacr.org/2020/606
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .