2 Secure Implementation of Lattice-Based Encryption Schemes
31
if bits ≥ log 2 (2q). Therefore, we have MSB(z 1 + y 2 mod 2 bits ) ⊕ 1 = carry. Then
we use the A2B algorithm by Debraize [21], so that we can apply MSB to each of
the output shares separately. The only remaining step now is to subtract q · carry
from (y 1 , y 2 ). This is achieved using the shares k 1 ⊕ k 2 = carry and the relation
k 1 ⊕ k 2 = k 1 + k 2 − 2k 1 k 2 as follows:
y 1 − (k 1 ⊕ k 2 )q = y1 − k 1 q − k 2 q + 2k 1 k 2 q
= y 1 − k 1 q − k 2 q + 2(k
1 + k
1 )(k
2 + k
2 )q
= y 1 − k 1 q − k 2 q + 2k
1 k
2 q + 2k
1 k
2 q + 2k
1 k
2 q + 2k
1 k
2 q.
Since (k 1 , k 2 ) is not completely independent of (y 1 , y 2 ) for some A2B, we include
a random value r in the computation of the sum in Algorithm 1.
Although the output (y 1 , y 2 ) of TransformPower2 fulfills the desired property of y 1 + y 2 mod 2 15 = x and could be easily transformed to (y
1 , y
2 ) with
y 1 ⊕ y 2 = x, this is not sufficient to recover m. Some additional steps are necessary
to perform a successful decoding. These steps are depicted in Fig. 2.3. Each circle
shows the distributions of the unshared values for a specific value of m (m = 0 is
thick, m = 1 is dashed) after each step, e.g., the first circle in the upper-left corner
shows the distributions for the original x where the values of x for m = 0 (resp.
m = 1) are grouped around the mean of zero (resp.
q
2 ). In the first step, we subtract
q
4 from (x 1 , x 2 ). This way no distribution is spread over the modulo border, which
would cause problems for the transformation to 15 bits. After the transformation
is done, we subtract
q
2 from the result to create the following relation for the new
shares (y 1 , y 2 ):
Algorithm 1 TransformPower2
Input: x 1 , x 2 , bits
Output: y 1 , y 2
1: y 1
$
←{0, 1} bits
2: y 2 ← x 1 − y 1
3: y 2 ← y 2 + x2
4: z 1 ← y 1 − q
5: [z 1 , z 2 ] ← A2B(z 1 , y 2 )
6: k 1 ← MSB(z 1 ) ⊕ 1
7: k 2 ← MSB(z 2 )
8: k
1
$
←{0, 1} bits
9: k
1 ← k 1 − k
1
10: k
2
$
←{0, 1} bits
11: k
2 ← k 2 − k
2
12: r
$
←{0, 1} bits
13: y 1 = (((((((r + y 1 ) − k 1 q) − k 2 q) + 2k
1 k
2 q) + 2k
1 k
2 q) + 2k
1 k
2 q) + 2k
1 k
2 q)
14: y 2 = y 2 − r
31
if bits ≥ log 2 (2q). Therefore, we have MSB(z 1 + y 2 mod 2 bits ) ⊕ 1 = carry. Then
we use the A2B algorithm by Debraize [21], so that we can apply MSB to each of
the output shares separately. The only remaining step now is to subtract q · carry
from (y 1 , y 2 ). This is achieved using the shares k 1 ⊕ k 2 = carry and the relation
k 1 ⊕ k 2 = k 1 + k 2 − 2k 1 k 2 as follows:
y 1 − (k 1 ⊕ k 2 )q = y1 − k 1 q − k 2 q + 2k 1 k 2 q
= y 1 − k 1 q − k 2 q + 2(k
1 + k
1 )(k
2 + k
2 )q
= y 1 − k 1 q − k 2 q + 2k
1 k
2 q + 2k
1 k
2 q + 2k
1 k
2 q + 2k
1 k
2 q.
Since (k 1 , k 2 ) is not completely independent of (y 1 , y 2 ) for some A2B, we include
a random value r in the computation of the sum in Algorithm 1.
Although the output (y 1 , y 2 ) of TransformPower2 fulfills the desired property of y 1 + y 2 mod 2 15 = x and could be easily transformed to (y
1 , y
2 ) with
y 1 ⊕ y 2 = x, this is not sufficient to recover m. Some additional steps are necessary
to perform a successful decoding. These steps are depicted in Fig. 2.3. Each circle
shows the distributions of the unshared values for a specific value of m (m = 0 is
thick, m = 1 is dashed) after each step, e.g., the first circle in the upper-left corner
shows the distributions for the original x where the values of x for m = 0 (resp.
m = 1) are grouped around the mean of zero (resp.
q
2 ). In the first step, we subtract
q
4 from (x 1 , x 2 ). This way no distribution is spread over the modulo border, which
would cause problems for the transformation to 15 bits. After the transformation
is done, we subtract
q
2 from the result to create the following relation for the new
shares (y 1 , y 2 ):
Algorithm 1 TransformPower2
Input: x 1 , x 2 , bits
Output: y 1 , y 2
1: y 1
$
←{0, 1} bits
2: y 2 ← x 1 − y 1
3: y 2 ← y 2 + x2
4: z 1 ← y 1 − q
5: [z 1 , z 2 ] ← A2B(z 1 , y 2 )
6: k 1 ← MSB(z 1 ) ⊕ 1
7: k 2 ← MSB(z 2 )
8: k
1
$
←{0, 1} bits
9: k
1 ← k 1 − k
1
10: k
2
$
←{0, 1} bits
11: k
2 ← k 2 − k
2
12: r
$
←{0, 1} bits
13: y 1 = (((((((r + y 1 ) − k 1 q) − k 2 q) + 2k
1 k
2 q) + 2k
1 k
2 q) + 2k
1 k
2 q) + 2k
1 k
2 q)
14: y 2 = y 2 − r