# Multiparty Strict Coin-Tossing Protocols Based on the Eigenvalue

Authors: Zhang YanShuo; Wang ZeHao; Zhang Le; Xia Chao
Journal: Security and Communication Networks
 (2022)

---

## Abstract

The coin-tossing protocol is an important research area in cryptography. It generates a random bit with uniform distribution even if some participants might fraud. However, traditional coin-tossing protocol could not solve the situation of multiparty. It only divides participants into two parts. In this paper, a new kind of multiparty strict coin-tossing protocol based on the eigenvalue of matrix was proposed. First, matrix tampering attacks can be resisted. On the other hand, collusion attack which was caused by the addition of the Lagrange interpolation formula could be overcome. The analysis shows that the correctness and security of both protocols was guaranteed. Based on the above statements, comparing with the classic coin-tossing protocols, the proposed scheme has the advantage of resisting parties aborting, low complexity, and practicability.


---

## Body

## 1. Introduction

In network communication that the communicating party is not in the same geographical position, once the judgment needs to be made, both parties should compare the guessing result and ensure the information is not disclosed at the same time. The coin-tossing protocol can be seen as an application case for secure multiparty computation.In cryptography, suppose Alice and Bob throw coins, and before the results are revealed, neither side wants to let the other one knows their own result, which is one of the important models for multiparty confidential computing [1]. Obviously, as there is no third-party arbitration, the fairness based on fraud prevention has become the most important consideration for the coin-tossing protocol.Many scholars have conducted research on the coin-tossing protocol. In 1982, Blum introduced the problem of tossing a fair coin through a modem [2]. In 1990, Ben et al. proposed a coin throw problem in Reference [3]. In 2003, Lindell et al. raised the fair coin-tossing protocol of two-party [4]. Kun et al. raised the coin-tossing protocol based on knapsack problem [5].Apparently, these protocols are limited to two parties and have not solved the problem of multiparty participation in coin-tossing. On the other hand, they did not solve the problem that all the participants have to decide their order in a fair way rather than be divided into two parts.In this paper, based on the matrix eigenvalues and eigenvectors, we have first proposed a new kind of strict multiparty coin-tossing protocol. Furthermore, we applied the Lagrange interpolation formula to design an improved strict multiparty tossing protocol which can resist collusion attacks. At last, analysis of both protocols and specific examples are proposed.


## 2. Basic Knowledge

### 2.1. Coin-Tossing Protocol

The definition of coin-tossing protocol is as follows:Definition 1.
[6] Coin-tossing protocols are protocols that generate a random bit with uniform distribution, although some corrupted parties might try to bias the output. The coin-tossing protocol is used as a building block in many cryptographic protocols.
Secure multiparty computation allows distrustful parties to compute it correctly and privately [4, 7, 8].The coin-tossing protocol raises questions of fairness and how corrupted parties can influence the scheme [9, 10].This is the problem we are going to discuss in the following section.


### 2.2. Eigenvalue and Eigenvector

The eigenvalue and eigenvector are defined as follows:Definition 2.
[11] Let A be a n-order matrix, if the number λ and n-dimensional nonzero column vectors p make the equation be established.(1)Ap=λp.
Then, the numberλ is called the eigenvalue of the matrix A, and the nonzero vector p is called the eigenvector of A corresponding to the eigenvalue λ. Equation (1) can also be written as follows:(2)A−λEp=0.
Equation (2) is a homogeneous linear system of n equations with n unknowns.


### 2.3. Lagrange Interpolation Formula

Letn+1 distinct interpolation points (nodes) xj,j=0,1…n, be given, together with corresponding numbers fj, which may or may not be samples of a function f. Unless stated otherwise, we assume that the nodes are real, although most of the results and comments generalize to the complex plane. Let ∏n denote the vector space of all polynomials of degree at most n. The classical problem addressed here is that of finding the polynomial p∈∏n that interpolates f at the points xj, i.e.,(3)pxj=fj,j=0,…,n.The problem is well-posed, i.e., it has a unique solution that depends continuously on the data. Moreover, as explained in virtually every introductory numerical analysis text, the solution can be written in the Lagrange form [12]:(4)px=∑j=0nfjljx,ljx=∏k=0,k≠jnx−xk∏k=0,k≠jnxj−xk.The Lagrange polynomiallj corresponding to the node xj has the following property:(5)ljxk=1,j=k,0,otherwise,j,k=0,…,n.


### 2.4. Meaning of Strict Multiparty

We could compare the protocols described in Section3 to the grouping process of a soccer game. A group of players are fairly and randomly divided into team A and team B. This process only divides the participants into two parts, but does not draw the strict order.Therefore, considering the order of all participants, we could define the meaning of the word “strict.” Its work process is more like drawing lots. All players need to decide their order in a fair way. We associate this idea with the matrix and propose a kind of the strict multiparty coin-tossing protocol.


## 2.1. Coin-Tossing Protocol

The definition of coin-tossing protocol is as follows:Definition 1.
[6] Coin-tossing protocols are protocols that generate a random bit with uniform distribution, although some corrupted parties might try to bias the output. The coin-tossing protocol is used as a building block in many cryptographic protocols.
Secure multiparty computation allows distrustful parties to compute it correctly and privately [4, 7, 8].The coin-tossing protocol raises questions of fairness and how corrupted parties can influence the scheme [9, 10].This is the problem we are going to discuss in the following section.


## 2.2. Eigenvalue and Eigenvector

The eigenvalue and eigenvector are defined as follows:Definition 2.
[11] Let A be a n-order matrix, if the number λ and n-dimensional nonzero column vectors p make the equation be established.(1)Ap=λp.
Then, the numberλ is called the eigenvalue of the matrix A, and the nonzero vector p is called the eigenvector of A corresponding to the eigenvalue λ. Equation (1) can also be written as follows:(2)A−λEp=0.
Equation (2) is a homogeneous linear system of n equations with n unknowns.


## 2.3. Lagrange Interpolation Formula

Letn+1 distinct interpolation points (nodes) xj,j=0,1…n, be given, together with corresponding numbers fj, which may or may not be samples of a function f. Unless stated otherwise, we assume that the nodes are real, although most of the results and comments generalize to the complex plane. Let ∏n denote the vector space of all polynomials of degree at most n. The classical problem addressed here is that of finding the polynomial p∈∏n that interpolates f at the points xj, i.e.,(3)pxj=fj,j=0,…,n.The problem is well-posed, i.e., it has a unique solution that depends continuously on the data. Moreover, as explained in virtually every introductory numerical analysis text, the solution can be written in the Lagrange form [12]:(4)px=∑j=0nfjljx,ljx=∏k=0,k≠jnx−xk∏k=0,k≠jnxj−xk.The Lagrange polynomiallj corresponding to the node xj has the following property:(5)ljxk=1,j=k,0,otherwise,j,k=0,…,n.


## 2.4. Meaning of Strict Multiparty

We could compare the protocols described in Section3 to the grouping process of a soccer game. A group of players are fairly and randomly divided into team A and team B. This process only divides the participants into two parts, but does not draw the strict order.Therefore, considering the order of all participants, we could define the meaning of the word “strict.” Its work process is more like drawing lots. All players need to decide their order in a fair way. We associate this idea with the matrix and propose a kind of the strict multiparty coin-tossing protocol.


## 3. Classic Coin-Tossing Protocols

### 3.1. Blum’s Coin-Tossing Protocol

Suppose two sides of the communication are Alice and Bob. They execute the following protocol [13]:Step1: Alice chooses a random bit a and sends a commitmentc = commit(a) to Bob.Step2: Bob chooses a random bitb and sends it to Alice.Step3: Alice sends the bit a to Bob together with de-commit(c).Step4: If Bob does not abort during the protocol, Alice outputsa⊕b, otherwise she outputs a random bit.Step5: If Alice does not abort during the protocol andc is a commitment to a, and then Bob outputs a⊕b, otherwise he outputs a random bit.


### 3.2. Coin-Tossing Protocol Based on Quadratic Residue

Suppose two sides of the communication are Alice and Bob. The protocol is as follows [14]:Step1: Bob chooses large prime numbersp,q and calculate n=pq, then chooses random number a that satisfied with Jacobi symbol [15] a/n=1 and sends n, a to Alice.Step2: Alice guesses if a is the quadratic residue ofn. Telling the result to Bob.Step3: Bob tells Alice she is right or not and sendsp,q to Alice.Step4: Alice checksp,q’s parity and calculates n=pq.


### 3.3. Coin-Tossing Protocol Based on One Way Function

Suppose two sides of the communication are Alice and Bob. They both hold a one way functionfx and do not know f−1x. The protocol is as follows [16]:Step1: Bob chooses a random numberx and sends Alice y=fx.Step2: Alice guesses the parity ofx and tells the result to Bob.Step3: Bob tells Alice she is right or not and sendsx to Alice.


## 3.1. Blum’s Coin-Tossing Protocol

Suppose two sides of the communication are Alice and Bob. They execute the following protocol [13]:Step1: Alice chooses a random bit a and sends a commitmentc = commit(a) to Bob.Step2: Bob chooses a random bitb and sends it to Alice.Step3: Alice sends the bit a to Bob together with de-commit(c).Step4: If Bob does not abort during the protocol, Alice outputsa⊕b, otherwise she outputs a random bit.Step5: If Alice does not abort during the protocol andc is a commitment to a, and then Bob outputs a⊕b, otherwise he outputs a random bit.


## 3.2. Coin-Tossing Protocol Based on Quadratic Residue

Suppose two sides of the communication are Alice and Bob. The protocol is as follows [14]:Step1: Bob chooses large prime numbersp,q and calculate n=pq, then chooses random number a that satisfied with Jacobi symbol [15] a/n=1 and sends n, a to Alice.Step2: Alice guesses if a is the quadratic residue ofn. Telling the result to Bob.Step3: Bob tells Alice she is right or not and sendsp,q to Alice.Step4: Alice checksp,q’s parity and calculates n=pq.


## 3.3. Coin-Tossing Protocol Based on One Way Function

Suppose two sides of the communication are Alice and Bob. They both hold a one way functionfx and do not know f−1x. The protocol is as follows [16]:Step1: Bob chooses a random numberx and sends Alice y=fx.Step2: Alice guesses the parity ofx and tells the result to Bob.Step3: Bob tells Alice she is right or not and sendsx to Alice.


## 4. Multiparty Coin-Tossing Protocol Based on the Eigenvalue

Suppose there aren participants who are marked as Pii=1,2…n. The protocol is based on finite field Zq where q>n and a secret matrix A which is held by P1. It is worth mentioning that matrix A has the following two properties:(1).
A is a n-order matrix.(2).
The eigen equation ofA has no multiple roots which means A has n different eigenvalues.SupposeA’s eigenvalues are λii=1,2…n and corresponding eigenvectors are pii=1,2…n. The content of the protocol is as follows:Step 1: ParticipantP1 chooses a secret n-order matrix A. P1 announces the main diagonal of A and all eigenvectors pii=1,2…n.Step 2: ParticipantsPii=2…n randomly select an eigenvector from pii=1,2…n and the last one belongs to participant P1. None of the eigenvectors could be chosen twice.Step 3: ParticipantP1 announces the secret matrix A. All participants calculate λii=1,2…n of their own according to equation (1).Step 4: Sortλii=1,2…n in ascending sequence, then each participant could get the corresponding order.As can be seen from the above protocol, the final order of each participant depends only on the size of the eigenvalues. It could not prevent multiple participants in the conspiracy from exchanging eigenvectors to adjust the order. This means that this protocol cannot resist collusion attack. We use the Lagrange interpolation formula to make up for this security hole.


## 5. Improved Multiparty Coin-Tossing Protocol Based on the Eigenvalue

Suppose there aren participants who are marked as Pii=1,2…n. The protocol is based on finite field Zq where q>n and a secret matrix A which is held by P1. It is worth mentioning that matrix A has the following two properties:(1)
A is a n-order matrix.(2)
The eigen equation ofA has no multiple roots which means A has n different eigenvalues.SupposeA’s eigenvalues are λii=1,2…n and corresponding eigenvectors are pii=1,2…n . The content of the protocol is as follows:Step 1: ParticipantP1 chooses a secret n-order matrix A. P1 announces the main diagonal of A and all eigenvectors pii=1,2…n.Step 2: ParticipantsPii=2,⋯n randomly select an eigenvector from pii=1,2…n and the last one belongs to participant P1. None of the eigenvectors could be chosen twice.Step 3: ParticipantP1 announces the secret matrix A. All participants calculate λii=1,2…n of their own according to equation (1).Step 4: All participantsPii=1,2…n randomly select constant ni∈Zq to form i,nii=1,2…n and calculate polynomial according to equation (3):(6)px=∑i=1nnilix,lix=∏k=1,k≠inx−k∏k=1,k≠jni−k.As there aren points in total, so px is a n−1-th degree polynomial at most:(7)px=a0+a1x+⋯+an−1xn−1,a0,a1…an−1∈Zq.We choose the coefficient of the nonzero minimum degree term inpx, suppose it is aj.Step 5: All participantsPii=1,2…n calculate:(8)si=λiaji=1,2…n.Sortsii=1,2…n in the ascending sequence, then each participant could get the corresponding order of themselves.


## 6. Instance of the Protocol

The protocol is based on finite fieldZ23. Suppose there are 6 participants who is marked as Pii=1,2,3 and a secret matrix A is held by P1. A is a 6-order matrix which is designed as follows:(9)A=5131804621817204701702108212172241122020051212172053.All eigenvalues and related eigenvectors pairsλi,pi (i = 1, 2, …, 6) are as follows:(10)λ1,p1=1,110101Τ;λ2,p2=2,111011Τ,λ3,p3=3,010111Τ;λ4,p4=4,101010Τ,λ5,p5=5,110111Τ;λ6,p6=6,101101Τ.Step1: According to the protocol, participantP1 holds the secret matrix A and announces the main diagonal: 5,18,0,22,5,3 and pii=1,2…6 to all members.Step2: Assume thatP2 chooses eigenvector p2, P3 chooses eigenvector p5, P4 chooses eigenvector p1, P5 chooses eigenvector p6, and P6 chooses eigenvector p3. The last eigenvector p4 is left to P1.Step3: ParticipantP1 announces the secret matrix A. All participants calculate λii=1,2…n of their own according to equation (1). So, the eigenvalues held by each participant are — P1:4;P2:2;P3:5;P4:1;P5:6;P6:3.Step4: All participantsPii=1,2…n randomly select constant ni∈Zq to form i,nii=1,2…n, assume that P1 chooses n1=5, P2 chooses n2=8, P3 chooses n3=1, P4 chooses n4=12, P5 chooses n5=6, and P6 chooses n6=18, we can obtain px according to equation (3):(11)px=5×x−2x−3x−4x−5x−61−21−31−41−51−6+8×x−1x−3x−4x−5x−62−12−32−42−52−6+1×x−1x−2x−4x−5x−63−13−23−43−53−6+12×x−1x−2x−3x−5x−64−14−24−34−54−6+6×x−1x−2x−3x−4x−65−15−25−35−45−6+18×x−1x−2x−3x−4x−56−16−26−36−46−5=22x5−2x4+13x3−12x2+17x+21.We choose the coefficient of the nonzero minimum degree term inpx, which is a0=21Step5: All participantsPii=1,2…n calculate:(12)s1=λ4a0=15;s2=λ2a0=19;s3=λ5a0=13;s4=λ1a0=21;s5=λ6a0=11;s6=λ3a0=17.Sortsii=1,2…n in the ascending sequence —s5,s3,s1,s6,s2,s4, the order of all members is —P5,P3,P1,P6,P2,P4.


## 7. Analysis of the Protocol

### 7.1. Analysis of Correctness

Because the protocol of multiparty is a kind of promotion of two-party, both have the same properties. We only need to analyze the situation of multiparty.When it comes to classic two-party coin-tossing protocol (suppose two sides of the communication are Alice and Bob), a correct and effective process should meet the following three principles [17]:(1)
Alice must throw a coin before Bob guess.(2)
After Bob guessing, Alice can no longer throw coins.(3)
Bob does not know how the coins land before guessing.Multiparty coin-tossing protocol also needs to meet these above principles. Under the premise of correct implementation of the protocol proposed in Sections4 and 5, once participant P1 announces the main diagonal of A and all eigenvectors pii=1,2…n, the “coin” has landed. Then, the step that every participant randomly chooses their own eigenvector can be seen as the “guess the front and back.” Apparently, this satisfies the principle one.The principle two is also satisfied. Since all eigenvectors have been selected in Step 2, so the coin throwing partyP1 cannot toss the coin again. On the other hand, because the main diagonal of A is made public, P1 has no way to change the eigenvalue of pii=1,2…n.The proof is detailed in Section 6.Obviously, the principle three is satisfied. Every participant has no need to know how the concrete structure of matrixA. Participant P1 cannot unilaterally deceive other participants for example tampering with the secret matrix as long as the protocol is executed correctly.To summarize, both protocols are based on the basic coin-tossing protocol’s principle of design. The correctness is proved.


### 7.2. Analysis of Security

There are three points worth discussing in terms of security. The first is the disclosure of the main diagonal and the eigenvectors of the secret matrix. This design prevents the matrix holderP1 from tampering with the secret matrix. The second is the resistance of the collusion attack by the Lagrange interpolation formula. The third is verification of legal participants.


#### 7.2.1. Protection against Matrix Tampering

What ifP1 is a fraud? Obviously if P1 only announces all eigenvectors pii=1,2…n of A, he can manipulate the result of a coin toss by alter the secret matrix A to make λii=1,2…n being different. The design of making the main diagonal of A public can prevent this kind of fraud. The proof is as follows:Proposition 1.
Only one exactly matrix can be determined by the main diagonal’s elements and all eigenvectors.
Prove: Suppose then-order secret matrix is A =  c1x12⋯x1nx21c2⋯x2n⋮⋮⋱⋮xn1xn2⋯cn whose elements is unknown except the main diagonal elements c1,c2…cn. Besides, eigenvalues λii=1,2…n of A are unknown and eigenvectors pii=1,2…n are all known. We suppose the column vector pi =  p1i,p2i…pniΤ,i=1,2…n and vector composed of unknowns is x =  x12⋯x1n,x21,x23⋯x2n⋯xn1⋯xnn−1,λ1,λ2⋯λnΤ, According to formula (1), we can get Api=λipi, i=1,2⋯n, which is equation set:(13)c1p1i+x12p2i+⋯+x1npni=λip1i,x21p1i+c2p2i+⋯+x2npni=λip2i,⋮,xn1p1i+xn2p2i+⋯+cnpni=λipni,,i=1,2…n.We put the term with the unknowns on the left and the constant term on the right:(14)x12p2i+⋯+x1npni−λip1i=−c1p1i,x21p1i+⋯+x2npni−λip2i=−c2p2i,⋮,xn1p1i+⋯+xnn−1pn−1i−λipni=−cnpni,,i=1,2…n.The above system of nonhomogeneous linear equations can be considered as the form ofDx=b, D is the coefficient matrix and b is the vector consist of constant terms. The coefficient matrix D is as follows:(15)D=p2i,p3i…pni︷n−10,0…0︷n−1n−10,0…0︷i−1−p1i0,0…0︷n−i0,0…0︷n−1p1i,p3i…pni︷n−10,0…0︷n−1n−2+i−1−p2i0,0…0︷n−i⋱⋮⋮0,0…0︷n−1n−1p1i,p2i…pn−1i︷n−10,0…0︷i−1−pni0,0…0︷n−i,i=1,2…n.Wheni is arranged from 1 to n row by row, the size of the coefficient matrix D is n2×n2.Because the eigenvector pii=1,2⋯n are linearly independent, the elementary row operation cannot make any row of the matrix get all 0s which means the rank of D is full. We obtain the following conclusion:(16)rD=rD|b=n2.The system of nonhomogeneous linear equationsDx=b has a unique solution, only one exactly matrix A can be determined.The proposition we just proposed directly limitsP1 to tamper with matrix elements or matrix eigenvalues. Once the main diagonal and all eigenvectors are published, the secret matrix A is locked. But there is still a security issue, what if two or more participants collude to deceive? For example, Alice and Bob exchange the eigenvector of themselves. At this time, the role of the Lagrange interpolation formula is reflected.


#### 7.2.2. Protection against Collusion Attack

The main purpose of the introduction of the Lagrange interpolation formula is to prevent members from collusion attacks. This idea mainly comes from Shamir’s Lagrange interpolation secret sharing threshold system [18–20].The scheme in Section4 directly determines the final strict order based on the sort of the eigenvalues. However, in the improved protocol proposed in Section 5, we do not directly sort the eigenvalues, all the participants negotiate a polynomial together and take a nonzero coefficient as a factor. This makes the final order completely random and is decided by all participants, and any collusion attack will not work.


#### 7.2.3. Verification

Suppose participantp1 wants to manipulate the result of a coin toss. The only way he can take is to alter the secret matrix A. However, participants can identify the fraud in the following ways:(1)
The main diagonal and eigenvectors ofA are not the same as what P1 published.(2)
Cannot calculate the correctλ like λ is not in finite field Zq.(3)
There are one or more repeated eigenvalues of matrixA.As long as any of the above three cases occur, it should be taken seriously because of fraud. At this time, participants who have an abnormal situation will report an error.From this perspective, participantP1 is under the supervision of all people. The protocol is reliable.


## 7.1. Analysis of Correctness

Because the protocol of multiparty is a kind of promotion of two-party, both have the same properties. We only need to analyze the situation of multiparty.When it comes to classic two-party coin-tossing protocol (suppose two sides of the communication are Alice and Bob), a correct and effective process should meet the following three principles [17]:(1)
Alice must throw a coin before Bob guess.(2)
After Bob guessing, Alice can no longer throw coins.(3)
Bob does not know how the coins land before guessing.Multiparty coin-tossing protocol also needs to meet these above principles. Under the premise of correct implementation of the protocol proposed in Sections4 and 5, once participant P1 announces the main diagonal of A and all eigenvectors pii=1,2…n, the “coin” has landed. Then, the step that every participant randomly chooses their own eigenvector can be seen as the “guess the front and back.” Apparently, this satisfies the principle one.The principle two is also satisfied. Since all eigenvectors have been selected in Step 2, so the coin throwing partyP1 cannot toss the coin again. On the other hand, because the main diagonal of A is made public, P1 has no way to change the eigenvalue of pii=1,2…n.The proof is detailed in Section 6.Obviously, the principle three is satisfied. Every participant has no need to know how the concrete structure of matrixA. Participant P1 cannot unilaterally deceive other participants for example tampering with the secret matrix as long as the protocol is executed correctly.To summarize, both protocols are based on the basic coin-tossing protocol’s principle of design. The correctness is proved.


## 7.2. Analysis of Security

There are three points worth discussing in terms of security. The first is the disclosure of the main diagonal and the eigenvectors of the secret matrix. This design prevents the matrix holderP1 from tampering with the secret matrix. The second is the resistance of the collusion attack by the Lagrange interpolation formula. The third is verification of legal participants.


### 7.2.1. Protection against Matrix Tampering

What ifP1 is a fraud? Obviously if P1 only announces all eigenvectors pii=1,2…n of A, he can manipulate the result of a coin toss by alter the secret matrix A to make λii=1,2…n being different. The design of making the main diagonal of A public can prevent this kind of fraud. The proof is as follows:Proposition 1.
Only one exactly matrix can be determined by the main diagonal’s elements and all eigenvectors.
Prove: Suppose then-order secret matrix is A =  c1x12⋯x1nx21c2⋯x2n⋮⋮⋱⋮xn1xn2⋯cn whose elements is unknown except the main diagonal elements c1,c2…cn. Besides, eigenvalues λii=1,2…n of A are unknown and eigenvectors pii=1,2…n are all known. We suppose the column vector pi =  p1i,p2i…pniΤ,i=1,2…n and vector composed of unknowns is x =  x12⋯x1n,x21,x23⋯x2n⋯xn1⋯xnn−1,λ1,λ2⋯λnΤ, According to formula (1), we can get Api=λipi, i=1,2⋯n, which is equation set:(13)c1p1i+x12p2i+⋯+x1npni=λip1i,x21p1i+c2p2i+⋯+x2npni=λip2i,⋮,xn1p1i+xn2p2i+⋯+cnpni=λipni,,i=1,2…n.We put the term with the unknowns on the left and the constant term on the right:(14)x12p2i+⋯+x1npni−λip1i=−c1p1i,x21p1i+⋯+x2npni−λip2i=−c2p2i,⋮,xn1p1i+⋯+xnn−1pn−1i−λipni=−cnpni,,i=1,2…n.The above system of nonhomogeneous linear equations can be considered as the form ofDx=b, D is the coefficient matrix and b is the vector consist of constant terms. The coefficient matrix D is as follows:(15)D=p2i,p3i…pni︷n−10,0…0︷n−1n−10,0…0︷i−1−p1i0,0…0︷n−i0,0…0︷n−1p1i,p3i…pni︷n−10,0…0︷n−1n−2+i−1−p2i0,0…0︷n−i⋱⋮⋮0,0…0︷n−1n−1p1i,p2i…pn−1i︷n−10,0…0︷i−1−pni0,0…0︷n−i,i=1,2…n.Wheni is arranged from 1 to n row by row, the size of the coefficient matrix D is n2×n2.Because the eigenvector pii=1,2⋯n are linearly independent, the elementary row operation cannot make any row of the matrix get all 0s which means the rank of D is full. We obtain the following conclusion:(16)rD=rD|b=n2.The system of nonhomogeneous linear equationsDx=b has a unique solution, only one exactly matrix A can be determined.The proposition we just proposed directly limitsP1 to tamper with matrix elements or matrix eigenvalues. Once the main diagonal and all eigenvectors are published, the secret matrix A is locked. But there is still a security issue, what if two or more participants collude to deceive? For example, Alice and Bob exchange the eigenvector of themselves. At this time, the role of the Lagrange interpolation formula is reflected.


### 7.2.2. Protection against Collusion Attack

The main purpose of the introduction of the Lagrange interpolation formula is to prevent members from collusion attacks. This idea mainly comes from Shamir’s Lagrange interpolation secret sharing threshold system [18–20].The scheme in Section4 directly determines the final strict order based on the sort of the eigenvalues. However, in the improved protocol proposed in Section 5, we do not directly sort the eigenvalues, all the participants negotiate a polynomial together and take a nonzero coefficient as a factor. This makes the final order completely random and is decided by all participants, and any collusion attack will not work.


### 7.2.3. Verification

Suppose participantp1 wants to manipulate the result of a coin toss. The only way he can take is to alter the secret matrix A. However, participants can identify the fraud in the following ways:(1)
The main diagonal and eigenvectors ofA are not the same as what P1 published.(2)
Cannot calculate the correctλ like λ is not in finite field Zq.(3)
There are one or more repeated eigenvalues of matrixA.As long as any of the above three cases occur, it should be taken seriously because of fraud. At this time, participants who have an abnormal situation will report an error.From this perspective, participantP1 is under the supervision of all people. The protocol is reliable.


## 7.2.1. Protection against Matrix Tampering

What ifP1 is a fraud? Obviously if P1 only announces all eigenvectors pii=1,2…n of A, he can manipulate the result of a coin toss by alter the secret matrix A to make λii=1,2…n being different. The design of making the main diagonal of A public can prevent this kind of fraud. The proof is as follows:Proposition 1.
Only one exactly matrix can be determined by the main diagonal’s elements and all eigenvectors.
Prove: Suppose then-order secret matrix is A =  c1x12⋯x1nx21c2⋯x2n⋮⋮⋱⋮xn1xn2⋯cn whose elements is unknown except the main diagonal elements c1,c2…cn. Besides, eigenvalues λii=1,2…n of A are unknown and eigenvectors pii=1,2…n are all known. We suppose the column vector pi =  p1i,p2i…pniΤ,i=1,2…n and vector composed of unknowns is x =  x12⋯x1n,x21,x23⋯x2n⋯xn1⋯xnn−1,λ1,λ2⋯λnΤ, According to formula (1), we can get Api=λipi, i=1,2⋯n, which is equation set:(13)c1p1i+x12p2i+⋯+x1npni=λip1i,x21p1i+c2p2i+⋯+x2npni=λip2i,⋮,xn1p1i+xn2p2i+⋯+cnpni=λipni,,i=1,2…n.We put the term with the unknowns on the left and the constant term on the right:(14)x12p2i+⋯+x1npni−λip1i=−c1p1i,x21p1i+⋯+x2npni−λip2i=−c2p2i,⋮,xn1p1i+⋯+xnn−1pn−1i−λipni=−cnpni,,i=1,2…n.The above system of nonhomogeneous linear equations can be considered as the form ofDx=b, D is the coefficient matrix and b is the vector consist of constant terms. The coefficient matrix D is as follows:(15)D=p2i,p3i…pni︷n−10,0…0︷n−1n−10,0…0︷i−1−p1i0,0…0︷n−i0,0…0︷n−1p1i,p3i…pni︷n−10,0…0︷n−1n−2+i−1−p2i0,0…0︷n−i⋱⋮⋮0,0…0︷n−1n−1p1i,p2i…pn−1i︷n−10,0…0︷i−1−pni0,0…0︷n−i,i=1,2…n.Wheni is arranged from 1 to n row by row, the size of the coefficient matrix D is n2×n2.Because the eigenvector pii=1,2⋯n are linearly independent, the elementary row operation cannot make any row of the matrix get all 0s which means the rank of D is full. We obtain the following conclusion:(16)rD=rD|b=n2.The system of nonhomogeneous linear equationsDx=b has a unique solution, only one exactly matrix A can be determined.The proposition we just proposed directly limitsP1 to tamper with matrix elements or matrix eigenvalues. Once the main diagonal and all eigenvectors are published, the secret matrix A is locked. But there is still a security issue, what if two or more participants collude to deceive? For example, Alice and Bob exchange the eigenvector of themselves. At this time, the role of the Lagrange interpolation formula is reflected.


## 7.2.2. Protection against Collusion Attack

The main purpose of the introduction of the Lagrange interpolation formula is to prevent members from collusion attacks. This idea mainly comes from Shamir’s Lagrange interpolation secret sharing threshold system [18–20].The scheme in Section4 directly determines the final strict order based on the sort of the eigenvalues. However, in the improved protocol proposed in Section 5, we do not directly sort the eigenvalues, all the participants negotiate a polynomial together and take a nonzero coefficient as a factor. This makes the final order completely random and is decided by all participants, and any collusion attack will not work.


## 7.2.3. Verification

Suppose participantp1 wants to manipulate the result of a coin toss. The only way he can take is to alter the secret matrix A. However, participants can identify the fraud in the following ways:(1)
The main diagonal and eigenvectors ofA are not the same as what P1 published.(2)
Cannot calculate the correctλ like λ is not in finite field Zq.(3)
There are one or more repeated eigenvalues of matrixA.As long as any of the above three cases occur, it should be taken seriously because of fraud. At this time, participants who have an abnormal situation will report an error.From this perspective, participantP1 is under the supervision of all people. The protocol is reliable.


## 8. Protocol Comparison

In Blum’s coin-tossing protocol, there are problems caused by parties aborting the protocol. It is proved that the best case is 1/4 of the bias of the protocol [6]. In this paper, apparently eigenvalue secrete matrix can not only solve this problem but also sort multi participants strictly. We only need to focus on the final sequence rather than pay attention to the specific value. Legitimate users are not affected.According to the coin-tossing protocol based on quadratic residue [7], the large prime numbers p,q are used to calculate composite number n. The execute of the protocol based on the quadratic residue calculation involving large prime numbers and congruence equations. Therefore, the computational complexity of the scheme is high. When it comes to the coin-tossing protocol based on the eigenvalue, the computational complexity is mainly based on the construction of secret matrix A which can be easily constructed. The reason lies in there is no need to care about the particular numbers of the eigenvalues.Some classic coin-tossing protocols lack of practicality. For example, the coin-tossing protocols based on one-way function [21] have this drawback because there are no real one-way functions, the almost-optimally fair multiparty coin-tossing [22] and multiparty coin tossing in four rounds [23] have no low complexity and strict property. In this respect, the proposal in this paper has advantage of practicability. The program can easily construct a matrix that has the properties to meet the requirements in protocols we proposed. The protocols in this paper are convenient and reliable.To summarize, a comparison of several coin-throwing protocols is shown in Figure1, which shows that our proposed solution is more advantageous.Figure 1
Comparison with classic coin-tossing protocols.


## 9. Conclusion

This paper first proposes a new kind of strict multiparty coin-tossing protocol based on the eigenvalue, then takes a step further to propose an improved version which is based on the Lagrange interpolation formula. The analysis shows the protocol is correct and can resist matrix tampering attack as long as collusion attack. Furthermore, we make sure the protocols based on the eigenvalue can resist parties aborting, have low complexity, and practicability which means they could easily be constructed.The coin-tossing protocol can resist the attack proposed in literature [24, 25], which has been studied in literature [26].



---

*Source: 1595520-2022-05-29.xml*