38
T. Oder et al.
Algorithm 4 Masked binomial sampler
Input: α 1 , α 2 , β 1 , β 2 ∈ {0, 1} k with α 1 ⊕ α 2 = α and β 1 ⊕ β 2 = β
Output: out 1 , out 2 with (out 1 + out 2 ) mod q binomial distributed
1: i ← 0
2: out 1 ← 0
3: out 2 ← 0
4: for i < k do
5:
out 1 = out 1 + (α 1 [i] − β 1 [i])
6:
out 2 = out 2 + (α 2 [i] − β 2 [i])
7:
X
$
←[0, q − 1], Y
$
←[0, q − 1], Z
$
←[0, q − 1]
8:
α 1
= α 1 − X
9:
α 2
= α 2 − Y
10:
out 1 = out 1 − 2((((Z + XY ) + Xα 2
) + α 1
Y ) + α 1
α 2
)
11:
β 1
= β 1 − X
12:
β 2
= β 2 − Y
13:
out 2 = out 2 + 2((((Z + XY ) + Xβ 2
) + β 1
Y ) + β 1
β 2
)
14:
i ← i + 1
15: end for
As shown above, the distribution of every intermediate variable of Algorithm 4
is independent of the sensitive variables α and β. Therefore, it is not possible for
an attacker, which can probe one value, to derive sensitive information. The output
shares out 1 and out 2 with out = out 1 + out 2 are both uniformly distributed in
[0, q − 1].
Masked PRNG The PRNG is also a possible target for a chosen-ciphertext
adversary as noted before. Therefore, we used the already implemented masked
version of SHAKE-128 to generate random numbers with a fixed seed.
2.3.3 Masked Comparison
It is further necessary to protect all comparisons against a side-channel adversary,
since even ˜
c ∗
1 , c ∗
2 , and c ∗
4 can be used to distinguish ˜
r 2 . Since these values are shared,
it is necessary to compute a function of both shares to compare them to the public
and possibly adversary controlled values ˜
c 1 , c 2 , and c 4 . To prevent leakage of the
sensitive variables we introduce an additional hashing-step before the comparison.
Using ˜
c 1 as an example, we perform the comparison of ˜
c 1 with the shared ˜
c ∗
1 =
˜
c ∗∗
1 + ˜
c ∗∗∗
1 as provided in Algorithm 5. The correctness of our approach is easy to
verify as
H
(˜ c
∗
1 − ˜
c
∗∗∗
1 )
?
= H
(˜ c
∗∗
1 )
⇔ H
(˜ c
∗
1 − ˜
c 1 + ˜
c
∗∗
1 )
?
= H
(˜ c
∗∗
1 ).
T. Oder et al.
Algorithm 4 Masked binomial sampler
Input: α 1 , α 2 , β 1 , β 2 ∈ {0, 1} k with α 1 ⊕ α 2 = α and β 1 ⊕ β 2 = β
Output: out 1 , out 2 with (out 1 + out 2 ) mod q binomial distributed
1: i ← 0
2: out 1 ← 0
3: out 2 ← 0
4: for i < k do
5:
out 1 = out 1 + (α 1 [i] − β 1 [i])
6:
out 2 = out 2 + (α 2 [i] − β 2 [i])
7:
X
$
←[0, q − 1], Y
$
←[0, q − 1], Z
$
←[0, q − 1]
8:
α 1
= α 1 − X
9:
α 2
= α 2 − Y
10:
out 1 = out 1 − 2((((Z + XY ) + Xα 2
) + α 1
Y ) + α 1
α 2
)
11:
β 1
= β 1 − X
12:
β 2
= β 2 − Y
13:
out 2 = out 2 + 2((((Z + XY ) + Xβ 2
) + β 1
Y ) + β 1
β 2
)
14:
i ← i + 1
15: end for
As shown above, the distribution of every intermediate variable of Algorithm 4
is independent of the sensitive variables α and β. Therefore, it is not possible for
an attacker, which can probe one value, to derive sensitive information. The output
shares out 1 and out 2 with out = out 1 + out 2 are both uniformly distributed in
[0, q − 1].
Masked PRNG The PRNG is also a possible target for a chosen-ciphertext
adversary as noted before. Therefore, we used the already implemented masked
version of SHAKE-128 to generate random numbers with a fixed seed.
2.3.3 Masked Comparison
It is further necessary to protect all comparisons against a side-channel adversary,
since even ˜
c ∗
1 , c ∗
2 , and c ∗
4 can be used to distinguish ˜
r 2 . Since these values are shared,
it is necessary to compute a function of both shares to compare them to the public
and possibly adversary controlled values ˜
c 1 , c 2 , and c 4 . To prevent leakage of the
sensitive variables we introduce an additional hashing-step before the comparison.
Using ˜
c 1 as an example, we perform the comparison of ˜
c 1 with the shared ˜
c ∗
1 =
˜
c ∗∗
1 + ˜
c ∗∗∗
1 as provided in Algorithm 5. The correctness of our approach is easy to
verify as
H
(˜ c
∗
1 − ˜
c
∗∗∗
1 )
?
= H
(˜ c
∗∗
1 )
⇔ H
(˜ c
∗
1 − ˜
c 1 + ˜
c
∗∗
1 )
?
= H
(˜ c
∗∗
1 ).