Reasoning behind vss.MinimumT

[coventry]

What's the reasoning behind this value for MinimumT?

// MinimumT returns the minimum safe T that is proven to be secure with this
// protocol. It expects n, the total number of participants.
// WARNING: Setting a lower T could make
// the whole protocol insecure. Setting a higher T only makes it harder to
// reconstruct the secret.
func MinimumT(n int) int {
	return (n + 1) / 2
}

My understanding is that t needs to be larger than the plausible size of any dishonest coalition of participants. If more than half are colluding, the paper cited at the top of rabin/vss.go suggests that the protocol is broken:

We assume that an adversary, A, can corrupt up to t of the n parties in the network, for
any value of t < n/2 (this is the best achievable threshold—or resilience—for solutions
that provide both secrecy and robustness). (p. 56, Gennaro et al.)

Their results seem to suggest this, too:

Theorem 1. Under the Discrete-Log Assumption, Protocol New-DKG from Fig. 2 is a
secure protocol for distributed key generation in dlog-based cryptosystems, namely, it
satisfies the correctness and secrecy requirements of Section 4.1 with threshold t, for
any t < n/2.

It's easy for a maximum to flip to a minimum in a slightly changed context, but I'm not quite seeing the reasoning, in the case of MinimumT.

[nikkolasg]

Mhhhh. I think it's mostly a notation problem here IIUC.

• In our implementation, t means the number of shares needed to reconstruct a deal. So here the minimum t that can guarantee a safe execution of the protocol is t = (n+1)/2 roughly.
• In the paper, they set t to be the number of faults that the protocol can sustain, so indeed must be below n / 2. It's the "opposite" of our t in the implementation.
  Does that make sense ?

It can probably be clearer I agree !

[coventry]

Thanks, @nikkolasg. I'd be grateful if you could expand on why that's the minimum number of shares which can guarantee safe execution of the protocol. (A reference to the relevant part of the paper or some other paper is fine.)

[nikkolasg]

I just came back on this issue and it just struck me that you're right: the default safe t value should be n/2 + 1 and not (n+1) / 2 -_-" As for your question, the reason is that n/2 + 1 is the closest integer above n/2, hence a "safe" value.

It's actually hardcoded like that in some places using this code and in tests, but not the default...
I'll change that soon.

[coventry]

I think the source of my confusion may be that the usage of t is overloaded in the code. On the one hand, t is the number of shares needed to reconstruct the secret. That is the usage of t in the paper (±1), and is reflected in the usage of d.t when picking the private polynomial. On the other hand, in MinimumT it's number of shares which need to be correct during the initial sharing, so that a consistent, unpredictable secret has been shared. That's reflected in the check in aggregator.EnoughApprovals (which is getting its t value from the dealer), and also in pedersen/dkg.go, which actually uses vss.MinimumT() as the default value.

In the first meaning, for safe reconstruction of the secret t can be any value greater than the number of plausibly colluding parties. In the second meaning, it seems reasonable to reject a deal if a majority fails to approve it, and one should always reject a deal disapproved by more participants than the bound on dishonest parties (as prescribed in the papers this code is based on), but I think it's a different value, and kyber.share would be more broadly useful if these values were represented by separate variables in the code, so that they could diverge.

[nikkolasg]

On the one hand, t is the number of shares needed to reconstruct the secret.
On the other hand, in MinimumT it's number of shares which need to be correct during the initial sharing

1. MinimumT is only an indication of a safe value to use.
2. This EnoughApprovals is going to disappear in a next PR I'm working on (as well as many other security fixes);
3. The value given by the dealer is only for simplification: it's normally derived from the public polynomial of the dealer. As well, there's gonna be a method to set the value threshold for a verifier directly in my next PR.

In the first meaning, for safe reconstruction of the secret t can be any value greater than the number of plausibly colluding parties. In the second meaning, it seems reasonable to reject a deal if a majority fails to approve it, and one should always reject a deal disapproved by more participants than the bound on dishonest parties (as prescribed in the papers this code is based on), but I think it's a different value, and kyber.share would be more broadly useful if these values were represented by separate variables in the code, so that they could diverge.

I'm not sure I am following you. If you have f malicious nodes, you need at least a threshold of t >= f+1 for reconstructing the share. The vss.MinimumT is simply an indication of that t = f+1 where f = n/2 since that is the absolute minimum for this value. One can absolutely use other higher values than that, so I'm not sure I understand your last sentence...

(Thanks for these well-spotted issues and for the lengthy discussion ;) )

[coventry]

No worries, @nikkolasg. Another way to look at it is to distinguish between the sharing phase and the reconstruction/MPC phase. In the sharing phase you may need a majority of honest participants, but for reconstruction you only need as many shares as the number of coefficients in the polynomial. Those two values can be different, but they are the same in the current implementation, as I read it. That's important for me, because I have an application in mind where I would like a minority of participants to be able to use the distributed key, for liveness purposes. So the threshold specified by MinimumT gave me pause, but this conversation has clarified things for me enough that I'm able to move forward. Thanks to you, too. :-)

[nikkolasg]

Ok I see what you mean. At the moment, you can already have a safe DKG with any number of shares, the EnoughApprovals is merely here to check that it is sufficient enough.But I agree it's not yet clear how to know how much approvals do you have at any time during the DKG. Plus:

This EnoughApprovals is going to disappear in a next PR I'm working on (as well as many other security fixes);

I'm working on the PR that will bring a QualifiedShares() function that returns how many shares are valid at any given time during the DKG, which I believe is what you will want to use.

[nikkolasg]

Reopening so I don't forget about the minimumT bug.