US 2024/0405986 A1Published application

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

AssigneeNXP B.V.

InventorsMarkus Schoenauer, Melissa Azouaoui, Olivier Bronchain, Tobias Schneider

Life of this patent

Estimating the term…

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.

Claims19

Dependent claims

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, comprising:

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 xi are rotated by a first rotation value s1 and bits of the second binary value y1 are rotated by a second rotation value t1, comprising:
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 zi 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, comprising:
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.

11 more elements

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, comprising:
calculating a third rotation value r1 by subtracting the second rotation value t1 from the first rotation value s1 modulo ω;
rotating the bits of the second binary value y1 by the third rotation value r1 to produce a second rotated binary value y1,rot;
and
performing a binary addition of the first binary value x1 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 first rotation value s1;
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, comprising:
initializing a sixth rotated value z2 to zero;
for each bit i of the fifth binary value y2 that is equal to 1:
rotating the bits of the fourth binary value x2 by i to produce a fourth rotated binary value x2,rot, where i is an index;
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.

9 more elements

A method of carrying out a binary arithmetic operation in a cryptographic operation for lattice-based cryptography in a processor, comprising:

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, comprising:
rotating the bits of the first binary value xi 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 zi 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, comprising:
initializing a sixth rotated value z2 to zero that is equal to 1;
for each bit i of the fifth binary value y2:
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.

11 more elements

Dependencies are inferred from the claim text.

patentgrep

Loading patent…

Abstract

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 xi are rotated by a first rotation value s1 and bits of the second binary value y1 are rotated by a second rotation value t1, comprising:
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 zi 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, comprising:
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.

11 more elements