22
T. Oder et al.
has therefore caused a massive rise in research activities in the area of post-quantum
cryptography (PQC) in the last couple of years. These research efforts culminated
in the NIST requesting candidates for quantum-secure cryptographic algorithms in
December 2016 [36] and releasing the list of submissions in December 2017.
The KEMs submitted to NIST base their security on entirely different security
assumptions that (by the current state of knowledge) cannot be attacked by quantum
algorithms. The majority of submitted KEMs is either based on linear codes,
multivariate quadratics, or lattices. Lattice-based schemes constitute the largest
group with 20 submitted KEMs in the first round of the standardization process
and still nine schemes in the second round. There are a couple of reasons for the
popularity of lattice-based cryptosystems. They offer reasonable parameter sizes,
high efficiency, and flexibility regarding their potential applications. The most
commonly used mathematical problem to build lattice-based KEMs is the learning
with errors (LWE) problem or its variant ring-LWE that works with polynomial
rings over finite fields and leads to even more efficient parameters.
With the advent of a Smart World and the Internet of Things, billions of devices
are becoming connected, exchanging massive amounts of data, often combined with
high demand on data security. Embedded applications of cryptography are therefore
of major relevance for today’s world. At the same time, these embedded targets
that require the application of security solutions often have access to only limited
resources. Implementations on embedded and constrained devices therefore have
the requirement to be efficient in terms of performance and memory. Furthermore,
in many embedded use cases an attacker has physical access to a device that contains
a secret key. This physical access can then be used to extract information about
intermediate values that appear during the execution of a cryptographic operation
by observing physical properties of the device. For instance, the dynamic power
consumption of the device can leak sensitive information about the secret key that
is used in the cryptographic operation. By collecting a large number of power traces
and analyzing them by statistical means, an attacker might be able to break a KEM
even if it is mathematically sound. Implementations targeting embedded devices
therefore also have to take into account side-channel attacks and apply appropriate
countermeasures.
Because of the high efficiency, schemes based on ring-LWE can be easily implemented on embedded devices as shown by many publications, like [1, 27, 29, 30, 50].
Most of the aforementioned implementations are only protected against timing
side-channels, i.e., the execution time of the implementation is independent from
any secret data. In this chapter, we show how to further on protect KEMs based
on ring-LWE against power analysis. To do so, we utilize masking, a common
countermeasures against power attacks. Masking schemes for ring-LWE KEMs
have already been investigated by Reparaz, Roy, Vercauteren, and Verbauwhede
in [43, 46] and Reparaz, de Clercq, Roy, Vercauteren, and Verbauwhede in [45].
Our solution significantly improves the proposed masking schemes in terms of
performance and failure rate and is also provably secure. To show the practicality
of our approach, we also present an implementation on an ARM Cortex-M4 and
conduct practical measurements that support our claims.
T. Oder et al.
has therefore caused a massive rise in research activities in the area of post-quantum
cryptography (PQC) in the last couple of years. These research efforts culminated
in the NIST requesting candidates for quantum-secure cryptographic algorithms in
December 2016 [36] and releasing the list of submissions in December 2017.
The KEMs submitted to NIST base their security on entirely different security
assumptions that (by the current state of knowledge) cannot be attacked by quantum
algorithms. The majority of submitted KEMs is either based on linear codes,
multivariate quadratics, or lattices. Lattice-based schemes constitute the largest
group with 20 submitted KEMs in the first round of the standardization process
and still nine schemes in the second round. There are a couple of reasons for the
popularity of lattice-based cryptosystems. They offer reasonable parameter sizes,
high efficiency, and flexibility regarding their potential applications. The most
commonly used mathematical problem to build lattice-based KEMs is the learning
with errors (LWE) problem or its variant ring-LWE that works with polynomial
rings over finite fields and leads to even more efficient parameters.
With the advent of a Smart World and the Internet of Things, billions of devices
are becoming connected, exchanging massive amounts of data, often combined with
high demand on data security. Embedded applications of cryptography are therefore
of major relevance for today’s world. At the same time, these embedded targets
that require the application of security solutions often have access to only limited
resources. Implementations on embedded and constrained devices therefore have
the requirement to be efficient in terms of performance and memory. Furthermore,
in many embedded use cases an attacker has physical access to a device that contains
a secret key. This physical access can then be used to extract information about
intermediate values that appear during the execution of a cryptographic operation
by observing physical properties of the device. For instance, the dynamic power
consumption of the device can leak sensitive information about the secret key that
is used in the cryptographic operation. By collecting a large number of power traces
and analyzing them by statistical means, an attacker might be able to break a KEM
even if it is mathematically sound. Implementations targeting embedded devices
therefore also have to take into account side-channel attacks and apply appropriate
countermeasures.
Because of the high efficiency, schemes based on ring-LWE can be easily implemented on embedded devices as shown by many publications, like [1, 27, 29, 30, 50].
Most of the aforementioned implementations are only protected against timing
side-channels, i.e., the execution time of the implementation is independent from
any secret data. In this chapter, we show how to further on protect KEMs based
on ring-LWE against power analysis. To do so, we utilize masking, a common
countermeasures against power attacks. Masking schemes for ring-LWE KEMs
have already been investigated by Reparaz, Roy, Vercauteren, and Verbauwhede
in [43, 46] and Reparaz, de Clercq, Roy, Vercauteren, and Verbauwhede in [45].
Our solution significantly improves the proposed masking schemes in terms of
performance and failure rate and is also provably secure. To show the practicality
of our approach, we also present an implementation on an ARM Cortex-M4 and
conduct practical measurements that support our claims.