tnakagawa/bipschnorr-Threshold.md

## bipschnorr-Threshold.md

      
    Raw
  

              bipschnorr-Threshold.md
            
          
    Threshold Signatures

This text is a procedure for t-of-k threshold signatures.
The symbols and functions used are defined in the following URL.
https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
Introduction


The number of users k.
The number of required signers t. ( 0 < t ≤ k )
The constant H refers to the generator. ( G ≠ H )

Let H = xG , x mod n , x is random.


The message m : an array of 32 bytes

The n , G and functions are cited from the original text.
Each user i(i = 1...k) is in an agreed ordered set so that user i is always the same for every user.
Shared Secret

Step 1

Each user i(i = 1...k) sends t commitments to a set of random numbers:

Let there be random numbers a_i0...a_i(t-1) and a'_i0...a'_i(t-1) in the range 1...n-1 , 2t integers.
Let the sharing polynomials be f_i(x) and f'_i(x)

f_i(x) = a_i0 + a_i1x¹ + ... + a_i(t-1)x^t-1
f'_i(x) = a'_i0 + a'_i1x¹ + ... + a'_i(t-1)x^t-1


Let the commitments be C_i0...C_i(t-1) : C_ih = a_ihG + a'_ihH (h = 0...t-1).
The user(i) sends commitments(C_i0...C_i(t-1)) to the other users(j = 1...k , j ≠ i).

Step 2

Each user(i = 1...k) sends shared secrets and the other users' commitments to each other user:

For j = 1...k , j ≠ i :

Let s_ij = f_i(j) mod n , s'_ij = f'_i(j)  mod n
The user(i) sends (s_ij , s'_ij) to the user(j).
The user(i) sends other user's commitments(C_h0...C_h(t-1) , h = 1...k , h ≠ i , h ≠ j)  to the user(j).


Each user(i = 1...k) verifies secret and commitments received from user(j = 1...k , j ≠ i) :

Fail if s_jiG + s'_jiH ≠ i⁰C_j0 + ... + i^t-1C_j(t-1)
Fail if commitments(C_h0...C_h(t-1), h = 1...k , h ≠ i , h ≠ j) does not match commitments received at Step 1.
If fail , sends result to other user(h = 1...k , h ≠ i).

Step 3

Each user(i = 1...k) sends shared points :

Let the A_i0...A_i(t-1) : A_ih = a_ihG (h = 0...t-1).
The user(i) sends A_i0...A_i(t-1) to other users(j = 1...k , j ≠ i).

Each user(i = 1...k) verifies shared points received from user(j = 1...k , j ≠ i) :

Fail if s_jiG  ≠ i⁰A_j0 + ... + i^t-1A_j(t-1)
If fail , sends result to other user(h = 1...k , h ≠ i).

The publickey of shared secret is sum of each 0-th points. : P = A₁₀ + ... + A_k0
Signing


The t users participating in the signing process(u_i , i = 1...t) .
1 ≤ u_i ≤ k , i = 1...t ; u_i1 ≠ u_i2 , i1 ≠ i2 , 1 ≤ i1 ≤ t , 1 ≤ i2 ≤ t .

Step 1

Each user u_i(u_i , i = 1...t) sends t commitments to a set of random numbers :

Let there be random numbers b_{u_i0}...b_{u_i(t-1)} and b'_{u_i0}...b'_{u_i(t-1)} in the range 1...n-1 , 2t integers.
Let the sharing polynomials be g_{u_i}(x) and g'_{u_i}(x)

g_{u_i}(x) = b_{u_i0} + b_{u_i1}x¹ + ... + b_{u_i(t-1)}x^t-1
g'_{u_i}(x) = b'_{u_i0} + b'_{u_i1}x¹ + ... + b'_{u_i(t-1)}x^t-1


Let the commitments be C'_{u_i0}...C'_{u_i(t-1)} : C'_{u_ih} = b_{u_ih}G + b'_{u_ih}H (h = 0...t-1).
The user(u_i) sends commitments(C'_{u_i0}...C'_{u_i(t-1)}) to the other users(u_j , j = 1...t , j ≠ i).

Step 2

Each user(u_i , i = 1...t) sends random numbers and the other user's commitments to each other user :

For j = 1...t , j ≠ i :

Let r_{u_iu_j} = g_{u_i}(u_j) mod n , r'_{u_iu_j} = g'_{u_i}(u_j)  mod n
The user(u_i) sends (r_{u_iu_j} , r'_{u_iu_j}) to the user(u_j).
The user(u_i) sends commitments(C'_{u_h0}...C'_{u_h(t-1)} , h = 1...t , h ≠ i , h ≠ j) of other users to the user(u_j).


Each user(u_i , i = 1...t) verifies random number and commitments received from user(u_j , j = 1...t , j ≠ i) :

Fail if r_{u_ju_i}G + r'_{u_ju_i}H ≠ u_i⁰C_{u_j0} + ... + u_i^t-1C_{u_j(t-1)}
Fail if commitments(C'_{u_h0}...C'_{u_h(t-1)} , h = 1...t , h ≠ i , h ≠ j) sent from user(i_j) does not match commitments received at Step 1.
If fail , sends result to other user(u_h , h = 1...t , h ≠ i).

Step 3

Each user(u_i , i = 1...t) sends random points :

Let the B_{u_i0}...B_{u_i(t-1)} : B_{u_ih} = b_{u_ih}G (h = 0...t-1).
The user(u_i) sends B_{u_i0}...B_{u_i(t-1)} to other users(u_j , j = 1...t , j ≠ i).

Each user(u_i , i = 1...t) verifies random points received from user(u_j , j = 1...t , j ≠ i) :

Fail if r_{u_ju_i}G  ≠ u_i⁰B_{u_j0} + ... + u_i^t-1B_{u_j(t-1)}
If fail , sends result to other user(u_h , h = 1...t , h ≠ i).

The Point of random number is sum of each 0-th points. : R = B_u₁0 + ... + B_{u_t0}
Step 4

Each user(u_i , i = 1...t) sends signature :

Let r = r_{u₁u_i} + ... + r_{u_tu_i}
Let R = B_u₁0 + ... + B_{u_t0}
If jacobi(y(R)) ≠ 1 , let r = n - r
Let P = A₁₀ + ... + A_k0
Let e = int(hash(bytes(x(R)) || bytes(P) || m)) mod n
Let s = s_{u₁u_i} + ... + s_{u_ku_i}
Let sig_{u_i} = r + es mod n
The user(u_i) sends sig_{u_i} to other users(u_j , j = 1...t , j ≠ i).

Each user(u_i , i = 1...t) verifies signature received from user(u_j , j = 1...t , j ≠ i) :

Let B be the point at infinity
For h = 1...t :

B = B + j⁰B_{u_h0} + ... + j^t-1B_{u_h(t-1)}


Let R = B_u₁0 + ... + B_{u_t0}
If jacobi(y(R)) ≠ 1 , let B = -B
Let P = A₁₀ + ... + A_k0
Let e = int(hash(bytes(x(R)) || bytes(P) || m)) mod n
Let A be the point at infinity
For h = 1...k :

A = A + j⁰A_{u_h0} + ... + j^t-1A_{u_h(t-1)}


Fail if sig_{u_j}G ≠ B + eA
If fail , sends result to other user(u_h , h = 1...t , h ≠ i).

Step 5

Anyone holding sig and who knows the predefined user order can produce a valid signature:

Let s = 0

For j = 1...t :

Let o = 1
For h = 1...t , u_h ≠ u_j :

o = o × u_h ÷ (u_h - u_j) mod n


s = s + o × sig_{u_j} mod n


Let R = B_u₁0 + ... + B_{u_t0}
The signature is bytes(x(R)) || bytes(s).

References

Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates

http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps
Acknowledgements

I would like to thank everyone who advised.