Post-quantum signature scheme using biometrics or other fuzzy data

A cryptographic system comprising:

• a signing device comprising:
• a fuzzy data interface to receive fuzzy data associated with a signee;
• a message interface to receive a message for the signee to digitally sign;
• a key generator to generate a signature-time signing key and a signature-time verification key, the signature-time signing key being generated to reside within a signing key space;
• a lattice-compatible linear sketch generator to generate a linear sketch, the linear sketch comprising a function of the fuzzy data and the signature-time signing key, wherein the fuzzy data is used as an encoding key in the linear sketch to encode the signature-time signing key;
• a lattice signature generator to receive the message and the signature-time signing key and to generate a lattice digital signature sigma for the message using the signature-time signing key, wherein the lattice digital signature sigma is generated using a lattice instantiation and the signing key space is a space defined by the lattice instantiation;
• and
• an output interface to output a digital signature comprising the lattice digital signature sigma, the linear sketch and the signature-time verification key,
• wherein the digital signature is verifiable using an initialisation-time verification key that varies from the signature-time verification key, wherein a variation of the signature-time verification key is comparable to a predefined homomorphic threshold.

A cryptographic system comprising:

• a verification device comprising:
• a message interface to receive a message to verify as being digitally signed by a signee;
• a digital signature interface to receive a digital signature, the digital signature comprising a lattice digital signature sigma, a signature-time verification key for the signee and a linear sketch, the lattice digital signature sigma being generated using the signature-time signing key, the linear sketch being generated based on fuzzy data associated with the signee, the lattice digital signature sigma being generated based on a lattice instantiation and the linear sketch being generated using a linear sketch function compatible with the lattice instantiation;
• a key data interface to receive key data comprising at least an initialisation-time verification key for the signee, wherein the initialisation-time verification key and the signature-time verification key are both generated using signing keys that reside in a signing key space defined by the lattice instantiation;
• a verification engine communicatively coupled to the message interface, the digital signature interface, and the key data interface to respectively receive the message, the digital signature and the key data, the verification engine being configured to:
• generate a reconstructed verification key from the linear sketch and the key data;
• compute a distance metric indicating a measure of difference between the signature-time verification key and the reconstructed verification key;
• and
• verify the digital signature based on at least the computed distance metric, and
• an output interface to output a result from the verification engine.