Key generation determinism or "Device backups"

[LLFourn]

So imagine that before generating a FROST key you first ask your frost member device for a backup of its static secret key as a bech32 string or seed words etc. What can we do with this and is it worth specifying in this document?

Any secret data that the device obtains in the future (i.e. key shares) could be encrypted to some key derivable from the backup. The encryption can be stored any place (please not tx witness) and retrieved later even if the device is destroyed through the backup. This has the advantage over share backups (#5) that you have only to do it once and all shares obtains by this device will be recoverable in the future assuming you can get your hands on a backup of them.

As an alternative to encrypted backups, parties could retrieve the key generation transcript, and then from the backup be able to re-generate and re-extract their key shares from the transcript (h/t @real-or-random). This would be advantageous since you could backup one thing for all the parties (but it would be a bigger backup).

My intuition here is that in terms of encrypted backups it doesn't seem like there is any distinguishing feature of them in this setting. They can be used any time there's secret stuff you're going to get but what to retrieve later so I think it would be nice to mention this approach but maybe it's fine to leave this to the application layer or another BIP. I'm sure a specification for this could be used elsewhere. A BIP for some variant of ECIES for secp256k1 seems like a good idea in general.

[real-or-random]

Quoting myself from #5, since the same applies here:

my thinking is that I want to keep the scope of this particular document limited to the actual cryptographic questions, for which we can make use of our expert knowledge. So I'd be hesitant to specify a concrete encoding method (e.g., bech32 or how many bits the int should have). But yeah, I agree, other standards that build on top will be necessary if we want interoperability... What you bring up are important questions, I just don't think they should be answered in this BIP (and that I want to be involved).

---

A BIP for some variant of ECIES for secp256k1 seems like a good idea in general.

Right, the encryption (which is anyway needed for the shares, indepedently of any backup) could be a separate BIP. It will be a small BIP then, but that's probably a good thing. I want to work on this soon, and may keep it in the current document first, but we could certainly move it to a separate document later.

[LLFourn]

Another thing I like about the idea of the deterministic transcript is that it can also be used for an accountability extension. Imagine that when you first post your shares you also commit to the randomness you used to generate your input ploy/share encryption. If things go badly (you must somehow be certain that the key generated will never be used) you can post this 32 bytes or whatever that seeded the whole thing and everyone can try and reproduce your part of the transcript -- if they can't you were malicious.

You of course have to be careful about this and it implies that each key generation session needs some unique identifier so you never generate the same seed twice. This sounds bad but maybe it's better than spec'ing verifiable decryption of shares -- having this kind of state is already a requirement for signing.

[real-or-random]

Indeed, committing to the randomness and revealing it is a generic way of ensuring accountability. What I wrote in #9 goes into a similar direction, though it's a bit more specific: you'd reveal the decryption key instead of a seed (but yeah, that's equally bad, it's just a different way of doing it).

---

A BIP for some variant of ECIES for secp256k1 seems like a good idea in general.

Right, the encryption (which is anyway needed for the shares, indepedently of any backup) could be a separate BIP.

Right after I wrote this, we figured out that a coordinator could aggregate all the encrypted shares meant for a single receiver if "encryption" is only scalar addition of a shared secret derived from ECDH, see jonasnick@2ac39fd. If we stick to this idea (we'll need to think a bit about its security), then this won't be a generally usable thing that could go to a separate BIP.

[LLFourn]

Right after I wrote this, we figured out that a coordinator could aggregate all the encrypted shares meant for a single receiver if "encryption" is only scalar addition of a shared secret derived from ECDH, see 2ac39fd. If we stick to this idea (we'll need to think a bit about its security), then this won't be a generally usable thing that could go to a separate BIP.

Wow. Scalar El-Gamal is not something I'd ever thought of before. I love this. Added to the spell book.

[jonasnick]

So imagine that before generating a FROST key you first ask your frost member device for a backup of its static secret key as a bech32 string or seed words etc.

The draft now covers both ideas:

• In EncPedPop, recovery is possible from a seed backup and the encrypted shares.
• In RecPedPop, recovery is possible from a seed backup and the transcript.

[LLFourn]

So imagine that before generating a FROST key you first ask your frost member device for a backup of its static secret key as a bech32 string or seed words etc.

The draft now covers both ideas:

* In `EncPedPop`, recovery is possible from a seed backup and the encrypted shares.

* In `RecPedPop`, recovery is possible from a seed backup and the transcript.

As an additional feature of RecPedPop, the state of any signing device can be fully recovered from a backup of a single secret per-device seed and the full public transcripts of all the DKG runs in which the device was involved. RecPedPop thus incorporates solutions for both secure channels and broadcast, and simplifies backups in practice.

Maybe be more specific about what "state" is recovered: the keys share. Saying the "state" can be fully recovered may not age well as people might think the nonce use state is also recovered (they may not know this BIP was written before the signing one).

Closing this as I like the approach and can discuss details in other issues.