Provide authenticity and non repudiation assuming a secure public key infrastructure: Party A signs a message m with a signature Sig using its secret key \(\mathsf{sk_A}\). Party B verifies correctness of the signature using public key of party A \(\mathsf{pk_A}\) and gets assurances that the message trully came from party A, nobody tamper it and party A cannot deny that it signed message m using its secret key \(\mathsf{sk_A}\)
Signatures are used in our everyday digital life to sign transactions, payments, contracts, documents, reports, etc. With the wide adoption of cryptocurrencies, the validity of a transactions lies on the signature of the issuer who holds its secret key to a wallet. Bitcoin,Ethereum use ECDSA digital signature algorithm.
A dealer wants to secret share a secret \(s \in \mathbb{Z}_q\),for a prime \(q\) such that \(t\) shares \(\{y_i\}_{i=0}^{t-1}\) out of total \(n\) suffice to reconstruct the secret \(s\). It chooses a polynomial \(a=a_0+a_1x+a_2x^2+a_{t-1}x^{t-1}\) of degree \(t-1\), sets \(a_0=s\) and gives to each party \(P_i\) the share \(a(i) = y_i\), \(i\in 1...n\).
To reconstruct Lagrange interpolation is used. We are looking for ways to identify a unique polynomial \(p_{t-1}(x)\), which satisfies \(p(i)=y_i\) of degree \(t-1\), from \(t\) pairs \((x_i,y_i), i\in 1...t\). That can be seen as solving the equation: \[\mathbf{A}x=b\], for a matrix \(\mathbf{A}\) and vectors \(x,b\) where \(b_i=y_i, i\in 1...t\) and \(A_{i,j} = p_j(x_i)\), where \(p_j(x) = x^j\).
Define the interpolation polynomial: \[p_{t-1}(x) = \sum_{j=0}^{t}y_j\mathcal{L_{t-1,j}(x)}\]
where the Lagrange polynomials \(\mathcal{L_{t-1,j}}(x)\) are defined as follows:
\[\mathcal{L_{t-1,j}}(x) = \prod_{k=0,k\ne j}^{t}\frac{x-x_k}{x_j-x_k}\]
Finally the polynomial \(f(x)\) we are looking: \(f(x)= p_{t-1}(x)\)
Find the 2 degree polynomial from the following pairs
| i | x | y |
|---|---|---|
| 0 | 2 | 3 |
| 1 | 1 | 4 |
| 2 | -5 | 8 |
First construct the Lagrange polynomials
\(\mathcal{L_{2,0}}(2)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}=\frac{(x-1)(x+5)}{(2-1)(2+5)}=\frac{x^2+5x-x-5}{7} =\frac{1}{7}(x^2+4x-5)\)
\(\mathcal{L_{2,1}}(1)= \frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}=\frac{(x-2)(x+5)}{(1-2)(1+5)}=\frac{x^2+5x-2x-10}{-6}=\frac{-1}{6}(x^2+3x-10)\)
\(\mathcal{L_{2,2}}(-5) = \frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}=\frac{(x-2)(x-1)}{(-5-2)(-5-1)}=\frac{x^2-x-2x+2}{42}=\frac{1}{42}(x^2-3x+2)\)
Compute the interpolating polynomial:
\(p_{2}(x) = \sum_{j=0}^{2}y_j\mathcal{L}_{2,j}=y_0\mathcal{L}_{2,0}+y_1\mathcal{L}_{2,1}+y_2\mathcal{L}_{2,2}\\=3\frac{1}{7}(x^2+4x-5)+4\frac{-1}{6}(x^2+3x-10)+8\frac{1}{42}(x^2-3x+2)\\=\frac{3}{7}(x^2+4x-5)-\frac{2}{3}(x^2+3x-10)+\frac{4}{21}(x^2-3x+2)\\=\frac{1}{3}x^2-\frac{18}{21}x+\frac{103}{21} = f(x)\)
That does not seem correct :) I am missing sth.
Goal: A coalition of \(n\) parties being able to generate a key such that without collaboration (\(t\) out of \(n\), \(t\le n\) ) noone knows the final secret key.
Verifiable secret sharing allows the receivers of the shares to verify whether they are consistent to all the participants and to the secret key the party has chosen. e.g: What if a party shares his correct public key with party \(j\) but a wrong one with all other parties?
JoinPublicKey: Each party \(P_i\) chooses secret \(x_i\) from \(\mathbb{Z}_q\) and broadcasts to all \(h_i=g^{x_i}\). The public key for everyone is \(\prod_{i=0}^{n-1}{h_i} =g^{ \sum_{i=0}^{n-1}{x_i}}\).
VerifyShare: Each party \(P_i\) chooses chooses a polynomial of degree \(k-1\): \[f_i = x_i+f_{i1}x+f_{i2}x^2+\cdots+f_{i1}x^3+f_{i,k-1}x^{k-1}\]
To avoid single point of failure: stealing/loosing the secret signing key which authorizes transfers of assets - threshold signatures are adopted by FinTech industry to distribute trust among multiple signers holding a share of the secret key but never the secret key at each entire form. Threshold ECDSA aglorithms in general are executed in two phases between \(n\) parties:
[TODO]:Add appropriate security definitions. Basically unforgeability: malicious parties cannot produce signatures for messages they haven't seen their signatures. Depends on number of corrupted parties: honest/dishonest majority and malicious/passive adversaries
[MR04,GGN16,L17]: 2 parties setting
ThresholdKeyGen:
ThresholdSign:
[MR04]: That works well for honest but curious adversaries. For malicious adversaries expensive ZKP are needed.
[L17] approach removes ZKP with some more preparation:
Notice that if \(P_1\) is malicious then its only input to the protocol is \(k_1,x_1\) for the DH exchange and can be proven secure with ZKP. Another proof is needed to guarantee \(P_1\) actually faithfully encrypted \(E_{pk1}(x_1)\): Given \(X_1=x_1\cdot G\) and \(E_{pk1}(x_1)\) prove that there exists such \(x_1\).
If \(P_2\) wants to cheat by sending an invalid message \(\sigma'\) then \(P_1\) can recompute the signature and check whether \(P_2\) is cheating because \(\sigma'\) is almost one step before being a valid signature: \(\sigma'=\sigma\cdot k_1^{-1}\). As such, there is no need for expensive ZKP.
The more well established hard problem assumptions a protocol is based its security, the better.
Rounds of the MPC protocol are mostly governing the complexity for threshold signatures schemes - thus network latency is crucial.
Honest majority: The majority of the players has the expected behavior in terms of funtionality and obey in the protocol rules: Out of \(n\) players at least \((n-1)/2\) are honest.
Dishonest majority: The majority of the players behave arbitrarily.
Static: The adversary has chosen before the beginning of the protocl which parties will corrupt.
Adaptive: The adversary can wait before the protocol starts to select the corrupted parties.
Identifiable abort: The honest parties can faithfully identify the cheating parties.
Honest majority allows for simpler protocols and subsequently more efficient but in real world that might be a strong assumption.
Bohen-Lynn-Shacham (BLS) is a determnistic signature scheme that uses bilinear pairings. It enjoys many interesting properties, such as: unique signatures that are unpredictable, signatures can be used as verifiable pseudo-random values, signatures can be aggregated in a compact fashion. Importantly is amenable to distributed computation.
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe