Distributed key generation (DKG)
We define a distributed key generation (DKG) as an interactive protocol that is used to generate a keypair We define this as (transcript, where is the number of participants in the is the indices of the adversarial participants (so is the resulting public key, and is some representation of the messages that have been exchanged.
We additionally consider an algorithm that, given and the shares submitted by honest parties, outputs the secret key corresponding to .
With this in place, we can define an omniscient interactive protocol (transcript, state OmniDKG that is aware of the internal state of each participant and thus can output sk (by running the Reconstruct algorithm) and state i.e., the internal state of the adversary.
Definition (Robustness). A DKG protocol is robust if the following properties hold:
A DKG transcript determines a public key that all honest parties agree on. There is an efficient algorithm
that takes as input a set of secret key shares where at least are from honest parties and verifies them against the public transcript produced by the DKG protocol. It outputs the unique value such that KeyGen
Beyond robustness, we also want a DKG to* preserve security* of the underlying primitive for which it is run. Previous related definitions of secrecy for DKGs required there to exist a simulator that could fix the output of the DKG; i.e., given an input could output (transcript, ) that the adversary could not distinguish from a real (transcript, pk) output by the DKG run with adversarial participants. While general, this definition is strong and required previous constructions to have more rounds or constraints than would otherwise be necessary; e.g., there seem to be significant barriers to satisfying this definition in any DKG where the adversary is allowed to go last, as they the know the entire transcript and can bias the final result.
In defining what it means for a DKG to preserve security, we first weaken this previous definition. Rather than require a simulator given to have the DKG output exactly , we consider that it can instead fix the output public key to have a known relation with its input public key. In particular, a simulator given can fix the output of the DKG to be pk, where the simulator knows such that for and as defined in the rekeyability definition. We call this property key expressability.
Definition (Key expressability). For a simulator , define as (transcript, SimDKG a run of the DKG protocol in which all honest participants are controlled by , which takes as input a public key and has private outputs and We say that a is key-expressable if there exists such a simulator such that
(transcript, pk) is distributed identically to the output of is a valid keypair,
To now define a security-preserving DKG, we intuitively consider a DKG being run in the context of a security game. To keep our definition as general as possible, our only requirements are that
the security game contains a line of the form (it also works if KeyGen takes a common reference string as additional input), pk is then later given as input to the adversary. We then say that the DKG preserves security if it is not possible for an adversary participating in the DKG to do better than it would have done in the original security game, in which it was given pk directly.
Formally, we have the following definition.
Definition (Security-preserving). Define as any security game containing the line KeyGen denoted and where pk is later input to an adversary (in addition to other possible inputs). Define ), parameterized by a starting line line and some value as Game but with replaced by and given as input rather than . It is clear that line
Define as the line transcript state OmniDKG and define DKG-Game Game' (line state ).
We say the DKG preserves security for Game if
for all PPT adversaries