Succinct PPRFs via Memory-Tight Reductions

Abstract

Several recent works have established lower bounds on the communication cost of secure messaging protocols using only selected primitives. We argue that these bounds no longer apply if succinct noninteractive multi-party key exchange (SMNIKE) exists, a setup-free primitive where no party’s message depends on the number of parties. Boneh and Zhandry (CRYPTO 2014) present an iO-based multi-party NIKE construction where the setup (or a special party’s message) depends on the number of parties, and else, messages are short. SMNIKE is a strengthening of their primitive.

Jain and Jin (JJ, FOCS 2022) construct input-succinct indistinguishability obfuscation (iO) for Turing machines, opening the possibility of SMNIKE via iO. Unfortunately, the keys of known puncturable PRFs (PPRFs) grow with their input length n. For example, the punctured key of the Goldreich–Goldwasser–Micali (GGM) PPRF has size nλ.

We introduce succinct PPRFs, where the punctured key is of size 5λ and, in particular, independent of the input size, as long as the punctured point has a short description. We then show how to combine succinct PPRFs with JJ to show that a variant of the Boneh–Zhandry construction is already an SMNIKE.

At the heart of our succinct PPRF construction is a novel memorytight reduction for GGM. While the original GGM reduction requires nq game hops and space λq, our reduction needs 4qn game hops but only 5λ memory, where q is the number of PRF queries. Our proof technique allows to show that GGM is a succinct PPRF, and also that GGM as a (standard) PRF has a memory-tight reduction against adversaries who make non-repeating queries, a restriction that we prove to be inherent.

This is joint work with Joël Alwen (Amazon Research), Jérôme Govinden (TU Darmstadt), Patrick Harasser (TU Darmstadt) and Stefano Tessaro (U Washington).