Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

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 ai0...ai(t-1) and a'i0...a'i(t-1) in the range 1...n-1 , 2t integers.
  • Let the sharing polynomials be fi(x) and f'i(x)
    • fi(x) = ai0 + ai1x1 + ... + ai(t-1)xt-1
    • f'i(x) = a'i0 + a'i1x1 + ... + a'i(t-1)xt-1
  • Let the commitments be Ci0...Ci(t-1) : Cih = aihG + a'ihH (h = 0...t-1).
  • The user(i) sends commitments(Ci0...Ci(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 sij = fi(j) mod n , s'ij = f'i(j) mod n
    • The user(i) sends (sij , s'ij) to the user(j).
    • The user(i) sends other user's commitments(Ch0...Ch(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 sjiG + s'jiH ≠ i0Cj0 + ... + it-1Cj(t-1)
  • Fail if commitments(Ch0...Ch(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 Ai0...Ai(t-1) : Aih = aihG (h = 0...t-1).
  • The user(i) sends Ai0...Ai(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 sjiG ≠ i0Aj0 + ... + it-1Aj(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 = A10 + ... + Ak0

Signing

  • The t users participating in the signing process(ui , i = 1...t) .
  • 1 ≤ ui ≤ k , i = 1...t ; ui1 ≠ ui2 , i1 ≠ i2 , 1 ≤ i1 ≤ t , 1 ≤ i2 ≤ t .

Step 1

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

  • Let there be random numbers bui0...bui(t-1) and b'ui0...b'ui(t-1) in the range 1...n-1 , 2t integers.
  • Let the sharing polynomials be gui(x) and g'ui(x)
    • gui(x) = bui0 + bui1x1 + ... + bui(t-1)xt-1
    • g'ui(x) = b'ui0 + b'ui1x1 + ... + b'ui(t-1)xt-1
  • Let the commitments be C'ui0...C'ui(t-1) : C'uih = buihG + b'uihH (h = 0...t-1).
  • The user(ui) sends commitments(C'ui0...C'ui(t-1)) to the other users(uj , j = 1...t , j ≠ i).

Step 2

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

  • For j = 1...t , j ≠ i :
    • Let ruiuj = gui(uj) mod n , r'uiuj = g'ui(uj) mod n
    • The user(ui) sends (ruiuj , r'uiuj) to the user(uj).
    • The user(ui) sends commitments(C'uh0...C'uh(t-1) , h = 1...t , h ≠ i , h ≠ j) of other users to the user(uj).

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

  • Fail if rujuiG + r'ujuiH ≠ ui0Cuj0 + ... + uit-1Cuj(t-1)
  • Fail if commitments(C'uh0...C'uh(t-1) , h = 1...t , h ≠ i , h ≠ j) sent from user(ij) does not match commitments received at Step 1.
  • If fail , sends result to other user(uh , h = 1...t , h ≠ i).

Step 3

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

  • Let the Bui0...Bui(t-1) : Buih = buihG (h = 0...t-1).
  • The user(ui) sends Bui0...Bui(t-1) to other users(uj , j = 1...t , j ≠ i).

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

  • Fail if rujuiG ≠ ui0Buj0 + ... + uit-1Buj(t-1)
  • If fail , sends result to other user(uh , h = 1...t , h ≠ i).

The Point of random number is sum of each 0-th points. : R = Bu10 + ... + But0

Step 4

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

  • Let r = ru1ui + ... + rutui
  • Let R = Bu10 + ... + But0
  • If jacobi(y(R)) ≠ 1 , let r = n - r
  • Let P = A10 + ... + Ak0
  • Let e = int(hash(bytes(x(R)) || bytes(P) || m)) mod n
  • Let s = su1ui + ... + sukui
  • Let sigui = r + es mod n
  • The user(ui) sends sigui to other users(uj , j = 1...t , j ≠ i).

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

  • Let B be the point at infinity
  • For h = 1...t :
    • B = B + j0Buh0 + ... + jt-1Buh(t-1)
  • Let R = Bu10 + ... + But0
  • If jacobi(y(R)) ≠ 1 , let B = -B
  • Let P = A10 + ... + Ak0
  • 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 + j0Auh0 + ... + jt-1Auh(t-1)
  • Fail if sigujG ≠ B + eA
  • If fail , sends result to other user(uh , 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 , uh ≠ uj :
        • o = o × uh ÷ (uh - uj) mod n
      • s = s + o × siguj mod n
  • Let R = Bu10 + ... + But0
  • 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.

@vietlq

This comment has been minimized.

Copy link

vietlq commented Sep 5, 2018

@tnakagawa: Thanks for sharing. I have a few questions:

  1. How to determine a good value for x in order to produce the secondary generator H?
  2. What are the criteria for x & H?
  3. Can x & H be reused for other rounds?
  4. Can you give example for x & H for the Bitcoin curve?

Thanks.

@tnakagawa

This comment has been minimized.

Copy link
Owner Author

tnakagawa commented Sep 14, 2018

Sorry for my late response.

I do not have a good idea.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.