Computer Science

The FHEW fully homomorphic encryption scheme of Ducas and Micciancio offers very fast homomorphic NAND-gate computations (on encrypted data) and a relatively fast refreshing procedure that allows to homomorphically evaluate arbitrary NAND boolean circuits. Unfortunately, the refreshing procedure needs to be executed after every single NAND computation, and each refreshing operates on a single encrypted bit, greatly decreasing the overall throughput of the scheme. We give a new refreshing procedure that simultaneously refreshes n FHEW ciphertexts, at a cost comparable to a single-bit FHEW refreshing operation. As a result, the cost of each refreshing is amortized over n encrypted bits, improving the throughput for the homomorphic evaluation of boolean circuits roughly by a factor n.  

Several lattice-based cryptography primitives and protocols are now practical and even available in commercial products, for example, public-key cryptography, homomorphic encryption, proxy re-encryption (PRE), and digital signatures. Many of these primitives based on the Learning With Errors problem are implemented in the PALISADE lattice cryptography library. This talk presents a survey of state-of-the-art lattice algorithms implemented in PALISADE (both for already practical primitives and research prototypes of more advanced capabilities) and discusses some of their applications. The first part of the talk focuses on FHE schemes and their extensions, such as PRE and threshold FHE. The remaining part is centered around lattice trapdoors and the protocols where lattice trapdoors are used as a primitive, including identity-based encryption, key-policy attribute-based encryption, and program obfuscation.

In this talk, I will present recent progresses on the design and implementation of Homomorphic Encryption for Arithmetic of Approximate Numbers (HEAAN), which supports encrypted computation with errors. I will also describe the advantages of HEAAN in practice as well as its bootstrapping method to achieve approximate fully homomorphic encryption.

The talk will be split in two parts: the first one will be a general introduction to Fully Homomorphic Encryption (FHE) while the second one will focus on the description of the TFHE scheme (https://eprint.iacr.org/2018/421.pdf).

In this talk, I will present an extension of Ducas, Lyubashesky and Prest instantiation of Gentry, Peikert and Vaikuntanathan (GPV) framework. More precisely, I will describe a larger class of trapdoored NTRU lattices that can be used to extend the practical parameter sets for some cryptographic schemes. Indeed, as shown by NIST candidates such as Kyber or Dilihtium, relying on module lattices and the relevant hard problems can allow for some meaningful trade-offs between security and efficiency. I will explain the regime of parameters that are needed to generate "almost optimal" (in an asymptotic sense) yet practical trapdoored NTRU modules. In particular, I will discuss the notion of hardness underlying this instantiation, and highlight some new results giving strong backups toward the computational and decisional hardness assumptions behind these trapdoors. On the more practical side, I will briefly compare the potency of a new signature scheme relying on these trapdoors to some of the NIST Round 2 candidates. Based on a joint work with Chitchanok Chuengsatiansup, Thomas Prest, Damien Stehlé and Keita Xagawa.

NTRU lattices use bases with a compact representation as polynomials; elements of a lattice of dimension $2n$ are encoded as a pair of polynomials with integer coefficients and taken modulo a given irreducible polynomial of degree $n$, usually $X^n+1$ (with $n$ a power of two). The private key is the knowledge of two polynomials $(f,g)$ with small coefficients. Some cryptographic algorithms based on NTRU lattices, in particular NTRUSign and Falcon, require a complete basis, i.e. two extra polynomials $F$ and $G$, also with small coefficients, that fulfill the NTRU equation: $fG - gF = q$, for a given small integer $q$. While generating $f$ and $g$ is simple, computing matching $F$ and $G$ requires considerable resources in CPU and RAM, making key pair generation inapplicable to small constrained systems. In this presentation, we will show how the NTRU equation can be solved much more efficiently by using the field norm over a tower of fields. We first show a novel method for computing the resultant of a small polynomial with the modulus $X^n+1$; we will then draw on that method to solve the NTRU equation in a resource-efficient way. When applied to the Falcon signature system, RAM cost of key pair generation was reduced by a factor of more than 100 (from about 3 MB down to less than 30 kB) and CPU cost was also reduced by a similar factor (from about 2 seconds to 21 milliseconds). This allows the implementation of the whole of Falcon, including key pair generation, on embedded systems, with constant-time code (free of timing-based side channels).

The Fiat-Shamir transformation is used to build secure signatures in the random oracle model. Unfortunately, existing proof techniques are incapable of proving the security of Fiat-Shamir in the quantum setting. The problem stems from (1) the difficulty of quantum rewinding, and (2) the inability of current techniques to adaptively program random oracles in the quantum setting. In this work, we show how to overcome these limitations. As an application, we show that existing lattice signatures based on Fiat-Shamir are secure without any modifications.