Distributed Randomness using Weighted VRFs

• CRS: \((g_{1}, g_{2})\) generators of two pairing groups \(\mathbb{G}_{1}\) and \(\mathbb{G}_{2}\).
• Key Generation: BLS-like except that even \(g_{1}^{element}\) is a secret.
  • \(a \leftarrow \mathbb{F}\)
  • \(sk \leftarrow g_{1}^{a}\)
  • \(pk \leftarrow g_{2}^{a}\)
  • Return \((sk, pk)\)
• Augment Key Pair: \((sk, pk) \rightarrow (ask, apk)\) Augmentation is a way for users to update the keys I guess. So, to prevent Byzantine parties from changing an honest user's keys, the scheme produces a proof of knowledge of the previous key.
  • \(r \leftarrow \mathbb{F}\)
  • \(\pi \leftarrow g_{1}^{r}\)
  • \(rk \leftarrow sk^{r} = g_{1}^{ar}\)
  • \(ask \leftarrow r\)
  • \(apk \leftarrow (\pi, rk)\)
  • Return \((ask, apk)\)
• Augmented Verify Public Key \((pk, apk) \rightarrow \{0,1\}\): This verifies the augmented keys.
  • Parse \((\pi, r) := apk\)
  • Return \(e(\pi, pk) = e(rk, g_{2})\)
• Sign: \((ask, m) \rightarrow \sigma\): Slightly different from BLS. Unlike BLS, we hash to \(\mathbb{G}_{2}\) and raise it to the power of \(1/{sk}\).
  • \(r \leftarrow ask\)
  • \(\sigma \leftarrow H_{2}(m)^{1/r}\)
  • Return \(\sigma\)
• Verify Signature: \((apk, m, \sigma) \rightarrow \{0,1\}\):
  • Parse \((\pi, \cdot) := apk\)
  • \(h_2 \leftarrow H_2(m)\)
  • Return \(e(\pi, \sigma) = e(g_{1}, h_{2})\)
• Derive VUF: \((apk, \sigma) \rightarrow vuf\): The VUF is a signature using the \(ask\) over a message \(m\).
  • Parse \((\cdot, rk) := apk\)
  • Return \(e(rk, \sigma) = e(g_{1}^{ar},H_{2}(m)^{1/r}) = e(g_{1},H_{2}(m))^{a}\)

Mainly secret share \(g_{1}^{a}\) among all the parties.

• CRS: \((g_{1}, g_{2})\)
• Key Generation:
  • \(a_{1},\ldots,a_{n} \leftarrow ShamirSecretShare(n,t)\)
  • \(sk_{i} \leftarrow g_{1}^{a_{i}}\)
  • \(pk_{i} \leftarrow g_{2}^{a_{i}}\)
  • Return \((sk_{i}, pk_{i})\) to party \(i\)
• Augment Key Pair: \((sk_{i}, pk_{i}) \rightarrow (ask_{i}, apk_{i})\)
  • \(r \leftarrow \mathbb{F}\)
  • \(\pi \leftarrow g_{1}^{r}\)
  • \(rk_{i} \leftarrow sk_{i}^{r} = g_{1}^{a_{i}r}\)
  • \(ask_{i} \leftarrow r\)
  • \(apk_{i} \leftarrow (\pi, rk_{i})\)
  • Return \((ask_{i}, apk_{i})\)
• Sign: \((ask_{i}, m) \rightarrow \sigma_{i}\)
  • \(r_{i} \leftarrow ask_{i}\)
  • \(\sigma_{i} \leftarrow H_{2}(m)^{1/r_{i}}\)
  • Return \(\sigma_{i}\)
• Verify: \((apk_{i}, m, \sigma_{i}) \rightarrow \{0,1\}\):
  • Parse \((\pi, \cdot) := apk_{i}\)
  • \(h_2 \leftarrow H_2(m)\)
  • Return \(e(\pi, \sigma_{i}) = e(g_{1}, h_{2})\)
• Derive: \((apk_{i}, \sigma_{i}) \rightarrow vuf\):
  • Parse \((\cdot, rk_{i}) := apk_{i}\)
  • Return \(e(rk_{i}, \sigma_{i})\)

This work implements weighting with a weight value \(w_{i}\) per party \(i\). This work then performs a \((\sum w_{i}, \sum w^{t}_{j})\) secret sharing. The signature share is \(H_2(m)^{1/r_i}\) independent of the weight. Only public keys are in the order of \(O(w_i)\) for each party \(i\). The size of the signature is \(O(1)\) similar to the threshold case.

Uses a different secrecy game. In this game, the view of an honest transcript is indistinguishable from the view of a simulated transcript. Note that this is different from traditional secrecy, because in traditional secrecy games, one of the two approaches are used:

• Show that given a transcript of a sharing, if a PPT adversary breaks the secrecy, it breaks an underlying cryptographic assumption.
• (IND*-secrecy) Show that a PPT adversary cannot distinguish between the hiding of 0 and hiding of 1.

Here, the simulation is not tied to a particular key. But the general transcripts need to be indistinguishable (so key changes are allowed).

Let \(g_{1}\), \(h_{1}\), \(g_{2}\) be generators in \(\mathbb{G_{1}}\), \(\mathbb{G_{1}}\), and \(\mathbb{G_{2}}\) respectively. Public keys are setup in \(\mathbb{G}_{1}\).

• Setup to create public key for registration \(i \rightarrow (sk_{i},(pk_{i},\pi_{i}))\): Standard BLS-like secret keys with a proof of knowledge.
  • \(sk_{i}\leftarrow \mathbb{F}\)
  • \(pk_{i}\leftarrow g^{sk_{i}}\)
  • \(\pi_{i}\leftarrow PoK.Dlog(g,sk_{i},pk_{i})\)
  • Return \((sk_{i}, (pk_{i},\pi_{i}))\)
• Proof of Knowledge \((g,y,\alpha) \rightarrow \pi\): Schnorr proof of knowledge
  • \(r\leftarrow \mathbb{F}\)
  • \(u \leftarrow g^{r}\)
  • \(c \leftarrow H(g,y,u)\in \mathbb{F}\)
  • \(z \leftarrow r+c\cdot\alpha\)
  • \(\pi \leftarrow (g,y,u,z)\)
  • Return \(\pi\)
• Verify Proof of Knowledge \((\pi)\rightarrow \{0,1\}\): Standard
  • Parse \(\Pi := (g,y,u,z)\)
  • \(c \leftarrow H(g,y,u)\)
  • Return \((g^{z} = u\cdot y^{c})\)
• Verify registered Public Key \((pk_{i}, \pi_{i})\rightarrow \{0,1\}\)
  • Parse \((\cdot, y, \cdot, \cdot) := \pi_{i}\)
  • If \(y \ne pk_{i}\) Return \(0\)
  • Return Verify Proof of Knowledge \(\pi_{i}\)
• Deal a secret \(s\leftarrow \mathbb{F}:\rightarrow \{R_{2},\vec{\pi}, \vec{com}_{1}, \vec{com}_{2},\vec{enc}_{1}\}\):
  • Create an \((n,t)\) polynomial with \(s\) as the secret.
  • \(\vec{com_{1}} \leftarrow \{g_{1}^{p(0)},g_{1}^{p(1)},\ldots,g_{1}^{p(n)}\}\)
  • \(\vec{com_{2}} \leftarrow \{g_{2}^{p(0)},g_{2}^{p(1)},\ldots,g_{2}^{p(n)}\}\)
  • For \(i\in [n]\), \(share_{i}\leftarrow h_{1}^{p(i)}\)
  • \(\pi \leftarrow Pok(g_{2},com_{2}[0],p(0))\)
  • \(\vec{\pi} \leftarrow \{\pi\}\)
  • \(r\rightarrow \mathbb{F}\)
  • \(\vec{enc} \leftarrow (g_{1}^{r}, h_{1}^{p(1)}pk_{1}^{r},\ldots, h_{1}^{p(n)}pk_{n}^{r})\) These are Elgamal encryptions. \(\vec{enc} = (g_{1}^{r},h_{1}^{p(1)}g_{1}^{sk_{1}r},\ldots,h_{1}^{p(n)}g_{1}^{sk_{n}r})\)
  • \(R_{2} \leftarrow g_{2}^{r}\)
  • Return \((R_{2},\vec{\pi}, \vec{com}_{1}, \vec{com}_{2}, \vec{enc})\)
• Public Verification \((R_{2},\pi, \vec{com}_{1}, \vec{com}_{2}, \vec{enc}) \rightarrow \{0,1\}\):
  • For \(\pi\in \vec{\pi}\), if \(\pi\) verification for proof of knowledge returns \(0\), return \(0\)
  • If degree check of \(\vec{com}_{1}\) for \((n,t)\) (SCRAPE Degree check) returns \(0\), return \(0\)
  • If \(e(com_{1}[0], g_{2}) \ne e(g_{1}, R_{2})\), return \(0\)
  • For \(\pi \in \vec{\pi}\)
    • Parse \(\Pi := (\cdot, y, \cdot, \cdot)\)
    • \(y_{i} \leftarrow y\)
  • If \(com_{2}[0] \ne \prod y_{i}\), return \(0\)
  • For \(i \in [0,n]\), if \(e(g_{1},com_{2}[i]) \ne e(com_{1}[i], g_{2})\)
  • For \(i \in [n]\), if \(e(h_{1}, com_{2}[i])\cdot e(pk_{i},R_{2}) \ne e(enc[i], g_{2})\)
• Aggregate sharings \((transcript_{1}, transcript_{2})\rightarrow transcript\):
  • Parse \(transcript_{1} := (R_{2}^{1},\vec{pi}^{1},\vec{com}_{1}^{1},\vec{com}_{2}^{1}, \vec{enc}_{1}^{1})\)
  • Parse \(transcript_{2} := (R_{2}^{2},\vec{pi}^{2},\vec{com}_{1}^{2},\vec{com}_{2}^{2}, \vec{enc}_{1}^{2})\)
  • \(R_{2} \leftarrow R_{2}^{1}\cdot R_{2}^{2}\)
  • \(\vec{\pi} \leftarrow \vec{\pi}^{1}|| \vec{\pi}^{2}\)
  • \(\vec{com}_{1} \leftarrow \vec{com}_{1}^{1} \cdot \vec{com}_{1}^{2}\)
  • \(\vec{com}_{2} \leftarrow \vec{com}_{2}^{1} \cdot \vec{com}_{2}^{2}\)
  • \(\vec{enc}_{1} \leftarrow \vec{enc}_{1}^{1}\cdot \vec{enc}_{1}^{2}\)
  • Return \((R_{2}, \vec{\pi}, \vec{com}_{1}, \vec{com}_{2}, \vec{enc}_{1})\)
• Decrypt share \((transcript, sk_{i}) \rightarrow (ssk_{i}, spk)\): We are sharing keys here. So the decryption is a secret and public key here.
  • Parse \(transcript := (\cdot, \cdot, \cdot, \vec{com}_{2}, \vec{enc}_{1})\)
  • \(ssk_{i} \leftarrow (enc_{1}[i]/enc_{1}[0])^{sk_{i}}\)
  • \(spk \leftarrow {com}_{2}[0]\)
  • Return \((ssk_{i}, spk)\)