CryptoDB
Succinct PPRFs via Memory-Tight Reductions
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | Several recent works have shown lower bounds on the communication cost of secure messaging protocols based on specific primitives. However, these bounds no longer apply if stronger primitives are allowed, such as succinct multi-party non-interactive key exchange (SMNIKE). This is a setup-free primitive where all messages are independent of the number $N$ of parties. Boneh and Zhandry (BZ, CRYPTO'14) present an iO-based MNIKE whose setup (or one message from a designated party) depends on $N$, but all other messages are short. SMNIKE is a strengthening of their primitive that forgoes the setup and where no message depends on $N$, thereby enabling applications in secure messaging. Jain and Jin (JJ, FOCS'22) build indistinguishability obfuscation (iO) for Turing machines with unbounded input length, opening the possibility of SMNIKE via iO and puncturable PRFs (PPRFs). Unfortunately, the punctured keys of known PPRFs grow with their input length $n$; e.g., for the Goldreich--Goldwasser--Micali (GGM) PPRF they have size $n \lambda$. We introduce succinct PPRFs (SPPRFs), a weakened form of PPRFs satisfying a relaxed correctness notion. Notably, SPPRFs have punctured keys whose size is independent of the input size, as long as the punctured point has a short description. We then combine SPPRFs with JJ to show that a variant of the BZ construction is an SMNIKE. At the heart of our SPPRF construction is a novel memory-tight reduction for GGM. While the original GGM reduction requires space $q \lambda$, our proof only needs $5 \lambda$ memory, where $q$ is the number of PRF queries. Our technique allows to show that GGM is an SPPRF, and also that GGM as a (standard) PRF has a memory-tight reduction against adversaries that do not repeat oracle queries, a restriction we prove to be inherent. |
BibTeX
@inproceedings{crypto-2025-35802,
title={Succinct PPRFs via Memory-Tight Reductions},
publisher={Springer-Verlag},
author={Joël Alwen and Chris Brzuska and Jérôme Govinden and Patrick Harasser and Stefano Tessaro},
year=2025
}