-
Notifications
You must be signed in to change notification settings - Fork 13
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Motivation for deterministic key generation unclear #40
Comments
You're right that deterministic key generation isn't a necessary consequence of the ability to recover from seed and recovery data. ChillDKG is not deterministic. participant_step1 takes a fresh randomness argument that is used to derive the secret shared by the participant. We should probably just remove "deterministically" from this sentence:
It's correct, but it gives the impression that the entire key generation is deterministic. The transcript is non-deterministic.
To recover a participant's secret, we just need their seed.
If an individual secret is lost, you find yourself in a |
Ok thanks I understand what you are going for now I think. I think I can restate my question in a more precise way as a response to:
What about if all we need is their secret decryption key rather than this "seed". The concept of a seed could be totally removed. If we just include your "to self" secret vss input encrypted to yourself in the aggregated ciphertexts then anyone with just the decryption key can recover the share. This means the spec can totally leave out of scope how you generate randomness for VSS, encryption nonces, the encryption keys themselves and so on while maintaining the same recoverability property. I noticed this because I was diligently implementing all the tagged hashes and prfs inputs etc as closely as I could to the spec etc but then stopped myself because I couldn't figure out why I was doing it. I replaced |
Is this is a per-session decryption key or long-term decryption key? What exactly does this improve and how? Would it allow the recovery data to remain public (mod privacy) and ensure agreement? Something like this could be built from EncPedPop.
This means we need to establish an entirely new PKI from scratch for CertEq for every DKG instead of being able to reuse long term "host" public keys derived from the seeds. |
And backing up a new secret for every session. |
The long-term decryption key. It's the "host key". The goal is to simplify the specification and to stop it being opinionated about how to generate all the random per keygen inputs. All aside from the "host key" can just be pulled from rng of the implementor's choosing.
Not as its written since it doesn't include the encrypted secret share contribution destined for yourself from yourself in the transcript.
Why? I am trying to say that there should be no "seeds" as private input to the protocol at all. Just long-term host keys. Anyone with the host secret key can decrypt the share from the recovery data. The spec doesn't have to care where the application gets the host key from. Maybe it's generated and stored on an HSM in some hardware specific way. |
(Take this with a grain of salt, I'm out of office and only spent a moment thinking about this.)
Your observation is essentially correct. We have a built-in PRF and derive everything from a single random seed. One way to look at this is (a bit) like BIP340 signing. We give the implementer a proper way to derive all the randomness. But we can't force anyone to follow the spec when it comes to the randomness. If the implementer deviates from this and uses their own RNG, this is fine in the end. (BIP340 is still different because it can get away without any randomness...) (Yes, then participants will need to encrypt their "to self" share, but I don't think this comes with any disadvantages.) Though, the truth is that things are as they are because this is how the spec evolved. We made the protocol randomness entirely ephemeral only a while ago. I don't think it was a super deliberate decision to derive everything from a single seed, so it's a good point that you bring up. I think one advantage of the status quo is that it's not the end of the world if you reuse the seed. We'll need to think about this again, but as far as I remember, the conclusion was that reusing the seed is not covered by the security proof in the paper, but it should be okay in practice. (You know, famous last words of the applied cryptographer.) This is partly due to how we derive things deterministically, and in particular what context information we throw into the hash/RNG as some form of defense in depth. If we let the user pass an RNG instead and this RNG is broken, it may for example happen that they'll reuse the encryption pads for different messages. This shouldn't happen in the current form of the protocol. Another advantage of deriving everything from a single seed is that it will simply test vectors. And these will already be complex enough for an interactive protocol. A last thing we had considered is that with the current protocol, you could in principle recover the entire VSS. This may or may be helpful in protocol extensions and/or debugging. (But yeah, this is really a very minor thing.) Perhaps a way in the middle is simply to state that the randomness can be generated differently. This will be again like BIP340. We'll just need to indicate precisely what inputs constitute "randomness" because there are many places where we use randomness. (I'm sure there's some way to indicate precisely what all is "randomness", e.g., some Python type.)
This is slightly related to #28 by the way.
This sentence doesn't say anything about the protocol using an internal PRF for deterministic, derivation. This just states the DKG output can be reproduced deterministically. (Decryption is a deterministic operation!). We should perhaps omit the word "deterministically" if it's confusing in this context. |
I don't think it changes the analysis here, but just wanted to mention there are some alternative methods available to handle these scenarios. The share repair protocol can be run such that a threshold of participants can help another participant recover their lost share. In addition, in the event of a lost share, it's often a good idea to run the refresh protocol to defend against an attacker who recovers the lost share (e.g. if the lost share is on a device that was physically lost). These protocols are off-chain and do not require a sweep. So I think in practice, we will likely see repair+refresh used to handle lost shares in federations. For recovering the VSS, a threshold of public verification shares can be used to derive the VSS, and a threshold of secret shares can be used to derive a threshold of public verification shares. |
With the context provided by @real-or-random my campaign can be reduced to including the "to self" encrypted share in the agg ciphertext and stressing the use of the host secret key to recover the output rather than a "seed" (they might be the same thing #28). Using a PRF to ease writing the spec tests is a fine approach I think. In practice though I'd encourage the PRF to be generated with true fresh randomness in addition (same as BIP340).
I think all the spec needs to do here is have the source of randomness passed in. The PRF works well for this. Repeating the same one with exactly the same inputs will get you the same outputs. Keep in mind as @jesseposner mentions you can recover the entire VSS output state for each party in principle with only
Because of the missing to-self encryption you do have to use internal PRF for deterministic derivation in precisely the way specified. I don't think deterministically is wrongly used or confusing it just shouldn't require deterministic derivation. |
Right. I opened PR #43 to do that. Is this what you're suggesting? PR #43 makes the code a bit simpler, increases communication slightly and does not increase the size of the eq_input (aka "transcript") because the sum of all encshares had already been included. I think that this is a reasonable argument that encrypting the "self share" to yourself is worth doing. I'm not quite convinced by @LLFourn's argument for doing this though. Deriving secrets via a PRF instead of obtaining the secrets via an RNG is a common defense-in-depth measure that protects against broken RNGs. Moreover, using an RNG can make exhaustive test vectors more difficult (although this depends on how the test vectors look like exactly; maybe it can be avoided). |
Yes! thanks.
To be clear, I agree that the PRF API is the best way to go about this spec. I just wanted to point out that with the changes in #43 an implementation can use true randomness in addition to secrets and public inputs to sample the PRF and this is a good thing since it adds to defense-in-depth. |
It's a bit off-topic, but let me point out that I read @FiloSottile's newsletter last week, in which argues for deterministic derivation for similar reasons that were brought in this issue, e.g., testability. And there's this paragraph:
This really reminded me of @LLFourn's comment above:
[1] I hope it's appropriate to @mention you and generate a notification here... :) |
I was implementing all hash arguments "just so" and took a moment to ask myself why it needed to be like this and I couldn't figure it out.
From the text this seems to be the current motivation:
This is true but why is this useful. In order for this to recover any secret we'd need all the seeds -- but we are in the threshold setting where we're trying to be robust against loss of individual secrets so this doesn't seem super helpful?
But the deterministic keygen property doesn't seem to be relevant here. In order to extract your secret share from the recorded transcript (i.e. recovery data) you just need to decrypt the share destined to you and verify the signature. You don't need to deterministically produce anything other than your static secret key.
Is the issue that you don't add your own contribution to your own secret share to the transcript? If so, I think it's much easier to just change that rather than forcing determinism on the whole key generation.
The text was updated successfully, but these errors were encountered: