Project topics and materials
Get Complete Project Material File(s) Now! »
CPA and CCA Security
The cryptosystem described by algorithms 4 and 5 is secure in the Chosen Plaintext Attack (CPA) model. In this attack model, the adversary is given two plaintexts and a ciphertext that encrypts one of the two, and must determine which plaintext is encrypted by the ciphertext. To do this, the adversary may query an encryption oracle. If such an adversary cannot succeed, then the cryptosystem is called CPA-secure (or IND-CPA). The RLWE encryption scheme essentially masks the plaintext using an RLWE sample. Since samples from the RLWE distribution are indistiguishable from pseudorandom samples, the ciphertext is pseudorandom. It is therefore not possible for the adversary, given two plaintext and a ciphertext, to determine which plaintext is encrypted by the given ciphertext. The RLWE-scheme is CPA-secure.
In practice, security in the CPA model may not be su cient, as it assumes a fairly weak attacker. The Chosen Ciphertext Attack (CCA) model assumes a more powerful attacker, who has access to a decryption oracle. The adversary may send any query to the decryption oracle, except for the given ciphertext. The goal, again, is to choose the correct plaintext given two plaintexts and an encryption of one the two. To succeed in this goal, the adversary could try to nd the secret key using the decryption oracle. Let (c1; c2) be a ciphertext such that all the coe cients are equal to zero, except for the rst coe cient of c1 which is equal to 1. Then algorithm 5 computes d 0 (1) s, which is equal to the secret key. For each coe cient si of s, the output of the decryption oracle reveals whether si is closer to 0 than to 2q . By making multiple queries and varying the coe cients of c2, the adversary can thus recover the complete secret key. Therefore, algorithm 5 is not secure in the CCA model. The Fujisaki-Okamoto transform [56] is a generic method to convert CPA-secure encryption and decryption algorithms to a CCA-secure Key-Exchange Mechanism (KEM). The transform uses some cryptographic hash functions G and H, and is described by algorithms 6 and 7. In order to prevent CCA on the decryption function, the decrypted ciphertext is re-encrypted and compared to the received ciphertext. This allows to verify that the ciphertext is valid, that is, it was generated using the encryption function. Chosen ciphertext attacks like the one described above are prevented by returning a string of random bits if the re-encryption is not equal to the received ciphertext. One technicality remains however, since the encryption function in non-deterministic. In order to make the CCA-secure encapsulation deterministic, the source of randomness used during the encryption is uniquely determined by evaluating a hash function on the public key and the plaintext. This ensures that a re-encryption of the plaintext can be correctly reconstructed using the decrypted ciphertext. To the contrary of the CPA-secure scheme, the plaintext in the CCA-secure scheme is not the same as the session key. The session key is created by hashing public key and plaintext dependent data together with the ciphertext.
Generalization and Module LWE
Module LWE (MLWE) was introduced by [75]. It is a generalization of RLWE and uses small matrices and vectors over the polynomial ring Rq. De nition 2 (MLWE [75]). For some integer parameter k > 0, an MLWE sample for some secret vector of polynomials s 2 Rkq is given by some uniformly random vector a $R kq, together with the polynomial b = a|s + e, where e $B (Rq). The search MLWE problem is to nd s given a number of samples. Note that for the polynomial degree n = 1 the MLWE problem is similar to the LWE problem with vectors of length k. For k = 1, MLWE is equivalent to RLWE over the ring Rq. In the MLWE variant, small matrices and vectors with polynomial coe cients are used. Table 3.1 shows how parameters n; k and m allow to distinguish between LWE, RLWE and MLWE. It has been shown by [75] that MLWE is at least as hard as solving some hard lattice problems using quantum algorithms.
Algorithms 8 and 9 describe the framework used for instance by NewHope, Kyber and FrodoKEM. Variations of this framework include the use of deterministic errors (\Learning with Rounding », LWR)
[45] or using Gaussian noise (used in FrodoKEM) instead of sampling the binomial distribution. The private key is de ned by sampling some s $ B (Rkq m). Then the public key is determined by computing a number of LWE/RLWE/MLWE samples for this secret. That is, sample a uniform random A $R kq k and e0 $B (Rmq k). The public key is given by (A; b) where b := s|A + e0.
Lattice Cryptography on FPGA
Table 3.2 shows implementation results of state of the art FPGA implementations of lattice based public key encryption. Polynomial multiplication is the most time consuming arithmetic operation in RLWE and MLWE based cryptosystems. Di erent solutions have been proposed in the state of the art FPGA implementations. The schoolbook algorithm is implemented by [97] and [77], in order to minimize the resource utilization. These area-optimized implementations are much slower than NTT-based solutions such as the one proposed by [105]. Comparing the computation time of the encryption algorithm of [97] and [105], it can be seen that the NTT-based implementation is around 50 times faster. The area results on the other hand, are less clear. While the schoolbook based solution [97] uses 4 times less LUTs, the DSP and BRAM utilization is the same. It seems that the trade-o between area and computation time is in favor of the NTT. It should be mentioned though, that [105] uses a Virtex-6 FPGA, which is better and more expensive than the Spartan-6 used by [97]. The very recent RLWE-256 implementation by [116] uses schoolbook polynomial multiplication. Their computation time is more than six times as high as the one reported in 2014 by [105], using the NTT. Moreover, the schoolbook implementation uses one more DSP block, and has a very similar LUT utilization Table 3.2: CPA and CCA-secure Encryption or Encapsulation (CPA, CCA) or ’Server’ part in Client-Server-Client key exchange (K-E), from the state of the art. If marked with (*), resource results are for both encryption and decryption.
Table of contents :
1 Introduction
1.1 Context
1.2 Objective and outline of the thesis
2 Denitions and Notations
3 State of the Art
3.1 Introduction
3.2 Public-Key Encryption
3.3 Lattice Problems
3.3.1 Cryptosystem
3.4 Ideal Lattices and RLWE
3.4.1 CPA and CCA Security
3.4.2 Generalization and Module LWE
3.4.3 NTRU
3.4.4 LWR
3.5 Implementation of LWE-based Cryptography
3.5.1 Modular arithmetic
3.5.2 Polynomial arithmetic
3.5.3 Lattice Cryptography on FPGA
3.6 Side-Channel Attacks
3.6.1 SCAs on Lattice Cryptography and Countermeasures
4 Implementation Environment
4.1 Introduction
4.1.1 FPGAs
4.1.2 High Level Synthesis
4.1.3 HLS and Cryptography
4.2 Finite-Field Arithmetic using HLS
4.2.1 Implementation results
4.3 Schoolbook Algorithm for Polynomial Multiplication
5 LWE, RLWE and MLWE on FPGA
5.1 Introduction
5.2 Implementation of main operations
5.3 FPGA Implementation of LWE
5.3.1 Parameters used in the implementations
5.3.2 Matrix arithmetic for LWE
5.3.3 Parallelization using HLS
5.3.4 Implementation results
5.4 RLWE Implementations
5.4.1 Optimizing the area utilization
5.5 MLWE implementations and comparison
5.5.1 Modifying the RLWE implementation
5.5.2 Parallelization of operations in Rkq
5.5.3 Parallelization using HLS
5.5.4 Implementation results
5.6 Randomness generation and CCA implementations
5.6.1 Rejection sampling
5.6.2 Alternative PRNG
5.6.3 CCA secure implementations
5.7 Comparison with other works
5.8 Conclusion
6 Countermeasures against Side-Channel Attacks
6.1 Introduction
6.1.1 Correlation Power Attack simulations in Python
6.2 Countermeasures in the State of the Art
6.3 New Variants of State of the Art Protections
6.3.1 Masking with a New Masked Decoder
6.3.2 Modied Shifting
6.3.3 Blinding
6.3.4 Shifting and Blinding Combined
6.4 New Protections
6.4.1 Shuing
6.4.2 Randomization using Redundant Number Representation
6.5 Comparison of all Protections
6.6 Generalizing the Countermeasures to Apply to MLWE/LWE
6.6.1 Masking
6.6.2 Blinding
6.6.3 Shifting
6.6.4 Shuing
6.6.5 Redundant number representation
6.7 Conclusion and Discussion
7 Conclusion
Resume en francais
