Computer-implemented systems and methods for performing computational tasks across a group operating in a trust-less or dealer-free manner

Patent metadata

Field	Value
Publication number	US-11438144-B2
Application number	US-201816772143-A
Country	US
Kind code	B2
Filing date	Dec 4, 2018
Priority date	Dec 13, 2017
Publication date	Sep 6, 2022
Grant date	Sep 6, 2022

Abstract

The invention relates to secure determination of a solution (S) to a computational task by a dealer-free threshold signature group. Access to a resource or reward is offered in exchange for the solution. The method enables individuals in said group to work together in a trust-less, or dealer-free manner. To achieve this, individuals generate their own key pair and use their public key to establish with the group an initial shared public key that they can all use, in parallel, to find a solution to the task. Their own private keys remain secret and, therefore, the collaboration is trust¬less, and operates efficiently, because a verified shared public key is created using the initial shared public key that was used when a solution is found and verified. The resource or reward can be secured by the verified shared public key. Because the private keys of each participant were used in the determination of the initial shared public key that lead to the solution then participants must then collaborate to unlock the resource or reward because the corresponding shared private key can only be generated by all participants or a pre-agreed threshold of participants. Efficiency is achievable by using an initial shared public key and calculating with the group a verified shared public key after the solution has been found. The invention enables the task to be trust-less by using the homomorphic properties of elliptic curve cryptography when applying Shamir's secret sharing scheme. The inventive concept resides in the secure, trust-less and efficient way in which a group can collaborate. The invention can be agnostic to the task.

First claim

The invention claimed is:

1. A computer-implemented method for secure determination of a solution (S) to a computational task by a pooled resource or group having a plurality of participants (P), said group operating in a trust-less, or dealer-free, system or manner, the method comprising:
establishing or joining a group (P) with n participants (P l . . . n ), wherein n≥2;
generating an initial private key share(s n 0 ) and initial public key share (pk 1 ) and establishing an initial shared public key (pko) with the group;
performing the task and searching for the solution (S) that determines an answer (A c ) to the task using an intermediate private key (r n 0 ) and the shared public key (pko) of the group;
finding and sharing the solution (S) with the group, or receiving the solution (S) from another participant, thus enabling the group to verify the solution to the task;
calculating with the group a verified shared public key (pk v ) using the initial shared public key (pk o ) and the intermediate private key (r n 0 ) that provided the solution (S);
constructing a verified secret key share (s v 0 ) by summing the initial private key (s o n ) and the intermediate private key (r n 0 ) that provided the solution (S);
collaborating with all of the other participants, or a threshold number of participants, to construct a verified shared secret key (sk v ) for the verified shared public key (pk v ), using verified secret key shares (sk v ), wherein the verified shared secret key (sk v ) is used as a code to enable the group to operate collectively to unlock or access a resource or stage of a process.

2. A computer-implemented method according to claim 1 , further comprising:
receiving from a client (C) or participant (P) the task and a client public key (pk c ) derived from a client's secret key (sk c ), wherein the client's public key is used in the determination of the solution to the task.

3. A computer-implemented method according to claim 1 , wherein performing the task and searching for the solution (S) includes:
using the intermediate private key (r n 0 ) to create an intermediate public key (R n 0 ) that is added to the initial shared public key (pko) to create a temporary public key (pk n R ) that is processed to determine whether the intermediate private key (r n 0 ) was a solution that determined the answer (A c ) sought; and
if the answer (A c ) is not determined, incrementing the value of the intermediate private key (r n 0 ) and repeating the process until the solution (S) is determined, and the answer (A c ) is proven.

4. A computer-implemented method according to claim 1 , wherein the initial shared public key (pk o ) and the verified shared public key (pk v ) are generated once.

5. A method according to claim 1 , wherein the task requires at least one group member to find a solution that, when processed, produces a Cryptocurrency address having a specified pattern.

6. A method according to claim 1 , wherein the task requires the determination of a set pattern (A), and said set pattern originates from a third-party or another participant, and wherein the third-party generated a third-party secret key (sk c ) and provides to the group a corresponding third party public key (pk c ), wherein pk c =sk c ×G, and G is an elliptic curve generator, and receiving the third party public key (pk c ), and determining the set pattern using the third party public key (pk c ) with an incremental variable (i), such that pk=pk c +i×G when the set pattern is determined, sending to the third-party the incremental variable (i) that enabled determination of the solution, such that the third party can verify the solution using their random secret key (sk c )
sk=sk c +i,
where pk=sk×G due to the homomorphic properties of elliptic curve point multiplication.

7. A method according to claim 1 , wherein the group (P) of n participants generate through a secure multiparty computation (MPC).

8. A method to claim 1 , wherein the initial shared public key (pko) is established amongst the group using Shamir's secret sharing scheme.

9. A method according to claim 1 , wherein the shared secret key (sk v , sk o ) is established amongst the group using Shamir's secret sharing scheme, and wherein a trust-less relationship is established between each participant P i by generating their own random degree t polynomial f i (x), and then securely sending f i (j) to each other participant P j , each participant summing all the received points f 1 (i)+f 2 (i)+ . . . +f n (i) to obtain their secret share s i =f (i), which is the P i point on the shared polynomial f (x).

10. A method according to claim 1 , wherein following creation of the initial private key share (s n 0 ) the initial public key share (pk 1 ) is computed using an elliptic curve generator G, as b i s n ×G, wherein the interpolation coefficient b i is:

b
i

=

Π

j
∈
U

,

j
≠
i

⁢

i

j
-
i

,

and
the initial public key shares are then broadcast to all participants and the initial shared public key (pk o ) is then calculated as the sum of any t+1 shares according to:

pk
=

∑

i
=
1

t
+
1

⁢

b
i

⁢

s
i

×
G

11. A method according to claim 1 , wherein the task is received from a client (C) or participant (P), said task being to find a private key for a Cryptocurrency address having a specified pattern therein,
wherein the intermediate private key (r n 0 ) is randomly generated and an intermediate public key (R n 0 ) is a multiple of the seed number by (r n 0 ) with an elliptic curve generator (G), and
the intermediate public key (R n 0 ) is added to the shared public key (pko) and processed to produce a Cryptocurrency address.

12. A method according to claim 1 , wherein upon all participants having the seed number (r v 0 ) that provided the solution (S), calculating the verified shared public key from
pk v =pk o +r v 0 ×G , and
constructing a verified secret key (sk v ) from verified secret key shares of each participant, calculated from,
s v n =s o n +r v 0 .

13. A method according to claim 1 , the method further

Assignees

• Nchain Licensing Ag

Inventors

• Trevethan Thomas

Classifications

• H04L9/085 Primary

  Secret sharing or secret splitting, e.g. threshold schemes · CPC title

• G06Q2220/00

  Business processing using cryptography · CPC title

• H04L2209/46

  Secure multiparty computation, e.g. millionaire problem · CPC title

• G06Q20/065

  using e-cash · CPC title

• H04L9/3066

  involving algebraic varieties, e.g. elliptic or hyper-elliptic curves · CPC title