Score:0

Crypto

Non-interactive EC DKG (Distributed Key Generation) question

Erik Aronesty

6/2/24, 12:11 PM

Normally, when computing an EC threshold DKG, I have all parties reveal a commitment to the public key, and only reveal their own public key after verifying the commitments. Otherwise it's trivial to produce a public key that gives one member control. In a 2 party, for example, one can just wait for the other's public key, compute the inverse, and then publish that.

But can you make it noninteractive by publishing a proof of secret key? IE: Alice publishes her public key and a signature of the public key with her private key. Then Bob sees it and does the same.

Is there any way Bob can select a key that gives him control over the sum of those two keys? I can't see how. Seems like the commitment step can be avoided with a simple proof of secret key.

Then all Alice has to do is refuse to accept Bob's fraction of the key unless the proof works.

1 + 2

distributed-decryption

elliptic-curve-generation

fgrieu

6/2/24, 12:52 PM

DKG stands for Distributed Key Generation.

Erik Aronesty

6/2/24, 2:08 PM

The only weakness i see is that bob can begin *searching* for weak public keys. But it's DLP-hard for him to forge a signature for weak keys he finds. There is a form of birthday attack i think, since he can vary both the signature and the public key, looking for intersections. But it's not any better than the typical attacks that render 256-bit EC keys as 128-bit strength.

Score:1

Crypto

Richard Thiessen

6/3/24, 1:29 PM

Yes publishing a proof of exponent knowledge works.

If you want to do this with no setup whatsoever, use "Simple Schnorr Multi-Signatures with Applications to Bitcoin". They mention the option of publishing proofs but present an alternate scheme that prevents rogue key attacks by multiplying each key by a pseudorandom value generated from the hash of all input keys.

They also deal with another attack during the signing protocol. It's a good protocol to implement.

+ 7

Erik Aronesty

6/16/24, 4:37 PM

unfortunately that doesn't work with threshold setups or redistribution, both of which i need

Richard Thiessen

6/17/24, 12:54 AM

That would have been important to mention in the question. ["Extensible Decentralized Secret Sharing and Application to Schnorr Signatures"](https://eprint.iacr.org/2022/1551) is about the most general threshold EC signature system I know of. Unfortunately it's interactive. Threshold and noninteractive and distributed? Not sure that's been done yet. Threshold DKG usually involves evaluating polynomials on secret values which requires parties be online.

Richard Thiessen

6/17/24, 1:06 AM

I strongly suspect that what you want is impossible(one party takes as input a set of keys `(K1,K2,...Kn)` and produces a threshold signature public key point `K_th`). Non-interactive multi signature keys can be generated by multiplying each signer's key by a public scalar. That's all that can be done non-interactively and you can't build a threshold public key from that. I'm pretty sure even in the `(n,(n+1))` threshold case where one key holder is generating the threshold key it's still impossible.

Erik Aronesty

6/19/24, 3:13 PM

non-interactivity was never a requirement for signing. it's ok to get a round of g*k commitments from the signers (k is their blinding factor). then a threshold schnorr sig is easy, you just apply the polynomial and get a consensus blinding factor, and use the same on on the partial-signatures you get. as far as the consensus public key, i just need the pubkeys of t signers, i can choose whatever polynomial i want after receiving the public keys. they don't need to know how they're being combined.

Erik Aronesty

6/19/24, 3:19 PM

actually that article seems very strange to me. the level of interactivity is unnecessary and the weakness of "r" parties being able to recover the key is bizarre. not sure what the goals are but i would never use that

Erik Aronesty

6/19/24, 3:20 PM

the more i look at it, i would add a "considered harmful" label to it, and move on

Richard Thiessen

6/19/24, 9:43 PM

"As far as the consensus public key, i just need the pubkeys of t signers, i can choose whatever polynomial i want after receiving the public keys." This is fine for a `k` of `k` multisignature but creating a threshold public key (some holders of key shares can be missing) AFAIK can't be done non-interactively using a bunch of publicized public keys. Maybe that's not what you meant by ["threshold"](https://en.wikipedia.org/wiki/Threshold_cryptosystem)?

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Non-interactive EC DKG (Distributed Key Generation) question

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.