Paper 2025/766

Unbiasable Verifiable Random Functions from Generic Assumptions

Abstract

We present conceptually simple constructions of verifiable random functions (VRF) that fulfill strong notions of unbiasability recently introduced by Giunta and Stewart [EC:GS24]. VRFs with such strong properties were previously only known in the random oracle model or from the decisional Diffie–Hellman assumption with preprocessing. In contrast, our constructions are based on generic assumptions and are thus the first to be plausibly post-quantum secure. Moreover, our constructions fulfill several additional properties such as: • If the underlying VRF is aggregate, key-homomorphic or computable in ${\mathsf{NC}}^1$, then so is our VRF. • For any verification key, the VRF output has almost the same min-entropy as the VRF input. Lastly, we outline a path towards a lattice-based VRF (without setup).