Enrollment/Share repairing

[LLFourn]

There are a few secure ways of generating a new share at a given index for a new party. This is useful for "repairing" a device that has lost its share or for "enrolling" a new party with a never before produced share.

Principles

First observe that you can't simply get t parties to evaluate the Lagrange basis polynomial determined by their secret shares at a new index and send this to the recipient. This would work but reveal each secret share in the process (everything else is public and can be divided out).

Secure approaches involve sharing your secret share with the other t-1 share holders as an initial first step. These sharings are usually done as t-of-t. This means your share is information theoretically hidden unless dishonest parties manage to get t shares -- which is impossible unless all other parties are dishonest (including the receiver of the new share) in which case you cannot guarantee security anyway.

Importantly, you do not have to do a verifiable sharing of your share -- if dishonest parties do incorrect sharings then all that will happen is the receiver will not receive the correct share.

Once you've shared your shares you can do local computations to produce a share of the new output share and send that to the party who's meant to receive the new share.

Concretely the question is how do you do this sharing and computation on shares. These slides show two schemes: https://github.com/chelseakomlo/talks/blob/master/2019-combinatorial-schemes/A_Survey_and_Refinement_of_Repairable_Threshold_Schemes.pdf. The "reduced" scheme leads to less messages passed in some network scenarios where messages are forwarded from one party to the next (e.g. ferrying SD cards).

There's also BGW MPC which is the more general approach: https://securecomputation.org/docs/pragmaticmpc.pdf (see section 3.3). This would make sense if we wanted to specify a general secp256k1 field MPC for allowing you to turn any single party scheme into a threshold scheme but is slightly more complicated than the more precise schemes above.

Set up

This sharing of your share has very similar set up requirements to keygen except that you should do verify the public encryption keys of the other parties prior to sending out shares. In KeyGen you are sharing randomness you've just generated -- if things go wrong you can throw it away. Here we need to make sure that the parties receiving shares are really who they claim to be prior to sending the shares.

We can "piggy back" some of these checks onto the original keygen itself: The share holders can encrypt their shares-of-their-share to the public image (group element) of the share of the other party i.e. use secret shares as decryption key. However, somehow you still need to be certain about only the intended recipient receives the shares of the new share.

I think this scheme would be out of scope for the first BIP as it doesn't depend too much on what keygen scheme is used -- as long as it's about doing shamir shares. It's probably worth discussing though. It'd be interesting to hear @real-or-random thoughts about proving security of these kinds of protocols in composition with signing.

[real-or-random]

At a first glance, my main concern here is that both Lain-Stinson and BGW are only proven secure against a semi-honest adversary. Making them maliciously secure will first need more fundamental research. (Unless we have a good reason why semi-honest suffices, but I don't think we have one.)

I think this scheme would be out of scope for the first BIP as it doesn't depend too much on what keygen scheme is used -- as long as it's about doing shamir shares.

I agree. Even if it was dependent on the used keygen scheme, my feeling is that any enrollment/repairing scheme is a large enough project.

It'd be interesting to hear @real-or-random thoughts about proving security of these kinds of protocols in composition with signing.

My first intuition is that these protocols (in their semi-honest form) shouldn't make trouble when it comes to composition. All the trouble with composition with signings comes from stuff that needs rewinding, i.e., the zero-knowledge proofs of knowledge (the PoPs). AFAIU, the enrollment/repairing protocols won't add new PoPs.

What I could imagine though -- but this is even more speculation -- is that maliciously secure variants could need other zero-knowledge proofs and these could then create trouble when it comes to signing.

[LLFourn]

At a first glance, my main concern here is that both Lain-Stinson and BGW are only proven secure against a semi-honest adversary. Making them maliciously secure will first need more fundamental research. (Unless we have a good reason why semi-honest suffices, but I don't think we have one.)

Why do you say the Lain-Simpson proof is only secure against semi-honest? My (very briskly formed) view is the proof shows that it is information theoretically secure against malicious adversaries. Of course this doesn't guarantee that the receiver of the new share gets the correct output (for that you would need stronger assumptions) -- but that's not such a big deal in our setting as the receiver has a public commitment to the share it's getting so it can just output FAIL if after multiplying by G it doesn't have the correct thing. The same argument would apply to BGW or other linear secret sharing schemes I think.

Even though this won't go in the BIP here it is a pretty important point for us so please let me know if you have thoughts.

[real-or-random]

Why do you say the Lain-Simpson proof is only secure against semi-honest?

I have only read the first sentence of the proof (of Theorem 4.1), but that one says: "Assume all players act honestly during the protocol." (The slide deck drew my attention to this. Slide 10 says: "Assume a passive adversary that is honest-but-curious.")

[LLFourn]

Buried on the first line! Very sneaky. Thanks.

My intuition still screams to me that these protocols still information theoretically hide the secret even against malicious adversaries. If you look at the protocol and the proofs the view of the adversary is seems to be independent of the messages it sends. Therefore giving it the power to choose its own messages doesn't get any power to learn the secret than it did before (it just gets the power to make the share output to the receiver invalid):

There is no step in this where the view of adversary will differ whether it deviates from the protocol or not. Clearly this is the case if it doesn't corrupt $P_r$. If it does corrupt $P_r$ it sees these $\sigma_j$ but each $\sigma_j$ is just a sum of things the adversary sent to the honest parties and the things the honest parties sent to each other. There is no way to extract anything extra from $\sigmaj$ by deviating from the protocol in the $\delta{j,i}$ distribution phase.

Hopefully I can put something together to prove this. My approach would be that for every malicious transcript you could produce the same view from a semi-honest interaction.