Robust eVRF DKG

.md

Robust eVRF DKG

The eVRF paper details a one-round DKG. It does not detail how secret shares are communicated. If incorrect shares are communicated, participants would have to engage in a blame protocol (mandating at least one additional round of communication). We remove the ability for incorrect shares to be communicated via a verifiable encryption scheme (detailed in the following), removing the need for post-DKG confirmation rounds (assuming a consistent view of the transcript of the protocol).

We also only require t participants to generate a key in order to achieve robustness. This does mean the generated key is biased, unless there's a fixed selection of which t participants will complete the protocol (which wouldn't be robust). For the intended use case, participation in FROST where the public key is represented as a 256-bit value, this is fine (as FROST itself was written with a biased DKG, and the ability to bias a 256-bit representation of a public key should only enable finding a collision with 2**128 bits of effort (assumed hard)).

Verifiable Encryption of a Scalar

We presume two elliptic curves, $C_T, C_E$ where $C_T$ is over field $q$ with scalar field $p$ and $C_E$ is over field $p$ with scalar field $r$. Accordingly, the coordinates of points of $C_E$ are scalars on $C_T$.

The message recipient samples a private key $x$ uniformly from $r$. They publish $X = x \cdot G_E$, where $G_E$ is a generator of $C_E$.

The message sender, with scalar message $s \in p$, samples $a, b$ uniformly from $r$. The message sender calculcates the elliptic curve Diffie-Hellmans $a \cdot X,~ b \cdot X$, taking the sum of their x-coordinates as the mask $m$. The message sender publishes $A = a \cdot G_E,~ B = b \cdot G_E,~ s' = s + m,~ M = m \cdot G_T$, where $G_T$ is a generator of $C_T$. They additionally publish a ZK proof for the following statement:

$$\{ A,~ B \in C_E,~ M \in C_T;~ a,b \in r:~ A = a \cdot G_E, B = b \cdot G_E, M = ((a \cdot X)\mathsf{.x} + (b \cdot X)\mathsf{.x}) \cdot G_T \}$$

$\mathsf{.x}$ refers to taking the x-coordinate of the point.

This ZK proof, in practice, would be built as an eVRF premised on the ECDH would be. The eVRF paper details scaling private points by public scalars, yet a Bulletproof circuit can also be constructed for scaling public points ($G_E,~ X$) by private scalars ($a,~ b$).

Verifying the encryption assumes the verifier has a commitment to the expected scalar $S = s \cdot G_T$. The verifier verifies the ZK proof and checks $s' \cdot G_T = S + M$.

Decryption is done by calculating $s = s' - ((x \cdot A)\mathsf{.x} + (x \cdot B)\mathsf{.x})$.

Open Questions

Is the randomness $a,~ b$ reusable to encrypt messages if they have distinct recipients? If one recipient was to be reused, would it be sufficient to simply increase their public key by $G_E$? The resulting ECDHs would be $a \cdot X,~ a \cdot (X+G_E)$ (the latter equivalent to $(a \cdot X) + A$), yet the difference in x-coordinates of those two points presumably shouldn't be calculable without one of the ECDH values (where both are assumed private to the sender and receiver).

Do the participants need to publish Proofs of Knowledge for their keys? The Bulletproofs itself is a Proof of Knowledge for those who participate, yet this scheme proposes not everyone participate (meaning not everyone provides Proofs of Knowledge). While a participant can set their discrete log to another recipient's, they should only be able perform decryption if they actually know the discrete logarithm (at worst causing a recipient to have more shares than intended). If the byte-encoding from the context string is invalid (due to a complete lack of validation), a random point with an unknown discrete logarithm could be sampled. This avoids the context needing any validation performed for the contained keys.

Are there any benefits to performing the deterministic derivation of secret shares in the robust variant? The resulting key can still be biased by the decision of which potential participants participate. It does make arbitrary bias harder in practice (as likely sufficient to prevent a participant from performing a Taproot-tweak to add an arbitrary script spend path, though that should be explicitly handled by tweaking the result of the DKG with an unspendable script path).

References

• Exponent-VRFs and Their Applications by Dan Boneh, Iftach Haitner, and Yehuda Lindell.