# US 2022/0045865 A1 · More efficient post-quantum signatures

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0045865 A1
- Document ID: US20220045865A1
- Status: Published application
- Kind: A1
- Application number: 17/429,317
- Filed: 2019-08-01
- Published: 2022-02-10
- Earliest claimed: 2019-02-08
- Assignees: Visa International Service Association
- Applicants: Visa International Service Association
- Inventors: Pratyay Mukherjee; Yilei Chen; Nicholas Genise
- Web page: https://patentgrep.com/patent/US20220045865A1

## CPC

- H04L 9/3247: {involving digital signatures}
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Techniques of generating a lattice-based verification matrix and signature vector are disclosed. The method enables generating device to sample a gadget matrix and then generate a reduced gadget matrix. The generating device may then sample a trapdoor matrix and use the trapdoor matrix and the reduced gadget matrix to generate a verification matrix. A sending device may receive the trapdoor matrix and the verification matrix from the generating device, in addition to receiving a message. The sending device may then use the trapdoor matrix and the verification matrix to generate a signature vector for the message. A verification device can receive the verification matrix, the message, and the signature vector. The verification device may use the verification matrix and the signature vector to verify the message.

## Claims

### Claim 1

A method for use in verifying digital signatures, the method comprising performing, by a generating device:
generating a gadget matrix G, wherein the columns of the gadget matrix G comprise ascending powers of a base b;
generating a reduced gadget matrix F, wherein the reduced gadget matrix F is generated by dropping l columns of the gadget matrix G;
sampling a probability distribution to form a trapdoor matrix R, wherein the trapdoor matrix functions as a secret key for generating a digital signature;
generating a verification matrix A using the reduced gadget matrix F and the trapdoor matrix R; and
transmitting, to a verification device, the verification matrix A, causing the verification device to verify the digital signature generated by a sending device, using the trapdoor matrix R.

### Claim 2 (depends on 1)

The method of claim 1, wherein the base b of the gadget matrix G is 2.

### Claim 3 (depends on 1)

The method of claim 1, wherein the trapdoor matrix R is sampled from a Gaussian distribution.

### Claim 4 (depends on 1)

The method of claim 1, wherein generating the verification matrix A comprises:
sampling a uniform distribution to form a uniform matrix Â;
forming a generation matrix Ā by concatenating an identity matrix I and the uniform matrix Â, wherein Ā=[I|Â]; and
forming the verification matrix A, wherein A=[Ā|F−ÂR].

### Claim 5 (depends on 1)

The method of claim 1, wherein l is in the range 0 to (logbq)/2 for a modulus q, and wherein the modulus q is between 216 and 224.

### Claim 6 (depends on 1)

The method of claim 1, wherein the gadget matrix G comprises n repeats of k columns with ascending powers of the base b, and where generating the reduced gadget matrix F further comprises dropping the l columns with the smallest powers of the base b from each group of k columns of the gadget matrix G.

### Claim 7 (depends on 1)

The method of claim 1, wherein the distribution is a Gaussian distribution.

### Claim 8 (depends on 1)

The method of claim 1, wherein the verification matrix A is transmitted to the sending device.

### Claim 9

(canceled)

### Claim 10

A method comprising performing by a sending device:
receiving a message m;
storing a verification matrix A and a trapdoor matrix R, wherein the trapdoor matrix is generated by sampling a probability distribution;
generating a signature vector x by (1) using the verification matrix A to form a lattice vector v, (2) sampling an intermediate vector z from a distribution based on the lattice vector v, and (3) forming the signature vector x from a product of the intermediate vector z and the trapdoor matrix R such that the signature vector x satisfies a relationship Ax=h(m)+e mod q for a hash h(m) of the message m, a modulus q, and an error vector e; and
transmitting, to a verification device, the message m and the signature vector x, wherein the verification device stores the verification matrix A for verifying that the signature vector x was generated by the sending device.

### Claim 11 (depends on 10)

The method of claim 10, wherein generating the signature vector x comprises:
sampling a perturbation p from a probability distribution;
forming the lattice vector v using the message m, the verification matrix A, and the perturbation p as inputs to a function defined by v=m−Ap;
sampling an intermediate vector z from a lattice Gaussian distribution, wherein the lattice Gaussian distribution is based on a lattice formed from the lattice vector v; and
forming the signature vector x by inputting the trapdoor matrix R, the perturbation p, an identity matrix I, and the intermediate vector z into a function defined by
x
=
p
+
[
R
I
]
⁢
z
.

### Claim 12

(canceled)

### Claim 13

(canceled)

### Claim 14 (depends on 10)

The method of claim 10, wherein the signature vector x is verified based on a size of the error vector e being less than a threshold.

### Claim 15 (depends on 14)

The method of claim 14, wherein the threshold is the dimension of the hash h(m).

### Claim 16

(canceled)

### Claim 17

(canceled)

### Claim 18 (depends on 10)

The method of claim 10, wherein the sending device receives the verification matrix A from a generating device.

### Claim 19 (depends on 10)

The method of claim 10, wherein the sending device transmits the hash h(m) to the verification device.

### Claim 20

A method for authenticating a sending device, the method comprising performing by a verification device:
storing a verification matrix A;
receiving from the sending device, a message m and a signature vector x;
computing an error vector e by solving an equation Ax=h(m)+e mod q for a hash h(m) of the message m and a modulus q;
quantifying a size of the error vector e;
comparing the size to a threshold; and
verifying the signature vector x based on the size of the error vector e being less than the threshold.

### Claim 21 (depends on 20)

The method of claim 20, wherein the threshold is a dimension of the hash h(m).

### Claim 22

(canceled)

### Claim 23

(canceled)

### Claim 24 (depends on 20)

The method of claim 20, further comprising receiving the hash h(m) from the sending device.

### Claim 25 (depends on 20)

The method of claim 20, further comprising generating the hash h(m) by applying a hashing function to the message m.

### Claim 26 (depends on 20)

The method of claim 20, wherein the verification matrix A is received from the sending device.

### Claim 27 (depends on 20)

The method of claim 20, wherein the verification matrix A is received from a generating device, and wherein the generating device generates the verification matrix A.

### Claim 28

(canceled)

### Claim at position 29

29-33. (canceled)
