Masked decomposition of polynomials for lattice-based cryptography

A data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for a cryptographic operation including a masked decomposition of a polynomial a having ns arithmetic shares into a high part a1 and a low part a0 for lattice-based cryptography in a processor, the instructions, comprising:

• performing a rounded Euclidian division of the polynomial a by a base α to compute t(⋅)A;
• extracting Boolean shares a1(⋅)B from n low bits of t by performing an arithmetic share to Boolean share (A2B) conversion on t(⋅)A and performing an AND with ζ−1, where ζ=−α−1 is a power of 2;
• unmasking a1 by combining Boolean shares of a1(⋅)B;
• calculating the Boolean shares a0(⋅)B of the low part a0;
• and
• performing a cryptographic function using a1 and a0(⋅)B.

A data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for a cryptographic operation including a masked decomposition of a polynomial a having ns arithmetic shares into a high part a1 and a low part a0 for lattice-based cryptography in a processor, the instructions, comprising:

• performing a rounded Euclidian division of the polynomial a by a base α to compute t(⋅)A;
• extracting Boolean shares a1(⋅)B from n low bits of t by performing an arithmetic share to Boolean share (A2B) conversion on t(⋅)A to produce t(⋅)B and performing a Boolean share to arithmetic share (B2A) conversion on t(⋅)B, where ζ=−α−1;
• unmasking a1 by combining arithmetic shares of a1(⋅)A;
• calculating the arithmetic shares a0(⋅)A of the low part a0;
• and
• performing a cryptographic function using a1 and a0(⋅)A.