* [bitcoin-dev] Multi party Schnorr Rust implementation @ 2018-11-27 17:52 Omer Shlomovits 2018-11-28 6:33 ` Devrandom 0 siblings, 1 reply; 5+ messages in thread From: Omer Shlomovits @ 2018-11-27 17:52 UTC (permalink / raw) To: bitcoin-dev; +Cc: Gary Benattar, elichai.turkel, Roman Zeyde, Morten Dahl [-- Attachment #1: Type: text/plain, Size: 747 bytes --] Hello all, I am working for the past few months with collaborators (in cc) on providing Rust reference implementations to existing multi party schemes for Schnorr signatures [1]. This includes aggregated signatures, accountable signatures (which for n out of n are multi-signatures) and threshold signatures (wip). The project can be found here: https://github.com/KZen-networks/multi-party-schnorr . We aim that if the protocol is run in a configuration of a single party it will be bip-schnorr [2] compliant. Hope you'll find it useful :) Questions, suggestions and pull requests are welcome! [1] https://github.com/KZen-networks/multi-party-schnorr/tree/master/papers [2] https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki [-- Attachment #2: Type: text/html, Size: 1353 bytes --] ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [bitcoin-dev] Multi party Schnorr Rust implementation 2018-11-27 17:52 [bitcoin-dev] Multi party Schnorr Rust implementation Omer Shlomovits @ 2018-11-28 6:33 ` Devrandom 2018-11-28 8:13 ` Omer Shlomovits 2018-11-28 10:49 ` Anthony Towns 0 siblings, 2 replies; 5+ messages in thread From: Devrandom @ 2018-11-28 6:33 UTC (permalink / raw) To: omer.shlomovits, Bitcoin Protocol Discussion Cc: g.benattar, elichai.turkel, mail, mortendahlcs [-- Attachment #1: Type: text/plain, Size: 1228 bytes --] Hi Omer, Are there any candidates for non-interactive threshold signatures? Interactive signatures are not very suitable for air-gapped use cases. On Tue, Nov 27, 2018 at 11:18 AM Omer Shlomovits via bitcoin-dev < bitcoin-dev@lists•linuxfoundation.org> wrote: > Hello all, > > I am working for the past few months with collaborators (in cc) on > providing Rust reference implementations to existing multi party schemes > for Schnorr signatures [1]. This includes aggregated signatures, > accountable signatures (which for n out of n are multi-signatures) and > threshold signatures (wip). > The project can be found here: > https://github.com/KZen-networks/multi-party-schnorr . > We aim that if the protocol is run in a configuration of a single party it > will be bip-schnorr [2] compliant. > > Hope you'll find it useful :) > Questions, suggestions and pull requests are welcome! > > > [1] > https://github.com/KZen-networks/multi-party-schnorr/tree/master/papers > [2] https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > [-- Attachment #2: Type: text/html, Size: 2331 bytes --] ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [bitcoin-dev] Multi party Schnorr Rust implementation 2018-11-28 6:33 ` Devrandom @ 2018-11-28 8:13 ` Omer Shlomovits 2018-11-28 10:49 ` Anthony Towns 1 sibling, 0 replies; 5+ messages in thread From: Omer Shlomovits @ 2018-11-28 8:13 UTC (permalink / raw) To: c1.bitcoin Cc: Morten Dahl, bitcoin-dev, Elichai Turkel, Roman Zeyde, Gary Benattar [-- Attachment #1: Type: text/plain, Size: 2908 bytes --] Hi, AFAIK, There is no way to do threshold signatures non-interactively for the general case of t out of n. Even if you are willing to maintain additional data structure on top of the standard and change verification algorithm (see for example appendix B in [1] where they use bitmaps). The best way that I came up with so far (which I plan to implement in the library) is to take SS01 paper [2], this also the paper cited in bip-schnorr [3], and to replace Pedersen VSS with Feldman VSS (Feldman VSS implementation can be found in [4] ). Basically taking the DKG from GG18 without paillier and the dlog pok (threshold ecdsa paper [5]) and use it for the threshold schnorr DKG and for the ephemeral key distributed generation. This will cause the lost of Robustness but will be more efficient. Generally speaking - the purpose of using threshold security is to replace hw security. The assumption is that you would rather trust that no more than t out of n different machines will get corrupted at same time than to trust one secure hardware. Maybe that relax a bit the demand for using air gapped devices? [1] https://docs.zilliqa.com/whitepaper.pdf [2] https://github.com/KZen-networks/multi-party-schnorr/blob/master/papers/provably_secure_distributed_schnorr_signatures_and_a_threshold_scheme.pdf [3] https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki#multisignatures-and-threshold-signatures [4] https://github.com/KZen-networks/curv/tree/master/src/cryptographic_primitives/secret_sharing [5] http://stevengoldfeder.com/papers/GG18.pdf On Wed, Nov 28, 2018 at 8:33 AM Devrandom <c1.bitcoin@niftybox•net> wrote: > Hi Omer, > > Are there any candidates for non-interactive threshold signatures? > Interactive signatures are not very suitable for air-gapped use cases. > > On Tue, Nov 27, 2018 at 11:18 AM Omer Shlomovits via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation.org> wrote: > >> Hello all, >> >> I am working for the past few months with collaborators (in cc) on >> providing Rust reference implementations to existing multi party schemes >> for Schnorr signatures [1]. This includes aggregated signatures, >> accountable signatures (which for n out of n are multi-signatures) and >> threshold signatures (wip). >> The project can be found here: >> https://github.com/KZen-networks/multi-party-schnorr . >> We aim that if the protocol is run in a configuration of a single party >> it will be bip-schnorr [2] compliant. >> >> Hope you'll find it useful :) >> Questions, suggestions and pull requests are welcome! >> >> >> [1] >> https://github.com/KZen-networks/multi-party-schnorr/tree/master/papers >> [2] https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists•linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> > [-- Attachment #2: Type: text/html, Size: 5000 bytes --] ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [bitcoin-dev] Multi party Schnorr Rust implementation 2018-11-28 6:33 ` Devrandom 2018-11-28 8:13 ` Omer Shlomovits @ 2018-11-28 10:49 ` Anthony Towns 2018-11-28 16:43 ` Jonas Nick 1 sibling, 1 reply; 5+ messages in thread From: Anthony Towns @ 2018-11-28 10:49 UTC (permalink / raw) To: Devrandom, Bitcoin Protocol Discussion On Tue, Nov 27, 2018 at 10:33:30PM -0800, Devrandom via bitcoin-dev wrote: > Are there any candidates for non-interactive threshold signatures? Interactive > signatures are not very suitable for air-gapped use cases. I think you can work around this to some extent by "batching" signing requests. (Background: For interactive multisignatures (threshold or not), the protocol is: produce secret nonce r, calculate public nonce R=r*G everyone shares H(R) everyone shares R, checks received values match received hashes everyone calculates s=r+H(R',P',m)*p, shares s For deterministic nonces, you generate r=H(p,m) based on the message being signed and your private key, so can only start this process when you start signing, and the sharing rounds mean interactivity. ) But you don't strictly need deterministic nonces, you just have to never use the same nonce with a different message. If you arrange to do that by keeping some state instead, you can calculate nonces in advance: phase 1: produce secret nonces r1..r1024, calculate R1..R1024 share H(R1)..H(R1024) phase 2: store other parties hashes, eg as H1..H1024 share R1..R1024 phase 3: check received nonces match, ie H(R1)=H1, etc phase 4: request to sign msg m, with nonce n if nonce n has already been used, abort mark nonce n as having being used lookup other signer's nonces n and sum them to get R' calculate s = rn + H(R',P',m)*p share s That way you could do phases 1-3 once, and then do 1024 signatures during the month on whatever your current timetable is. You could also combine these phases, so when you get a signing request you: * receive msg to sign m, n=4; everyone else's R4, H(R5) * check H(R4) = previously received "H(R4)" * calculate R4' by summing up your and everyone's R4s * bump state to n=5 * do the signature... * send sig=(s,R4), R5, H(R6) which would let you have an untrusted app that does the coordination and shares the nonces and nonce-hashes, and getting all the needed air-gapped communication in a single round. (This is effectively doing phase 3 and 4 for the current signature, phase 2 for the next signature, and phase 1 for the signature after that all in one round of communication) That seems almost as good as true non-interactivity to me, if your signing hardware is capable of securely storing (and updating) a few kB of state (which is probably not quite as easy as it sounds). Cheers, aj ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [bitcoin-dev] Multi party Schnorr Rust implementation 2018-11-28 10:49 ` Anthony Towns @ 2018-11-28 16:43 ` Jonas Nick 0 siblings, 0 replies; 5+ messages in thread From: Jonas Nick @ 2018-11-28 16:43 UTC (permalink / raw) To: Anthony Towns, Bitcoin Protocol Discussion > For deterministic nonces, you generate r=H(p,m) based on the message > being signed and your private key, so can only start this process when > you start signing, and the sharing rounds mean interactivity. It's not your point but it should be noted that this is not secure unless all other signers give you zero knowledge proof that they've generated their nonce in the same way. Otherwise, if your asked to sign the same message you'll use the same nonce for two different challenges. In your example you'd compute s=r+H(R',P',m)*p and s'=r+H(R'',P',m)*p from which an observer can compute the secret key p. On 11/28/18 10:49 AM, Anthony Towns via bitcoin-dev wrote: > On Tue, Nov 27, 2018 at 10:33:30PM -0800, Devrandom via bitcoin-dev wrote: >> Are there any candidates for non-interactive threshold signatures? Interactive >> signatures are not very suitable for air-gapped use cases. > > I think you can work around this to some extent by "batching" signing > requests. > > (Background: > > For interactive multisignatures (threshold or not), the protocol is: > > produce secret nonce r, calculate public nonce R=r*G > everyone shares H(R) > everyone shares R, checks received values match received hashes > everyone calculates s=r+H(R',P',m)*p, shares s > > For deterministic nonces, you generate r=H(p,m) based on the message > being signed and your private key, so can only start this process when > you start signing, and the sharing rounds mean interactivity. > > ) > > But you don't strictly need deterministic nonces, you just have to never > use the same nonce with a different message. If you arrange to do that > by keeping some state instead, you can calculate nonces in advance: > > phase 1: > produce secret nonces r1..r1024, calculate R1..R1024 > share H(R1)..H(R1024) > > phase 2: > store other parties hashes, eg as H1..H1024 > share R1..R1024 > > phase 3: > check received nonces match, ie H(R1)=H1, etc > > phase 4: > request to sign msg m, with nonce n > if nonce n has already been used, abort > mark nonce n as having being used > lookup other signer's nonces n and sum them to get R' > calculate s = rn + H(R',P',m)*p > share s > > That way you could do phases 1-3 once, and then do 1024 signatures during > the month on whatever your current timetable is. > > You could also combine these phases, so when you get a signing request you: > > * receive msg to sign m, n=4; everyone else's R4, H(R5) > > * check H(R4) = previously received "H(R4)" > * calculate R4' by summing up your and everyone's R4s > * bump state to n=5 > * do the signature... > > * send sig=(s,R4), R5, H(R6) > > which would let you have an untrusted app that does the coordination and > shares the nonces and nonce-hashes, and getting all the needed air-gapped > communication in a single round. (This is effectively doing phase 3 and > 4 for the current signature, phase 2 for the next signature, and phase > 1 for the signature after that all in one round of communication) > > That seems almost as good as true non-interactivity to me, if your signing > hardware is capable of securely storing (and updating) a few kB of state > (which is probably not quite as easy as it sounds). > > Cheers, > aj > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2018-11-28 16:43 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2018-11-27 17:52 [bitcoin-dev] Multi party Schnorr Rust implementation Omer Shlomovits 2018-11-28 6:33 ` Devrandom 2018-11-28 8:13 ` Omer Shlomovits 2018-11-28 10:49 ` Anthony Towns 2018-11-28 16:43 ` Jonas Nick
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox