Exponent-VRFs and Their Applications

. Verifiable random functions (VRFs) are pseudorandom functions with the addition that the function owner can prove that a generated output is correct (i.e., generated correctly relative to a committed key). In this paper we introduce the notion of an exponent-VRF (eVRF) : a VRF that does not provide its output y explicitly, but instead provides Y = y · G where G is a generator of some finite cyclic group (or Y = g y in multiplicative notation). We construct eVRFs from DDH and from the Paillier encryption scheme (both in the random-oracle model). We then show that an eVRF can be used to solve several long-standing open problems in threshold cryptography. In particular, we construct (1) a one-round fully simulatable distributed key-generation protocols (after a single two-round initialization phase), (2) a two-round fully simulatable signing protocols for multiparty Schnorr with a deterministic variant, (3) a two-party ECDSA protocol that has a deterministic variant, (4) a threshold Schnorr signing where the parties can later prove that they signed without being able to frame another group, (5) an MPC-friendly and verifiable HD-derivation. Efficient simulatable protocols of this round complexity were not known prior to this work. All of our protocols are concretely efficient.

可验证随机函数（VRFs）是一种伪随机函数，其额外特性是函数所有者能够证明所生成的输出是正确的（即相对于一个已承诺的密钥正确生成）。在本文中，我们引入指数 - 可验证随机函数（eVRF）的概念：一种不明确提供其输出y，而是提供Y = y·G的可验证随机函数，其中G是某个有限循环群的生成元（或者在乘法表示中为Y = g^y）。我们从判定性Diffie - Hellman问题（DDH）以及Paillier加密方案（两者均在随机预言模型中）构建eVRF。然后我们表明，eVRF可用于解决门限密码学中几个长期存在的开放性问题。特别是，我们构建了（1）一轮完全可模拟的分布式密钥生成协议（在一个两轮的初始化阶段之后），（2）用于多方Schnorr的两轮完全可模拟签名协议及其确定性变体，（3）具有确定性变体的两方ECDSA协议，（4）一种门限Schnorr签名，其中各方之后能够证明他们进行了签名而无法诬陷另一个群组，（5）一种对多方计算友好且可验证的分层确定性（HD）派生。在此项工作之前，这种轮复杂度的高效可模拟协议是未知的。我们所有的协议在具体实现上都是高效的。