Nxp B.v.

Joost Roland Renes

Tobias Schneider

Joppe Willem Bos

Christine Van Vredendaal

Björn Fay

Melissa Azouaoui

Marc Gourjon

Marcel Medwed

Stefan Lemsitzer

Mario Lamberger

Olivier Bronchain

Markus Schoenauer

Pim Vullers

Mohamed ElGhamrawy

Various embodiments relate to a data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for a cryptographic operation including matrix multiplication for lattice-based cryptography in a processor, the instructions, including: applying a first function to the rows of a matrix of polynomials to generate first outputs, wherein the first function excludes the identity function; adding an additional row to the matrix of polynomials to produce a modified matrix, wherein each element in the additional row is generated by a second function applied to a column of outputs associated with each element in the additional row; multiplying the modified matrix with a vector of polynomials to produce an output vector of polynomials; applying a verification function to the output vector that produces an indication of whether a fault occurred in the multiplication of the modified matrix with the vector of polynomials; and carrying out a cryptographic operation using output vector when the verification function indicates that no fault occurred in the multiplication of the modified matrix with the vector of polynomials.

Fault detection in post-quantum cyptography

A method of performing a Dilithium signature operation on a message M using a secret key sk, including: generating a polynomial y using an ExpandMask function; calculating a polynomial z based upon y, c, and s; performing a bound check on z based upon γand β; performing a bound check on ctbased upon γ; calculating a polynomial {tilde over (r)} based upon A, z, c, t, α, and w; performing a bound check on {tilde over (r)} based upon γand β; calculating a hint polynomial h based on the {tilde over (r)}; and returning a digital signature of the message M where the digital signature includes z and h.

Low-memory masked Dilithium with alternative signing algorithm

A data processing system and method for norm checking a cryptographic operation for lattice-based cryptography in a processor, the instructions, including: multiplying a first polynomial by a second polynomial to produce a first output, wherein the d arithmetic shares have a modulus q'; securely converting the first output to d Boolean shares; securely subtracting a third polynomial from the first output to produce a second output, wherein the third polynomial is randomly generated and then offset by a first constant parameter; securely adding a first constant based upon a bound check and the first constant parameter to the second output to shift the values of the second output to positive values to produce a third output; and securely adding a second constant based upon the bound check to the third output to produce a carry bit.

Masked infinity norm check for crystals-dilithium signature generation

Various embodiments relate to a fault detection system and method for a digital signature algorithm, including: producing a digital signature of a message using a digital signature algorithm; storing parameters from a last round of the digital signature algorithm; executing the last round of the digital signature algorithm using the stored parameters to produce a check signature; comparing the digital signature to the check signature; and outputting the digital signature when the digital signature is the same as the check signature.

Fault countermeasures for digital signatures with aborts

Various embodiments relate to a hardware device configured to compute a plurality of chained hash functions in parallel, including: a processor implementing p hash functions configured to operate on a small input, where p is an integer; a data unit connected to the plurality of hash functions, configured to store the outputs of plurality of hash functions that are then used as the input to a next round of computing the hash function, wherein the processor receives a single instruction and p small data inputs, and wherein each of the p hash functions are used to perform a chained hash function operation on a respective small input of the p small inputs.

Speeding up hash-chain computations

Various embodiments relate to a data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for masked sampling of polynomials for lattice-based cryptography in a processor, the instructions, including: determining a number m of random bits to be sampled based upon a sample bound parameter β; producing a plurality of Boolean masked shares of a polynomial coefficient each having the determined number m of random bits using a uniform random function; determining that the polynomial coefficient is within a range of values based upon the sample bound parameter β; converting the plurality of Boolean masked shares of the polynomial coefficient to a plurality of arithmetic masked shares of the polynomial coefficient; and shifting the plurality of arithmetic masked shares based upon the sample bound parameter β.

Efficient and masked sampling of polynomials for lattice-based cryptography

Various embodiments relate to a method for multiplying a first and a second polynomial in a ring[X]/(X+1) where q is a positive integer. The method comprising: mapping the first polynomial into k smaller third polynomials over k smaller rings based upon primitive roots of unity, where k is a positive integer; mapping the second polynomial into k smaller fourth polynomials over the k smaller rings based upon primitive roots of unity; applying an isomorphism to the k third polynomials resulting in k fifth polynomials; applying the isomorphism to the k fourth polynomials resulting in k sixth polynomials; applying a Kronecker substitution on the k fifth polynomials and the k sixth polynomials and perform the multiplication of the k fifth polynomials and the k sixth polynomials to produce a multiplication result; applying an inverse of the isomorphism to the multiplication result to obtain the multiplication of the first polynomial and the second polynomial; and mapping the k inverted polynomials to a single polynomial in the ring.

Combining regular and symbolic NTTs using co-processors

Various embodiments relate to a method for masked decoding of a polynomial a using an arithmetic sharing a to perform a cryptographic operation in a data processing system using a modulus q, the method for use in a processor of the data processing system, including: subtracting an offset &#x3b4; from each coefficient of the polynomial a; applying an arithmetic to Boolean (A2B) function on the arithmetic shares of each coefficient aof the polynomial a to produce Boolean shares &#xe2;that encode the same secret value a; and performing in parallel for all coefficients a shared binary search to determine which of coefficients aare greater than a threshold t to produce a Boolean sharing value {circumflex over (b)} of the bitstring b where each bit of b decodes a coefficient of the polynomial a.

Masked decoding of polynomials

Various embodiments relate to a method for securely comparing a first polynomial represented by a plurality of arithmetic shares and a second compressed polynomial represented by a bitstring where the bits in the bitstring correspond to coefficients of the second polynomial, including: performing a first masked shift of the shares of the coefficients of the first polynomial based upon the start of the interval corresponding to the compressed coefficient of the second polynomial and a modulus value; performing a second masked shift of the shares of the coefficients of the first polynomial based upon the end of the interval corresponding to the compressed coefficient of the second polynomial; bitslicing the most significant bit of the first masked shift of the shares coefficients of the first polynomial; bitslicing the most significant bit of the second masked shift of the shares coefficients of the first polynomial; and combining the first bitsliced bits and the second bitsliced bits using an AND function to produce an output including a plurality of shares indicating that the first polynomial would compress to a bitstream matching the bitstream representing the second compressed polynomial.

Masked comparison circumventing compression in post-quantum schemes

Various embodiments relate to a method and system for securely comparing a first and second polynomial, including: selecting a first subset ofcoefficients of the first polynomial and a second subset ofcorresponding coefficients of the second polynomial, wherein the coefficients of the first polynomial are split intoshares and the first and second polynomials havecoefficients; subtracting the second subset of coefficients from one of the shares of the first subset of coefficients; reducing the number of elements in the first subset of coefficients toelements by combining groups of/elements together; generating a random number for each of the elements of the reduced subset of coefficients; summing the product of each of the elements of the reduced subset of coefficients with their respective random numbers; summing theshares of the sum of the products; and generating an output indicating that the first polynomial does not equal the second polynomial when the sum does not equal zero.

Efficient masked polynomial comparison

Various embodiments relate to a method for multiplying a first and a second polynomial in the ring[X]/(X&#x2212;1) to perform a cryptographic operation in a data processing system, the method for use in a processor of the data processing system, including: receiving the first polynomial and the second polynomial by the processor; mapping the first polynomial into a third polynomial in a first ring and a fourth polynomial in a second ring using a map; mapping the second polynomial into a fifth polynomial in the first ring and a sixth polynomial in the second ring using the map; multiplying the third polynomial in the first ring with the fifth polynomial in the first ring to produce a first multiplication result; multiplying the fourth polynomial in the second ring with the sixth polynomial in the second ring to produce a second multiplication result using Renes multiplication; and combining the first multiplication result and the second multiplication result using the map.

Method for multiplying polynomials for a cryptographic operation

A method is provided for authenticating one device to another device. In the method, a first device proves to a second device that a first credential comprising multiple first attributes is valid. The second device proves to the first device that a second credential comprising multiple second attributes is valid. The first device reveals a first attribute of the multiple first attributes to the second device. The second device verifies the first attribute and decides whether to continue revealing attributes. If continuing, the second device reveals to the first device a first attribute of the multiple second attributes. The first device verifies the first attribute of the multiple second attributes. The first device decides whether to continue revealing attributes. Attributes can be revealed until one of the first or second devices end the method or until no attributes of the multiple first and second attributes remain to be revealed.

Authentication method in a communication system

A method is provided for multiplying two polynomials. In the method, first and second polynomials are evaluated at 2t inputs, where t is greater than or equal to one, and where each input is a fixed power of two 2multiplied with a different power of a primitive root of unity, thereby creating 2 times 2t integers, where l is an integer such that 2is at least as large as the largest coefficient of the resulting product multiplying the first and second polynomials. The 2 times 2t integers are then multiplied pairwise, and a modular reduction is performed to get 2t integers. A linear combination of the 2t integers multiplied with primitive roots of unity is computed to get 2t integers whose limbs in the base 2-bit representation correspond to coefficients of the product of the first and second polynomials. The method can be implemented on a processor designed for performing RSA and/or ECC type cryptographic operations.

Growing community of inventors

Eindhoven, Netherlands

Joost Roland Renes