Paper 2022/1146

A Sponge-Based PRF with Good Multi-user Security

Abstract

Both multi-user PRFs and sponge-based constructions have generated a lot of research interest lately. Dedicated analyses for multi-user security have improved the bounds a long distance from the early generic bounds obtained through hybrid arguments, yet the bounds generally don't allow the number of users to be more than birthday-bound in key-size. Similarly, known sponge constructions suffer from being only birthday-bound secure in terms of their capacity. We present in this paper $$, a multi-user PRF built from a random permutation using a full-state sponge with feed-forward, which uses a combination of the user keys and unique user IDs to solve both the problems mentioned by improving the security bounds for multi-user constructions and sponge constructions. For $$ construction query blocks and $$ permutation queries, with key-size $$ and tag-size $$ = $$ (where $$ is the state-size or the size of the underlying permutation), both $$ and $$ must touch birthday bound in $$ in order to distinguish $$ from a random function.