Masked comparison circumventing compression in post-quantum schemes
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.
1. 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, comprising:
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.
2. The method of claim 1 , wherein performing a first masked shift of the shares of the coefficients of the first polynomial further comprises:
calculating
x i =a i , and
x i (0) =( x i (0) +2 [log 2 (q)]−1 −s )mod q
where a i is the arithmetic shares of the i th coefficient of the first polynomial a, q is the modulus, and s is the start of the interval of values compressing to bit values in b i associated with the i th coefficient of the compressed polynomial.
3. The method of claim 2 , wherein performing a second masked shift of the shares of the coefficients of the first polynomial further comprises:
calculating
y i =a i , and
y i (0) =( y i (0) −e )mod q
where e is the end of the interval of values compressing to bit values in b associated with the i th coefficient of the compressed polynomial.
4. The method of claim 3 , further comprising:
calculating
{circumflex over (x)} i =A 2 B ( x i ) and
ŷ i =A 2 B ( y i ),
where the function A2B converts arithmetic shares of the input into Boolean shares, {circumflex over (x)} i is the Boolean shared first masked shift of the coefficients of the first polynomial, and ŷ i is the Boolean shared second masked shift of the coefficients of the first polynomial.
5. The method of claim 4 , wherein
bitslicing the most significant bit of the first masked shift of the shares coefficients of the first polynomial includes calculating
{circumflex over (x)} i =sharewiseLSR( {circumflex over (x)} i ,[log 2 ( q )]−1), and
bitslicing the most significant bit of the second masked shift of the shares coefficients of the first polynomial includes calculating
ŷ i =sharewiseLSR( ŷ i ,[log 2 ( q )]−1),
where the function sharewiseLSR(z, l) performs a right shift of l bits of z on each share of z.
6. The method of claim 5 , further comprising:
calculating
{circumflex over (t)} x ={0, . . . ,0},
{circumflex over (t)} y ={0, . . . ,0}.
calculating for all values of j from 0 to k−1
{circumflex over (t)} x =sharewiseOR( {circumflex over (t)} x ,sharewiseLSL( {circumflex over (x)} k·i+j ,j )), and
{circumflex over (t)} y =sharewiseOR( {circumflex over (t)} y ,sharewiseLSL( ŷ k·i+j ,j ))
where {circumflex over (t)} x is a first temporary variable, {circumflex over (t)} y is a second temporary variable, j is an index, k is the number of coefficients processed in parallel, i is an index value, sharewiseOR is a function that performs a bitwise OR on the shares of the inputs, and the function sharewiseLSL(z, l) performs a left shift of l bits of z on each share of z.
7. The method of claim 6 , wherein combining the first bitsliced bits and the second bitsliced bits further comprises:
calculating for all values of j from 0 to k−1
ĉ =maskedAND( ĉ ,maskedAND( {circumflex over (t)} x ,{circumflex over (t)} y ))
where ĉ is the shared output indicating that the first polynomial would compress to a bitstream matching the bitstream representing the second compressed polynomial and the function maskedAND performs a masked bitwise AND of the inputs.
8. The method of claim 7 , wherein combining the first bitsliced bits and the second bitsliced bits further comprises repeatedly ANDing the upper and lower bits of each the shares of ĉ together until a single bit per share results.
9. The method of claim 7 , wherein combining the first bitsliced bits and the second bitsliced bits further comprises ANDing all of the bits of each of the shares of ĉ together until a single bit per share results.
10. The method of claim 1 , wherein the modulus is a prime number.
11. A data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions 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 to perform a cryptographic operation in a processor, the instructions, comprising:
instructions for 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;
instructions for 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;
instructions for bitslicing the most significant bit of the first masked shift of the shares coefficients of the first polynomial;
instructions for bitslicing the most significant bit of the second masked shift of the shares coefficients of the first polynomial; and
instructions for 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.
12. The data processing system of claim 11 , wherein instructions for performing a first masked shift of the shares of the coefficients of the first polynomial further comprises:
instructions for calculating
x i =a i , and
x i (0) =( x i (0) +2 [log 2 (q)]−1 −s )mod q
where a i is the arithmetic shares of the i th coefficient of the first polynomial a, q is the modulus, and s is the start of the interval of values compressing to bit values in b i associated with the i th coefficient of the compressed polynomial.
13. The data processing system of claim 12 , wherein instructions for performing a second masked shift of the shares of the coefficients of the first polynomial further comprises:
instructions for calculating
y i =a i , and
y i (0) =( y i (0) −e )mod q
where e is the end of the interval of values compressing to bit values in b associated with the i th coefficient of the compressed polynomial.
14. The data processing system of claim 13 , further comprising:
instructions for calculating
{circumflex over (x)} i =A 2 B ( x i ) and
ŷ i =A 2 B ( y i ),
where the function A2B converts arithmetic shares of the input into Boolean shares, {circumflex over (x)} i is the Boolean shared first masked shift of the coefficients of the first polynomial, and ŷ i is the Boolean shared second masked shift of the coefficients of the first polynomial.
15. The data processing system of claim 14 , wherein
instructions for bitslicing the most significant bit of the first masked shift of the shares coefficients of the first polynomial includes instructions for calculating
{circumflex over (x)} i =sharewiseLSR( {circumflex over (x)} i ,[log 2 ( q )]−1), and
instructions for bitslicing the most significant bit of the second masked shift of the shares coefficients of the first polynomial includes instructions for calculating
ŷ i =sharewiseLSR( ŷ i ,[log 2 ( q )]−1),
where the function sharewiseLSR(z, l) performs a right shift of l bits of z on each share of z.
16. The data processing system of claim 15 , further comprising:
instructions for calculating
{circumflex over (t)} x ={0, . . . ,0},
{circumflex over (t)} y ={0, . . . ,0}.
instructions for calculating for all values of j from 0 to k−1
{circumflex over (t)} x =sharewiseOR( {circumflex over (t)} x ,sharewiseLSL( {circumflex over (x)} k·i+j ,j )), and
{circumflex over (t)} y =sharewiseOR( {circumflex over (t)} y ,sharewiseLSL( ŷ k·i+j ,j ))
where {circumflex over (t)} x is a first temporary variable, {circumflex over (t)} y is a second temporary variable, j is an index, k is the number of coefficients processed in parallel, i is an index value, sharewiseOR is a function that performs a bitwise OR on the shares of the inputs, and the function sharewiseLSL(z, l) performs a left shift of l bits of z on each share of z.
17. The data processing system of claim 16 , wherein instructions for combining the first bitsliced bits and the second bitsliced bits further comprises:
instructions for calculating for all values of j from 0 to k−1
ĉ =maskedAND( ĉ ,maskedAND( {circumflex over (t)} x ,{circumflex over (t)} y ))
where ĉ is the shared output indicating that the first polynomial would compress to a bitstream matching the bitstream representing the second compressed polynomial and the function maskedAND performs a masked bitwise AND of the inputs.
18. The data processing system of claim 17 , wherein instructions for combining the first bitsliced bits and the second bitsliced bits further comprises instructions for repeatedly ANDing the upper and lower bits of each the shares of ĉ together until a single bit per share results.
19. The data processing system of claim 17 , wherein instructions for combining the first bitsliced bits and the second bitsliced bits further comprises instructions for ANDing all of the bits of each of the shares of ĉ together until a single bit per share results.
20. The data processing system of claim 11 , wherein the modulus is a prime number.