Lattice based signatures with uniform secrets

Patent metadata

Field	Value
Publication number	US-12120245-B2
Application number	US-202318241396-A
Country	US
Kind code	B2
Filing date	Sep 1, 2023
Priority date	Sep 26, 2019
Publication date	Oct 15, 2024
Grant date	Oct 15, 2024

Abstract

Improvements to post-quantum lattice-based digital signature schemes are disclosed. By sampling cryptographic material, including cryptographic key matrices and masking vectors from a uniform distribution, embodiments eliminate the need for a security check during generation of a digital signature vector. As a result, digital signatures can be generated faster and at a lower failure rate. A generating device can generate a verification matrix A and a secret matrix S from a uniform distribution, and an error matrix E from a special distribution (such as a Gaussian). The generating device can combine the three matrices to generate a public matrix Y. The first and the fourth matrices (A, Y) can be used as a public key used to verify digital signatures. The second and the third matrices (S, E) can be used as a private key used to generate digital signatures.

First claim

What is claimed is:

1. A computer system comprising:
a processor; and
a non-transitory computer readable medium coupled to the processor, the non-transitory computer readable medium comprising code, executable by the processor for implementing a method comprising:
generating a verification matrix A comprising a first plurality of elements, the first plurality of elements sampled from a uniform distribution;
generating a secret matrix S comprising a second plurality of elements, the second plurality of elements sampled from the uniform distribution;
generating an error matrix E comprising a third plurality of elements, the third plurality of elements sampled from a non-uniform distribution;
generating a public matrix Y using a modulus q as Y=SA+E mod q;
generating a public key comprising the verification matrix A and the public matrix Y;
generating a private key comprising the secret matrix S and the error matrix E;
generating a digital signature for a message m using the private key and a random vector r, the random vector r, generated by sampling from the uniform distribution; and
sending the digital signature and the message m to a verifying device that is configured to verify the signed message using the public key.

2. The computer system of claim 1 , further comprising transmitting the public key and the private key to a signing device.

3. The computer system of claim 1 , wherein the uniform distribution is implemented using a ring.

4. The computer system of claim 1 , wherein the uniform distribution is bound by the modulus q, such that each element of the first plurality of elements and the second plurality of elements is less than or equal to the modulus q.

5. The computer system of claim 1 , wherein each element of the first plurality of elements and the second plurality of elements is an integer greater than or equal to 0 and less than or equal to q−1.

6. The computer system of claim 1 , wherein:
the verification matrix A is an n by m matrix;
the secret matrix S is an h by n matrix;
the error matrix E is an h by m matrix;
h is less than or equal to n; and
m is greater than n.

7. The computer system of claim 1 , wherein the computer system comprising a signing device, wherein generating the digital signature for the message m includes:
(1) generating the random vector r by sampling from the uniform distribution;
(2) generating a product vector rA by calculating a product of the random vector r and the verification matrix A;
(3) generating a rounded product vector by discarding one or more least significant bits from each element of the product vector rA;
(4) generating an intermediate vector using the rounded product vector modulus q;
(5) generating a challenge vector c by hashing the message m and the intermediate vector;
(6) calculating a verification vector v based on the product vector rA, the challenge vector c, and the error matrix E;
(7) verifying that a plurality of elements of the verification vector v are within a predetermined interval of values;
(8) generating a signature vector z based on the random vector r, the challenge vector c, and the secret matrix S, wherein the digital signature includes the signature vector z and the challenge vector c; and
(9) sending the digital signature and the message m to the verifying device.

8. The computer system of claim 7 , further comprising:
if the plurality of elements of the verification vector v are not within the predetermined interval of values, repeating steps (1) through (7) until the plurality of elements of the verification vector v are within the predetermined interval of values.

9. The computer system of claim 7 , wherein (6) calculating the verification vector v comprises calculating rA−cE.

10. The computer system of claim 7 , wherein generating the signature vector z comprises calculating r+cS.

11. The computer system of claim 7 , wherein step (7) comprises:
determining a plurality of least significant bits of the verification vector v;
calculating a norm of the plurality of least significant bits; and
verifying that the norm is within the predetermined interval of values.

12. The computer system of claim 7 , wherein the predetermined interval of values is determined based on a parameter β, wherein the parameter β is greater than or equal to a norm of a product of the challenge vector c and the error matrix E with a specified probability.

13. The computer system of claim 12 , wherein the specified probability comprises a probability greater than 99.99%.

14. The computer system of claim 7 , wherein the signing device comprises an authorization computer, and wherein the message m comprises an authorization response message, the authorization response message indicating to the verifying device an authorization status of an interaction between the verifying device and a user device or a user of the user device.

15. A computer system comprising:
a processor; and
a non-transitory computer readable medium coupled to the processor, the non-transitory computer readable medium comprising code, executable by the processor for implementing a method comprising:
storing a public key received from a generating device and comprising a verification matrix A and a public matrix Y;
receiving, from a signing device, a message m and a digital signature including a signature vector z and a first challenge vector c;
generating a first verification vector v based on the verification matrix A, the public matrix Y, the signing vector z, and the first challenge vector c, wherein the signature vector z is based on a random vector r generated by sampling from a uniform distribution;
generating a rounded verification vector w by discarding one or more least significant bits from the verification vector v;
generating a second challenge vector by hashing the message m and the rounded verification vector w;
comparing the first challenge vector c to the second challenge vector;
verifying the signing device in response to the first challenge vector c matching the second challenge vector; and
after verifying the signing device and evaluating an authorization response message, performing an interaction with a user device or a user of the user device.

16. The computer system of claim 15 , wherein the rounded verification vector w is equal to an intermediate vector generated by the signing device, wherein the intermediate vector is equal to a rounded product vector rA modulus q.

17. The computer system of claim 15 , wherein the first verification vector v=ZA−cY.

18. The computer system of claim 15 , wherein a device performing the verifying comprises a resource provider computer, wherein the signing device comprises an authorization computer, wherein the message m comprises the authorization response message.

19. The computer system of claim 15 , wherein the first verification vector v is equal to a second verification vector generated by the signing device, the second verification vector based on a product vector rA, the first challenge vector c, and an error matrix E.

Assignees

• Visa Int Service Ass

Inventors

• Masny Daniel
• Chen Yilei
• Behnia Rouzbeh

Classifications

• H04L9/3093

  involving Lattices or polynomial equations, e.g. NTRU scheme · CPC title

• H04L9/0825

  using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates · CPC title

• H04L9/3247 Primary

  involving digital signatures · CPC title