Why are the guardian "key backups" not used by default?

[felixdoerre]

During the key ceremony, the n guardians share their individual part of the election key, via shamir's secret sharing with all other guardians. So each guardian has n values for election partial key backup. (One for each guardian including himself). When decrypting a value, the cooperating guardians can use the partial key backups they received from the refusing guardians during the ceremony, to calculate their "regular" decryption share instead of them.

An easier way to proceed after the key ceremony would be to just sum up all the election partial key backup-values resulting in a single polynomial of degree t which then is a "backup" of the joint key. t of this backup values for the joint key can then be used to decrypt a ciphertext directly.

Right now, for 3 out of 5 guardians, decrypting with 2 refusing guardians results in 3 group elements per cooperating guardian and 13 per refusing guardian: 2 * 13 + 3*3 = 35. Using the redistributed key only requires 9.

Using the shamir-shared key directly also vastly cuts down complexity in my opinion, as each guardian now only has to hold a single secret value (their shamir-share of the joint key), compared to n+1 values previously.

[benaloh]

We don't want to ever form this secret polynomial or the joint secret key. Anyone with access to this single secret key would be able to decrypt individual votes. With the process that we use, not only is the joint secret key never formed, but missing guardian keys are never formed either. If, in the example you give, we were to do the simpler thing and just reconstruct the secret keys of the two missing guardians, then from that point forward, any one remaining guardian could decrypt individual votes.

Guardians never reveal their secret key material. Instead, they use their secret keys to perform partial decryptions and their shares of missing guardian secret keys to form shares of missing partial decryptions. This provides maximal protection to the secret keys.

[felixdoerre]

I don't suggest to reconstruct the full polynomial nor the joint secret key.

Let me give an example. Assume 3 Guardians with quorum 2. They share a joint election key s = s_1 + s_2 + s_3 with g^s being the public election key. They all perform partial key backups by choosing m_i, defining polynomials f_i(x) = m_i * x + s_i and send f_i(j) to guardian number j (while also publishing g^m_i and ZK-proofs). Until here this is the regular electionguard key ceremony.
Now each guardian can individually add all the f_i(j) to get f(j) = f_1(j) + f_2(j) + f_3(j). This will give each guardian a point on the combined polynomial f(x) = (m_1+m_2+m_3) *x + s_1 + s_2 + s_3, which is a secret sharing of the joint election key s = f(0).

When decrypting (R=g^r, (g^s)^r * g^m), instead of calculating the individual shares R^s_i we directly calculate R^s, like we would when reconstructing a missing guardian's share from backups: Assume guardian 3 is missing and L_1(x), L_2(x) are the corresponding Lagrange polynomials. This gives s = f(0) = L_1(0) * f(1) + L_2(0) * f(2), so the 2 Guardians calculate R^f(1) and R^f(2) which are then combined into (R^f(1))^L_1(0) * (R^f(2))^L_2(0) = R^s.

Note that:

• After the key ceremony the guardians don't get more information than before, they don't exchange new values but only re-arrange the values that they already have
• The joint secret key and/or the polynomial sharing it, is never revealed, none of the guardians has access to the shared secret key. Guardians never reveal their secret key material, but only use it to perform a single partial decryption (instead of one per missing guardian and an additional one for themselves).
• I argue that this way of decrypting provides exactly the same protection to the guardian's keys. In fact, if we would use the interpolation not only for the missing guardians, but for all, everything that is published in the approach I propose can already be calculated from what was shared before (Instead of publishing R^f_1(1), R^f_2(1), R^f_3(1), guardian 1 only publishes R^f(1) = R^f_1(1) * R^f_2(1) * R^f_3(1)).

[benaloh]

Thanks for the clarifications. I apologize for misinterpreting the prior post.

Let me try to restate this in a different way to make sure that we're on the same page. Although it may never be explicitly constructed, with N guardians and a threshold of K, there is an implicit degree K-1 polynomial P formed by summing the N degree K-1 polynomials generated and shared by the guardians. The constant term of P is, of course, the (implicit) joint election secret key. Once all N of the guardian polynomials have been successfully shared, guardian j will not only have the value Pi(j) of each shared polynomial but will also be able to easily construct the value P(j) of the implicit joint polynomial.

I understand the suggestion here as being for each guardian to, instead of forming a partial decryption using its own secret key, form a share of the final decryption by using its constructed P(j) value. These decryption shares can be proven to be correct using Chaum-Pedersen proofs in a manner very similar to how partial decryptions can be proven to be correct. Given any K of these decryption shares, the appropriate Lagrange coefficients can be used to compute the full decryption.

This is an interesting alternative that is well worthy of further consideration. There are definite trade-offs and benefits to each approach. I'll admit to having a liking for the (admittedly optimistic) flow in which we begin by assuming that all N guardians are present and use all of their data equally to form decryptions. If there are missing guardians, then and only then, a quorum set of available guardians performs additional steps to compensate for the missing guardians. I definitely would not like the perception that would be given if, for instance with a 3 out of 5 system, we just produced tallies from the first 3 guardians to show up and told the remaining guardians that they were superfluous and could go home. However, it seems that mathematically, we could have all available guardians produce shares of the tallies knowing that we could construct the tallies from any quorum set of these shares.

The share reconstruction process has proven to be surprisingly cumbersome in practice due to the labelling guardians and the UX for indicating which guardians are available. But this is an approach that should be considered. I very much appreciate the suggestion and hope that you'll understand if we take the time to think this through carefully.

[benaloh]

Another thing that I should add here is that we've designed an approach for EGv2 that will look very different. Although we will still be using guardians, the guardian decryption data will not be exposed in the election record. Instead, we will be internally combining the decryption data produced by the guardians into a single proof of each decryption. Thus, people looking at the election record and writing independent verifiers will see decryptions and proofs as though they were formed by a single entity with the joint private key. This will make the verification process much simpler.

I believe that the suggestion of working with decryption shares rather than partial decryptions will also allow us to combine internal data and present the same public front of a single decryption proof. But this again requires careful thought to make certain that there are no unexpected complications.

[felixdoerre]

However, it seems that mathematically, we could have all available guardians produce shares of the tallies knowing that we could construct the tallies from any quorum set of these shares.

Yes, that sounds like a very good idea. Especially because at that stage it might not be even known if all guardians will participate or just fail to produce their R^P(j) with correct proof.

I believe that the suggestion of working with decryption shares rather than partial decryptions will also allow us to combine internal data and present the same public front of a single decryption proof. But this again requires careful thought to make certain that there are no unexpected complications.

Let me propose an idea for that:
To calculate (with proof) R^s for a given R, where each guardian j holds P(j) with P(0) = s we do the following:

1. We have each (participating) guardian j draw a new random k-1 degree polynomial Q_j publish the commitments on coefficients and send points on it to each other. Let's call additional joint secret q = Q(0) (just like they would draw a new secret during the key ceremony).
2. We have the guardians calculate R^P(j), g^Q(j), R^Q(j). We can combine any k of them to R^P(0) = R^s, g^Q(0) = g^q, R^Q(0) = R^q using Lagrange coefficients.
3. We hash context, R^s, g^q, R^q together for a challenge c (everyone individually, the mediator, ...)
4. The Guardians each publish: z_j = Q(j) + c * P(j)
5. We combine (any k of them) them to z = Q(0) + c * P(0) = q + c * s using Lagrange coefficients. To finish the Chaum-Pedersen ZK-proof.

If for decryption, guardians are missing, we can continue without the shared that would be provided by them. Having less guardians draw a polynomial Q_j is not a problem, we just sum up fewer polynomials as if the non-participating guardian's polynomial was all zeros.

That leaves us with:

• g^s (election public key), R^s, g^q, R^q,
• z = q + c*s
  This allows to verify a regular Chaum-Pedersen proof:
• g^z == g^q * (g^s)^c
• R^z == R^q * (R^s)^c

I think the additional "k-out-of-n"-sharing for Q is unavoidable if we want to produce a valid proof for the final decryption: Knowing the value q in the proof would be equivalent to knowing s, so having it identically shared feels reasonable. Sharing that with a different threshold (e.g. k'-out-of-k' for k' guardians participating in the decryption process), would make combining z not such an easy linear combination.

Sadly that complicates things a bit, as we now require 3 rounds of communication:

• First round: publish commitments on individual Polynomial's coefficients Q_i, and points on Q_i to their designated guardians
• Second round round: Build R^P(j), g^Q(j), R^Q(j)
• Third round round: Build z_i

Having individual chaum-pedersen proofs requires a single round, as we don't need a round to build up a shared masking secret and another one for building up a joint challenge:

• Publish R^P(j) with locally generated proof.

The election record could then contain all R^P(j) from all participating guardians (So it would definitely make a difference for the public record, for more guardians than needed to participate, as that includes the information and proof about who participated and who refused), and the verification tool can then just choose any quorum set of those to verify the decryption.

So in my opinion the additional complexity in the decryption process for producing a single decryption proof does not justify the slightly reduced complexity in a verifier.

[benaloh]

Thank you. I think we have a mechanism for removing the guardians from the election record without having to share new polynomials. We'll want to check the details to ensure that it applies equally well to this scenario. This will be included in our v2 spec which we hope to release soon.