System and method for deterministic signing of a message using a multi-party computation (MPC) process

Patent metadata

Field	Value
Publication number	US-10833871-B2
Application number	US-201916726965-A
Country	US
Kind code	B2
Filing date	Dec 26, 2019
Priority date	Nov 8, 2018
Publication date	Nov 10, 2020
Grant date	Nov 10, 2020

Abstract

A method for signing a message, comprising performing a first Multi-Party Computation (MPC) process by multiple parties to compute a pseudorandom function, an input of the first MPC process comprises shares of a private signing key, each share is held by each party, the message is an input value to the pseudorandom function. The output of the first MPC process comprises multiple pairs of shares, each party holding a pair of shares, wherein each pair comprises a first value used for the MPC signing process and a second verifying value used for verifying correctness of the values provided by the multiple parties for the MPC signing process, and computing the signature on the message by performing an MPC signing protocol on the message, the MPC signing protocol receives as input shares of the output of the pseudorandom function from the multiple parties, and the message to be signed.

First claim

What is claimed is:

1. A method for signing a message, comprising:
receiving a request to sign the message;
performing a first Multi-Party Computation (MPC) process by multiple parties to compute a pseudorandom function, an input of the first MPC process comprises shares of a private signing key, each share is held by a party of the multiple parties,
wherein the message to be signed is an input value to the pseudorandom function,
wherein an output of the first MPC process to compute the pseudorandom function comprises producing multiple pairs of shares of the output of the pseudorandom function, each party of the multiple parties holding a pair of shares,
wherein each pair of the multiple pairs comprises a first value used for the MPC signing process and a second verifying value used for verifying correctness of the values provided by the multiple parties for the MPC signing process, and
wherein each party of the multiple parties provides one of the values in the pair of shares based on a random mechanism executed multiple times, to verify that at least once the value used for the MPC signing process is provided by the multiple parties and at least once the second verifying value is provided by the multiple parties;

computing the signature on the message by performing an MPC signing protocol on the message, wherein the MPC signing protocol receives as input shares of the output of the pseudorandom function from the multiple parties for the signature randomness, and the message to be signed; and
sending the signature to the entity from which the request was sent after performing the MPC signing protocol on the message.

2. The method of claim 1 , wherein the key to the pseudorandom function is the private signing key.

3. The method of claim 1 , wherein the shares of the private signing key are used as part of the signing process.

4. The method of claim 1 , wherein encrypting the pair of shares using an elliptic curve.

5. The method of claim 1 , further comprising verifying correctness of the shares of the private signing key inputted by the multiple parties to the MPC signing process using the verifying values.

6. The method of claim 5 , wherein verifying correctness of the shares of the private signing key comprises performing an arithmetic manipulation on the verifying values.

7. The method of claim 5 , wherein the values provided by the multiple parties to the MPC signing process are used after verifying correctness of the shares of the private signing key.

8. The method of claim 1 , further comprising:
the multiple parties creating a commitment on an encryption of the pair of shares of the private signing key,
at least one party of the multiple parties sending the commitment to another party of the multiple parties; and
the parties receiving the commitment opening the commitments and verifying that the values provided by the multiple parties to the MPC signing process are correct.

9. The method of claim 1 , wherein the pseudorandom function is a key-derivation function.

10. A method for signing a message, comprising:
performing a first Multi-Party Computation (MPC) process by multiple parties to compute a pseudorandom function, an input of the first MPC process comprises shares of a private signing key, each share is held by a party of the multiple parties, wherein the message to be signed is an input value to the pseudorandom function,
wherein an output of the first MPC process to compute the pseudorandom function comprises producing multiple pairs of shares of the output of the pseudorandom function, each party of the multiple parties holding a pair of shares, and
wherein each pair of the multiple pairs comprises a first value used for the MPC signing process and a second verifying value used for verifying correctness of the values provided by the multiple parties for the MPC signing process;

verifying correctness of the shares of the private signing key inputted by the multiple parties to the MPC signing process using the verifying values,
wherein verifying correctness of the shares of the private signing key comprises performing an arithmetic manipulation on the verifying values, and
wherein each party of the multiple parties provides one of the values in the pair of shares based on a random mechanism executed multiple times, to verify that at least once the value used for the MPC signing process is provided by the multiple parties and at least once the second verifying value is provided by the multiple parties; and

computing the signature on the message by performing an MPC signing protocol on the message, wherein the MPC signing protocol receives as input shares of the output of the pseudorandom function from the multiple parties for the signature randomness, and the message to be signed.

11. The method of claim 10 , wherein the key to the pseudorandom function is the private signing key.

12. The method of claim 10 , wherein the shares of the private signing key are used as part of the signing process.

13. The method of claim 10 , further comprising receiving a request to sign the message.

14. The method of claim 13 , further comprising sending the signature to the entity from which the request was sent after performing the MPC signing protocol on the message.

15. The method of claim 10 , wherein encrypting the pair of shares using an elliptic curve.

16. The method of claim 10 , further comprising:
the multiple parties creating a commitment on an encryption of the pair of shares of the private signing key;
at least one party of the multiple parties sending the commitment to another party of the multiple parties; and
the parties receiving the commitment opening the commitments and verifying that the values provided by the multiple parties to the MPC signing process are correct.

17. A method for signing a message, comprising:
performing a first Multi-Party Computation (MPC) process by multiple parties to compute a pseudorandom function, an input of the first MPC process comprises shares of a private signing key, each share is held by a party of the multiple parties,
wherein the message to be signed is an input value to the pseudorandom function,
wherein an output of the first MPC process to compute the pseudorandom function comprises producing multiple pairs of shares of the output of the pseudorandom function, each party of the multiple parties holding a pair of shares, and
wherein each pair of the multiple pairs comprises a first value used for the MPC signing process and a second verifying value used for verifying correctness of the values provided by the multiple parties for the MPC signing process;

verifying correctness of the shares of the private signing key inputted by the multiple parties to the MPC signing process using the verifying values, wherein the values provided by the multiple parties to the MPC signing process are used after verifying correctness of the shares of the private signing key, wherein each party of the multiple parties provides one of the values in the pair of shares based on a random mechanism executed multiple times, to verify that at least once the value used for the MPC signing process is provided by the multiple parties and at least once the second verifying value is provided by the multiple parties; and
computing the signature on the message by performing an MPC signing protocol on the message, wherein the MPC signing protocol receives as input shares of the output of the pseudorandom function from the multiple parties for the signature randomness, and the message to be signed.

18. Th

Assignees

• Unbound Tech Ltd
• Univ Bar Ilan

Inventors

• Ranellucci Samuel
• Lindell Yehuda

Classifications

• H04L9/50

  using hash chains, e.g. blockchains or hash trees · CPC title

• H04L2209/46

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

• H04L9/3255

  using group based signatures, e.g. ring or threshold signatures · CPC title

• H04L9/088

  Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms (network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068) · CPC title

• H04L9/3239

  involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD · CPC title