[bitcoin-dev] Multi party Schnorr Rust implementation

[bitcoin-dev] Multi party Schnorr Rust implementation

[Omer Shlomovits]

[-- 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 --]

Re: [bitcoin-dev] Multi party Schnorr Rust implementation

[Devrandom]

[-- 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 --]

Re: [bitcoin-dev] Multi party Schnorr Rust implementation

[Omer Shlomovits]

[-- 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 --]

Re: [bitcoin-dev] Multi party Schnorr Rust implementation

[Anthony Towns]

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

Re: [bitcoin-dev] Multi party Schnorr Rust implementation

[Jonas Nick]

> 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
>