Masked decomposition of polynomials for lattice-based cryptography
Various implementations relate to 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 n s arithmetic shares into a high part a 1 and a low part a 0 for lattice-based cryptography in a processor, the instructions, including: performing a rounded Euclidian division of the polynomial a by a base α to compute t (⋅)A ; extracting Boolean shares a 1 (⋅)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 a 1 by combining Boolean shares of a 1 (⋅)B ; calculating arithmetic shares a 0 (⋅)A of the low part a 0 ; and performing a cryptographic function using a 1 and a 0 (⋅)A .
1. 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 n s arithmetic shares into a high part a 1 and a low part a 0 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 a 1 (⋅)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 a 1 by combining Boolean shares of a 1 (⋅)B ;
calculating arithmetic shares a 0 (⋅)A of the low part a 0 ; and
performing a cryptographic function using a 1 and a 0 (⋅)A .
2. The data processing system of claim 1 , wherein performing a rounded Euclidian division of the polynomial a by a base α to compute t (⋅)A includes adding α/2 to a (⋅)A and dividing by α.
3. The data processing system of claim 2 , wherein performing a rounded Euclidian division of the polynomial a by a base α to compute t (⋅)A includes calculating:
t (⋅)A =a (⋅)A +γ; and
t (⋅)A =α −1 ×t (⋅)A −( q mod ζ),
where γ=α/2 and q is a prime modulus.
4. The data processing system of claim 1 , wherein calculating arithmetic shares a 0 (⋅)A of the low part a 0 includes:
calculating u (⋅)A by subtracting a 1 from t (⋅)A and adding q mod ζ, where q is a prime modulus; and
multiplying u (⋅)A by α and then subtracting α/2.
5. 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 n s arithmetic shares into a high part a 1 and a low part a 0 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 a 1 (⋅)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 a 1 by combining Boolean shares of a 1 (⋅)B ;
calculating the Boolean shares a 0 (⋅)B of the low part a 0 ; and
performing a cryptographic function using a 1 and a 0 (⋅)B .
6. The data processing system of claim 5 , wherein performing a rounded Euclidian division of the polynomial a by a base α to compute t (⋅)A includes adding α/2 to a (⋅)A and dividing by α.
7. The data processing system of claim 6 , wherein performing a rounded Euclidian division of the polynomial a by a base α to compute t (⋅)A includes calculating:
t (⋅)A =a (⋅)A +γ; and
t (⋅)A =α −1 ×t (⋅)A −( q mod ζ),
where γ=α/2 and q is a prime modulus.
8. The data processing system of claim 5 , wherein calculating the Boolean shares a 0 (⋅)B of the low part a 0 includes:
shifting t (⋅)B n bits to the right, where n is a number of bits in ζ; and
calculating
a 0 (⋅)B =SecAdd(((γ+( q mod ζ)) (⋅)B ,¬t (⋅)B )
where γ=α/2 and q is a prime modulus.
9. 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 n s arithmetic shares into a high part a 1 and a low part a 0 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 a 1 (⋅)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 a 1 by combining arithmetic shares of a 1 (⋅)A ;
calculating the arithmetic shares a 0 (⋅)A of the low part a 0 ; and
performing a cryptographic function using a 1 and a 0 (⋅)A .
10. The data processing system of claim 9 , wherein performing a rounded Euclidian division of the polynomial a by a base α to compute t (⋅)A includes adding α/2 to α (⋅)A and dividing by α.
11. The data processing system of claim 10 , wherein performing a rounded Euclidian division of the polynomial a by a base α to compute t (⋅)A includes calculating:
t (⋅)A =a (⋅)A +γ; and
t (⋅)A =α −1 ×t (⋅)A −( q mod ζ),
where γ=α/2 and q is a prime modulus.
12. The data processing system of claim 9 , wherein calculating the arithmetic shares a 0 (⋅)A of the low part a 0 includes:
calculating u (⋅)A by subtracting a 1 from t (⋅)A and adding q mod ζ, where q is a prime modulus; and
multiplying u (⋅)A by α and then subtracting α/2.