Method and processing device for performing a lattice-based cryptographic operation

Patent metadata

Field	Value
Publication number	US-11265163-B2
Application number	US-201916377292-A
Country	US
Kind code	B2
Filing date	Apr 8, 2019
Priority date	Apr 9, 2018
Publication date	Mar 1, 2022
Grant date	Mar 1, 2022

Abstract

In various embodiments, a method for performing a lattice-based cryptographic operation is provided. The method includes obtaining a noise polynomial, a secret polynomial and a public polynomial, disguising at least one of the noise polynomial, the secret polynomial and the public polynomial by means of multiplying it with a random blinding polynomial, calculating the sum of the noise polynomial with the product of the public polynomial and the secret polynomial based on the disguised at least one polynomial, and determining a result of the lattice-based cryptographic operation based on the calculated sum of the noise polynomial with the product of the public polynomial and the secret polynomial.

First claim

What is claimed is:

1. A computer implemented method for performing a lattice-based cryptographic operation using a processing device and/or a hardware security module, the method comprising:
obtaining from a memory a noise polynomial, a secret polynomial and a public polynomial;
reducing leakage of information about the secret polynomial or the noise polynomial by disguising, using a masking circuit, at least one of the noise polynomial, the secret polynomial and the public polynomial, wherein disguising the at least one of the noise polynomial, the secret polynomial and the public polynomial comprises a security controller circuit multiplying the at least one of the noise polynomial, the secret polynomial and the public polynomial with a random blinding polynomial;
the security controller circuit calculating the sum of the noise polynomial with the product of the public polynomial and the secret polynomial based on the disguised at least one of the noise polynomial, the secret polynomial and the public polynomial;
the security controller circuit determining a result of the lattice-based cryptographic operation based on the calculated sum of the noise polynomial with the product of the public polynomial and the secret polynomial;
wherein multiplying the at least one of the noise polynomial, the secret polynomial and the public polynomial with the random blinding polynomial transforms the at least one of the noise polynomial, the secret polynomial and the public polynomial into a disguised polynomial to prevent implementation attacks comprising at least one of physical attacks, observatory attacks, invasive attacks, or semi-invasive attacks.

2. The method of claim 1 ,
wherein one or more of the secret polynomial, the noise polynomial and the public polynomial represent one or more secret cryptographic keys.

3. The method of claim 1 ,
wherein the sum of the noise polynomial with the product of the public polynomial and the secret polynomial represents a public key or a cipher text.

4. The method of claim 1 , further comprising:
disguising the noise polynomial and the secret polynomial by multiplying them with the same random blinding polynomial or different blinding polynomials.

5. The method of claim 1 , further comprising:
disguising at least one of the noise polynomial, the secret polynomial and the public polynomial to prevent physical attacks on the secret polynomial, the noise polynomial or both.

6. The method of claim 1 , further comprising:
generating the random blinding polynomial based on an output of a random number generator.

7. The method of claim 1 , further comprising:
generating the random blinding polynomial by sampling it from a uniform distribution.

8. The method of claim 1 , further comprising:
determining the noise polynomial by random sampling from an error distribution.

9. The method of claim 8 ,
wherein the error distribution is a uniform distribution, a discrete Gaussian distribution or a small uniform distribution.

10. The method of claim 1 , further comprising:
determining the secret polynomial by random sampling from a set or uniform distribution, discrete Gaussian distribution, small uniform distribution or sparse distribution.

11. The method of claim 1 ,
wherein the noise polynomial, the secret polynomial, the public polynomial and the blinding polynomial are polynomials modulo a predetermined polynomial with coefficients modulo a predetermined integer.

12. The method of claim 1 , further comprising:
calculating the sum of the noise polynomial with the product of the public polynomial and the secret polynomial for the same secret polynomial for a multiplicity of different public polynomials.

13. The method of claim 12 , further comprising:
blinding at least one of the secret polynomial and the noise polynomial to prevent the extraction of information of the secret polynomial from the calculations for the multiplicity of different public polynomials by an attacker.

14. The method of claim 12 , further comprising:
refreshing the random blinding operations between calculations of the sum of the noise polynomial with the product of the public polynomial and the secret polynomial for different public polynomials.

15. The method of claim 1 , further comprising:
disguising at least one of the noise polynomial and the secret polynomial by multiplying it with a random blinding polynomial and adding the same or a different random blinding polynomial to the result of the multiplication or adding a random blinding polynomial to it and multiplying the result of the sum with the same or a different random blinding polynomial.

16. The method of claim 1 , further comprising:
performing the disguising of at least one of the noise polynomial, the secret polynomial and the public polynomial and calculating the sum of the noise polynomial with the product of the public polynomial and the secret polynomial based on the disguised at least one polynomial in Number Theoretic Transform domain.

17. The method of claim 16 , further comprising:
transforming the noise polynomial, the secret polynomial and the public polynomial into Number Theoretic Transform domain and transforming the result of the sum of the noise polynomial with the product of the public polynomial and the secret polynomial back from Number Theoretic Transform domain.

18. The method of claim 1 , further comprising:
performing the lattice-based cryptographic operation in a signature or public key crypto processing.

19. The method of claim 1 , wherein obtaining a noise polynomial comprises random sampling from an error distribution.

20. A processing device for performing a lattice-based cryptographic operation, the processing device comprising:
a memory configured to store a noise polynomial, a secret polynomial and a public polynomial;
a masking circuit configured to reduce leakage of information about the secret polynomial or the noise polynomial by disguising at least one of the noise polynomial, the secret polynomial and the public polynomial, wherein disguising the at least one of the noise polynomial, the secret polynomial and the public polynomial comprises multiplying the at least one of the noise polynomial, the secret polynomial and the public polynomial with a random blinding polynomial;
a calculating circuit configured to calculate the sum of the noise polynomial with the product of the public polynomial and the secret polynomial based on the disguised at least one of the noise polynomial, the secret polynomial and the public polynomial;
a cryptographic circuit configured to determine a result of the lattice-based cryptographic operation based on the calculated sum of the noise polynomial with the product of the public polynomial and the secret polynomial;
wherein multiplying the at least one of the noise polynomial, the secret polynomial and the public polynomial with the random blinding polynomial transforms the at least one of the noise polynomial, the secret polynomial and the public polynomial into a disguised polynomial to prevent implementation attacks comprising at least one of physical attacks, observatory attacks, invasive attacks, or semi-invasive attacks.

Assignees

• Infineon Technologies Ag

Inventors

• Poeppelmann Thomas

Classifications

• G06F21/72

  in cryptographic circuits · CPC title

• G09C1/00

  Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00) · CPC title

• H04L9/3093 Primary

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

• H04L9/0662

  with particular pseudorandom sequence generator · CPC title

• H04L9/002

  Countermeasures against attacks on cryptographic mechanisms (network architectures or network communication protocols for protection against malicious traffic H04L63/1441) · CPC title