Verifiable Random Functions from (Leveled) Multilinear Maps

Abstract

Verifiable random functions (VRFs), firstly proposed by Micali, Rabin, and Vadhan (FOCS 99), are pseudorandom functions with the additional property that the party holding the seed sk can generate a non-interactive, publicly verifiable proof $\pi$ for the statements “$F_{sk}(x)=y$”, for any input x. To date only a few VRF schemes are known and most known constructions either allow only a small input space, or don’t achieve full adaptive security under a non-interactive complexity assumption. The only known adaptively secure VRF scheme with exponentially-large input space is based on $\ell$-Decisional Diffie-Hellman Exponent assumption (Hohenberger and Waters, Eurocrypt 2010).

In this work, we present a VRF scheme which is proved adaptively secure for exponentially-large input spaces under (n, k)-Modified Multilinear Decisional Diffie-Hellman Exponent assumption. Our construction is directly derived from the construction of constrained VRFs given by Fuchsbauer (SCN 14) based on (leveled) multilinear-maps. Since in Fuchsbauer’s scheme the adaptive security is obtained via complexity leveraging, which leads to a security loss that is exponential in the input length. Our core idea is to apply a simulation technique similar to the VRF analysis of Hohenberger (Eurocrypt 2010), where we partition the input space into those for which we can provide a proof and those for which we cannot. We then show that with non-negligible probability, the adversary will only query us on inputs for which we can provide proofs, except for the challenge query, for which the proof is unknown.

This research is supported by the Strategy Pilot Project of Chinese Academy of Sciences (Grant No. Y2W0012203).

A Appendix

1.1 A.1 Proof of Lemma 1

Proof

In other words, the probability of the simulation not triggering a general abort is at least $\zeta _{\textsf {min}}$. This analysis follows that of [16], which we reproduce here for completeness. Without loss of generality, we can assume the adversary always makes the maximum number of queries Q (since the probability of not aborting increases with fewer queries). Fix an arbitrary $\mathbf {x}=(x^{(1)},\ldots , x^{(Q)}, x^*)\in \{0,1\}^{(Q+1)\times \ell }$. Then, with the probability over the choice of $\mathbf {r}$, t, we have that $\mathrm {Pr}[\overline{\textsf {abort}}~ \text {on}~\mathbf {x}]$ is

$$\begin{aligned} =&\mathrm {Pr}\big [C(x^*)= n~\wedge \bigwedge _{i=1}^{Q}K(x^{(i)})=1 \big ] \end{aligned}$$

(9)

$$\begin{aligned} =&\mathrm {Pr}\big [\bigwedge _{i=1}^{Q}K(x^{(i)})=1 \big ]\cdot \mathrm {Pr}\big [C(x^*)= n|\bigwedge _{i=1}^{Q}K(x^{(i)})=1 \big ]\end{aligned}$$

(10)

$$\begin{aligned} =&\big (1-\mathrm {Pr}\big [\bigwedge _{i=1}^{Q}K(x^{(i)})=0 \big ]\big )\cdot \mathrm {Pr}\big [C(x^*)= n|\bigwedge _{i=1}^{Q}K(x^{(i)})=1 \big ]\end{aligned}$$

(11)

$$\begin{aligned} \ge&\big (1-\sum _{i=1}^{Q}\mathrm {Pr}[K(x^{(i)})=0]\big )\cdot \mathrm {Pr}\big [C(x^*)= n|\bigwedge _{i=1}^{Q}K(x^{(i)})=1 \big ]\end{aligned}$$

(12)

$$\begin{aligned} =&\big (1-\frac{Q}{z}\big )\cdot \mathrm {Pr}\big [C(x^*)= n|\bigwedge _{i=1}^{Q}K(x^{(i)})=1 \big ]\end{aligned}$$

(13)

$$\begin{aligned} =&\big (1-\frac{Q}{z}\big )\cdot \mathrm {Pr}\big [zt + r' + \sum ^{\ell }_{i=1}r_{i,x^*_i}= n|\bigwedge _{i=1}^{Q}K(x^{(i)})=1 \big ]\end{aligned}$$

(14)

$$\begin{aligned} =&\frac{1}{\ell +1}\cdot \big (1-\frac{Q}{z}\big )\cdot \mathrm {Pr}\big [K(x^*)=0|\bigwedge _{i=1}^{Q}K(x^{(i)})=1 \big ]\end{aligned}$$

(15)

$$\begin{aligned} =&\frac{1}{\ell +1}\cdot \big (1-\frac{Q}{z}\big )\cdot \frac{\mathrm {Pr}\big [K(x^*)=0 \big ]\cdot \mathrm {Pr}\big [\bigwedge _{i=1}^{Q}K(x^{(i)})=1|K(x^*)=0 \big ]}{\mathrm {Pr}\big [\bigwedge _{i=1}^{Q}K(x^{(i)})=1 \big ]}\end{aligned}$$

(16)

$$\begin{aligned} \ge&\frac{1}{(\ell +1)z}\cdot \big (1-\frac{Q}{z}\big )\cdot \mathrm {Pr}\big [\bigwedge _{i=1}^{Q}K(x^{(i)})=1|K(x^*)=0 \big ]\end{aligned}$$

(17)

$$\begin{aligned} =&\frac{1}{(\ell +1)z}\cdot \big (1-\frac{Q}{z}\big )\cdot \big (1-\mathrm {Pr}\big [\bigvee _{i=1}^{Q}K(x^{(i)})=0|K(x^*)=0 \big ]\big )\end{aligned}$$

(18)

$$\begin{aligned} \ge&\frac{1}{(\ell +1)z}\cdot \big (1-\frac{Q}{z}\big )\cdot \big (1-\sum _{i=1}^{Q}\mathrm {Pr}\big [K(x^{(i)})=0|K(x^*)=0 \big ]\big )\end{aligned}$$

(19)

$$\begin{aligned} =&\frac{1}{(\ell +1)z}\cdot \big (1-\frac{Q}{z}\big )^2\end{aligned}$$

(20)

$$\begin{aligned} \ge&\frac{1}{(\ell +1)z}\cdot \big (1-\frac{2Q}{z}\big )\end{aligned}$$

(21)

$$\begin{aligned} =&\frac{1}{8Q(\ell +1)} \end{aligned}$$

(22)

Equations 13 and 17 derive from $\mathrm {Pr}[K(x^{i})=0]=\frac{1}{z}$ for any query $x^{i}$ and $\mathrm {Pr}[K(x^{*})=0]=\frac{1}{z}$ for any challenge $x^{*}$. Equation 15 gets a factor of $\frac{1}{\ell +1}$ from the simulator taking a guess of t. Equation 16 follows from Bayes’ Theorem. Equation 20 follows from the pairwise independence of the probabilities that $K(x^{i}) = 0$, $K(x^*)=0$ for any pair of queries $x^{i}\ne x^*$, since they will differ in at least one random $r_j$ value. Equation 22 follows from our setting of $z=4Q$.

1.2 A.2 Proof of Lemma 2

Proof

Let $\zeta _{x}=\zeta (\mathbf {x})$, as defined in Sect. 4, be the probability that a set of queries $\mathbf {x}$ do not cause a regular abort. In Game 2, $T=O(\epsilon ^{-2}\ln (\epsilon ^{-1})\zeta _{\textsf {min}}^{-1}\ln (\zeta _{\textsf {min}}^{-1}))$ samples are taken to approximate this value as $\zeta '_{x}$. By Chernoff Bounds, we have that for all $\mathbf {x}$

$$\begin{aligned} \mathrm {Pr}[T\zeta '_{x}< T\zeta _{x}(1-\frac{\epsilon }{8})]< e^{-[128\epsilon ^{-2}\ln ((\epsilon /8)^{-1})\zeta _{\textsf {min}}^{-1}\ln (\zeta _{\textsf {min}}^{-1})(\zeta _{\textsf {min}})(\epsilon /8)^{2}/2]}, \end{aligned}$$

which reduces to

$$\begin{aligned} \mathrm {Pr}[\zeta '_{x}< \zeta _{x}(1-\frac{\epsilon }{8})]< \frac{\epsilon }{8}\zeta _{\textsf {min}}. \end{aligned}$$

The probability of not aborting is equal to the probability of not regular aborting (RA) times the probability of not artificial aborting (AA). Recall that for a measured $\zeta '_{x}$ an artificial abort will not happen with probability $\frac{\zeta _{\textsf {min}}}{\zeta '_{x}}$. The probability of aborting is therefore

$$\begin{aligned} \mathrm {Pr}[\textsf {abort}]=&1- \mathrm {Pr}[\overline{\textsf {abort}}] = 1 - \mathrm {Pr}[\overline{\textsf {RA}}]\mathrm {Pr}[\overline{\textsf {AA}}]= 1- \zeta _{x}\mathrm {Pr}[\overline{\textsf {AA}}] \\ \ge&1-\zeta _{x}(\frac{\epsilon }{8}\zeta _{\textsf {min}}+\frac{\zeta _{\textsf {min}}}{\zeta _{x}(1-\epsilon /8)})\\ \ge&1-(\frac{\epsilon }{8}\zeta _{\textsf {min}}+\frac{\zeta _{\textsf {min}}}{1-\epsilon /8})\\ \ge&1-(\frac{\epsilon }{8}\zeta _{\textsf {min}}+\zeta _{\textsf {min}}(1+\frac{2\epsilon }{8}))\\ \ge&1-\zeta _{\textsf {min}}-\frac{2\epsilon }{8}\zeta _{\textsf {min}}. \end{aligned}$$

1.3 A.3 Proof of Lemma 3

Proof

Let $\zeta _{x}=\zeta (\mathbf {x})$, as defined in Sect. 4, be the probability that a set of queries $\mathbf {x}$ do not cause a regular abort. In Game 2, $T=O(\epsilon ^{-2}\ln (\epsilon ^{-1})\zeta _{\textsf {min}}^{-1}\ln (\zeta _{\textsf {min}}^{-1}))$ samples are taken to approximate this value as $\zeta '_{x}$. By Chernoff Bounds, we have that for all $\mathbf {x}$

$$\begin{aligned} \mathrm {Pr}[T\zeta '_{x}> T\zeta _{x}(1+\frac{\epsilon }{8})]< e^{-[256\epsilon ^{-2}\ln ((\epsilon /8)^{-1})\zeta _{\textsf {min}}^{-1}\ln (\zeta _{\textsf {min}}^{-1})(\zeta _{\textsf {min}})(\epsilon /8)^{2}/4]}, \end{aligned}$$

which reduces to

$$\begin{aligned} \mathrm {Pr}[\zeta '_{x}> \zeta _{x}(1+\frac{\epsilon }{8})]< \frac{\epsilon }{8}\zeta _{\textsf {min}}. \end{aligned}$$

The probability of not aborting is equal to the probability of not regular aborting (RA) times the probability of not artificial aborting (AA). Recall that for a measured $\zeta '_{x}$ an artificial abort will not happen with probability $\frac{\zeta _{\textsf {min}}}{\zeta '_{x}}$. Therefore, for any $\mathbf {x}$, the $\mathrm {Pr}[\overline{\textsf {AA}}]\ge (1-\frac{\epsilon }{8}\zeta _{\textsf {min}})\frac{\zeta _{\textsf {min}}}{\zeta _{x}(1+\epsilon /8)}$. It follows that

$$\begin{aligned} \mathrm {Pr}[\overline{\textsf {abort}}]=&\mathrm {Pr}[\overline{\textsf {RA}}]\mathrm {Pr}[\overline{\textsf {AA}}]= \zeta _{x}\mathrm {Pr}[\overline{\textsf {AA}}] \\ \ge&\zeta _{x}(1-\frac{\epsilon }{8}\zeta _{\textsf {min}})\frac{\zeta _{\textsf {min}}}{\zeta _{x}(1+\epsilon /8)}\\ \ge&\zeta _{\textsf {min}}(1-\frac{\epsilon }{8})^2\\ \ge&\zeta _{\textsf {min}}(1-\frac{\epsilon }{4}). \end{aligned}$$