Where \( x, y \) are unknowns in some field \( \FF \) and \(a \), \( b \), and \( d \) are constants in the same field.
The field \( \FF \) is usually a finite field \( \ZZ_p \) (or, equivalently, \( \mathit{GF}(p) \)) for some prime \( p \).
Notation
For a given curve equation (whether Weirstrass, Montgomery, or Twisted Edwards) We denote by \( E(\FF) \) the set \( \left\{ (x,y) \in \FF^2 \mid \text{the curve equation is satisfied}\right\} \)
We will denote elliptic curve points in caligraphic font (e.g., \(\cvPt{P}\)).
We will denote public information with capital letters.
Given any two points \( \cvPt{P}_1, \cvPt{P}_2 \in E(\FF) \) there is a method of adding \( \cvPt{P}_1 \) and \( \cvPt{P}_2 \) to find a new point \( \cvPt{P}_1 + \cvPt{P}_2 \in E(\FF) \).
The set \( E(\FF) \) with this addition method forms a group with all that entails.
Of particular interest in this talk is the group associativity property:
\[ \left( \cvPt{P}_1 + \cvPt{P}_2 \right) + \cvPt{P}_3 = \cvPt{P}_1 + \left( \cvPt{P}_2 + \cvPt{P}_3 \right) \quad \forall \, \cvPt{P}_1, \cvPt{P}_2, \cvPt{P}_3 \in E(\FF) \]
There is a natural action of the integers on this group wherein given \( k \in \ZZ \):
\[ k\cvPt{P} := \underbrace{\cvPt{P} + \cvPt{P} + \dotsb + \cvPt{P}}_{k\text{ times}} \]
Note: this action has a distributive property: \( (k_1 + k_2)\cvPt{P} = k_1\cvPt{P} + k_2\cvPt{P} \).
Definition:
Suppose \( \cvPt{Q} = k\cvPt{P} \) for some \( k \in \ZZ \). The problem of compuing \( k \), given \( \cvPt{Q} \) is called the Elliptic Curve Discrete Logarithm problem.
The hardness of this problem is the basis of the security of elliptic curve cryptography.
Shamir Secret Sharing
A secret \( s \in \ZZ_p \) can be shared in a \( t \)-in-\( n \) sharing scheme wherein \( n \) actors have shares of the secret and any \( t \) or more may combine their shares by:
Randomly generating an degree \( t-1 \) polynomial \( P \) such that \( P(0) = s \)
Give each of the \( n \) actors a share \( \sigma_i = \left(x_i, P(x_i)\right) \).
Any subset of shares \( \left\{ \sigma_c \mid c \in C \subset \left\{1,\dotsc,n\right\}\right\} \) (where \( \lvert C \rvert \ge t \)) can resconstruct the secret by
\[ s = \sum_{c \in C} P\left(x_c\right) l_c(C) \quad\text{where}\quad l_i(C) = \prod_{c\in C, c \ne i} \frac{x_c}{x_c - x_i} \]
c.f. “How to Share a Secret” by Adi Shamir in Commun. ACM November 1979
Threshold Signatures
Definition:
A threshold signature is a signature computed by two or more parties in such a way that neither the parties, nor their roles in the signature computation can be determined from the signature.
Such a signature might be composed of otherwise valid signatures.
Individual contributions can be combined directly, or via Shamir secret sharing.
In the specific case of Ed25519 we use the twisted Edwards curve
\[ E\left(\ZZ_p\right) = \left\{ (x,y) \in \ZZ_p^2 \mid x^2 + y^2 = 1 + \tfrac{121665}{121666}x^2y^2 \right\} \]
where \( p = 2^{255}-19 \).
Specifically, calculations are performed over the cyclic subgroup generated by the point
\( \cvPt{G} = \left(x, \tfrac{4}{5}\right)\) with positive \( x \)-coordinate.
This subgroup has prime order
\[ \ell = 2^{252}+27,\!742,\!317,\!777,\!372,\!353,\!535,\!851,\!937,\!790,\!883,\!648,\!493 \]
Note: points in \( E(\FF_p) \) that are not in this cyclic subgroup must have order 1, 2, 4, or 8.
\( E(\FF_p) \) is bi-rationally equivalent to Curve25519 (a Mongtommery curve for key exchange).
CITATION NEEDED
Ed25519 Key Generation
To generate a public/private key pair for Ed25519 signing:
Generate 32 random bytes in a cryptographically secure manner.
Call this \( s \), and refer to it as the “secret seed”.
Calculate \( h = \operatorname{SHA512}(s) \).
Split \( h \) into two halves.
\( H_1 = h_0, \dotsc, h_{255} \)
\( H_2 = h_{256}, \dotsc, h_{511} \)
We refer to \( H_2 \) as the “signing prefix”.
Key Clamping:
Clear the bits \( h_0 \), \( h_1 \), \( h_2 \), and \( h_{255} \) in \( H_1 \). (i.e., set them to zero).
Set the bit \( h_{254} \) (i.e., set it to one).
Let \( a = \sum_{i=0}^{255} h_i 2^i \) (i.e., interpret \( H_1 \) as a number). We refer to this as the “secret scalar”.
We calculate the public key \( A = a\cvPt{G} \).
Note: \( a\cvPt{G} = (a \operatorname{mod} \ell)\cvPt{G} \).
Ed25519 Key Clamping
The bit manipulation (sometimes called “clamping”) of the bits of \( H_1 \) in step 4. guarantees that \( a \) is a multiple of 8.
This step is also peformed in the key generation for Curve25519 public keys where it provides an important protection against attacks in the key exchange using low order points outside of the cyclic group.
We note in passing that clamping will have the effect of guaranteeing that all keys for Ed25519 are bi-rationally equivalent to valid keys for Curve25519.
Ed25519 Signing and Verification
Definition:
\( \operatorname{NUM}(X) \) is defined as \( \operatorname{NUM}(X) = \sum_{i=0}^{511} h_i 2^i \) where \( h = \operatorname{SHA512}( X ) \).
Given a message, \( M \), we sign the message by:
Calculate \( \cvPt{R} = r\cvPt{G} \) where \( r = \operatorname{NUM}(H_2 \concat M) \).
Calculate \( k = \operatorname{NUM}(\cvPt{R} \concat \cvPt{A} \concat M) \).
Calculate \( S = (r+ka) \operatorname{mod} \ell \).
The signature is the pair \( \left( \cvPt{R}, S \right) \).
To verify a signature:
Verify that \( \cvPt{R} \) and \( \cvPt{A} \) correctly encode points, and that \( 0 \le S < \ell \).
Calculate \( k = \operatorname{NUM}(\cvPt{R} \concat \cvPt{A} \concat M) \).
Check that \( (8S)\cvPt{G} = 8\cvPt{R} + (8k)\cvPt{A} \).
Ed25519 for Threshold Signatures
We note that if \( (a_1, \cvPt{A_1}) \) and \( (a_2, \cvPt{A_2}) \) are valid Ed25519 key pairs (i.e., secret scalar and public key), then because of the associative property of curve addition:
\[ (a_1 + a_2)\cvPt{G} = a_1\cvPt{G} + a_2 \cvPt{G} = \cvPt{A}_1 + \cvPt{A}_2 \]
and so \( (a_1 + a_2, \cvPt{A}_1 + \cvPt{A}_2) \) is also a valid Ed25519 key pair.
Similarly, if in signing, if \( \cvPt{R_1} = r_1 \cvPt{G} \) and \( \cvPt{R_2} = r_2 \cvPt{G} \) then \( (r_1 + r_2) \cvPt{G} = R_1 + R_2 \).
If we fix \( k = \operatorname{NUM}(R_1 + R_2 \concat \cvPt{A} \concat M) \) then if \( S_1 = (r_1 + ka_1) \operatorname{mod} \ell \) and \( S_2 = (r_2 + k a_2) \operatorname{mod} \ell \) then
\[
\begin{aligned}
S_1 + S_2 &= (r_1 + ka_1) \operatorname{mod} \ell + (r_2 + k a_2) \operatorname{mod} \ell \\
&= (r_1 + ka_1 + r_2 + ka_2) \operatorname{mod} \ell &= \left( \left(r_1 + r_2\right) + k \left(a_1 + a_2\right) \right) \operatorname{mod} \ell
\end{aligned}
\]
Complications for Threshold Signatures
There is no clear threshold signing prefix value.
Sum of individual signing prefixes is not the same as the signing prefix for the aggregate public key.
Deterministic nonce \( r \) might allow leaking of private key.
Bit manipulations in key generation.
Distributive property of the group action mean that aggregate public keys will still be a multiple of 8.
Setting of 2nd-most significant bit makes it unclear if the aggregate key will still be a key that could be generated directly.
Need to agree on value of \( k \) for signing.
Probably not an issue in practice; will require some communication.
Standardisation Drafts
There are currently two IETF drafts relating to threshold schemes for elliptic curves, both by P. M. Hallam-Baker
Specifically covers threshold signature schemes for Ed25519 (and Ed448)
Strictly speaking, this draft expired in July 2021.
Hallam-Baker Drafts
Gives a threshold threshold signing-method that works both directly and via Shamir secret sharing.
Two roles: “dealer” and “signer”. Dealer requests signatures (and controlls the flow), and signers perform signature.
Points out several attacks.
Of particular note: the deterministic value of \( r \) when signing can be exploited by the dealer to potentially discover the signing keys of the signers. Recommends random generation instead.
Notable absense of method to generate keys for Shamir secret sharing variant.
The section named “Distributed Key Generation” has content consisting of only “[TBS]”.
Hallam-Baker Signing Protocol
We assume that each signer, \( \Psi_i \) has a keypair \( (a_i, \cvPt{A}_i \) ).
Dealer selects and notifies signers, sends \( M \) to signers.
Transmiting \( \cvPt{R}_i \) and \( S_i \) to the dealer.
The dealer completes the signature by:
Computing \( S = \sum_i S_i \)
Verifying that the signature \( (\cvPt{R}, S) \) is valid
TIDE System
The TIDE system uses the same signing protocol as Hallam-Baker
TIDE have solved the distributed key generation problem absent in the Hallam-Baker drafts, using the swarm random number generator described by Geetika.
No actor—nether the user (the dealer), nor the ORKs (the signers and key generators)—ever sees or the aggregate secret scalar.
The aggregate secret scalar is never stored.
Signing is nonetheless possible becuse of the Shamir secret sharing implemented in the swarm random number generator.
TIDE Swarm Ed25519 Key Generation
The users selects \( n \) ORK's to generate the key and act as signers.
Each ORK, \( O_i \) generates
A secret scalar \( a_i \).
A \( t \)-in-\( n \) Shamir secret sharing polynomial \( P_i(x) \) to share secret \( a_i \)
in addition, \( O_i \), also has a known unique (to the Swarm) \( x \)-coordinate, \( x_i \).
Each ORK, \( O_i \) calculates:
Public key \( \cvPt{A}_i = a_i\cvPt{G} \).
Shares \( (x_j, P_i(x_j)) \) of its secret scalar for all other ORKS, \( O_j \) in the swarm. These are encrypted.
and transmits these to the user.
After receiving responses from all ORKs in the swarm, the user:
Calculates \( \cvPt{A} = \sum_i \cvPt{A}_i \).
Transmits to each ork, \( O_i \) the value \( \cvPt{A} \) and all shares \( (x_i, P_j(x_i) ) \) for that ORK.
Each ORK, \( O_i \) calculates it's share of the aggregate secret scalar \( \sigma_i = \left(x_i, \sum_{j=1}^n P_j(x_i)\right)\)
The aggregate secret scalar is \( a = \sum_{i=1}^n a_i \).