More efficient post-quantum signatures

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.

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.