Lattice-based threshold signature method and threshold decryption method
AssigneePQShield Ltd
InventorsShuichi KATSUMATA, Mary MALLER, Rafaël DEL PINO, Fabrice MOUHARTEM, Thomas PREST, Thomas ESPITAU
Life of this patent
Estimating the term…
Abstract
Lattice-based threshold signature schemes and threshold decryption schemes are described. The threshold signature schemes are described in two or three rounds and are secure under Module Learning with Errors and Module Short integer Solution assumptions. In each of the signature and threshold decryption schemes, blinders may be introduced to shield information about the secret key that may otherwise be leaked by honest participants in the scheme.
Claims20
A method performed by one or more information processing apparatus for calculating a linear function that includes a product of a secret, s, and a linear function component using a threshold number, T, out of a number N of secret shares generated from a secret, s, wherein the number of secret shares, N, is greater than the threshold number, T, the method comprising:
- generating a public matrix, A, and the secret, s;
- generating a small noise, e, and a public key, ek, that includes a sum of the small noise, e, with a product of the public matrix, A, and the secret, s;
- generating N secret shares, si, from the secret, s;
- for each of a threshold number, T, of the secret shares:
- generating a blinder;
- and
- generating masked shares of the calculation of the linear function by calculating
- a first component that is based on a product of the secret share, and the linear function component, and adding or subtracting from the first component a noise and the blinder;
- and
- in an aggregating phase:
- summing a combination of the masked share associated with each secret share, whereby the blinders cancel out over the sum of masked shares to allow determination of the linear function.
A threshold signature method performed by one or more information processing apparatus for generating a signature using a threshold number, T, out of a number N of secret shares generated from a secret, s, wherein the number of secret shares, N, is greater than the threshold number, T, the method comprising:
- generating a public matrix, A, and the secret, s;
- generating a small noise, e, and a public key, vk=(A, t) including a portion of the public key, t, that comprises a sum of the small noise, e, with a product of the public matrix, A, and the secret, s;
- and
- generating N secret shares, si, from the secret, s;
- for each of the threshold number T of secret shares:
- generating T individual commitments, wi, each comprising one or more learning with errors samples, wj;
- aggregating the T individual commitments, wi, to generate an aggregated commitment, w;
- generating a challenge, c, that is a hash of at least a message to be signed, msg, and the aggregated commitment, w;
- generating T individual responses, zj, based on the challenge, c, the secret share, sj, and one or more ephemeral randomness used to generate the one or more learning with errors sample, rj;
- in an aggregating phase:
- generating the aggregated commitment, w, by summing the learning with errors samples, wj across the T secret shares;
- generating an aggregated response, z, by summing the individual responses, zj;
- generating a global challenge, c, by hashing at least the message to be signed, msg, and the aggregated commitment, w;
- generating a hint, h, by:
- determining a noisy commitment, y, by subtracting a product of the global challenge, c, and the portion of the public key, t, from a product of the aggregated response, z, and the public matrix, A;
- and
- subtracting the noisy commitment, y, from the aggregated commitment, w, to generate the hint, h;
- and
- outputting a signature comprising the global challenge, c, the aggregated response, z, and the hint, h.
One or more information processing apparatus, each comprising a processor and a storage medium storing computer-readable instructions, wherein the computer-readable instructions are configured to cause the one or more information processing apparatus to perform a method for calculating a linear function that includes a product of a secret, s, and a linear function component using a threshold number, T, out of a number N of secret shares generated from a secret, s, wherein the number of secret shares, N, is greater than the threshold number, T, the method comprising:
- generating a public matrix, A, and the secret, s;
- generating a small noise, e, and a public key, ek, that includes a sum of the small noise, e, with a product of the public matrix, A, and the secret, s;
- generating N secret shares, s¿, from the secret, s;
- for each of a threshold number, T, of the secret shares:
- generating a blinder;
- and
- generating masked shares of the calculation of the linear function by calculating a first component that is based on a product of the secret share, and the linear function component, and adding or subtracting from the first component a noise and the blinder;
- and
- in an aggregating phase:
- summing a combination of the masked share associated with each secret share, whereby the blinders cancel out over the sum of masked shares to allow determination of the linear function.
A non-transitory computer-readable storage medium storing a program that, when executed on one or more information processing apparatus cause the one or more information processing apparatus to perform a method for calculating a linear function that includes a product of a secret, s, and a linear function component using a threshold number, T, out of a number N of secret shares generated from a secret, s, wherein the number of secret shares, N, is greater than the threshold number, T, the method comprising:
- generating a public matrix, A, and the secret, s;
- generating a small noise, e, and a public key, ek, that includes a sum of the small noise, e, with a product of the public matrix, A, and the secret, s;
- generating N secret shares, si, from the secret, s;
- for each of a threshold number, T, of the secret shares:
- generating a blinder;
- and
- generating masked shares of the calculation of the linear function by calculating a first component that is based on a product of the secret share, and the linear function component, and adding or subtracting from the first component a noise and the blinder;
- and
- in an aggregating phase:
- summing a combination of the masked share associated with each secret share, whereby the blinders cancel out over the sum of masked shares to allow determination of the linear function.
Dependencies are inferred from the claim text.