30
T. Oder et al.
linearity of the operations, it is easily possible to perform these computations
on each share separately. However, this approach does not work for the final
Decode. In [43, 46], the authors proposed to use a rather complex decoder for
the arithmetically masked shares instead. To increase efficiency, we rely on a
new approach MDecode which first transforms the arithmetic shares to Boolean
shares and then performs the decoding. With this approach, we can avoid the
costly arithmetically masked decoder and the additional error of the scheme
from [45].
Correctness To show the correctness of this scheme, we first denote the outputs
of the INTT operations as z and z with z = z + z . Showing that this relation
holds is trivial, since the INTT is linear and the scheme is identical to [43, 46] up
to this point. Instead, we show that MDecode(z , z ) = (m
cpa , m
cpa ) with m cpa =
m
cpa ⊕ m
cpa . To this end, we start by describing how an arithmetic-to-Boolean
(A2B) transformation [17, 19, 21, 25, 56] can be used to easily decode one shared
coefficient of z. Then we demonstrate a solution to efficiently adjust the approach
to our encoding scheme, i.e., four coefficients of z for one bit of m cpa .
In our basic example, we assume the arithmetic shares (x 1 , x 2 ) with
x 1 + x 2 (mod q) = x = m · ·
q
2
+ e
for some error e and want to recover (m 1 , m 2 ) with m 1 ⊕ m 2 = m without leaking
sensitive information. Our solution to this problem is based on the observation that a
sharing of the most significant bit can be easily extracted from Boolean shares, while
it is hard for arithmetic shares. However, we cannot straightforwardly apply an A2B
transformation to (x 1 , x 2 ) as all A2B algorithms work with arithmetic shares which
are computed modulo a power of two.
Therefore, we propose to first transform (x 1 , x 2 ) to the shares (y 1 , y 2 ) with y 1 +
y 2 mod 2 15 = x given that 2 15 is the second-next-larger power of two for q =
12,289. This process is shown in Algorithm 1 where every operation is done mod
2 bits , A2B denotes an arithmetic-to-Boolean transformation, and MSB returns the
most significant bit of the input. In the algorithm, we first sample a random 15-bit
value y 1 and reshare the input shares mod 2 bits . However, in some cases this does
not result in a correct sharing as in Line 3 the shares are
y 1 + y 2 mod 2
bits
= x + q · carry,
where the carry is set if x 1 + x 2 ≥ q. To adjust this, we compute carry and
subtract q · carry from (y 1 , y 2 ) in a secured fashion. First, we compute z 1 ← y 1 −
q mod 2 bits . By doing this, we create the following relation for the most significant
bit of z 1 + y 2 mod 2 bits :
MSB(z 1 + y 2 mod 2
bits ) =
0 x 1 + x 2 ≥ q
1 x 1 + x 2 < q
,
T. Oder et al.
linearity of the operations, it is easily possible to perform these computations
on each share separately. However, this approach does not work for the final
Decode. In [43, 46], the authors proposed to use a rather complex decoder for
the arithmetically masked shares instead. To increase efficiency, we rely on a
new approach MDecode which first transforms the arithmetic shares to Boolean
shares and then performs the decoding. With this approach, we can avoid the
costly arithmetically masked decoder and the additional error of the scheme
from [45].
Correctness To show the correctness of this scheme, we first denote the outputs
of the INTT operations as z and z with z = z + z . Showing that this relation
holds is trivial, since the INTT is linear and the scheme is identical to [43, 46] up
to this point. Instead, we show that MDecode(z , z ) = (m
cpa , m
cpa ) with m cpa =
m
cpa ⊕ m
cpa . To this end, we start by describing how an arithmetic-to-Boolean
(A2B) transformation [17, 19, 21, 25, 56] can be used to easily decode one shared
coefficient of z. Then we demonstrate a solution to efficiently adjust the approach
to our encoding scheme, i.e., four coefficients of z for one bit of m cpa .
In our basic example, we assume the arithmetic shares (x 1 , x 2 ) with
x 1 + x 2 (mod q) = x = m · ·
q
2
+ e
for some error e and want to recover (m 1 , m 2 ) with m 1 ⊕ m 2 = m without leaking
sensitive information. Our solution to this problem is based on the observation that a
sharing of the most significant bit can be easily extracted from Boolean shares, while
it is hard for arithmetic shares. However, we cannot straightforwardly apply an A2B
transformation to (x 1 , x 2 ) as all A2B algorithms work with arithmetic shares which
are computed modulo a power of two.
Therefore, we propose to first transform (x 1 , x 2 ) to the shares (y 1 , y 2 ) with y 1 +
y 2 mod 2 15 = x given that 2 15 is the second-next-larger power of two for q =
12,289. This process is shown in Algorithm 1 where every operation is done mod
2 bits , A2B denotes an arithmetic-to-Boolean transformation, and MSB returns the
most significant bit of the input. In the algorithm, we first sample a random 15-bit
value y 1 and reshare the input shares mod 2 bits . However, in some cases this does
not result in a correct sharing as in Line 3 the shares are
y 1 + y 2 mod 2
bits
= x + q · carry,
where the carry is set if x 1 + x 2 ≥ q. To adjust this, we compute carry and
subtract q · carry from (y 1 , y 2 ) in a secured fashion. First, we compute z 1 ← y 1 −
q mod 2 bits . By doing this, we create the following relation for the most significant
bit of z 1 + y 2 mod 2 bits :
MSB(z 1 + y 2 mod 2
bits ) =
0 x 1 + x 2 ≥ q
1 x 1 + x 2 < q
,