Low entropy keygen check

[LLFourn]

When doing keygen you have to somehow do an out of band check with each party that they have the same result, or assume a PKI setup (which can be setup with an out-of-band check). A typical way to do this would be to hash the transcript and check with each party that the 32 bytes match. In many scenarios this will be a human eyeball comparing 32-bytes on screens somewhere. Would it be possible to reduce this to a statistically secure check (several bytes) rather than computationally secure check (which will be 32 bytes)>?

I think so, since the certified version of the protocol is three rounds you can at least run a coin tossing protocol in parallel to the main protocol and get a uniformly random bit string at the end which can be prefixed to the transcript before producing the "equality check" -- this allows us to use a 4 byte hash rather than 32 bytes (for 32 bit statistical security). Even simpler: change the certification signature to a VRF and then 4 byte hash those.

Of course if you have already set up PKI then there's no need to even do this check but in many situations you won't be able to do the PKI setup so this gives you the option of getting the human(s) to check a short string.

This is a question more than a proposal at this stage: does this seem sound?

[real-or-random]

Yep, this looks sound to me.

In your idea, if the out-of-band step is the equality check, it needs to happen after the start of protocol. This is the only drawback I see.

In the current design of ChillDKG, we use a PKI to make the out-of-band step (namely comparing the host public keys) more independent of the protocol. The step can happen at any time. Most users will want to perform it before the actual protocol starts, but they can also perform it during the protocol, and in principle even after the protocol.

We had assumed that a PKI is strictly better, and we had not considered low-entropy checks at all.

I think this is a nice example of the vast design space here. There are so many different things one could optimize for, but not at the same time. We had many discussions about whether we should prefer feature X or feature Y. We tried to build a solution that's hopefully good enough for a wide spectrum of use cases. When one targets a specific use case, one can for sure build a better protocol.

ps: This kind of feedback is super helpful. Your fresh eyes and fresh brain often add an entirely different perspective to the discussion.

[jonasnick]

Interesting idea. To keep this BIP focused and manageable, I think this would be best specified in a separate spec (which should be compatible with the existing ChillDKG BIP).

Thanks @real-or-random for explaining @LLFourn's scheme to me. Rephrasing:

The proposal is to run a secure coin tossing protocol alongside the DKG to generate shared randomness r. Participants would only compare session parameters after obtaining r. For example, they could compare H(r||sessionparams), which would limit an adversary's success probability to 2^-32. This works because session parameters must be established before the DKG begins, and because r is unpredictable.