CN117240467A

CN117240467A - Method, system and node for realizing threshold signature

Info

Publication number: CN117240467A
Application number: CN202311119660.7A
Authority: CN
Inventors: 林立; 王欣; 王尧; 闫莺
Original assignee: Ant Blockchain Technology Shanghai Co Ltd
Current assignee: Ant Blockchain Technology Shanghai Co Ltd
Priority date: 2023-08-31
Filing date: 2023-08-31
Publication date: 2023-12-15
Also published as: WO2025043916A1

Abstract

A method of implementing a distributed threshold signature, comprising: a distributed key generation stage: each of the n participants generates a first random value and a second random value respectively, and exchanges with other participants after homomorphic encryption; each party generates a private key share based on the collected first and second random values and a sum of the secret shares generated by the distributed key generation protocol; an offline phase of distributed signing, each of at least t+1 participants performs: updating the share of the private key, generating a third random value of the private key and a public key corresponding to the third random value, and broadcasting; an online phase of distributed signing, each of the at least t+1 participants performing: after collecting the third random value public key, calculating the total coordinates of the third random value public key, and calculating r in the signature share of the message based on the total coordinates, and furtherCalculating a component s of the signature share of the message from r and the third random value of the self, the updated self private key share _i Thereby obtaining a signature share.

Description

Method, system and node for realizing threshold signature

Technical Field

The embodiment of the specification belongs to the technical field of cryptography, and particularly relates to a method, a system and a node for realizing threshold signature.

Background

In cryptography, public key cryptography, known as public key cryptography for short, is cryptography using a pair of public and private keys (public-private keys are denoted pk-sk, where pk represents public key, sk represents secret key), corresponding to cryptography using only one private key. Public key cryptography includes encryption algorithms and digital signature algorithms. Public-private key cryptography pairs are the basis for modern cryptographic security, and many applications are based on pk-sk, such as https (Hypertext Transfer Protocol Secure, secure hypertext transfer protocol) based application layer encrypted transport protocols, blockchain, etc.

The private key generally represents the identity of the party that owns the private key, which can only be held by the owner of the private key and cannot be disclosed, while the corresponding public key can be disclosed. Signing with the private key may represent approval by the private key owner of certain information of the digital world, and the signed information may also represent certain behavior of the private key owner in the message of the agreement. In general, an owner has a private key alone, and then the owner can sign a certain information by using its private key and send the signed information to other parties. After receiving this signature, the receiver can verify the signature using the corresponding public key. The recipient can confirm that the owner signed the information and that the signed information has not been tampered with.

Sometimes an account requires a flexible access control policy, especially where one account is commonly controlled by multiple parties on a blockchain. Under some requirements, one account needs to be commonly controlled by n participants. Thus, controlling the account, such as a transfer, requires approval by all n parties to control the account's transfer. Under other requirements, the account may be controlled without all consent from n participants, but with consent from t+1 of the n participants (t+1 < n, t being the threshold), which may be achieved by a threshold signature. In the threshold cryptography, private key information is shared to a plurality of independent participants, and each private key calculation requires agreement of the plurality of participants, so that the algorithm security is improved; and when a small number of participants fail and are not available, the usability of the private key is not affected. A secure (t, n) threshold cryptographic algorithm should be satisfied that (1) any more than t participants can calculate the final signature, exchanged keys or plaintext, while t or less than t participants cannot get any information about the above result; (2) No information about the private key and the private key shares of the participants is revealed during the execution of the algorithm.

Disclosure of Invention

The invention aims to provide a method, a system and a node for realizing threshold signature, which comprise the following steps:

a method of implementing a distributed threshold signature, comprising: a distributed key generation stage: each of the n participants generates a first random value and a second random value respectively, and exchanges with other participants after homomorphic encryption; each party generates a private key share based on the collected first and second random values and a sum of the secret shares generated by the distributed key generation protocol; an offline phase of distributed signing, each of at least t+1 participants performs: updating the share of the private key, generating a third random value of the private key and a public key corresponding to the third random value, and broadcasting; an online phase of distributed signing, each of the at least t+1 participants performing: after collecting the third random value public key, calculating the total coordinates of the third random value public key, calculating r in the signature share of the message based on the total coordinates, and calculating the component s of the signature share of the message based on r, the third random value of the message, the updated private key share of the message _i Thereby obtaining a signature share.

A computer device, comprising:

A processor;

and a memory in which a program is stored, wherein when the processor executes the program, the following operations are performed:

generating a first random value and a second random value, and exchanging with other participants after homomorphic encryption; each party generates a private key share based on the collected first and second random values and a sum of the secret shares generated by the distributed key generation protocol;

updating the share of the private key, generating a third random value of the private key and a public key corresponding to the third random value, and broadcasting;

after collecting the third random value public key, calculating the total coordinates of the third random value public key, calculating r in the signature share of the message based on the total coordinates, and calculating the component s of the signature share of the message based on r, the third random value of the message, the updated private key share of the message _i Thereby obtaining a signature share.

A storage medium storing a program, wherein the program when executed performs the operations of:

The scheme provided by the application can support any threshold value.

Drawings

In order to more clearly illustrate the technical solutions of the embodiments of the present disclosure, the drawings that are needed in the description of the embodiments will be briefly described below, and it is obvious that the drawings in the following description are only some embodiments described in the present disclosure, and that other drawings may be obtained according to these drawings without inventive effort for a person skilled in the art.

FIG. 1 is a schematic diagram of distributed threshold key generation in one embodiment;

figure 2 is a schematic diagram of a distributed threshold signature in one embodiment.

Detailed Description

In order to make the technical solutions in the present specification better understood by those skilled in the art, the technical solutions in the embodiments of the present specification will be clearly and completely described below with reference to the drawings in the embodiments of the present specification, and it is obvious that the described embodiments are only some embodiments of the present specification, not all embodiments. All other embodiments, which can be made by one of ordinary skill in the art without undue burden from the present disclosure, are intended to be within the scope of the present disclosure.

DKG (Distributed Key Generation) protocol, a distributed key generation protocol, refers to a distributed protocol that cooperatively generates a set of keys among a plurality of parties participating in the protocol. The VSS (Verifiable Secret Sharing) protocol, namely the verifiable secret sharing protocol, is an important theoretical basis of the DKG protocol.

VSS refers to the fact that, when sharing one piece of secret data among a plurality of parties, the secret data can be split into a plurality of pieces without revealing the secret data itself, and the pieces can be stored in the plurality of parties. Then, when the secret data needs to be restored, all the fragments need to be collected to successfully restore the complete secret data.

The VSS protocol was first proposed by Shamir in 1979 to be a polynomial-based secret sharing protocol. The VSS protocol was developed by Shamir's Secret Sharing (SSS), and Shamir Secret Sharing was first introduced.

Shamir secret sharing, which includes two phases of secret sharing (or secret distribution) and secret reconstruction, first requires the construction of a polynomial by a Dealer:

f(x)＝a ₀ +a ₁ x+a ₂ x ² +…+a _n x ⁿ polynomial (, x)

Wherein a is ₀ Is secret data to be shared.

The n-degree polynomial is composed of a set of coefficients (a ₀ ，a ₁ ，a ₂ ，…，a _n ) The unique determination, the set of coefficients includes n+1 values. Thus, if the curve corresponding to the n-th order polynomial is known to pass through n+1 different points on the plane, the coordinates (x ₁ ,y ₁ ),(x ₂ ,y ₂ ),…,(x _n ,y _n ),(x _n+1 ,y _n+1 ) Then a system of (n+1) th-order equations of n+1 equations can be obtained, from which the n+1 coefficients a can be determined ₀ ，a ₁ ，a ₂ ，…，a _n Further determining the polynomial (x), finally obtaining the secret data a ₀ Is a value of (2). Coordinates (x) ₁ ,y ₁ ),(x ₂ ,y ₂ ),…,(x _n ,y _n ),(x _n+1 ,y _n+1 ) I.e. n +1 secret slices.

With respect to solving for curves passing through points from existing points, this solving process is called polynomial interpolation. There are various ways to implement polynomial interpolation, and a common Lagrangian interpolation method is described below. Given an n-degree polynomial, the polynomial is known to correspond to a curve passing through n+1 points (x ₁ ,y ₁ ),(x ₂ ,y ₂ ),…,(x _n ,y _n ),(x _n+1 ,y _n+1 ) The polynomial of the nth order curve can be obtained by lagrangian interpolation as follows:

the polynomial (x) is in fact equivalent to the polynomial (x). Let x=0 in polynomial (x), then f (0) =a ₀ I.e. the secret data a can be obtained ₀ Is a value of (2). Therefore, the secret data a can also be obtained by setting x=0 in the polynomial (x:) ₀ Values of (2)I.e. f (0) =a ₀ 。

For n+1 points (x ₁ ,y ₁ ),…,(x _n ,y _n ),(x _n+1 ,y _n+1 ) The above polynomial (x) can also be expressed as:

wherein,also, for constant items or secret values, there are

In summary, n+1 points on the polynomial may be taken and shared among n+1 participants, e.g., each participant obtains coordinates of one point. Collecting coordinates of any less than n+1 points does not infer the original secret data a ₀ The secret data a can be restored by reconstructing the polynomial coefficients only after all n+1 points have been obtained ₀ Is a value of (2). In addition, even if the coordinates of any less than n+1 points, for example, the coordinates of n points are collected, since there are innumerable n-th-order curves passing through the n points, the secret data a cannot be leaked from the probability ₀ Is a value of (2). The degree of the polynomial is also referred to herein as the degree of the degree n.

Based on the method, threshold Shamir secret sharing can be achieved. For example, t-of-n secret sharing is to share secrets among n participants and specifies that the minimum secret shards required for recovery have a threshold value greater than t, i.e., greater than or equal to t+1. For example, in a transaction in which 4 parties participate, the agreed threshold is 3, i.e., n=4, t=2, and if t+1=3 parties are greater than or equal to t+1=3 parties provide own secret fragments, the secret can be restored, otherwise, the secret cannot be restored. Specifically, a polynomial of t=2 degrees may be constructed:

f(x)＝a ₀ +a ₁ x+a ₂ x ² Polynomial (/ x)

Can obtain 4 different points on the curve passing plane corresponding to the 2-degree polynomial, namely obtain coordinates (x) ₁ ,y ₁ ),(x ₂ ,y ₂ ),(x ₃ ,y ₃ ),(x ₄ ,y ₄ ) And the coordinates of the 4 points are distributed to one participant in the secret sharing stage. The 4 participants were set to Party ₁ ,Party ₂ ,Party ₃ ,Party ₄ Thus, assume Party ₁ Having slices (x) ₁ ,y ₁ )，Party ₂ Having slices (x) ₂ ,y ₂ )，Party ₃ Having slices (x) ₃ ,y ₃ )，Party ₄ Having slices (x) ₄ ,y ₄ ). Since the polynomial (x) can be determined from any 3 points on the corresponding curve, party is therefore _i When any three parties provide own secret shards in (i epsilon {1,2,3,4 }), a polynomial (x) can be restored in the secret reconstruction stage, so that a secret value a can be obtained ₀ . When any less than three parties provide own secret shards, the polynomial (x) cannot be restored, and the secret value a cannot be obtained ₀ . The above t is also referred to as a threshold.

The above Shamir secret sharing and threshold Shamir secret sharing require a role of generating polynomials and distributing secret patches, which may be referred to as Dealer. This Dealer is an entity that knows the secret and needs to be a trusted third party for each party. There is also a need for an entity, e.g. a Dealer or a party, but also other entities, for aggregating at least t+1 fragments and deriving secrets.

In engineering practice, polynomials are often defined in a finite field (based on elliptic curves or discrete logarithms) or in a prime field (based on RSA), rather than in a real or natural number field.

In the classical Shamir secret sharing scheme, the participants are assumed to be honest. In practice there may be dishonest behaviour, or so-called devil behaviour, e.g. deception of a certain party or parties, distribution of erroneous secret fragments to the party or parties, etc.

In secret sharing, verifiable secret sharing (Verifiable Secret Sharing, VSS) is proposed in order to verify a disfigurement, such as a party verifying that a Dealer spoofs itself (verifying whether the Dealer sent a wrong secret piece as described above). Feldman VSS is a practical VSS solution based on the Shamir secret sharing architecture, comprising:

the Dealer has a secret and distributes n slices of the secret to n participants, where t+1 participants can reconstruct the secret, and a t degree polynomial can be constructed using a threshold Shamir secret sharing scheme similar to that described above:

f(x)＝a ₀ +a ₁ x+a ₂ x ² +…+a _t x ^t polynomial (/ x)

Dealer is Party for each participant _i Optionally selecting a non-0 x _i Calculate s _i ＝f(x _i ) And secret the child s _i Encryption of Party sent to participant _i . Meanwhile, dealer calculationWhere j=0, 1,2,.. t, and disclose A _j I.e. publication { A ₀ ,A ₁ ,A ₂ ,…,A _t }。A _j Also referred to as public verification parameters. Here A _j The method of generating (a) is the same as the method of generating the public key based on the private key on the elliptic curve, and thus, a _j May also be referred to as public key sharding or public key sharing (share).

For the case where the selected polynomial is a corresponding elliptic curve, disclosure A _j Is safe because according to the nature of elliptic curve, it cannot be according to A _j Back-pushing to obtain a _j 。

Public authentication parameter { A ₀ ,A ₁ ,A ₂ ,…,A _t Also known as commitment. The commitment can be used to verify whether a value of the polynomial is correct, since the coefficients of the polynomial are bound. In discrete logarithm based implementations, g is the generator (gene) of the cyclic group over the finite fieldrator), g may be in Dealer and Party _i Pre-configured. The above-mentioned sub-secrets may also be referred to as secret shares.

The party receives the sub-secret s _i Thereafter, the common verification parameters may be employed to verify s _i Is effective in the following. S can be verified by verifying whether the following equation holds true _i Whether or not to be effective:

polynomial (.) x) of the following formula the right side can be derived as follows:

the right side of the polynomial (x) can also be written as:

it can be seen that for Party _i The Dealer selects a non-0 x for it _i ，x _i For example i, then Party _i I and a common authentication parameter { A }, may be employed ₀ ,A ₁ ,A ₂ ,…,A _t To the right of the polynomial (x) is computed and the generator g and the subsecret s are used _i To calculate the left side of the polynomial (x) and to determine whether the left and right sides of the polynomial (x) are equalWhether or not it is { A ₀ ,A ₁ ,A ₂ ,…,A _t Corresponds to a point on the curve. This verification belongs to the verification of the secret distribution phase. For simplicity, x can be taken generally _i ＝i。

General basis in engineeringIn discrete logarithm implementations, modulo arithmetic is used for the above formulas, e.g., mod p, where p is a large prime number, and p is also Dealer and Party _i Pre-configured. mod p is also omitted in the following analogy.

In the secret reconstruction phase, for example, at least t+1 participants respectively send their secret fragments to the Dealer, the Dealer can verify each secret fragment using the common verification parameters corresponding to the polynomial. Verification is not passed, and the party sending the secret shard can be proved to be wrongly; the secret shards that pass verification can be used as the basis for reconstructing the secret.

And in the secret reconstruction stage, after collecting secret fragments of at least t+1 participants, reconstructing a polynomial f (x) through a Lagrange interpolation method, thereby obtaining a value of f (0), and obtaining the secret value.

Furthermore, by the common authentication parameter { A } ₀ ,A ₁ ,A ₂ ,…,A _t May also be applied to secret a ₀ Is verified, i.e. can verify (0, a) ₀ ) Whether it is a point on the curve, because the following relationship exists:

that is, for the secret a ₀ Is verified by the validity of the (A) and can be simplified to pass through the public verification parameter A ₀ Realizing the method.

In the above derivation, 0 is defined ⁰ =1, and 0 ^k ＝0，k≠0。

In the above scenario, a Dealer is required, which is centralized, is a secret-aware entity, and as previously described, needs to be a trusted third party, or requires that the participants all trust the Dealer. In a distributed scenario, both distributed secret distribution and distributed secret reconstruction are required, which requires the removal of a centralized Dealer, thus implementing the de-trust. To address this problem, an improved protocol called join-Feldman was proposed by Rabin et al in 1999. The basic idea of this protocol is to execute the Feldman VSS protocol in parallel, where each participant generates a random polynomial locally and then shares the randomly selected secret value among all participants. Since it is a promise of the secret that is shared and not the secret itself, the secret cannot be recovered as long as multi-person collusion cheating exceeding the threshold t does not occur. Such Distributed VSS protocol with trusted third parties removed is also known as DVSS protocol (Distributed VSS).

Specifically, taking 4 participants as an example, assuming that the threshold t=2, the degree of the polynomial is also 2, and the decentralizing threshold secret sharing, that is, the Joint-Feldman implementation scheme, includes the following steps:

each P _i (Party _i Abbreviated as P _i I e {1,2,3,4 }) sets the secret s to be shared _i0 And randomly select other parameters to generate a t-degree polynomial:

participant P ₁ Generating a 2 degree polynomial:

f ₁ (z)＝a ₁₀ +a ₁₁ z+a ₁₂ z ² wherein a is ₁₀ Is P ₁ Set secret s ₁ ；

Participant P ₂ Generating a 2 degree polynomial:

f ₂ (z)＝a ₂₀ +a ₂₁ z+a ₂₂ z ² wherein a is ₂₀ Is P ₂ Set secret s ₂ ；

Participant P ₃ Generating a 2 degree polynomial:

f ₃ (z)＝a ₃₀ +a ₃₁ z+a ₃₂ z ² wherein a is ₃₀ Is P ₃ Set secret s ₃ ；

Participant P ₄ Generating a 2 degree polynomial:

f ₄ (z)＝a ₄₀ +a ₄₁ z+a ₄₂ z ² wherein a is ₄₀ Is P ₄ Set secret s ₄ 。

Next, each party P _i Generating and distributing n values on a curve corresponding to the t degree polynomial of the self, wherein n=4, t=2 and n are still set=1, 2,3,4, then:

participant P ₁ Generating s ₁₁ ＝f ₁ (1)、s ₁₂ ＝f ₁ (2)、s ₁₃ ＝f ₁ (3)、s ₁₄ ＝f ₁ (4) Self-reserve s ₁₁ And respectively encrypt and send s ₁₂ To P ₂ Encrypted transmission s ₁₃ To P ₃ Encrypted transmission s ₁₄ To P ₄ ；

Participant P ₂ Generating s ₂₁ ＝f ₂ (1)、s ₂₂ ＝f ₂ (2)、s ₂₃ ＝f ₂ (3)、s ₂₄ ＝f ₂ (4) Self-reserve s ₂₂ And respectively encrypt and send s ₂₁ To P ₁ Encrypted transmission s ₂₃ To P ₃ Encrypted transmission s ₂₄ To P ₄ ；

Participant P ₃ Generating s ₃₁ ＝f ₃ (1)、s ₃₂ ＝f ₃ (2)、s ₃₃ ＝f ₃ (3)、s ₃₄ ＝f ₃ (4) Self-reserve s ₃₃ And respectively encrypt and send s ₃₁ To P ₁ Encrypted transmission s ₃₂ To P ₂ Encrypted transmission s ₃₄ To P ₄ ；

Participant P ₄ Generating s ₄₁ ＝f ₄ (1)、s ₄₂ ＝f ₄ (2)、s ₄₃ ＝f ₄ (3)、s ₄₄ ＝f ₄ (4) Self-reserve s ₄₄ And respectively encrypt and send s ₄₁ To P ₁ Encrypted transmission s ₄₂ To P ₂ Encrypted transmission s ₄₃ To P ₃ 。

Also, each participant P _i And also generates public verification parameters corresponding to the self t degree polynomialWhere k=0, 1, …, t, and published to each party, specifically:

participant P ₁ GeneratingComprises->Broadcast { A ₁₀ ,A ₁₁ ,A ₁₂ Go to P ₂ 、P ₃ And P ₄ ；

Participant P ₂ GeneratingComprises->Broadcast { A ₂₀ ,A ₂₁ ,A ₂₂ Go to P ₁ 、P ₃ And P ₄ ；

Participant P ₃ GeneratingComprises->Broadcast { A ₃₀ ,A ₃₁ ,A ₃₂ Go to P ₁ 、P ₂ And P ₄ ；

Participant P ₄ GeneratingComprises->Broadcast { A ₄₀ ,A ₄₁ ,A ₄₂ Go to P ₁ 、P ₂ And P ₃ 。

Thus P ₁ Receiving s ₂₁ After that, { A } ₂₀ ,A ₂₁ ,A ₂₂ Verifying; p (P) ₁ Receiving s ₃₁ After that, { A } ₃₀ ,A ₃₁ ,A ₃₂ Verifying; p (P) ₁ Receiving s ₄₁ After that, { A } ₄₀ ,A ₄₁ ,A ₄₂ Verifying; the verification method is similar to the above, and will not be repeated.

Similarly, P ₂ Receiving s ₁₂ After that, { A } ₁₀ ,A ₁₁ ,A ₁₂ Verifying; p (P) ₂ Receiving s ₃₂ After that, { A } ₃₀ ,A ₃₁ ,A ₃₂ Verifying; p (P) ₂ Receiving s ₄₂ After that, { A } ₄₀ ,A ₄₁ ,A ₄₂ Verifying;

similarly, P ₃ Receiving s ₁₃ After that, { A } ₁₀ ,A ₁₁ ,A ₁₂ Verifying; p (P) ₃ Receiving s ₂₃ After that, { A } ₂₀ ,A ₂₁ ,A ₂₂ Verifying; p (P) ₃ Receiving s ₄₃ After that, { A } ₄₀ ,A ₄₁ ,A ₄₂ Verifying;

similarly, P ₄ Receiving s ₁₄ After that, { A } ₁₀ ,A ₁₁ ,A ₁₂ Verifying; p (P) ₄ Receiving s ₂₄ After that, { A } ₂₀ ,A ₂₁ ,A ₂₂ Verifying; p (P) ₄ Receiving s ₃₄ After that, { A } ₃₀ ,A ₃₁ ,A ₃₂ Verifying.

Assuming that the set of authenticated participants obtained after each participant is authenticated is set as Qual, and qual= { P is set ₁ ,P ₂ ,P ₃ ,P ₄ -such that:

P ₁ locally generated secret shares s with different parties ₁₁ 、s ₂₁ 、s ₃₁ 、s ₄₁ And a common authentication parameter { A } ₁₀ ,A ₁₁ ,A ₁₂ }，{A ₂₀ ,A ₂₁ ,A ₂₂ }，{A ₃₀ ,A ₃₁ ,A ₃₂ }，{A ₄₀ ,A ₄₁ ,A ₄₂ }；

P ₂ Locally generated secret shares s with different parties ₁₂ 、s ₂₂ 、s ₃₂ 、s ₄₂ And a common authentication parameter { A } ₁₀ ,A ₁₁ ,A ₁₂ }，{A ₂₀ ,A ₂₁ ,A ₂₂ }，{A ₃₀ ,A ₃₁ ,A ₃₂ }，{A ₄₀ ,A ₄₁ ,A ₄₂ }；

P ₃ Locally generated secret shares s with different parties ₁₃ 、s ₂₃ 、s ₃₃ 、s ₄₃ And a common authentication parameter { A } ₁₀ ,A ₁₁ ,A ₁₂ }，{A ₂₀ ,A ₂₁ ,A ₂₂ }，{A ₃₀ ,A ₃₁ ,A ₃₂ }，{A ₄₀ ,A ₄₁ ,A ₄₂ }；

P ₄ Locally generated secret shares s with different parties ₁₄ 、s ₂₄ 、s ₃₄ 、s ₄₄ And a common authentication parameter { A } ₁₀ ,A ₁₁ ,A ₁₂ }，{A ₂₀ ,A ₂₁ ,A ₂₂ }，{A ₃₀ ,A ₃₁ ,A ₃₂ }，{A ₄₀ ,A ₄₁ ,A ₄₂ }。

Then:

participant P ₁ Can calculate the secret share s ₁ The method comprises the following steps: s is(s) ₁ ＝s ₁₁ +s ₂₁ +s ₃₁ +s ₄₁ ；

Participant P ₂ Can calculate the secret share s ₂ The method comprises the following steps: s is(s) ₂ ＝s ₁₂ +s ₂₂ +s ₃₂ +s ₄₂ ；

Participant P ₃ Can calculate the secret share s ₃ The method comprises the following steps: s is(s) ₃ ＝s ₁₃ +s ₂₃ +s ₃₃ +s ₄₃ ；

Participant P ₄ Can calculate the secret share s ₄ The method comprises the following steps: s is(s) ₄ ＝s ₁₄ +s ₂₄ +s ₃₄ +s ₄₄ ；

Each participant P _i Can calculate the secret share s by itself _i Broadcast to other participants. Each party P _i Collect the alignment { s ] ₁ ,s ₂ ,s ₃ ,s ₄ After at least a threshold t+1 secret shares, the secret s can be reconstructed ₀ . Here, for t=2, each party P _i After collecting at least the threshold t+1=2+1=3 secret shares, the secret s can also be reconstructed ₀ 。

This is because the sum of the curves of the participants can be summed to give a total curve:

f(z)＝f ₁ (z)+f ₂ (z)+f ₃ (z)+f ₄ (z)

f(z)＝(a ₁₀ +a ₁₁ z+a ₁₂ z ² )+(a ₂₀ +a ₂₁ z+a ₂₂ z ² )+(a ₃₀ +a ₃₁ z+a ₃₂ z ² )

+(a ₄₀ +a ₄₁ z+a ₄₂ z ² )

f(z)＝(a ₁₀ +a ₂₀ +a ₃₀ +a ₄₀ )+(a ₁₁ +a ₂₁ +a ₃₁ +a ₄₁ )z+(a ₁₂ +a ₂₂ +a ₃₂ +a ₄₂ )z ²

polynomial (I)

This is the case:

s ₁ ＝s ₁₁ +s ₂₁ +s ₃₁ +s ₄₁ ＝f ₁ (1)+f ₂ (1)+f ₃ (1)+f ₄ (1)；

s ₂ ＝s ₁₂ +s ₂₂ +s ₃₂ +s ₄₂ ＝f ₁ (2)+f ₂ (2)+f ₃ (2)+f ₄ (2)；

s ₃ ＝s ₁₃ +s ₂₃ +s ₃₃ +s ₄₃ ＝f ₁ (3)+f ₂ (3)+f ₃ (3)+f ₄ (3)；

s ₄ ＝s ₁₄ +s ₂₄ +s ₃₄ +s ₄₄ ＝f ₁ (4)+f ₂ (4)+f ₃ (4)+f ₄ (4)；

for the total curve f (z), there is a relationship:

s ₁ ＝f ₁ (1)+f ₂ (1)+f ₃ (1)+f ₄ (1)＝f(1)；

s ₂ ＝f ₁ (2)+f ₂ (2)+f ₃ (2)+f ₄ (2)＝f(2)；

s ₃ ＝f ₁ (3)+f ₂ (3)+f ₃ (3)+f ₄ (3)＝f(3)；

s ₄ ＝f ₁ (4)+f ₂ (4)+f ₃ (4)+f ₄ (4)＝f(4)；

secret s ₀ ＝a ₁₀ +a ₂₀ +a ₃₀ +a ₄₀ 。

Thus, any party P _i Collecting secret shares s ₁ 、s ₂ 、s ₃ 、s ₄ After at least 3 points on the corresponding curve of the polynomial (I) are obtained, namely (x) ₁ ＝1,y ₁ ＝s ₁ ),(x ₂ ＝2,y ₂ ＝s ₂ ),(x ₃ ＝3,y ₃ ＝s ₃ ),(x ₄ ＝4,y ₄ ＝s ₄ ) At least 3 of these 4 coordinates, so that the total curve f (z) can be restored. Further, f (0) =a can be calculated ₁₀ +a ₂₀ +a ₃₀ +a ₄₀ ＝s ₀ Thus, the secret s can be obtained ₀ 。

Also, by verifying the parameter { A } ₁₀ ,A ₁₁ ,A ₁₂ }，{A ₂₀ ,A ₂₁ ,A ₂₂ }，{A ₃₀ ,A ₃₁ ,A ₃₂ }，{A ₄₀ ,A ₄₁ ,A ₄₂ May also be applied to secret s _i Can be verified by verifying the validity of (0, s) _i ) Whether it is a point on the total curve. Specifically, the validity is judged by verifying whether the following equation is established:

this is because the following relationship exists:

the right side of the polynomial (II) equal sign is also commonly referred to as public key share and is denoted as pub _i I=1, 2, …, n for verifying the corresponding private key share.

As previously mentioned, x can be taken generally _i I for eachi=1, 2, …, n. Thus, i can be the number of each participant.

For secret s ₀ Verification of (x), i.e. x _i =0, the above formula can be further deduced as follows:

definition 0 ⁰ =1, and 0 ^k =0, k+.0, so the above equation can be further derived:

It can be seen that based on the polynomial (III), s can be verified ₀ Is the legitimacy of (2).

Moreover, based on the derivation in the above polynomial (III), for verification s ₀ Can be further simplified into:

the right side of the polynomial (IV) is also generally designated as the total public key and is denoted as pub.

The join-Feldman protocol can realize distributed secret sharing, namely, the main content of DKG is completed. The above-described secret sharing implementation is a series of secret sharing implementations starting from Shamir to threshold Shamir, feldman VSS protocol, and then to join-Feldman DVSS protocol. In fact, besides the series of schemes taking Shamir secret sharing as a starting point, there are schemes based on additive secret sharing (Additive Secret Share), SPDZ (an important protocol in multiparty security computation, which was first proposed in 2012), or chinese remainder theorem, etc., and finally DKG may also be implemented, which is omitted here and not repeated.

By implementing the DKG protocol, the problem that a single point of failure is caused by generating a key by a single entity, so that the whole is not available, and the problem that a single point of generating the key needs to be trusted can be overcome. However, due to the individual parties P _i Broadcast-generated secret shares s _ij I, j e (1, 2, …, n), n being the number of participants, and each participant P _i Can calculate the secret share s by itself _i Broadcast to other participants so that each participant P _i Collect the alignment { s ] ₁ ,s ₂ ,s ₃ ,s ₄ After at least a threshold t+1 secret shares, the secret s can be reconstructed ₀ In this way, at least t+1 participants will be led to obtain the final reconstructed secret s ₀ I.e. the secret s will be exposed ₀ The total curve will also become unusable. If a new secret s is to be generated again next time ₀ The process of executing the DKG protocol needs to be repeated.

The DKG protocol can be used for constructing a distributed threshold signature protocol by combining the properties of threshold and secret promise and the like and a threshold signature algorithm matched with the DKG protocol. Blockchains are largely used as distributed systems with signature algorithms. In this way, nodes in the blockchain generate secret shares in a distributed manner through DKG, at least t+1 blockchain nodes adopt the secret shares as private key shares to sign information to be signed and broadcast, any blockchain node which collects at least t+1 signature shares can recover the total signature and recover the total public key in the mode, and the recovered total signature can be verified by the total public key, so that threshold signature is realized. Moreover, this has the advantage that the secret shares held by each block link point need not be broadcasted to other nodes, so that the secret shares of each block link point are not exposed, i.e. the private key is not exposed, and therefore the secret shares generated by one DKG can be reused many times without performing one DKG protocol for each threshold signature.

The national cipher is a domestic cipher algorithm identified by the national cipher bureau, and mainly comprises SM1, SM2, SM3, SM4 and the like. In public key cryptography, there are widely used ECC (Elliptic Curve Cryptography, elliptic curve cryptography, an asymmetric (or public key) encryption algorithm based on discrete logarithm problem, which can be expressed by adding or multiplying points on elliptic curve) and RSA (an asymmetric cryptographic algorithm, which is formed by splicing the first letters of Ron Rivest, adi shamir and Leonard Adleman surnames based on the multiplication result of two large prime numbers in a number theory) which are difficult to factor. Under the same security strength, the ECC is longer than the private key bit of RSA and the system parameters are much smaller, which means that the memory space required by applying ECC is much smaller, the bandwidth requirement for transmission is lower, the logic gate number of the logic circuit required by hardware to realize ECC is less than RSA, and the power consumption is lower. These advantages of ECC make it a public key cryptographic algorithm with development potential and application prospect, and several national and industry organizations have adopted ECC as a public key cryptographic algorithm standard by 2000 internationally. Under the background, the research of ECC of independent intellectual property rights is organized and studied from 2001 in China, and an SM2 algorithm is developed and completed at 2004 on the basis of absorbing the existing ECC research results at home and abroad by applying the public key cryptographic algorithm design and safety analysis theory and method which are accepted by the international cryptographic community. The SM2 algorithm is published in 12 th 2010 for the first time, and 3 rd 2012 becomes a commercial password standard (standard number is GM/T0003-2012) in China, and 8 th 2016 becomes a national password standard (standard number is GB/T32918-2016) in China.

SM2 contains a digital signature algorithm, a key exchange protocol and a public key encryption algorithm. The underlying SM2 signature algorithm includes:

signing party Alice selects one elliptic curve E _q (a, b) and a base point g, and sharing this information to a verifier Bob, where q is a modulus;

alice is in finite fieldTop select a private key +.>And generates a public key x=g from the private key ^x ；

Alice is in finite fieldUp-select a random number +.>And calculate k=g ^k ＝(x ₁ ,y ₁ )，x ₁ 、y ₁ Respectively the abscissa and the ordinate of the K point on the elliptic curve;

alice calculates a message m to be signed through hash to obtain a digest value H (m), and calculates:

r＝H(m)+x ₁ mod q type (a)

And based on this calculation:

s＝(1+x) ^-1 (k-r.x) mod p; (b)

Alice generates signature σ= (r, s), and sends message m, signature σ, public key X to signer Bob.

Bob calculates the coordinates of point K' using base point g, signature σ, public key X:

K′＝g ^s ·X ^r+s ＝(x′ ₁ ,y′ ₁ ) (c)

Bob uses the abscissa x ' of the r, message m, and K ' points in signature σ ' ₁ The following equation is verified:

r＝H(m)+x′ ₁ mod q type (d)

If the above equation holds, the signature is valid; otherwise, the signature is invalid.

This is because, equivalently, verifying the coordinates of the K 'point (x' ₁ ,y′ ₁ ) Coordinates (x) of the K point employed in the signature ₁ ,y ₁ ) Equal:

(x′ ₁ ,y′ ₁ )＝s·G+(r+s)·x·G＝(1+x)·s·G+r·x·G＝(k-r·x)·G+r·x·G＝k·G

＝(x ₁ ,y ₁ )

or expressed in an exponential form as follows:

(x′ ₁ ,y′ ₁ )＝g ^s ·X ^r+s ＝g ^s ·g ^X(r+s) ＝g ^s ·g ^X(r+s) ＝g ^(1+X)s+Xr ＝g ^(k-r·X)+Xr ＝g ^k ＝(x ₁ ,y ₁ )

the basic SM2 signature algorithm described above can be extended to a threshold signature algorithm. For example, through the DKG procedure described above, n signers P ₁ ,P ₂ ,…,P _n Each having its own secret share and having a total public key, wherein the threshold value is t, and t<n. At least t+1 signature parties in the n parties respectively adopt secret shares of themselves as private key shares respectively, after signing and broadcasting the same information to be signed, any verification party collecting at least t+1 signature shares can recover the total signature, and the total signature can be verified by adopting the total public key, so that the threshold signature is realized. Shang Ming et al in 2014 published in the article "SM 2 elliptic curve threshold cryptographic algorithm" of "cryptographic report," constructed a distributed signature algorithm based on SM2 that satisfies the t-n threshold, i.e., n parties respectively generate a private key fragment and a corresponding public key through a protocol, and at least t+1 of the n parties need to participate in the SM2 distributed signature protocol to generate a corresponding SM2 signature and verify. The disadvantage of this algorithm is that the above (t, n) must be satisfied with n.gtoreq.2t+1, which makes the application very inflexible. For example, the algorithm cannot meet the (2, 4) threshold or the (2, 3) threshold, which is most often used in real world use.

The above relationship may be represented by the distributed threshold key generation of fig. 1 and the distributed threshold signature of fig. 2.

The embodiment of the application provides a distributed threshold signature method based on SM 2.

The embodiment of the application can comprise two parts, namely a distributed threshold key generation part and a distributed threshold signature part, wherein the two parts are processes of how to mutually transmit data and how to process the data through a protocol form between the parties, so that the specific purpose is realized by cooperation.

The procedure of the distributed threshold key generation protocol is first described below. In this process, it is assumed that there are n participants, P ₁ ，P ₂ ，…，P _n . Each party P via a distributed threshold key generation protocol _i (i= {1,2, …, n }) a respective private key share x 'may be generated' _i 。

Each participant P _i An own public-private key pair for homomorphic encryption, such as the Paillier public-private key pair (E _i ,e _i ) Wherein e is _i Is a private key, E _i Is the corresponding public key. Homomorphic encryption techniques can "homomorphic" the plaintext data, i.e., map the plaintext data to a new, secure state, such that only recipients with a secret key can obtain the plaintext data. Paillier homomorphic addition is a public key encryption system widely used in cryptography, proposed by Pascal Paillier (1999). Its main feature is that it has additive homomorphic property, which means that given two ciphertexts, the ciphertexts of their corresponding plain text sum can be calculated without decryption. Specifically, assume that there are two plaintext m1 and m2, whose Paillier encrypted ciphertext is c1 and c2, respectively. The additive homomorphism of Paillier can be implemented as a new ciphertext c, which is exactly the ciphertext of the sum of m1 and m2, obtained by computing the product of c1 and c2. The additive homomorphism is an important feature of the Paillier encryption algorithm, and is expressed simply as: e (m) ₁ )·E(m ₂ )＝E(m ₁ +m ₂ ) Dot product here, i.e. subsequent homomorphism additionThis homomorphism property allows some form of computation of the encrypted data to be accomplished without revealing the original data. />

Each participant P _i After the generated homomorphic encryption public and private key pair, the public key can be sent to other participants.

For example, party P ₁ Generating a Paillier encrypted public-private key (E ₁ ,e ₁ ) Then, homomorphic encryption public key E ₁ Broadcasting to other participants; participant P ₂ Generating a Paillier encrypted public-private key (E ₂ ,e ₂ ) Then, homomorphic encryption public key E ₂ Broadcasting to other participants; participant P ₃ Generating a Paillier encrypted public-private key (E ₃ ,e ₃ ) Then, homomorphic encryption public key E ₃ Broadcasting to other participants; participant P ₄ Generating a Paillier encrypted public-private key (E ₄ ,e ₄ ) Then, homomorphic encryption public key E ₄ Broadcasting to other participants; participant P ₅ Generating a Paillier encrypted public-private key (E ₅ ,e ₅ ) Then, homomorphic encryption public key E ₅ Broadcast to other participants.

Each participant P _i A second random value gamma may be generated _i Then there are 5 participants P ₁ ，P ₂ ，P ₃ ，P ₄ ，P ₅ Respectively generating second random values gamma ₁ 、γ ₂ 、γ ₃ 、γ ₄ 、γ ₅ . Each participant P _i The secret value gamma generated respectively _i The sum is gamma, i.e

Also, each participant P _i A t degree polynomial f may be generated _i (z)＝a _i0 +a _i1 z+a _i2 z ² +…+a _it z ^t Wherein a is _i0 Is P _i The secret set is here referred to as gamma _i . The threshold here is t, so that the degree of the polynomial is also t.

Let the threshold be 2 and let the total number of participants be 5, i.e. t=2, n=5, there are a total of 5 participants P ₁ ，P ₂ ，P ₃ ，P ₄ ，P ₅ Respectively using the secret values gamma generated by each ₁ 、γ ₂ 、γ ₃ 、γ ₄ 、γ ₅ Constructing a polynomial, wherein:

P ₁ generating a 2 degree (t=2) polynomial: f (f) ₁ (z)＝a ₁₀ +a ₁₁ z+a ₁₂ z ² Wherein a is ₁₀ Is P ₁ Set secret gamma ₁ ；

P ₂ Generating a 2 degree (t=2) polynomial: f (f) ₂ (z)＝a ₂₀ +a ₂₁ z+a ₂₂ z ² Wherein a is ₂₀ Is P ₂ Set secret gamma ₂ ；

P ₃ Generating a 2 degree (t=2) polynomial: f (f) ₃ (z)＝a ₃₀ +a ₃₁ z+a ₃₂ z ² Wherein a is ₃₀ Is P ₃ Set secret gamma ₃ ；

P ₄ Generating a 2 degree (t=2) polynomial: f (f) ₄ (z)＝a ₄₀ +a ₄₁ z+a ₄₂ z ² Wherein a is ₄₀ Is P ₄ Set secret gamma ₄ ；

P ₅ Generating a 2 degree (t=2) polynomial: f (f) ₅ (z)＝a ₅₀ +a ₅₁ z+a ₅₂ z ² Wherein a is ₅₀ Is P ₅ Set secret gamma ₅ ；

Further, each party P _i N secret shares may be generated, one of which is reserved by itself, and the remaining secret shares sent to the other participants are encrypted. For example, party P _i Generating coordinates of n points on a polynomial corresponding curve of the self as n secret shares, reserving the coordinates of one point of the self, and encrypting and transmitting the coordinates of the other points to other participants.

Specifically, for example:

P ₁ generating s ₁₁ ＝f ₁ (1)、s ₁₂ ＝f ₁ (2)、s ₁₃ ＝f ₁ (3)、s ₁₄ ＝f ₁ (4)、s ₁₅ ＝f ₁ (5) Self-reserve s ₁₁ And respectively encrypt and send s ₁₂ To P ₂ Encrypted transmission s ₁₃ To P ₃ Encrypted transmission s ₁₄ To P ₄ Encrypted transmission s ₁₅ To P ₅ ；

P ₂ Generating s ₂₁ ＝f ₂ (1)、s ₂₂ ＝f ₂ (2)、s ₂₃ ＝f ₂ (3)、s ₂₄ ＝f ₂ (4)、s ₂₅ ＝f ₂ (5) Self-reserve s ₂₂ And respectively encrypt and send s ₂₁ To P ₁ Encrypted transmission s ₂₃ To P ₃ Encrypted transmission s ₂₄ To P ₄ Encrypted transmission s ₂₅ To P ₅ ；

P ₃ Generating s ₃₁ ＝f ₃ (1)、s ₃₂ ＝f ₃ (2)、s ₃₃ ＝f ₃ (3)、s ₃₄ ＝f ₃ (4)、s ₃₅ ＝f ₃ (5) Self-reserve s ₃₃ And respectively encrypt and send s ₃₁ To P ₁ Encrypted transmission s ₃₂ To P ₂ Encrypted transmission s ₃₄ To P ₄ Encrypted transmission s ₃₅ To P ₅ ；

P ₄ Generating s ₄₁ ＝f ₄ (1)、s ₄₂ ＝f ₄ (2)、s ₄₃ ＝f ₄ (3)、s ₄₄ ＝f ₄ (4)、s ₄₅ ＝f ₄ (5) Self-reserve s ₄₄ And respectively encrypt and send s ₄₁ To P ₁ Encrypted transmission s ₄₂ To P ₂ Encrypted transmission s ₄₃ To P ₃ Encrypted transmission s ₄₅ To P ₅ ；

P ₅ Generating s ₅₁ ＝f ₅ (1)、s ₅₂ ＝f ₅ (2)、s ₅₃ ＝f ₅ (3)、s ₅₄ ＝f ₅ (4)、s ₅₅ ＝f ₅ (5) Self-reserve s ₅₅ And respectively encrypt and send s ₅₁ To P ₁ Encrypted transmission s ₅₂ To P ₂ Encrypted transmission s ₅₃ To P ₃ Encrypted transmission s ₅₄ To P ₄ ；

This is the case:

P ₁ locally generated secret shares s with different parties ₁₁ 、s ₂₁ 、s ₃₁ 、s ₄₁ 、s ₅₁ ；

P ₂ Locally generated secret shares s with different parties ₁₂ 、s ₂₂ 、s ₃₂ 、s ₄₂ 、s ₅₂ ；

P ₃ Locally generated secret shares s with different parties ₁₃ 、s ₂₃ 、s ₃₃ 、s ₄₃ 、s ₅₃ ；

P ₄ Locally generated secret shares s with different parties ₁₄ 、s ₂₄ 、s ₃₄ 、s ₄₄ 、s ₅₄ ；

P ₅ Locally generated secret shares s with different parties ₁₅ 、s ₂₅ 、s ₃₅ 、s ₄₅ 、s ₅₅ 。

In addition, each party P _i Can calculate the secret value generated by itself as gamma _i Corresponding homomorphic encryption value R _i ＝E _i (γ _i ) And broadcast to other participants.

Then, each party P _i One secret share s that can be reserved by itself _ii And from other participants P _j The resulting secret share s _ji The sum of the secret shares being obtained after the sum, e.g. by summing, e.g. by party P _i Is the sum of the secret shares of (a)Specific examples are:

participant P ₁ The sum omega of secret shares can be calculated ₁ The method comprises the following steps: omega ₁ ＝s ₁₁ +s ₂₁ +s ₃₁ +s ₄₁ +s ₅₁ ；

Participant P ₂ The sum omega of secret shares can be calculated ₂ The method comprises the following steps: omega ₂ ＝s ₁₂ +s ₂₂ +s ₃₂ +s ₄₂ +s ₅₂ ；

Participant P ₃ The sum omega of secret shares can be calculated ₃ The method comprises the following steps: omega ₃ ＝s ₁₃ +s ₂₃ +s ₃₃ +s ₄₃ +s ₅₃ ；

Participant P ₄ The sum omega of secret shares can be calculated ₄ The method comprises the following steps: omega ₄ ＝s ₁₄ +s ₂₄ +s ₃₄ +s ₄₄ +s ₅₄ ；

Participant P ₅ The sum omega of secret shares can be calculated ₅ The method comprises the following steps: omega ₅ ＝s ₁₅ +s ₂₅ +s ₃₅ +s ₄₅ +s ₅₅ 。

Also, each participant P _i Can also generate a public verification parameter A corresponding to the self t degree polynomial _ik ＝a _ik G, where k=0, 1, …, t, and published to each party, specifically:

participant P ₁ Generation A _1k ＝a _1k G, k=0, 1, …, t=2, including a ₁₀ ＝a ₁₀ G＝s ₁₀ G，A ₁₁ ＝a ₁₁ G，A ₁₂ ＝a ₁₂ G, broadcast { A ₁₀ ,A ₁₁ ,A ₁₂ Go to P ₂ 、P ₃ 、P ₄ And P ₅ ；

Participant P ₂ Generation A _2k ＝a _2k G, k=0, 1, …, t=2, including a ₂₀ ＝a ₂₀ G＝s ₂₀ G，A ₂₁ ＝a ₂₁ G，A ₂₂ ＝a ₂₂ G, broadcast { A ₂₀ ,A ₂₁ ,A ₂₂ Go to P ₁ 、P ₃ 、P ₄ And P ₅ ；

Participant P ₃ Generation A _3k ＝a _3k G, k=0, 1, …, t=2, including a ₃₀ ＝a ₃₀ G＝s ₃₀ G，A ₃₁ ＝a ₃₁ G，A ₃₂ ＝a ₃₂ G, broadcast { A ₃₀ ,A ₃₁ ,A ₃₂ Go to P ₁ 、P ₂ 、P ₄ And P ₅ ；

Participant P ₄ Generation A _4k ＝a _4k G, k=0, 1, …, t=2, including a ₄₀ ＝a ₄₀ G＝s ₄₀ G，A ₄₁ ＝a ₄₁ G，A ₄₂ ＝a ₄₂ G, broadcast { A ₄₀ ,A ₄₁ ,A ₄₂ Go to P ₁ 、P ₂ 、P ₃ And P ₅ ；

Participant P ₅ Generation A _5k ＝a _5k G，k＝0,1,…,t＝2, include A ₅₀ ＝a ₅₀ G＝s ₅₀ G，A ₅₁ ＝a ₅₁ G，A ₅₂ ＝a ₅₂ G, broadcast { A ₅₀ ,A ₅₁ ,A ₅₂ Go to P ₁ 、P ₂ 、P ₃ And P ₄ 。

Each participant P _i Can also be according to P _j Public authentication parameter { A } _j0 ,A _j1 ,…，A _jt Verification P _j The transmitted secret share s _ji For example, by the following formula:

s _ji G＝A _j0 +iA _j1 +…+i ^t A _jt

specific:

participant P ₁ Through s ₂₁ G＝A ₂₀ +A ₂₁ +A ₂₂ Verification s ₂₁ Through s ₃₁ G＝A ₃₀ +A ₃₁ +A ₃₂ Verification s ₃₁ Through s ₄₁ G＝A ₄₀ +A ₂₁ +A ₄₂ Verification s ₄₁ Through s ₅₁ G＝A ₅₀ +A ₅₁ +A ₅₂ Verification s ₅₁ ；

Participant P ₂ Through s ₁₂ G＝A ₁₀ +2A ₁₁ +2 ² A ₁₂ Verification s ₁₂ Through s ₃₂ G＝A ₃₀ +2A ₃₁ +2 ² A ₃₂ Verification s ₃₂ Through s ₄₂ G＝A ₄₀ +2A ₂₁ +2 ² A ₄₂ Verification s ₄₂ Through s ₅₂ G＝A ₅₀ +2A ₅₁ +2 ² A ₅₂ Verification s ₅₂ ；

Participant P ₃ Through s ₁₃ G＝A ₁₀ +3A ₁₁ +3 ² A ₁₂ Verification s ₁₃ Through s ₂₃ G＝A ₃₀ +3A ₃₁ +3 ² A ₃₂ Verification s ₂₃ Through s ₄₃ G＝A ₄₀ +3A ₂₁ +3 ² A ₄₂ Verification s ₄₃ Through s ₅₃ G＝A ₅₀ +3A ₅₁ +3 ² A ₅₂ Verification s ₅₃ ；

Participant P ₄ Through s ₁₄ G＝A ₁₀ +4A ₁₁ +4 ² A ₁₂ Verification s ₁₄ Through s ₂₄ G＝A ₂₀ +4A ₂₁ +4 ² A ₂₂ Verification s ₂₄ Through s ₃₄ G＝A ₄₀ +4A ₂₁ +4 ² A ₄₂ Verification s ₄₂ Through s ₅₄ G＝A ₅₀ +4A ₅₁ +4 ² A ₅₂ Verification s ₅₂ ；

Participant P ₅ Through s ₁₅ G＝A ₁₀ +5A ₁₁ +5 ² A ₁₂ Verification s ₁₅ Through s ₂₅ G＝A ₂₀ +5A ₂₁ +5 ² A ₂₂ Verification s ₂₅ Through s ₃₅ G＝A ₃₀ +5A ₃₁ +5 ² A ₃₂ Verification s ₃₅ Through s ₄₅ G＝A ₄₀ +5A ₄₁ +5 ² A ₄₂ Verification s ₄₅ ；

Either party may terminate the protocol if the authentication is not passed.

On the other hand, each party P _i The first random value can be randomly selectedThen 5 participants P ₁ ，P ₂ ，P ₃ ，P ₄ ，P ₅ Respectively generating first random values as x ₁ 、x ₂ 、x ₃ 、x ₄ 、x ₅ . The corresponding public keys are respectively Each participant P _i The first random value corresponding public key generated by the self can be broadcasted to other participants P _i,j≠i . Then P _i The local area is provided with: { X ₁ ,X ₂ ,X ₃ ,...,X _n }. Specifically, for 5 participants P ₁ ，P ₂ ，P ₃ ，P ₄ ，P ₅ Each local has { X } ₁ ,X ₂ ,X ₃ ,X ₄ ,X ₅ }。

To this end, each party P _i Can collect the first random value corresponding public key set { X } _j } _j∈[1,n] And a second random value homomorphic ciphertext set { R _j } _j∈[1,n] 。

Each participant P _i May correspond to the public key set { X } based on the first random value _j } _j∈[1,n] The total public key X is calculated in a similar manner to that described above, for example by the following formula:

as previously described, this total public key may be used to verify the total signature after subsequent aggregation. Wherein x=x ₁ +x ₂ +…+x _n 。

In addition, each party P _i For P _j The first mask number between one party can be randomly selectedAnd can calculate the first intermediate ciphertext D through homomorphic algorithm _i,j And send to P _j For example using Paillier encryption and computation

Thus, for party P _i Can receiveThen decryption can be performed using its own homomorphic encryption private key, such as public key E encrypted using Paillier _i Corresponding private key e ₁ Decryption to obtain x _j ·γ _i -β _j,i ＝α _i,j . Further, P _i A first intermediate value can be calculated +.> And broadcast a first intermediate value delta _i To other parties.

In the next step, party P _i Collecting the first intermediate value delta _j,j∈[1,n] After that, can calculateThen +.>As a private key shard of its own.

For example, for 5 participants P ₁ ，P ₂ ，P ₃ ，P ₄ ，P ₅ ：

P ₁ For P ₂ Randomly selecting a first mask number beta between one of the participants _1,2 Encryption and computation of a first intermediate ciphertext using a PaillierAnd send D _1,2 To P ₂ The method comprises the steps of carrying out a first treatment on the surface of the Similarly, P ₁ For P ₃ Randomly selecting a first mask number beta between one of the participants _1,3 Calculate a first intermediate ciphertextAnd send D _1,3 To P ₃ The method comprises the steps of carrying out a first treatment on the surface of the Similarly, P ₁ For P ₄ Randomly selecting a first mask number beta between one of the participants _1,4 Calculate the first intermediate ciphertext ++> And send D _1,4 To P ₄ The method comprises the steps of carrying out a first treatment on the surface of the Similarly, P ₁ For P ₅ Randomly selecting a first mask number beta between one of the participants _1,5 Calculate the first intermediate ciphertext ++>And send D _1,5 To P ₅ 。

P ₂ For P ₁ Randomly selecting a first mask number beta between one of the participants _2,1 Encryption and computation of a first intermediate ciphertext using a PaillierAnd send D _2,1 To P ₁ The method comprises the steps of carrying out a first treatment on the surface of the Similarly, P ₂ For P ₃ Randomly selecting a first mask number beta between one of the participants _2,3 Calculate a first intermediate ciphertextAnd send D _2,3 To P ₃ The method comprises the steps of carrying out a first treatment on the surface of the Similarly, P ₂ For P ₄ Randomly selecting a first mask number beta between one of the participants _2,4 Calculate the first intermediate ciphertext ++> And send D _2,4 To P ₄ The method comprises the steps of carrying out a first treatment on the surface of the Similarly, P ₂ For P ₅ Randomly selecting a first mask number beta between one of the participants _2,5 Calculate the first intermediate ciphertext ++>And send D _2,5 To P ₅ 。

P ₃ For P ₁ Randomly selecting a first mask number beta between one of the participants _3,1 Encryption and computation of a first intermediate ciphertext using a PaillierAnd send D _3,1 To P ₁ The method comprises the steps of carrying out a first treatment on the surface of the Similarly, P ₃ For P ₂ Randomly selecting a first mask number beta between one of the participants _3,2 Calculate a first intermediate ciphertextAnd send D _3,2 To P ₂ The method comprises the steps of carrying out a first treatment on the surface of the Similarly, P ₃ For P ₄ Randomly selecting a first mask number beta between one of the participants _3,4 Calculate the first intermediate ciphertext ++> And send D _3,4 To P ₄ The method comprises the steps of carrying out a first treatment on the surface of the Similarly, P ₃ For P ₅ Randomly selecting a first mask number beta between one of the participants _3,5 Calculate the first intermediate ciphertext ++>And send D _3,5 To P ₅ 。

P ₄ For P ₁ Randomly selecting a first mask number beta between one of the participants _4,1 Encryption and computation of a first intermediate ciphertext using a PaillierAnd send D _4,1 To P ₁ The method comprises the steps of carrying out a first treatment on the surface of the Similarly, P ₄ For P ₂ Randomly selecting a first mask number beta between one of the participants _4,2 Calculate a first intermediate ciphertext And send D _4,2 To P ₂ The method comprises the steps of carrying out a first treatment on the surface of the Similar toOf P of ₄ For P ₃ Randomly selecting a first mask number beta between one of the participants _4,3 Calculate the first intermediate ciphertext ++>And send D _4,3 To P ₃ The method comprises the steps of carrying out a first treatment on the surface of the Similarly, P ₄ For P ₅ Randomly selecting a first mask number beta between one of the participants _4,5 Calculate the first intermediate ciphertext ++>And send D _4,5 To P ₅ 。

P ₅ For P ₁ Randomly selecting a first mask number beta between one of the participants _5,1 Encryption and computation of a first intermediate ciphertext using a PaillierAnd send D _5,1 To P ₁ The method comprises the steps of carrying out a first treatment on the surface of the Similarly, P ₅ For P ₂ Randomly selecting a first mask number beta between one of the participants _5,2 Calculate a first intermediate ciphertextAnd send D _5,2 To P ₂ The method comprises the steps of carrying out a first treatment on the surface of the Similarly, P ₅ For P ₃ Randomly selecting a first mask number beta between one of the participants _5,3 Calculate the first intermediate ciphertext ++> And send D _5,3 To P ₃ The method comprises the steps of carrying out a first treatment on the surface of the Similarly, P ₅ For P ₄ Randomly selecting a first mask number beta between one of the participants _5,4 Calculate the first intermediate ciphertext ++>And send D _5,4 To P ₄ 。

Thus P ₁ Can receive D _2,1 、D _3,1 、D _4,1 、D _5,1 Thus, P ₁ Can decrypt to obtain x ₂ ·γ ₁ -β _2,1 ＝α _1,2 ，x ₃ ·γ ₁ -β _3,1 ＝α _1,3 ，x ₄ ·γ ₁ -β _4,1 ＝α _1,4 ，x ₅ ·γ ₁ -β _5,1 ＝α _1,5 . And then P ₁ Intermediate values can be calculated And broadcast delta ₁ 。

Similarly, P ₂ Can receive D _1,2 、D _3,2 、D _4,2 、D _5,2 Thus, P ₂ Can decrypt to obtain x ₁ ·γ ₂ -β _1,2 ＝α _2,1 ，x ₃ ·γ ₂ -β _3,2 ＝α _2,3 ，x ₄ ·γ ₂ -β _4,2 ＝α _2,4 ，x ₅ ·γ ₂ -β _5,2 ＝α _2,5 . And then P ₂ Intermediate values can be calculated And broadcast delta ₂ 。/>

Similarly, P ₃ Can receive D _1,3 、D _2,3 、D _4,3 、D _5,3 Thus, P ₃ Can decrypt to obtain x ₁ ·γ ₃ -β _1,3 ＝α _3,1 ，x ₂ ·γ ₃ -β _2,3 ＝α _3,2 ，x ₄ ·γ ₃ -β _4,3 ＝α _3,4 ，x ₅ ·γ ₃ -β _5,3 ＝α _3,5 . Feeding inAnd P is ₃ Intermediate values can be calculated And broadcast delta ₃ 。

Similarly, P ₄ Can receive D _1,4 、D _2,4 、D _3,4 、D _5,4 Thus, P ₄ Can decrypt to obtain x ₁ ·γ ₄ -β _1,4 ＝α _4,1 ，x ₂ ·γ ₄ -β _2,4 ＝α _4,2 ，x ₃ ·γ ₄ -β _3,4 ＝α _4,3 ，x ₅ ·γ ₄ -β _5,4 ＝α _4,5 . And then P ₄ Intermediate values can be calculated And broadcast delta ₄ 。

Similarly, P ₅ Can receive D _1,5 、D _2,5 、D _3,5 、D _4,5 Thus, P ₅ Can decrypt to obtain x ₁ ·γ ₅ -β _1,5 ＝α _5,1 ，x ₂ ·γ ₅ -β _2,5 ＝α _5,2 ，x ₃ ·γ ₅ -β _3,5 ＝α _5,3 ，x ₄ ·γ ₅ -β _4,5 ＝α _5,4 . And then P ₅ Intermediate values can be calculated And broadcast delta ₅ 。

In the next step, party P ₁ Collect Ji _j,j∈[1,5] After that, can calculate

Similarly, P ₂ Collect Ji _j,j∈[1,5] Then, can also be calculated to obtain

Similarly, P ₃ Collect Ji _j,j∈[1,5] Then, can also be calculated to obtain

Similarly, P ₄ Collect Ji _j,j∈[1,5] Then, can also be calculated to obtain

Similarly, P ₅ Collect Ji _j,j∈[1,5] Then, can also be calculated to obtain

Further, party P ₁ Can be used forAs its own share of the private key (i.e., private key shard);

likewise, party P ₂ Can be used forAs its own private key share;

Likewise, party P ₃ Can be used forAs its own private key share;

likewise, the participantsP ₄ Can be used forAs its own private key share; />

Likewise, party P ₅ Can be used forAs its own private key share;

thus, each participant P _i Finally, the first random value x generated by each participant is obtained _i Sum and second random value gamma _i The sum, but because the process of exchanging information between the participants combines homomorphic encryption and the design of intermediate ciphertext and intermediate value, any participant P is not exposed _i Respective first random values x _i And a second random value gamma _i . And in turn, each party P in combination with the sum of the secret shares obtained by the distributed key generation protocol _i The private key share x 'of the self can be obtained' _i 。

The distributed signing process is described below and may include both an offline phase and an online phase. The distributed key generation process described above requires n participants to participate in the protocol process together. The distributed threshold signature process described below requires only at least t+1 participants to participate in the protocol process together. In particular, the threshold t=2 is still taken as an example here.

Offline stage: updating self private key share x' _i Generates a third random value k of the self _i Corresponding third random value homomorphic ciphertext K _i And a third random value public key G _i Broadcast K _i And G _i The method comprises the steps of carrying out a first treatment on the surface of the A second mask number is generated and a second intermediate plaintext is exchanged by homomorphic encryption.

Specifically, the method comprises the following steps:

S21：

first, t+1 participants, each participant P _i Calculation of Lagrange coefficientsAnd adopts the Lagrange coefficient updates its own private key share: x is x _i ″←l _i (0)·x′ _i . Here, for example, i is 1, 2, 3, then:

participant P ₁ Calculation of Lagrange coefficientsAnd updates its own private key share x ₁ ←l ₁ (0)·x′ ₁ ；

Participant P ₂ Calculation of Lagrange coefficients And updates its own private key share x ₂ ←l ₂ (0)·x′ ₂ ；

Participant P ₃ Calculation of Lagrange coefficientsAnd updates its own private key share x ₃ ←l ₃ (0)·x′ ₃ 。

Second, each of the t+1 participants generates a third random value k _i Corresponding third random value homomorphic ciphertext K _i And a third random value public key G _i And broadcast the third random value homomorphic ciphertext K _i And a third random value public key G _i . In particular, for example, party P _i ,i∈[1,t+1]Generating a third random value k _i And (2) andparticipant P _i A third random value homomorphic ciphertext, e.g., paillier ciphertext K, may be calculated _i ＝E _i (k _i ) And calculating a third random value public key G _i For example->Specifically, t+1 is 3, and the participation party is P ₁ 、P ₂ 、P ₃ When (1):

P ₁ generating a third random value k ₁ And calculates the Paillier ciphertext K of the third random value ₁ ＝E ₁ (k ₁ ) And calculating a third random value public keyBroadcast K ₁ And G ₁ ；

P ₂ Generating a third random value k ₂ And calculates the Paillier ciphertext K of the third random value ₂ ＝E ₂ (k ₂ ) And calculating a third second random value public keyBroadcast K ₂ And G ₂ ；

P ₃ Generating a third random value k ₃ And calculates the Paillier ciphertext K of the third random value ₃ ＝E ₃ (k ₃ ) And calculating a third second random value public keyBroadcast K ₃ And G ₃ 。

In addition, each party P _i A second mask number is also generated and a second intermediate plaintext is exchanged by homomorphic encryption. Specifically, the method comprises the following steps: p (P) _i For party P _j Generating a second mask numberAnd based on the updated private key share x _i "received third random value homomorphic ciphertext K _j And the second mask number->Calculates a second intermediate ciphertext ++>With other participants P _j Exchange second intermediate ciphertext->Decrypting the second intermediate ciphertext->Obtaining a second intermediate plaintext->Specifically, S22 and S23 below may be mentioned.

S22：

Participant P receiving broadcast _i For P _j K sent out _j Selecting a second mask number Here, the value range of the finite field subscript is represented as the 5 th power of q, which is a proven value range with cryptographic security. Second mask count->Can be generally +.>Larger values are selected within the range. Further, P _i The second intermediate ciphertext may be calculated by homomorphic algorithm>And send to P _j ：

Specific:

P ₁ receiving P ₂ Broadcast K ₂ ＝E ₂ (k ₂ ) Then, selecting a second mask numberFurther, P ₁ The second intermediate ciphertext may be calculated by homomorphic algorithm>And send to P ₂ Wherein:

thus P ₂ Received byAlthough P ₂ With a corresponding Paillier private key e ₂ ，k ₂ Also P ₂ Generated but due to P therein ₁ Second mask number selected->Masking effect of P ₂ Cannot estimate P ₁ Private key share x' ₁ Thereby completing the information transfer on the basis. Similar to the above, the description is omitted.

Similarly, P ₁ Receiving P ₃ Broadcast K ₃ ＝E ₃ (k ₃ ) Then, selecting a second mask numberFurther, P ₁ The second intermediate ciphertext may be calculated by homomorphic algorithm>And send to P ₃ Wherein:

similarly, P ₂ Receiving P ₁ Broadcast K ₁ ＝E ₁ (k ₁ ) Then, selectTaking a second mask numberFurther, P ₂ The second intermediate ciphertext may be calculated by homomorphic algorithm>And send to P ₁ Wherein:

similarly, P ₂ Receiving P ₃ Broadcast K ₃ ＝E ₃ (k ₃ ) Then, selecting a second mask numberFurther, P ₂ The second intermediate ciphertext may be calculated by homomorphic algorithm>And send to P ₃ Wherein:

similarly, P ₃ Receiving P ₁ Broadcast K ₁ ＝E ₁ (k ₁ ) Then, selecting a second mask numberFurther, P ₃ The second intermediate ciphertext may be calculated by a homomorphic encryption algorithm>And send to P ₁ Wherein:

similarly, P ₃ Receiving P ₂ Broadcast K ₂ ＝E ₂ (k ₂ ) Then, selecting a second mask numberFurther, P ₃ The second intermediate ciphertext may be calculated by a homomorphic encryption algorithm>And send to P ₂ Wherein: />

S23：

Further, each party P _i Received second intermediate ciphertextDecrypting by adopting a corresponding homomorphic encryption private key to obtain plaintext ++>Referred to herein as a second intermediate plaintext, wherein:

To this end, P _i Having locally k _i Updated self private key share x _i And for P _j A kind of electronic device

On-line stage: each P of the at least t+1 participants _i Using the collected third random value public key G _i Calculating the total coordinate K of the third random value public key, and adoptingCalculating r in the signature share for message m using the total coordinate K, and based on r and its own third random value K _i Updated private key share x _i For party P _j Is the second intermediate plaintext of (2)And a second mask number->Calculating the component s of the signature share for message m _i Thereby obtaining signature share sigma _i (r,s _i )。

S31：

At least t+1 participants each P _i Can collect the third random value public key G _{j,j∈[1,t+1]} So that the total coordinates can be calculated based on at least t+1 third random value public keysWherein x is ₁ 、y ₁ The abscissa and the ordinate of the K point on the elliptic curve, respectively.

On the other hand, P _i The message m to be signed can be calculated by means of a hash to obtain the digest value H (m), and r=h (m) +x in the signature share can be calculated on the basis of the total coordinate K point ₁ mod q. This is similar to the formula (a) described above.

Due to any P _i The messages m for are identical, i.e. H (m) are also identical. Also, t+1 k _j The sum is also the same and the total coordinate K is also the same. Thus, any P _i The r in the calculated signature shares is also the same.

S32：

P _i Can be based on r and a third random value k of itself _i Updated self private key share x _i For party P _j Is the second intermediate plaintext of (2)And a second mask number->Calculating the component s of the signature share for message m _i Thereby obtaining signature share sigma _i (r,s _i )。

Specifically, s is calculated as follows _i ：

Wherein,simplified, the->x″ _i Is the updated private key share, i.e. equal to l _i (0)·x′ _i 。

Thus, after any party obtains at least t+1 signature shares, the at least t+1 signature shares may be aggregated into a total signatureCan prove->Namely (1+x) ^-1 (k-r.x). It can be seen that here s in the total signature σ is in the same form as s in the formula (b) in the basic SM2 signature algorithm described above. Thus, the correctness of the total signature σ can be verified using the aforementioned total public key X.

In addition, the total private key is the sum of the updated private key shares:

Continuing the example above, either party (either one of n=5 parties or one other than n=5 parties) obtains a signature share of t+1=3:

for example, based onP ₁ And (3) calculating:

similarly, based onP ₂ And (3) calculating:

s ₂ ＝k ₂ ·(l ₂ (0)·x′ ₂ +l ₁ (0)·x′ ₁ +l ₃ (0)·x′ ₃ )+l ₂ (0)·rx′ ₂

similarly, based onP ₃ And (3) calculating:

s ₃ ＝k ₃ ·(l ₃ (0)·x′ ₃ +l ₁ (0)·x′ ₁ +l ₂ (0)·x′ ₂ )+l ₃ (0)·rx′ ₃

so that:

in the above example, the case where t+1 is the right number is mainly described. In fact, it may be the case that there are more than t+1 participants, i.e. the number of participants in the distributed signature protocol phase is more than t+1, through the above procedure, the same aggregate signature as that equal to t+1 can still be obtained, and thus still be verified by the total public key.

Similar to the ECC-based cryptography scheme, the same k cannot be encrypted twice, otherwise it would be cracked by others to get k. Therefore, a new k is preferably used during each signature. It may be that at least t+1 participants execute the offline phase again to generate at leastt+1 k _i Thereby obtaining a new k.

The above procedure may be that the distributed key generation phase is performed cooperatively by n participants once, and then the off-line phase + on-line phase is performed by at least t +1 participants each time the signature is made. It is also possible that after n participants cooperatively perform a distributed key generation phase, at least t+1 participants perform multiple offline phases, thereby generating multiple different k values, and thus different R values and corresponding R values, for signature of each subsequent online phase.

The method uses the homomorphic algorithm scheme like Pailier to replace the multiparty MPC multiplication protocol used in SM2 elliptic curve threshold cryptographic algorithm, thereby overcoming the limitation condition that n is more than or equal to 2t+1 and achieving the distributed threshold signature algorithm of any threshold.

Secondly, in the whole distributed threshold key generation process, no participant can know the total private key, and only know the own threshold private key fragment x _i Only t+1 participants in n persons cooperate to sign. In the distributed threshold signature process, the distributed signature can be realized only by at least t+1 of n users without all participation of the n users, thereby greatly improving the fault tolerance of the system.

Furthermore, the embodiment of the application supports an offline-online mode, wherein only one round of interaction is needed between online stage participants, thereby greatly simplifying the complexity of signature.

An embodiment of a computer device of the present application is described below, comprising:

a processor;

The following describes an embodiment of a storage medium of the present application for storing a program, wherein the program when executed performs the following operations:

In the 90 s of the 20 th century, improvements to one technology could clearly be distinguished as improvements in hardware (e.g., improvements to circuit structures such as diodes, transistors, switches, etc.) or software (improvements to the process flow). However, with the development of technology, many improvements of the current method flows can be regarded as direct improvements of hardware circuit structures. Designers almost always obtain corresponding hardware circuit structures by programming improved method flows into hardware circuits. Therefore, an improvement of a method flow cannot be said to be realized by a hardware entity module. For example, a programmable logic device (Programmable Logic Device, PLD) (e.g., field programmable gate array (Field Programmable Gate Array, FPGA)) is an integrated circuit whose logic function is determined by the programming of the device by a user. A designer programs to "integrate" a digital system onto a PLD without requiring the chip manufacturer to design and fabricate application-specific integrated circuit chips. Moreover, nowadays, instead of manually manufacturing integrated circuit chips, such programming is mostly implemented by using "logic compiler" software, which is similar to the software compiler used in program development and writing, and the original code before the compiling is also written in a specific programming language, which is called hardware description language (Hardware Description Language, HDL), but not just one of the hdds, but a plurality of kinds, such as ABEL (Advanced Boolean Expression Language), AHDL (Altera Hardware Description Language), confluence, CUPL (Cornell University Programming Language), HDCal, JHDL (Java Hardware Description Language), lava, lola, myHDL, PALASM, RHDL (Ruby Hardware Description Language), etc., VHDL (Very-High-Speed Integrated Circuit Hardware Description Language) and Verilog are currently most commonly used. It will also be apparent to those skilled in the art that a hardware circuit implementing the logic method flow can be readily obtained by merely slightly programming the method flow into an integrated circuit using several of the hardware description languages described above.

The controller may be implemented in any suitable manner, for example, the controller may take the form of, for example, a microprocessor or processor and a computer readable medium storing computer readable program code (e.g., software or firmware) executable by the (micro) processor, logic gates, switches, application specific integrated circuits (Application Specific Integrated Circuit, ASIC), programmable logic controllers, and embedded microcontrollers, examples of which include, but are not limited to, the following microcontrollers: ARC 625D, atmel AT91SAM, microchip PIC18F26K20, and Silicone Labs C8051F320, the memory controller may also be implemented as part of the control logic of the memory. Those skilled in the art will also appreciate that, in addition to implementing the controller in a pure computer readable program code, it is well possible to implement the same functionality by logically programming the method steps such that the controller is in the form of logic gates, switches, application specific integrated circuits, programmable logic controllers, embedded microcontrollers, etc. Such a controller may thus be regarded as a kind of hardware component, and means for performing various functions included therein may also be regarded as structures within the hardware component. Or even means for achieving the various functions may be regarded as either software modules implementing the methods or structures within hardware components.

The system, apparatus, module or unit set forth in the above embodiments may be implemented in particular by a computer chip or entity, or by a product having a certain function. One typical implementation device is a server system. Of course, the application does not exclude that as future computer technology advances, the computer implementing the functions of the above-described embodiments may be, for example, a personal computer, a laptop computer, a car-mounted human-computer interaction device, a cellular telephone, a camera phone, a smart phone, a personal digital assistant, a media player, a navigation device, an email device, a game console, a tablet computer, a wearable device, or a combination of any of these devices.

Although one or more embodiments of the present description provide method operational steps as described in the embodiments or flowcharts, more or fewer operational steps may be included based on conventional or non-inventive means. The order of steps recited in the embodiments is merely one way of performing the order of steps and does not represent a unique order of execution. When implemented in an actual device or end product, the instructions may be executed sequentially or in parallel (e.g., in a parallel processor or multi-threaded processing environment, or even in a distributed data processing environment) as illustrated by the embodiments or by the figures. The terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, it is not excluded that additional identical or equivalent elements may be present in a process, method, article, or apparatus that comprises a described element. For example, if first, second, etc. words are used to indicate a name, but not any particular order.

For convenience of description, the above devices are described as being functionally divided into various modules, respectively. Of course, when one or more of the present description is implemented, the functions of each module may be implemented in the same piece or pieces of software and/or hardware, or a module that implements the same function may be implemented by a plurality of sub-modules or a combination of sub-units, or the like. The above-described apparatus embodiments are merely illustrative, for example, the division of the units is merely a logical function division, and there may be additional divisions when actually implemented, for example, multiple units or components may be combined or integrated into another system, or some features may be omitted or not performed. Alternatively, the coupling or direct coupling or communication connection shown or discussed with each other may be an indirect coupling or communication connection via some interfaces, devices or units, which may be in electrical, mechanical or other form.

The present invention is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each flow and/or block of the flowchart illustrations and/or block diagrams, and combinations of flows and/or blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.

These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks.

These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.

In one typical configuration, a computing device includes one or more processors (CPUs), input/output interfaces, network interfaces, and memory.

The memory may include volatile memory in a computer-readable medium, random Access Memory (RAM) and/or nonvolatile memory, such as Read Only Memory (ROM) or flash memory (flash RAM). Memory is an example of computer-readable media.

Computer readable media, including both non-transitory and non-transitory, removable and non-removable media, may implement information storage by any method or technology. The information may be computer readable instructions, data structures, modules of a program, or other data. Examples of storage media for a computer include, but are not limited to, phase change memory (PRAM), static Random Access Memory (SRAM), dynamic Random Access Memory (DRAM), other types of Random Access Memory (RAM), read Only Memory (ROM), electrically Erasable Programmable Read Only Memory (EEPROM), flash memory or other memory technology, read only compact disc read only memory (CD-ROM), digital Versatile Discs (DVD) or other optical storage, magnetic cassettes, magnetic tape magnetic disk storage, graphene storage or other magnetic storage devices, or any other non-transmission medium, which can be used to store information that can be accessed by a computing device. Computer-readable media, as defined herein, does not include transitory computer-readable media (transmission media), such as modulated data signals and carrier waves.

One skilled in the relevant art will recognize that one or more embodiments of the present description may be provided as a method, system, or computer program product. Accordingly, one or more embodiments of the present description may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Moreover, one or more embodiments of the present description can take the form of a computer program product on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, etc.) having computer-usable program code embodied therein.

One or more embodiments of the present specification may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. One or more embodiments of the present specification may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices.

In this specification, each embodiment is described in a progressive manner, and identical and similar parts of each embodiment are all referred to each other, and each embodiment mainly describes differences from other embodiments. In particular, for system embodiments, since they are substantially similar to method embodiments, the description is relatively simple, as relevant to see a section of the description of method embodiments. In the description of the present specification, a description referring to terms "one embodiment," "some embodiments," "examples," "specific examples," or "some examples," etc., means that a particular feature, structure, material, or characteristic described in connection with the embodiment or example is included in at least one embodiment or example of the present specification. In this specification, schematic representations of the above terms are not necessarily directed to the same embodiment or example. Furthermore, the particular features, structures, materials, or characteristics described may be combined in any suitable manner in any one or more embodiments or examples. Furthermore, the different embodiments or examples described in this specification and the features of the different embodiments or examples may be combined and combined by those skilled in the art without contradiction.

The foregoing is merely an example of one or more embodiments of the present specification and is not intended to limit the one or more embodiments of the present specification. Various modifications and alterations to one or more embodiments of this description will be apparent to those skilled in the art. Any modification, equivalent replacement, improvement, or the like, which is within the spirit and principles of the present specification, should be included in the scope of the claims.

Claims

1. A method of implementing a distributed threshold signature, comprising:

a distributed key generation stage: each of the n participants generates a first random value and a second random value respectively, and exchanges with other participants after homomorphic encryption; each party generates a private key share based on the collected first and second random values and a sum of the secret shares generated by the distributed key generation protocol;

an offline phase of distributed signing, each of at least t+1 participants performs: updating the share of the private key, generating a third random value of the private key and a public key corresponding to the third random value, and broadcasting;

an online phase of distributed signing, each of the at least t+1 participants performing: after collecting the third random value public key, calculating the total coordinates of the third random value public key, calculating r in the signature share of the message based on the total coordinates, and calculating the component s of the signature share of the message based on r, the third random value of the message, the updated private key share of the message _i Thereby obtaining a signature share.

2. The method of claim 1, wherein after any party obtains at least t+1 signature shares, the at least t+1 signature shares are aggregated into a total signature.

3. The method of claim 2, the n participants further generating a total public key via a distributed key generation protocol; after any party obtains the total signature and the total public key, the correctness of the total signature is verified by adopting the total public key.

4. The method of claim 1, the distributed key generation phase, each of the n participants performing:

s11: generating a first random value and a second random value, calculating a second random value homomorphic ciphertext and broadcasting; and generating a sum of the respective secret shares by a distributed key generation protocol using the second random value as a secret;

s12: receiving a second random value homomorphic ciphertext, generating a first mask number among the participants aiming at other participants, calculating a first intermediate ciphertext based on the first mask number among the participants, the first random value generated by the first intermediate ciphertext and the second random value homomorphic ciphertext obtained by exchange, and transmitting the first intermediate ciphertext to the corresponding received participants;

s13: receiving a first intermediate ciphertext sent by other participants, decrypting to obtain a first intermediate plaintext, calculating an intermediate value based on a first random value and a second random value of the intermediate plaintext and a first mask number between the first intermediate plaintext and the participants, which are obtained by decryption, and broadcasting the intermediate value; the private key shares are calculated based on the sum of the private key shares obtained by itself and the sum of the collected intermediate values.

5. The method of claim 4, the distributed key generation phase further comprising:

generating a public key share of the first random value and broadcasting;

and collecting the public key shares of n participants, and calculating to obtain a total public key.

6. The method according to claim 1, wherein each of at least t+1 participants in the offline phase updates its own private key share, comprising in particular:

the Lagrangian coefficients are used to update the private key shares of themselves.

7. The method of claim 1, wherein each of the at least t+1 participants in the offline phase further generates and broadcasts a third random value homomorphic ciphertext of itself, further generates a second mask number, and exchanges a second intermediate plaintext through homomorphic encryption.

8. The method according to claim 7, wherein each of the at least t+1 participants in the offline phase further generates and broadcasts a third random value homomorphic ciphertext of itself, further generates a second mask number, and exchanges a second intermediate plaintext by homomorphic encryption, specifically comprising:

generating a second mask number for other participants, calculating a second intermediate ciphertext based on the updated private key share, the received third random value homomorphic ciphertext and the homomorphic ciphertext of the second mask number, and exchanging the second intermediate ciphertext with the other participants; and decrypting the second intermediate ciphertext to obtain a second intermediate plaintext.

9. The method of claim 8, wherein the generating a second mask number for the participant and calculating a second intermediate ciphertext based on the updated private key share, the received third random value homomorphic ciphertext, and the homomorphic ciphertext of the second mask number, exchanging the second intermediate ciphertext with the other participant; decrypting the second intermediate ciphertext to obtain a second intermediate plaintext, comprising:

s22: the participants receiving the broadcast generate second mask numbers for other participants, calculate second intermediate ciphertexts based on the updated private key share, the received homomorphic ciphertexts of the third random value and the homomorphic ciphertexts of the second mask numbers, and send the second intermediate ciphertexts to the corresponding participants;

s23: and homomorphic decryption is carried out on the received second intermediate ciphertext to obtain a second intermediate plaintext.

10. The method of claim 8, each of the at least t+1 participants in the online phase performing:

s31: calculating the total coordinate K of the third random value public key by adopting the collected third random value public key, and calculating r in the signature share of the message m by adopting the total coordinate;

s32: based on r and selfThree random values, updated private key share of the self, second intermediate plaintext for other parties and second mask number for other parties, component s of signature share calculated for message m _i Thereby obtaining a signature share.

11. A computer device, comprising:

a processor;

12. A storage medium storing a program, wherein the program when executed performs the operations of:

after collecting the third random value public key, calculating the total coordinates of the third random value public key, calculating r in the signature share of the message based on the total coordinates, and further based on r, the third random value of the self and the updated self private valueComponent s of key share to message computation signature share _i Thereby obtaining a signature share.