Unique aggregate signatures with appli- cations to distributed verifiable random functions.
Veronika Kuchta, Mark Manulis · 2013
Abstract. The computation process of a Distributed Verifiable Random Function (DVRF) on some input specified by the user involves multiple, possibly malicious servers, and results in a publicly verifiable pseudoran-dom output to the user. Previous DVRF constructions assumed trusted generation of secret keys for the servers and imposed a threshold on the number of corrupted servers. In this paper we propose the first generic approach for building DVRFs, under much weaker setup assumptions, where we only require existence of a shared random string. More precisely, we first aim at constructions of Distributed Verifiable Unpredictable Functions (DVUF) that can then be converted to DVRF using inner products with a random string as spec-ified by Micali, Rabin, and Vadhan (FOCS’99) for the non-distributed VUF/VRF case. Our main contribution are generic DVUF constructions from aggregate signatures that satisfy the property of uniqueness. We define unique-ness for two flavors of aggregate signatures (with public and sequen-tial aggregation) and show that both flavors can be used to obtain DVUF. By proving uniqueness of existing pairing-based aggregate sig-nature schemes we immediately obtain several concrete communication-efficient DVUF/DVRF instantiations. 1