Masking with efficient unmasking via domain embedding in cryptographic devices and applications

Abstract

Disclosed aspects and implementations are directed to systems and techniques for protecting cryptographic operations against side-channel attacks. In one example, polynomials associated with secret data and public data defined on a working domain having a first dimension are mapped to an auxiliary domain having a larger second dimension. The mapped polynomials are masked using masking polynomials associated with a kernel of a homomorphism transformation from the auxiliary domain to the working domain. One or more computations are then performed on the masked polynomials in the auxiliary domain and an output is transformed from the auxiliary domain to the working domain.

What is claimed is: 
     
         1 . A method to perform a cryptographic operation, the method comprising:
 mapping, to an auxiliary domain, each of (i) a first polynomial associated with a first data and defined on a working domain and (2) a second polynomial associated with a second data and defined on the working domain, wherein the working domain has a first dimension and the auxiliary domain has a second dimension that is greater than the first dimension;   masking, using a processing device, the first mapped polynomial with a first masking polynomial to obtain a first masked polynomial;   masking, using the processing device, the second mapped polynomial with a second masking polynomial to obtain a second masked polynomial, wherein the first masking polynomial and the second masking polynomial are associated with a kernel of a homomorphism transformation from the auxiliary domain to the working domain;   performing, using the first masked polynomial and the second masked polynomial, one or more computations in the auxiliary domain; and   obtaining, using the processing device, an output of the cryptographic operation, wherein obtaining the output comprises transforming an output of the one or more operations from the auxiliary domain to the working domain.   
     
     
         2 . The method of  claim 1 , wherein coefficients of each of the first polynomial and the second polynomial are defined modulo a first modulus in the working domain, wherein coefficients of each of the first masked polynomial and the second masked polynomial are defined modulo a second modulus in the working domain, and wherein the first modulus divides the second modulus. 
     
     
         3 . The method of  claim 2 , wherein masking the first mapped polynomial with the first masking polynomial comprises adding a product of the first modulus and each of a plurality of randomly-sampled coefficients of the first masking polynomial to a respective same-degree coefficient of the first mapped polynomial. 
     
     
         4 . The method of  claim 2 , wherein the second modulus is randomly sampled from a target range of values. 
     
     
         5 . The method of  claim 4 , wherein the target range of values is determined by at least one of:
 a bit size of one or more registers storing coefficients of the first masked polynomial; or   an operand size of a processing unit that performs the one or more computations in the auxiliary domain.   
     
     
         6 . The method of  claim 1 , wherein the one or more computations in the auxiliary domain comprise a first Number Theoretic Transform (NTT) of the first masked polynomial, and a second NTT of the second masked polynomial. 
     
     
         7 . The method of  claim 6 , wherein the one or more computations in the auxiliary domain further comprise:
 an elementwise multiplication of the first NTT and the second NTT, and   an inverse NTT of an output of the elementwise multiplication of the first NTT and the second NTT.   
     
     
         8 . The method of  claim 6 , wherein the first NTT and the second NTT are computed using a plurality of butterfly operations that deploy a plurality of twiddle factors, wherein one or more twiddle factors of the plurality of twiddle factors are masked using random numbers divisible by the first modulus. 
     
     
         9 . The method of  claim 6 , wherein the first NTT of the first masked polynomial is based on a root of unity modulo the second modulus, and wherein the root of unity modulo the second modulus is computed using a root of unity modulo the first modulus. 
     
     
         10 . A method to perform a cryptographic operation, the method comprising:
 identifying, using a processing device, a plurality of input polynomials with coefficients defined modulo a first modulus;   generating, using the processing device a plurality of masking polynomials with coefficients divisible by the first modulus and defined modulo a second modulus that is greater than the first modulus;   obtaining a plurality of masked polynomials, wherein each of the plurality of masked polynomials is computed, modulo the second modulus, using a respective input polynomial of the plurality of input polynomials and a respective masking polynomial of the plurality of masking polynomials;   computing, using one or more Number Theoretic Transforms (NTTs) performed modulo the second modulus, a polynomial multiplication product of the plurality of masking polynomials; and   obtaining, using the processing device, an output of the cryptographic operation using the polynomial multiplication product reduced modulo the first modulus.   
     
     
         11 . The method of  claim 10 , wherein the first modulus divides the second modulus. 
     
     
         12 . The method of  claim 10 , wherein coefficients of each of the plurality of masking polynomials are randomly-sampled from a set of numbers divisible by the first modulus. 
     
     
         13 . The method of  claim 10 , wherein the second modulus is randomly sampled from a target range of values. 
     
     
         14 . The method of  claim 13 , wherein the target range of values is determined by at least one of:
 a bit size of one or more registers storing coefficients of the plurality of masked polynomials; or   an operand size of a processing unit that supports computation of the one or more NTTs.   
     
     
         15 . The method of  claim 10 , wherein computing the polynomial multiplication product comprises computing, modulo the second modulus:
 a first NTT of a first masked polynomial of the plurality of masked polynomials;   a second NTT of a second masked polynomial of the plurality of masked polynomials;   an elementwise multiplication product of the first NTT and the second NTT, and   an inverse NTT of the elementwise multiplication product of the first NTT and the second NTT.   
     
     
         16 . The method of  claim 11 , wherein the one or more NTTs are computed using a plurality of butterfly operations that deploy a plurality of twiddle factors, wherein at least a subset of the plurality of twiddle factors are masked using random numbers divisible by the first modulus. 
     
     
         17 . A processing device comprising:
 one or more registers to store a first polynomial associated with a first data and a second polynomial associated with a second data, wherein the first polynomial and the second polynomial and defined on a working domain having a first dimension; and   one or more processing units to:
 map, to an auxiliary domain, the first polynomial and the second polynomial to an auxiliary domain having a second dimension that is greater than the first dimension; 
 mask the first mapped polynomial with a first masking polynomial to obtain a first masked polynomial; 
 mask the second mapped polynomial with a second masking polynomial to obtain a second masked polynomial, wherein the first masking polynomial and the second masking polynomial are associated with a kernel of a homomorphism transformation from the auxiliary domain to the working domain; 
 perform, using the first masked polynomial and the second masked polynomial, one or more computations in the auxiliary domain; and 
 obtain an output of the cryptographic operation, wherein obtaining the output comprises transforming an output of the one or more operations from the auxiliary domain to the working domain. 
   
     
     
         18 . The processing device of  claim 17 , wherein coefficients of each of the first polynomial and the second polynomial are defined modulo a first modulus in the working domain, wherein coefficients of each of the first masked polynomial and the second masked polynomial are defined modulo a second modulus in the working domain, and wherein the first modulus divides the second modulus. 
     
     
         19 . The processing device of  claim 18 , wherein to mask the first mapped polynomial with the first masking polynomial, the one or more processing units are to add a product of the first modulus and each of a plurality of randomly-sampled coefficients of the first masking polynomial to a respective same-degree coefficient of the first mapped polynomial. 
     
     
         20 . The processing device of  claim 17 , wherein the one or more computations in the auxiliary domain further comprise:
 an elementwise multiplication of the first NTT and the second NTT, and   an inverse NTT of an output of the elementwise multiplication of the first NTT and the second NTT;   
       wherein the first NTT and the second NTT are computed using a plurality of butterfly operations that deploy a plurality of twiddle factors, wherein one or more twiddle factors of the plurality of twiddle factors are masked using random numbers divisible by the first modulus.