US-12621150-B2 - Bit-rotation to prevent single-bit leakage in lattice based cryptography

Abstract

A system and method of carrying out a binary arithmetic operation in a cryptographic operation for lattice-based cryptography. The variables used in the binary arithmetic operation may have their bits randomly rotated to counter side channel attacks. An addition and multiplication operation on variables with rotated bits are disclosed.

Inventors

• Markus Schoenauer
• Melissa Azouaoui
• Olivier Bronchain
• Tobias Schneider

Assignees

• NXP B.V.

Dates

Publication Date

20260505

Application Date

20230531

Claims (19)

1. 1 . A data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for carrying out a binary arithmetic operation in a cryptographic operation for lattice-based cryptography in a processor, the instructions, when executed, cause the processor to perform a method comprising: performing a binary addition of a first binary value x 1 and a second binary value y 1 with ω bits, wherein bits of the first binary value x 1 are rotated by a first rotation value s 1 and bits of the second binary value y 1 are rotated by a second rotation value t 1 , comprising: rotating the bits of the first binary value x 1 by the second rotation value t 1 to produce a first rotated binary value x 1,rot ; rotating the bits of the second binary value y 1 by the first rotation value s 1 to produce a second rotated binary value y 1,rot ; calculating a third rotation value r 1 by adding the first rotation value s 1 and the second rotation value t 1 modulo ω; and performing a binary addition of the first rotated binary value x 1,rot and the second rotated binary value y 1,rot to produce a third rotated binary value z 1 , wherein the bits of the third rotated binary value z 1 are rotated by the third rotation value r 1 ; and performing a binary multiplication of a fourth binary value x 2 and a fifth binary value y 2 with ω bits, wherein the bits of the fourth binary value x 2 are rotated by a fourth rotation value s 2 and the bits of the fifth binary value y 2 are rotated by a fifth rotation value t 2 , comprising: initializing a sixth rotated value z 2 to zero; for each bit i of the fifth binary value y 2 that is equal to 1; calculating a sixth rotation value r 2 by subtracting the fifth rotation value t 2 from i where i is an index; rotating the bits of the fourth binary value x 2 by the sixth rotation value r 2 to produce a fourth rotated binary value x 2,rot ; and performing a binary addition of the fourth rotated binary value x 2,rot and the sixth rotated value z 2 to update the sixth rotated value z 2 , wherein the bits of the sixth rotated value z 2 are rotated by the fourth rotation value s 2 ; and wherein the rotating of the bits hides positions of the bits to prevent bit leakage attacks.
2. 2 . The data processing system of claim 1 , wherein ω is a power of two and wherein adding the first rotation value s 1 and the second rotation value t 1 modulo ω includes calculating ( s 1 + t 1 ) ∧ ( ω - 1 ) .
3. 3 . The data processing system of claim 1 , wherein ω has a value greater than k where k is a number of bits in x 1 and y 1 and wherein a zero is adjacent the most significant bits of x 1 and y 1 .
4. 4 . The data processing system of claim 3 , wherein a portion of the bits between the zero adjacent the most significant bits of x 1 and y 1 and a least significant bits of x 1 and y 1 are set to random values.
5. 5 . The data processing system of claim 1 , wherein ω has a value greater than 2k where k is a number of bits in x 2 and y 2 and wherein k zeros are adjacent the most significant bits of x 2 and y 2 .
6. 6 . The data processing system of claim 5 , wherein a portion of the bits between the k zeros adjacent the most significant bits of x 2 and y 2 and a least significant bits of x 2 and y 2 are set to random values.
7. 7 . The data processing system of claim 1 , further comprising randomly generating s 1 , t 1 , s 2 , and t 2 .
8. 8 . A data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for carrying out a binary arithmetic operation in a cryptographic operation for lattice-based cryptography in a processor, the instructions, when executed, cause the processor to perform a method comprising: performing a binary addition of a first binary value x 1 and a second binary value y 1 with ω bits, wherein bits of the first binary value x 1 are rotated by a first rotation value s 1 and bits of the second binary value y 1 are rotated by a second rotation value t 1 , comprising: calculating a third rotation value r 1 by subtracting the second rotation value t 1 from the first rotation value s 1 modulo ω; rotating the bits of the second binary value y 1 by the third rotation value r 1 to produce a second rotated binary value y 1,rot ; and performing a binary addition of the first binary value x 1 and the second rotated binary value y 1,rot to produce a third rotated binary value z 1 , wherein the bits of the third rotated binary value z 1 are rotated by the first rotation value s 1 ; and performing a binary multiplication of a fourth binary value x 2 and a fifth binary value y 2 with ω bits, wherein the bits of the fourth binary value x 2 are rotated by a fourth rotation value s 2 , comprising: initializing a sixth rotated value z 2 to zero; for each bit i of the fifth binary value y 2 that is equal to 1: rotating the bits of the fourth binary value x 2 by i to produce a fourth rotated binary value x 2,rot , where i is an index; and performing a binary addition of the fourth rotated binary value x 2,rot and the sixth rotated value z 2 to update the sixth rotated value z 2 , wherein the bits of the sixth rotated value z 2 are rotated by the fourth rotation value s 2 ; and wherein the rotating of the bits hides positions of the bits to prevent bit leakage attacks.
9. 9 . The data processing system of claim 8 , wherein ω is a power of two and wherein adding the first rotation value s 1 and the second rotation value t 1 modulo ω includes calculating ( s 1 + t 1 ) ∧ ( ω - 1 ) .
10. 10 . The data processing system of claim 8 , wherein ω has a value greater than k where k is a number of bits in x 1 and y 1 and wherein a zero is adjacent the most significant bit of x 1 .
11. 11 . The data processing system of claim 10 , wherein a portion of the bits between the k zeros adjacent the most significant bits of x 1 and y 1 and a least significant bits of x 1 and y 1 are set to random values.
12. 12 . The data processing system of claim 1 , further comprising randomly generating s 1 , and s 2 .
13. 13 . A method of carrying out a binary arithmetic operation in a cryptographic operation for lattice-based cryptography in a processor, the method comprising: performing, by the processor, a binary addition of a first binary value x 1 and a second binary value y 1 with ω bits, wherein bits of the first binary value x 1 are rotated by a first rotation value s 1 and bits of the second binary value y 1 are rotated by a second rotation value t 1 , comprising: rotating, by the processor, the bits of the first binary value x 1 by the second rotation value t 1 to produce a first rotated binary value x 1,rot ; rotating, by the processor, the bits of the second binary value y 1 by the first rotation value s 1 to produce a second rotated binary value y 1,rot ; calculating, by the processor, a third rotation value r 1 by adding the first rotation value s 1 and the second rotation value t 1 modulo ω; and performing, by the processor, a binary addition of the first rotated binary value x 1,rot and the second rotated binary value y 1 , rot to produce a third rotated binary value z 1 , wherein the bits of the third rotated binary value z 1 are rotated by the third rotation value r 1 ; and performing, by the processor, a binary multiplication of a fourth binary value x 2 and a fifth binary value y 2 with ω bits, wherein the bits of the fourth binary value x 2 are rotated by a fourth rotation value s 2 and the bits of the fifth binary value y 2 are rotated by a fifth rotation value t 2 , comprising: initializing, by the processor, a sixth rotated value z 2 to zero that is equal to 1; for each bit i of the fifth binary value y 2 : calculating, by the processor, a sixth rotation value r 2 by subtracting the fifth rotation value t 2 from i where i is an index; rotating, by the processor, the bits of the fourth binary value x 2 by the sixth rotation value r 2 to produce a fourth rotated binary value x 2,rot , and performing, by the processor, a binary addition of the fourth rotated binary value x 2,rot and the sixth rotated value z 2 to update the sixth rotated value z 2 , wherein the bits of the sixth rotated value z 2 are rotated by the fourth rotation value s 2 ; and wherein the rotating of the bits hides positions of the bits to prevent bit leakage attacks.
14. 14 . The method of claim 13 , wherein ω is a power of two and wherein adding the first rotation value s 1 and the second rotation value t 1 modulo ω includes calculating (s 1 +t 1 ){circumflex over ( )}(ω−1).
15. 15 . The method of claim 13 , wherein ω has a value greater than k where k is a number of bits in x 1 and y 1 and wherein a zero is adjacent the most significant bits of x 1 and y 1 .
16. 16 . The method of claim 15 , wherein a portion of the bits between the zero adjacent the most significant bits of x 1 and y 1 and a least significant bits of x 1 and y 1 are set to random values.
17. 17 . The method of claim 13 , wherein ω has a value greater than 2k where k is a number of bits in x 2 and y 2 and wherein k zeros are adjacent the most significant bits of x 2 and y 2 .
18. 18 . The method of claim 17 , wherein a portion of the bits between the k zeros adjacent the most significant bits of x 2 and y 2 and a least significant bits of x 2 and y 2 are set to random values.
19. 19 . The method of claim 13 , further comprising randomly generating s 1 , t 1 , s 2 , and t 2 .

Description

FIELD OF THE DISCLOSURE Various exemplary embodiments disclosed herein relate to bit-rotation to prevent single-bit leakage in lattice based cryptography. BACKGROUND Recent significant advances in quantum computing have accelerated the research into post-quantum cryptography schemes: cryptographic algorithms which run on classical computers but are still secure even when faced with an adversary with access to a quantum computer. This demand is driven by interest from standardization bodies, such as the call for proposals for new public-key cryptography standards by the National Institute of Standards and Technology (NIST). On Jul. 5, 2022, NIST selected two primary algorithms to standardize: CRYSTALS-Kyber for key establishment and CRYSTALS-Dilithium for digital signatures. In addition, NIST also chose two further signature schemes (FALCON and SPHINCS+) for standardization. While the latter are expected to have specialized applications (e.g., FALCON for servers with floating point support), CRYSTALS-Dilithium (which is referred to as Dilithium in the rest of this disclosure) is expected to be the general replacement for elliptic curve cryptography digital signatures (e.g., Elliptic Curve Digital Signature Algorithm (ECDSA)), in particular for embedded use cases. SUMMARY A summary of various exemplary embodiments is presented below. Further various embodiments relate to a data processing system including instructions embodied in a non-transitory computer readable medium, the instructions for carrying out a binary arithmetic operation in a cryptographic operation for lattice-based cryptography in a processor, the instructions, including: performing a binary addition of a first binary value x1 and a second binary value y1 with ω bits, wherein bits of the first binary value x1 are rotated by a first rotation value s1 and bits of the second binary value y1 are rotated by a second rotation value t1, including: rotating the bits of the first binary value x1 by the second rotation value t1 to produce a first rotated binary value x1,rot; rotating the bits of the second binary value y1 by the first rotation value s1 to produce a second rotated binary value y1,rot; calculating a third rotation value r1 by adding the first rotation value s1 and the second rotation value t1 modulo ω; and performing a binary addition of the first rotated binary value x1,rot and the second rotated binary value y1,rot to produce a third rotated binary value z1, wherein the bits of the third rotated binary value z1 are rotated by the third rotation value r1; and performing a binary multiplication of a fourth binary value x2 and a fifth binary value y2 with ω bits, wherein the bits of the fourth binary value x2 are rotated by a fourth rotation value s2 and the bits of the fifth binary value y2 are rotated by a fifth rotation value t2, including: initializing a sixth rotated value z2 to zero; for each bit i of the fifth binary value y2 that is equal to 1; calculating a sixth rotation value r2 by subtracting the fifth rotation value t2 from i where i is an index; rotating the bits of the fourth binary value x2 by the sixth rotation value r2 to produce a fourth rotated binary value x2,rot; and performing a binary addition of the fourth rotated binary value x2,rot and the sixth rotated value z2 to update the sixth rotated value z2, wherein the bits of the sixth rotated value z2 are rotated by the fourth rotation value s2. Various embodiments are described, wherein ω is a power of two and wherein adding the first rotation value s1 and the second rotation value t1 modulo ω includes calculating (s1+t1)∧(ω−1). Various embodiments are described, wherein a has a value greater than k where k is a number of bits in x1 and y1 and wherein a zero is adjacent the most significant bits of x1 and y1. Various embodiments are described, wherein a portion of the bits between the zero adjacent the most significant bits of x1 and y1 and a least significant bits of x1 and y1 are set to random values. Various embodiments are described, wherein a has a value greater than 2k where k is a number of bits in x2 and y2 and wherein k zeros are adjacent the most significant bits of x2 and y2. Various embodiments are described, wherein a portion of the bits between the k zeros adjacent the most significant bits of x2 and y2 and a least significant bits of x2 and y2 are set to random values. Various embodiments are described, further including randomly generating s1, t1, s2, and t2. Further various embodiments relate to a data processing system including instructions embodied in a non-transitory computer readable medium, the instructions for carrying out a binary arithmetic operation in a cryptographic operation for lattice-based cryptography in a processor, the instructions, including: performing a binary addition of a first binary value x1 and a second binary value y1 with ω bits, wherein bits of the first binary value x1 are rotated by a first rotation value s1 and bits of