Protecting polynomial rejection through masked compression comparison

A data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for a cryptographic operation using a masked rejection of a polynomial with coefficients having ns arithmetic shares for lattice-based cryptography in a processor, the instructions, comprising:

• generating a ns arithmetic shares for each coefficient of the polynomial;
• performing a masked compression of each coefficient of the polynomial using the ns arithmetic shares for each coefficient of the polynomial, including:
• shifting a first arithmetic share of the ns arithmetic shares by an input mask λ1;
• scaling the shifted first arithmetic share by a value based on a first compression factor δ and a masking scaling factor φ1;
• shifting the scaled first arithmetic share by a value based on the masking scaling factor φ1;
• scaling the second to ns shares of the ns arithmetic shares by a value based on the first compression factor δ and the masking scaling factor φ1;
• converting the ns scaled arithmetic shares to Boolean shares;
• right shifting the ns Boolean shares based upon the masking scaling factor φ1 and a second compression factor φ2;
• and
• XORing an output mask λ2 to the shifted first Boolean share to produce ns compressed Boolean shares,
• wherein the compressed ns Boolean shares indicate compressed polynomial coefficients having a predetermined value when the polynomial coefficients are within boundary values;
• comparing the polynomial coefficients represented by the ns compressed Boolean shares to the predetermined value;
• and
• carrying out a cryptographic operation using the ns arithmetic shares when the polynomial coefficients represented by the ns compressed shares are equal to the predetermined value.

A method for a cryptographic operation using masked compressing of coefficients of a polynomial having ns arithmetic shares for lattice-based cryptography, comprising:

• shifting a first arithmetic share of the ns arithmetic shares by an input mask λ1;
• scaling the shifted first arithmetic share by a value based on a first compression factor δ and a masking scaling factor φ1;
• shifting the scaled first arithmetic share by a value based on the masking scaling factor φ1;
• scaling a second to ns shares of the ns arithmetic shares by a value based on the first compression factor δ and the masking scaling factor φ1;
• converting the ns scaled arithmetic shares to ns Boolean shares;
• right shifting the ns Boolean shares based upon the masking scaling factor φ1 and a second compression factor φ2;
• XORing an output mask λ2 to the shifted first Boolean share to produce ns compressed Boolean shares;
• and
• carrying out a cryptographic operation using the ns arithmetic shares when the ns compressed Boolean shares indicates that the coefficients of the polynomial are within boundary values.