2 Secure Implementation of Lattice-Based Encryption Schemes
23
2.2 Background
2.2.1 Notation
Unless explicitly stated, we denote addition (resp. subtraction) modulo q with +
(resp. −). We denote multiplication by · and point-wise multiplication by ◦. We
use ⊕ as operator for addition modulo 2. Polynomials in R q = Z q [x]/x n + 1
are labeled by bold lowercase letters. Polynomials in NTT domain are additionally
marked with a tilde (˜ a). When we access a single bit of a bit vector, we use an index
in square brackets to identify the respective bit.
2.2.2 Cryptographic Background
In the following, we introduce the necessary cryptographic concepts.
Key Encapsulation Mechanisms Encrypted communication can either be conducted using symmetric or asymmetric cryptography. In symmetric cryptography
both parties share the same secret key that they use to encrypt their communication
with. In asymmetric cryptography on the other hand, each party has a pair of keys
consisting of one private key that is only known to the owner of the key and one
public key that is also known to potential communication partners. Symmetric
cryptography is much more efficient and therefore the primary choice to realize
encrypted communication. The major drawback however is that both parties have
to agree on a secret key in such a way that an eavesdropper does not get any
information about that key. Therefore asymmetric cryptography is usually used to
agree on a shared, symmetric key and all further communication is then encrypted
symmetrically. The asymmetric primitives used to exchange a symmetric key are
called Key Encapsulation Mechanisms (KEMs).
Hash Functions A cryptographic hash function is a one-way function that maps
data of arbitrary size to data of fixed size. The most important properties of
cryptographic hash functions are pre-image resistance, second pre-image resistance,
and collision resistance. Pre-image resistance describes the one-way property of a
hash functions, i.e., the difficulty to find an input that if hashed matches a given
output. Second pre-image resistance on the other hand means that given a certain
input, it is difficult to find another (different) input that generates the same hash
value. Collision resistance means that it is hard to find any pair of different inputs
that generate the same hash value. If the output is not fixed but variable, the
algorithm is called an extendable-output function (XOF). Hash functions are also
often used to instantiate random oracles in cryptographic schemes.
Security Model The security of encryption schemes (or KEMs) can be analyzed
regarding different attacker models. The simplest attacker model is to assume
that the attacker has access to some plaintext–ciphertext pair and tries to deduce
23
2.2 Background
2.2.1 Notation
Unless explicitly stated, we denote addition (resp. subtraction) modulo q with +
(resp. −). We denote multiplication by · and point-wise multiplication by ◦. We
use ⊕ as operator for addition modulo 2. Polynomials in R q = Z q [x]/x n + 1
are labeled by bold lowercase letters. Polynomials in NTT domain are additionally
marked with a tilde (˜ a). When we access a single bit of a bit vector, we use an index
in square brackets to identify the respective bit.
2.2.2 Cryptographic Background
In the following, we introduce the necessary cryptographic concepts.
Key Encapsulation Mechanisms Encrypted communication can either be conducted using symmetric or asymmetric cryptography. In symmetric cryptography
both parties share the same secret key that they use to encrypt their communication
with. In asymmetric cryptography on the other hand, each party has a pair of keys
consisting of one private key that is only known to the owner of the key and one
public key that is also known to potential communication partners. Symmetric
cryptography is much more efficient and therefore the primary choice to realize
encrypted communication. The major drawback however is that both parties have
to agree on a secret key in such a way that an eavesdropper does not get any
information about that key. Therefore asymmetric cryptography is usually used to
agree on a shared, symmetric key and all further communication is then encrypted
symmetrically. The asymmetric primitives used to exchange a symmetric key are
called Key Encapsulation Mechanisms (KEMs).
Hash Functions A cryptographic hash function is a one-way function that maps
data of arbitrary size to data of fixed size. The most important properties of
cryptographic hash functions are pre-image resistance, second pre-image resistance,
and collision resistance. Pre-image resistance describes the one-way property of a
hash functions, i.e., the difficulty to find an input that if hashed matches a given
output. Second pre-image resistance on the other hand means that given a certain
input, it is difficult to find another (different) input that generates the same hash
value. Collision resistance means that it is hard to find any pair of different inputs
that generate the same hash value. If the output is not fixed but variable, the
algorithm is called an extendable-output function (XOF). Hash functions are also
often used to instantiate random oracles in cryptographic schemes.
Security Model The security of encryption schemes (or KEMs) can be analyzed
regarding different attacker models. The simplest attacker model is to assume
that the attacker has access to some plaintext–ciphertext pair and tries to deduce