26
T. Oder et al.
ring-LWE. A uniformly random polynomial is sampled by SampleUniformPoly()
and we decided to include ˜
a in the public key for simplification. Note that it would
be possible to generate the secret key or ˜
a from a seed of 256-bits (or to choose ˜
a
as a global constant; see [3] for a discussion). Additionally, the secret key ˜
r 2 could
be generated from a seed or stored in normal domain and efficiently encoded as it is
not distributed uniformly but roughly follows a discrete Gaussian (see [39, 49]).
However, for comparability and maintainability, we leave these straightforward
optimizations and trade-offs as future work as they are not essential for our use-case.
For successful decryption knowledge of the secret key r 2 is required. Otherwise, the
large term ae 1 r 2 cannot be eliminated when computing c 1 r 2 +c 2 . An encoding of the
n-bit message m is necessary as some small noise (i.e., e = e 1 r 1 + e 2 r 2 + e 3 ) is still
present after calculating c 1 r 2 + c 2 and would prohibit the retrieval of the message
after decryption. This also shows why the noise distribution is chosen to be rather
small—a too big noise level would make reliable decoding impossible. Thus, to
allow the extraction of the message despite the noise during decryption RLWE.CPA
requires (as a minimum) a simple message encoding. We replace the standard
threshold encoding and decoding functions with a variant that encodes one message
bit into four coefficients [38]. The encoding function used in RLWE.CPA enc
NTT
is defined as Encode(m ∈ {0, 1} n/4 ) =
n−1
i=0 m[[i/4] ·
q
2 · x i (where m[i]
denotes the i-th bit of m). The decoding function used in RLWE.CPA dec
NTT takes
four coefficients z 1 , z 2 , z 3 , z 4 ∈ [−−q/2, q/2] as input that carry one bit of the
message. Decode(z 1 , z 2 , z 3 , z 4 ) is defined to return 1 if |z 1 | + |z 2 | + |z 3 | + |z 4 | < q
and 0 otherwise.
2.2.3 Side-Channel Attacks and Countermeasures
In this section we review side-channel attacks and countermeasures.
Timing Attacks When implementing cryptographic algorithms, the developer has
to make sure that the execution time is independent of the secret data that is
processed. Otherwise an attacker might be able to exploit the information about the
execution time. Such attacks should not only be considered for embedded devices
for which the attacker has physical access to, but also remote timing attacks are
a threat that must be considered as shown by Brumley and Boneh [14]. Timing
information can be leaked by conditional branches, instructions with non-constant
execution time, and memory accesses that trigger cache hits or misses [8].
Differential Power Analysis Introduced in 1998 by Kocher et al. [31], DPA needs
many power traces and one analyzes the set of traces with statistical methods. When
performing DPA an attacker does not attack the whole key at once, but only a part,
e.g., one byte. A DPA is divided in an online phase and an offline phase. During
the online phase, the attacker runs a vast amount of executions of the algorithm
to be attacked with different inputs and measures the power consumption of the
T. Oder et al.
ring-LWE. A uniformly random polynomial is sampled by SampleUniformPoly()
and we decided to include ˜
a in the public key for simplification. Note that it would
be possible to generate the secret key or ˜
a from a seed of 256-bits (or to choose ˜
a
as a global constant; see [3] for a discussion). Additionally, the secret key ˜
r 2 could
be generated from a seed or stored in normal domain and efficiently encoded as it is
not distributed uniformly but roughly follows a discrete Gaussian (see [39, 49]).
However, for comparability and maintainability, we leave these straightforward
optimizations and trade-offs as future work as they are not essential for our use-case.
For successful decryption knowledge of the secret key r 2 is required. Otherwise, the
large term ae 1 r 2 cannot be eliminated when computing c 1 r 2 +c 2 . An encoding of the
n-bit message m is necessary as some small noise (i.e., e = e 1 r 1 + e 2 r 2 + e 3 ) is still
present after calculating c 1 r 2 + c 2 and would prohibit the retrieval of the message
after decryption. This also shows why the noise distribution is chosen to be rather
small—a too big noise level would make reliable decoding impossible. Thus, to
allow the extraction of the message despite the noise during decryption RLWE.CPA
requires (as a minimum) a simple message encoding. We replace the standard
threshold encoding and decoding functions with a variant that encodes one message
bit into four coefficients [38]. The encoding function used in RLWE.CPA enc
NTT
is defined as Encode(m ∈ {0, 1} n/4 ) =
n−1
i=0 m[[i/4] ·
q
2 · x i (where m[i]
denotes the i-th bit of m). The decoding function used in RLWE.CPA dec
NTT takes
four coefficients z 1 , z 2 , z 3 , z 4 ∈ [−−q/2, q/2] as input that carry one bit of the
message. Decode(z 1 , z 2 , z 3 , z 4 ) is defined to return 1 if |z 1 | + |z 2 | + |z 3 | + |z 4 | < q
and 0 otherwise.
2.2.3 Side-Channel Attacks and Countermeasures
In this section we review side-channel attacks and countermeasures.
Timing Attacks When implementing cryptographic algorithms, the developer has
to make sure that the execution time is independent of the secret data that is
processed. Otherwise an attacker might be able to exploit the information about the
execution time. Such attacks should not only be considered for embedded devices
for which the attacker has physical access to, but also remote timing attacks are
a threat that must be considered as shown by Brumley and Boneh [14]. Timing
information can be leaked by conditional branches, instructions with non-constant
execution time, and memory accesses that trigger cache hits or misses [8].
Differential Power Analysis Introduced in 1998 by Kocher et al. [31], DPA needs
many power traces and one analyzes the set of traces with statistical methods. When
performing DPA an attacker does not attack the whole key at once, but only a part,
e.g., one byte. A DPA is divided in an online phase and an offline phase. During
the online phase, the attacker runs a vast amount of executions of the algorithm
to be attacked with different inputs and measures the power consumption of the