# Distributed key generation (for discrete-log based cryptosystems) with fake shares

Under the definition of Gennaro et al (link), a DKG protocol needs to satisfy “correctness” and “secrecy”. Correctness is divided into three sub-properties:

C1. All subsets of $$t+1$$ shares provided by honest players define the same unique secret key $$x$$.

C2. All honest parties have the same value of public key $$y = g^x$$ $$mod$$ $$p$$, where $$x$$ is the unique secret guaranteed by (C1).

C3. $$x$$ is uniformly distributed in $$Z_q$$ (and hence y is uniformly distributed in the subgroup generated by $$g$$).

Secrecy means that no information on $$x$$ can be learned by the adversary except for what is implied by the value $$y = g^x$$ $$mod$$ $$p$$. In terms of simulatability: for every (probabilistic polynomial-time) adversary $$A$$, there exists a (probabilistic polynomial-time) simulator $$SIM$$, such that on input an element $$y$$ in the subgroup of $$Z_p$$ generated by $$g$$, produces an output distribution which is polynomially indistinguishable from $$A$$'s view of a run of the DKG protocol that ends with $$y$$ as its public key output, and where $$A$$ corrupts up to $$t$$ parties.

They then continue and say: “The above is a minimal set of requirements needed in all known applications of such a protocol. In many applications a stronger version of (C1) is desirable, which reflects two additional aspects: (1) It requires the existence of an efficient procedure to build the secret $$x$$ out of $$t+1$$ shares; and (2) it requires this procedure to be robust, i.e. the reconstruction of $$x$$ should be possible also in the presence of malicious parties that try to foil the computation.”

The question:

We are looking for a DKG procedure that satisfies the first aspect of the stronger version of (C1), but not the second one. This means that in the presence of $$t+1$$ honest shares, reconstructing $$x$$ should be possible efficiently. However, in the presence of malicious parties, it is impossible to distinguish honest shares from malicious shares and reconstructing $$x$$ boils down to checking all the combinations of $$t+1$$ shares until one that comprises only of honest shares is found.

• What is your question exactly? – Daniel Jan 30 at 10:15
• The question appears in the last paragraph – avi Jan 30 at 10:17
• There was an edit here that removed a large part of the second paragraph after C3, to indicate that that part was not necessary for the question. I've undone that edit as it may conflict with the intent of the asker (and it may also hide possible misunderstandings relevant to the question). If you have these kind of issues with a question, then (first) prefer a comment rather than a substantial edit. The change of the first name to the last name was of course acceptable and I've copied that change, thanks. – Maarten Bodewes Jan 31 at 21:03