In 2002, Cachin et. al defined Asynchronous Verifiable Secret Sharing (AVSS) method and which uses bi-variate polynomials [1]. In most secret sharing schemes we have a polynomial with one variable, such as \(p(x)=a_0+a_1x+a_2x^2+...\). With Shamir's Secret Shares we store the secret share at \(a_0\), and where we distribute points on the polynomial, and then rebuild them back into a polynomial, and which should then reveal the secret. With AVSS we use bi-variate polynomials and which has two variables (\(x\) and \(y\)). Bi-variate polynomials are in the form of \(f(x,y) =a_{00} + a_{10}x + a_{01} y + a_{11} xy + a_{21} x^2y + + a_{12} xy^2 + a_{22} x^2y^2 + ... \). In this case, the secret is kept at \(a_{00}\). With the Shamir method, we define a threshold (\(t\)) from a number of shares (\(n\)), and then aim to recover a polynomial \(f(x,y\)) and where the secret share is at \(f(0,0\)).
Asynchronous Verifiable Secret Sharing (AVSS) |
Background
Within secret sharing models we can have three main categories:
- Synchronous model. This is implemented in systems that use a global clock to synchonise messages, and where there will be well-defined delays in processing.
- Asynchronous model. This is where there is no synchonization of messages, and where delays can vary depending on workloads. One of the key issues is that it is difficult to differentiate a slow response from a participating party from a corrupt sender who refuses to send back messages. This leads to more complexity in the methods used by asychronous methods.
- Hybrid. This is a mixture of synchonous and asynchronous models, and where there may be a few rounds of synchonization followed by asychronous operations.
In a typical secret sharing method, the dealer defines a polynomial of \(p(x)=a_0+a_1x+a_2x^2+...\) and where \(a_0\) defines the secret. The dealer then sends out points on the polynomial, such for \(x=1\) and where we have the \(y\) value of \(p(x=1)\). We can also create a commitment from the dealer, so that each participant can check that their share is valid. Within an asychronous environment, the dealer may not wait around before all the shares have been acknowledged. AVSS supports a participating party to reconstruct its share using a distributed protocol that does not require the dealer to be present. This requires \(f+1\) participants. In asynchronous settings in which if participants might fail, a dealer can wait for at most n f participants to acknowledge receiving a valid share, before it inevitably may walk away. The asynchronous VSS problem requires that if the dealer (or any participant) completes the sharing protocol, then every correct participant can eventually reconstruct its share using a distributed protocol involving \(f + 1\) participants.
In AVSS, we start with a bi-variate polynomial (\(m \times n\)):
\(f(x,y) = \sum_{k=0}^{n-1}\sum_{j=0}^{m-1} a_{jk}x^ky^j\)
For \(n=3\) and \(m=3\), we have:
\(f(x,y) =a_{00} + a_{10}x + a_{01} y + a_{11} xy + a_{21} x^2y + + a_{12} xy^2 + a_{22} x^2y^2 \)
In a secret sharing system, we aim to find the solution at \(p(0,0)\).
We can represent the factors in a matrix form of:
\( \begin{equation*} v_{m,n} = \begin{pmatrix} a_{0,0} & a_{0,1} & \cdots & a_{0,n-1} \\ a_{1,0} & a_{1,1} & \cdots & a_{1,n-1} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m-1,1} & a_{m-1,1} & \cdots & a_{m-1,n-1} \end{pmatrix} \end{equation*} \)
In AVSS, we place the secret at \(a_{0,0}\) and random values in the other positions:
\( \begin{equation*} f_{m,n} = \begin{pmatrix} s & r_{0,1} & \cdots & r_{0,n-1} \\ r_{1,0} & r_{1,1} & \cdots & r_{1,n-1} \\ \vdots & \vdots & \ddots & \vdots \\ r_{m-1,1} & r_{m-1,1} & \cdots & r_{m-1,n-1} \end{pmatrix} \end{equation*} \)
We then generate a random matrix:
\( \begin{equation*} f'_{m,n} = \begin{pmatrix} v_{0,0} & v_{0,1} & \cdots & v_{0,n-1} \\ v_{1,0} & v_{1,1} & \cdots & v_{1,n-1} \\ \vdots & \vdots & \ddots & \vdots \\ v_{m-1,1} & v_{m-1,1} & \cdots & v_{m-1,n-1} \end{pmatrix} \end{equation*} \)
We then take a base point on the secp256k1 curve (\(G\)) and then scale with \(f_(m,n)\), and then add this to \(f'(m,n)\) to another base point (\(H\)). This then gives gives a number of secp256k1 points for the commitments from the dealer:
\( \begin{equation*} C_{m,n} = \begin{pmatrix} sG + r_{0,0}H & r_{0,1}G+ r_{0,1}H & \cdots & r_{0,n-1}G + r_{0,n-1}H \\ r_{1,0}G + r_{1,0}H & r_{1,1}G + r_{1,1}H & \cdots & r_{1,n-1}G + r_{1,n-1}H \\ \vdots & \vdots & \ddots & \vdots \\ r_{m-1,1}G + r_{m-1,1}H & r_{m-1,1}G + r_{m-1,1}H & \cdots & r_{m-1,n-1}G + r_{m-1,n-1}H \end{pmatrix} \end{equation*} \)
Each of the nodes \(i\) then get:
\(C\)
\(a_i(y) = f(i,y)\)
\(a_i'(y) = f'(i,y)\)
\(b_i(x) = f(x,i)\)
\(b_i'(x) = f'(x,i)\)
Thus Node 1 (\(x=1\)) gets the polynomial factors of:
\( a_1(y) = sG+ v_{0,0}H, r_{0,1}G + v_{0,1}H, \cdots r_{0,n-1}G + v_{0,n-1}H \)
Thus Node 2 (\(x=2\)) gets the polynomial factors of:
\(a_2(y) = sG+ v_{0,0}H, r_{0,1}G + v_{0,1}H \times 4, \cdots r_{0,n-1}G + v_{0,n-1}H \times 2^{n-1}\)
Thus Node 3 (\(x=3\)) gets the polynomial factors of:
\(a_3(y) = sG+ v_{0,0}H, r_{0,1}G + v_{0,1}H \times 9, \cdots r_{0,n-1}G + v_{0,n-1}H \times 3^{n-1}\)
Every node \(i\) will receive \(C\), the share polynomial of \(a_i(y)\) and \(a_i'(y)\), and the sub-share polynomials are \(b_i(y)\) and \(b_i'(y)\)
Each node can then check their shares against the commitment from the dealer.
The sequence is then:
1. The Dealer creates a bi-variate polynomial and puts the secret at \(f(0,0)\) and with random values at all the other other places in the matrix:
f := GenerateRandomBivariatePolynomial(secret, threshold)
2. Create random bitvariate polynomial:
fprime := GenerateRandomBivariatePolynomial(*RandomBigInt(), threshold)
3. Create commitment matrix, and which is the point assigns the \(f\) as scalar values to the \(G\) base point, and \(fprime\) with the \(H\) based point, and then adds these together, to get the form \(a_{ij}G + a'_{ij}H\).
C := GetCommitmentMatrix(f, fprime)
These are points on the secp256k1 curve. When a node receives a share, it can then check that the share is valid. In the following, we will take the first share for its validity:
sigma := polyEval(EvaluateBivarPolyAtX(f, *big.NewInt(int64(threshold))), 0) sigmaprime := polyEval(EvaluateBivarPolyAtX(fprime, *big.NewInt(int64(threshold))), 0) fmt.Printf("\n1st share: Sigma=%s, Sigma_p=%s", sigma, sigmaprime) rtn := AVSSVerifyShare(C, *big.NewInt(int64(threshold)), *sigma, *sigmaprime) fmt.Printf("\nVerified share: %v ", rtn)
Coding
The following code is based on the Tor.us source. In this case we will define \(t\) for the threshold and \(n\) for the number of shares:
// Based on https://github.com/torusresearch/torus-node package main import ( "crypto/rand" "fmt" "main/secp256k1" "math/big" "os" "strconv" ) func RandomBigInt() *big.Int { randomInt, _ := rand.Int(rand.Reader, secp256k1.GeneratorOrder) return randomInt } func AVSSVerifyShare(C [][]secp256k1.Point, m big.Int, sigma big.Int, sigmaprime big.Int) bool { sG := secp256k1.BigIntToPoint(secp256k1.Curve.ScalarBaseMult(sigma.Bytes())) rH := secp256k1.BigIntToPoint(secp256k1.Curve.ScalarMult(&secp256k1.H.X, &secp256k1.H.Y, sigmaprime.Bytes())) sGrH := secp256k1.BigIntToPoint(secp256k1.Curve.Add(&sG.X, &sG.Y, &rH.X, &rH.Y)) pt := secp256k1.Point{X: *big.NewInt(int64(0)), Y: *big.NewInt(int64(0))} for j := range C { Cj0 := C[j][0] mj := new(big.Int).Exp(&m, big.NewInt(int64(j)), secp256k1.GeneratorOrder) Cj0mj := secp256k1.BigIntToPoint(secp256k1.Curve.ScalarMult(&Cj0.X, &Cj0.Y, mj.Bytes())) pt = secp256k1.BigIntToPoint(secp256k1.Curve.Add(&pt.X, &pt.Y, &Cj0mj.X, &Cj0mj.Y)) } if sGrH.X.Cmp(&pt.X) != 0 || sGrH.Y.Cmp(&pt.Y) != 0 { return false } return true } func GenerateRandomBivariatePolynomial(secret big.Int, threshold int) [][]big.Int { bivarPolyCoeffs := make([][]big.Int, threshold) for j := range bivarPolyCoeffs { bivarPolyCoeffs[j] = make([]big.Int, threshold) for l := range bivarPolyCoeffs[j] { if j == 0 && l == 0 { bivarPolyCoeffs[j][l] = secret } else { bivarPolyCoeffs[j][l] = *RandomBigInt() } } } return bivarPolyCoeffs } func GetCommitmentMatrix(f [][]big.Int, fprime [][]big.Int) [][]secp256k1.Point { threshold := len(f) bivarPolyCommits := make([][]secp256k1.Point, threshold) for j := range bivarPolyCommits { bivarPolyCommits[j] = make([]secp256k1.Point, threshold) for l := range bivarPolyCommits[j] { gfjl := secp256k1.BigIntToPoint(secp256k1.Curve.ScalarBaseMult(f[j][l].Bytes())) hfprimejl := secp256k1.BigIntToPoint(secp256k1.Curve.ScalarMult( &secp256k1.H.X, &secp256k1.H.Y, fprime[j][l].Bytes(), )) bivarPolyCommits[j][l] = secp256k1.BigIntToPoint(secp256k1.Curve.Add(&gfjl.X, &gfjl.Y, &hfprimejl.X, &hfprimejl.Y)) } } return bivarPolyCommits } type PrimaryPolynomial struct { Coeff []big.Int Threshold int } func PolyEval(polynomial PrimaryPolynomial, x big.Int) *big.Int { return polyEval(polynomial, int(x.Int64())) } func polyEval(polynomial PrimaryPolynomial, x int) *big.Int { // get private share xi := big.NewInt(int64(x)) sum := new(big.Int) sum.Add(sum, &polynomial.Coeff[0]) for i := 1; i < polynomial.Threshold; i++ { tmp := new(big.Int).Mul(xi, &polynomial.Coeff[i]) sum.Add(sum, tmp) sum.Mod(sum, secp256k1.GeneratorOrder) xi.Mul(xi, big.NewInt(int64(x))) xi.Mod(xi, secp256k1.GeneratorOrder) } return sum } func EvaluateBivarPolyAtX(bivarPoly [][]big.Int, index big.Int) PrimaryPolynomial { fiY := PrimaryPolynomial{ Coeff: make([]big.Int, len(bivarPoly)), Threshold: len(bivarPoly), } for l := range bivarPoly[0] { // loop through horizontally first for j := range bivarPoly { // loop through vertically fiY.Coeff[l] = *new(big.Int).Add( &fiY.Coeff[l], new(big.Int).Mul( &bivarPoly[j][l], new(big.Int).Exp(&index, big.NewInt(int64(j)), secp256k1.GeneratorOrder), ), ) } } return fiY } func EvaluateBivarPolyAtY(bivarPoly [][]big.Int, index big.Int) PrimaryPolynomial { fiX := PrimaryPolynomial{ Coeff: make([]big.Int, len(bivarPoly)), Threshold: len(bivarPoly), } for j := range bivarPoly { // loop through vertically first for l := range bivarPoly[j] { // loop through horizontally fiX.Coeff[j] = *new(big.Int).Add( &fiX.Coeff[j], new(big.Int).Mul( &bivarPoly[j][l], new(big.Int).Exp(&index, big.NewInt(int64(l)), secp256k1.GeneratorOrder), ), ) } } return fiX } func showMatrix(msg string, m [][]big.Int, size int) { fmt.Printf("%s\n", msg) for i := 0; i < size; i++ { fmt.Printf("Row: ") for j := 0; j < size; j++ { fmt.Printf("%s ", m[i][j].String()) } fmt.Printf("\n") } fmt.Printf("\n") } func showPoints(msg string, m [][]secp256k1.Point, size int) { fmt.Printf("%s\n", msg) for i := 0; i < size; i++ { fmt.Printf("Row: ") for j := 0; j < size; j++ { fmt.Printf("%s ", m[i][j].X.String()) } fmt.Printf("\n") } fmt.Printf("\n") } func main() { threshold := 3 s := 5 nodes := 5 // secret := *RandomBigInt() argCount := len(os.Args[1:]) if argCount > 0 { s, _ = strconv.Atoi(os.Args[1]) } if argCount > 1 { threshold, _ = strconv.Atoi(os.Args[2]) } if argCount > 2 { nodes, _ = strconv.Atoi(os.Args[3]) } secret := *big.NewInt(int64(s)) fmt.Printf("Secret=%d, threshold=%d, nodes=%d\n", s, threshold, nodes) f := GenerateRandomBivariatePolynomial(secret, threshold) showMatrix("=== Show f (share at f(0,0))===", f, threshold) fprime := GenerateRandomBivariatePolynomial(*RandomBigInt(), threshold) showMatrix("=== Show f' ===", fprime, threshold) C := GetCommitmentMatrix(f, fprime) showPoints("=== Show Commitments (C - X points) ===", C, threshold) sigma := polyEval(EvaluateBivarPolyAtX(f, *big.NewInt(int64(threshold))), 0) sigmaprime := polyEval(EvaluateBivarPolyAtX(fprime, *big.NewInt(int64(threshold))), 0) fmt.Printf("\n1st share: Sigma=%s, Sigma_p=%s", sigma, sigmaprime) rtn := AVSSVerifyShare(C, *big.NewInt(int64(threshold)), *sigma, *sigmaprime) fmt.Printf("\nVerified share: %v ", rtn) /* for node := 0; node < nodes; node++ { i := *big.NewInt(int64(node + 1)) AIY := EvaluateBivarPolyAtX(f, i) AIprimeY := EvaluateBivarPolyAtX(fprime, i) BIX := EvaluateBivarPolyAtY(f, i) BIprimeX := EvaluateBivarPolyAtY(fprime, i) fmt.Printf("AIY=%v, AIprimeY=%v, BIX=%v, BIPrimeX=%v\n", AIY.Coeff, AIprimeY.Coeff, BIX.Coeff, BIprimeX.Coeff) } */ }
A sample run:
Secret=5, threshold=3, nodes=5 === Show f (share at f(0,0))=== Row: 5 9743195669945784265736128598508718513383431809992852931467201572222501709532 11921601245529184890572677981314550793638440277120977934507285858736284872764 Row: 38914775169750618295866116389646254021539712841774945361261041297120280450770 39728712398652269566024872460140072549594041362028713476440569412633907719597 93804328507791152440549289202239599104421824368912194876844146484734559224879 Row: 29699601562624258681390881187189276130152510632542564550139048371246796426949 20177829835342526168771993908034295528249900168488246059089443608353861373117 50725914710115279957671906851075719555745896639024880177910113896553695516565 === Show f' === Row: 115470196996176989345349889981956268662981937404082398634901967695935968192584 33044579844575268229918544233776696118670553243354949460102752276645043035280 94715233694196754547344213678075119784007634903399571068809848072191720921783 Row: 4340250202862599175210727375498478088765750740690216946430308017593134758098 36851108627021186689738145561635749516393072041227168049762415989053802072740 85484825408312771819133941960259191534837442943831567555553302176157039053809 Row: 92533102775313911545179309541127851019948561944739879791724032538117151496081 65933151131078972969485082821058756347303210836121412732507767307017160267569 86168717839084739660292482381227107627026797065820199045141906676115087565692 === Show Commitments (C) === Row: 115470196996176989345349889981956268662981937404082398634901967695935968192584 33044579844575268229918544233776696118670553243354949460102752276645043035280 94715233694196754547344213678075119784007634903399571068809848072191720921783 Row: 4340250202862599175210727375498478088765750740690216946430308017593134758098 36851108627021186689738145561635749516393072041227168049762415989053802072740 85484825408312771819133941960259191534837442943831567555553302176157039053809 Row: 92533102775313911545179309541127851019948561944739879791724032538117151496081 65933151131078972969485082821058756347303210836121412732507767307017160267569 86168717839084739660292482381227107627026797065820199045141906676115087565692 Sigma=36664471860921596749403324827578523677479041380983203887219069808027524711845, Sigma_p=34952158684060427389027977909099099286115732896212732538867879459624443976911 Verified share: true
Coding
Reference
[1] Cachin, Christian, et al. "Asynchronous verifiable secret sharing and proactive cryptosystems." Proceedings of the 9th ACM Conference on Computer and Communications Security. 2002 [here].
[2] Cachin, C., & Tessaro, S. (2005, October). Asynchronous verifiable information dispersal. In 24th IEEE Symposium on Reliable Distributed Systems (SRDS'05) (pp. 191-201). IEEE.