Monthly lattice and crypto meetings

The meetings are organized by Fabien Laguillaumie, Benoît Libert and Damien Stehlé, and financially supported by ERC Starting Grant ERC-2013-StG-335086-LATTAC.

If you want to attend, please contact the organizers: relatively precise headcount is required to book appropriate rooms.

Next meeting: 05.04.2017 - 06.04.2017

Topic: Cryptographic constructions with and without lattices.
Location: ENS Lyon, Monod campus.
Room: 116 on Thursday morning, 115 the rest of the time.
Work room, for around the talks: 316C.

We 05/04, 1:30pm-3:30pm: Florian Bourse (ENS Paris): CCA-Secure Inner-Product Functional Encryption from Projective Hash Functions

In an inner-product functional encryption scheme, the plaintexts are vectors and the owner of the secret key can delegate the ability to compute weighted sums of the coefficients of the plaintext of any ciphertext. Recently, many inner-product functional encryption schemes were proposed. However, none of the known schemes are secure against chosen ciphertext attacks (IND-FE-CCA). We present a generic construction of IND-FE-CCA inner-product functional encryption from projective hash functions with homomorphic properties. We show concrete instantiations based on the DCR assumption, the DDH assumption, and more generally, any Matrix DDH assumption.

The talk will be based on this article.

This is joint work with Fabrice Benhamouda and Helger Lipmaa.

4pm-6pm: Fabrice Mouhartem (ENS de Lyon): Adaptive oblivious transfer from LWE

Adaptive oblivious transfer (OT) is a protocol where a sender initially commits to a database M_1, …, M_N. Then, a receiver can query the sender up to k times with private indexes ρ_1, …, ρ_k so as to obtain M_{ρ_1}, …, M_{ρ_k} and nothing else. Moreover, for each i ∈ [k], the receiver’s choice ρ_i may depend on previously obtained messages {M_{ρ_j}}_{j< i} . Oblivious transfer with access control (OT-AC) is a flavor of adaptive OT where database records are protected by distinct access control policies that specify which credentials a receiver should obtain in order to acces each M_i. So far, all known OT-AC protocols only support access policies made of conjunctions or rely on ad hoc assumptions in pairing-friendly groups (or both). In this paper, we provide an OT-AC protocol where access policies may consist of any branching program of polynomial length, which is sufficient to realize any access policy in NC^1. The security of our protocol is proved under the Learning-with-Errors (LWE) and Short-Integer-Solution (SIS) assumptions. As a result of independent interest, we provide protocols for proving the correct evaluation of a committed branching program on a committed input.

This is joint work with Benoît Libert, San Ling, Khoa Nguyen and Huaxiong Wang.

Th 06/04, 9:30am-11:30am: Damien Stehlé (ENS de Lyon): From Inner-Product Functional Encryption to Trace-and-Revoke with Public Traceability

We describe a generic construction of a trace-and-revoke broadcast encryption scheme from a functional encryption scheme for inner products modulo a prime integer. The resulting scheme achieves the strongest notion of adaptive security for the tracing procedure, as well as public traceability in the black-box confirmation model. Thus, tracing traitors can be delegated to untrusted parties in our constructions. By combining the construction with inner product functional encryption schemes from Agrawal et al. [CRYPTO'16], we obtain concrete trace-and-revoke schemes with security based on the Decision Composite Residuosity (DCR) and Learning With Errors (LWE) hardness assumptions. Our LWE based construction resolves a question explicitly left open by Ling et al. [CRYPTO'14]. We also adapt our technique to obtain an ecient, publicly traceable traitor tracing scheme with security based on the DDH hardness assumption. Our constructions are ecient, and enjoy hardness based on standard assumptions. Such a combination of eciency, public traceability and support for both trace and revoke was not known before to the best of our knowledge.

This is joint work with Shweta Agrawal, Sanjay Bhattacherjee, Duong Hieu Phan and Shota Yamada.

1:30pm-3:30pm: Olivier Blazy (U. Limoges): Hash Proof Systems over Lattices Revisited

Hash Proof Systems or Smooth Projective Hash Functions (SPHFs) are a form of implicit arguments introduced by Cramer and Shoup at Eurocrypt’02. They have found many applications since then, in particular for authenticated key exchange or honest-verifier zero-knowledge proofs. While they are relatively well understood in group settings, they seem painful to construct directly in the lattice setting. Only one construction of an SPHF over lattices has been proposed, by Katz and Vaikuntanathan at Asiacrypt’09. But this construction has an important drawback: it only works for an ad-hoc language of ciphertexts. Concretely, the corresponding decryption procedure needs to be tweaked, now requiring q many trapdoor inversion attempts, where q is the modulus of the underlying Learning With Error (LWE) problem. Using harmonic analysis, we explain the source of this limitation, and propose a way around it. We show how to construct SPHFs for standard languages of LWE ciphertexts, and explicit our construction over a tag-CCA2 encryption scheme à la Micciancio-Peikert (Eurocrypt’12). If there is enough time, we will conclude with applications of these SPHFs to password-authenticated key exchange, honest-verifier zero-knowledge and a variant of witness encryption.

This is joint work with Fabrice Benhamouda and Léo Ducas.

Following meetings

To be announced.

Past meetings

08.03.2017 - 09.03.2017

Topic: Algebraic number theory and Ring-LWE.
Location: ENS Lyon, Monod campus.
Room: 116.
Work room, for around the talks: 316C.

We. 08/03, 13:30-15:30. Guillaume Hanrot (ENS Lyon): Crash course in algebraic number theory

We. 08/03, 16:00-18:00. Wouter Castryck (U. Lille), Remarks on the error distributions in ring-based LWE

The existing literature contains several ring-based variants of the Learning With Errors problem, all of which are often referred to as Ring-LWE, a habit which has led to some confusion in the recent past. The main difference lies in the choice of the probability distribution from which the errors are to be sampled. We will briefly compare the main versions, such as Poly-LWE and “proper” Ring-LWE as introduced by Lyubashevsky et al., and discuss some pitfalls that arise when mixing things up.

The talk will be based on this article.

This is joint work with Ilia Iliashenko and Frederik Vercauteren.

Th. 09/03, 10:00-12:00. Thomas Espitau (U. Paris 6): Computing generator in cyclotomic integer rings

The Principal Ideal Problem (resp. Short Principal Ideal Problem), shorten as PIP (resp. SPIP), consists in finding a generator (resp. short generator) of a principal ideal in the ring of integers of a number field. Several lattice-based cryptosystems rely on the presumed hardness of these two problems. Yet, in practice, most of them do not use an arbitrary number field but a power-of-two cyclotomic field. The Smart and Vercauteren fully homomorphic encryption scheme and the multilinear map of Garg, Gentry and Halevi epitomize this common restriction. Recently, Cramer, Ducas, Peikert and Regev show that solving the SPIP in such cyclotomic rings boils down to solving the PIP. We complete their result by an algorithm that solves PIP in cyclotomic fields in subexponential time L|∆K| (1/2, 0.717) = e^((0.717+o(1))n^(1/2) log n), where ∆K denotes the discriminant of the number field and n its degree. This asymptotic complexity could be compared with the one obtained by Biasse and Fieker method, that aims at finding a generator as we do, but runs in L|∆K| (2/3). Besides this theoretical improvement, our algorithm allows to recover in practice the secret key of the Smart and Vercauteren scheme, for the smallest proposed parameters. In this talk we propose to detail the main and novel aspects of this algorithm, namely:
* The Gentry-Szydlo algorithm to perform a halving of dimension by working in the totally real subfield of the cyclotomic field.
* A q-descent procedure using lattice reduction and ideal arithmetic to reduce the problem to PIP for L(1/2)-smooth ideals.
* A linear algebra phase to solve the L(1/2)-smooth instances.
All along the presentation we will emphasize on the relations between the commutative algebra side (ideals arithmetic, manipulations of number field elements,...) and the geometric side (norms related issues, lattice reduction,...).

The talk will be based on this article.

Joint work with Pierre-Alain Fouque, Alexandre Gélin and Paul Kirchner.

Th. 09/03, 14:00-16:00. Léo Ducas (CWI), Short Stickelberger Class Relations and application to Ideal-SVP

The hardness of finding short vectors in ideals of cyclotomic number fields (Ideal-SVP) serves as the worst-case hypothesis underlying the Ring-LWE assumption, and therefore the security of numerous cryptographic schemes --- including key-exchange, public-key encryption and fully-homomorphic encryption. A series of recent works has shown that *Principal* Ideal-SVP is not always as hard as finding short vectors in general lattices, and some schemes were broken using quantum algorithms --- the *Soliloquy* encryption scheme, Smart-Vercauteren fully homomorphic encryption scheme from *PKC 2010*, and Gentry-Garg-Halevi cryptographic multilinear-maps from *Eurocrypt 2013*. Those broken schemes were using a special class of principal ideals, but this approach can also solve SVP for principal ideals in the *worst-case* in quantum polynomial time for an approximation factor of $\exp(\tilde O(\sqrt n))$. This exposed an unexpected hardness gap between general lattices and some structured ones, and called into question the hardness of various problems over structured lattices, such as Ideal-SVP and Ring-LWE. In this work, we generalize the previous result to general ideals. Precisely, we show how to solve the close principal multiple problem (CPM) by exploiting the classical theorem that the class-group is annihilated by the (Galois-module action of) the so-called Stickelberger ideal. Under some plausible number-theoretical hypothesis, our approach provides a close enough principal multiple in quantum polynomial time. Combined with the previous results, this solves Ideal-SVP in the worst case in quantum polynomial time for an approximation factor of $\exp(\tilde O(\sqrt n))$. Although it does not seems that the security of Ring-LWE based cryptosystems is directly affected, we contribute novel ideas to the cryptanalysis of schemes based on structured lattices. Moreover, our result shows a deepening of the gap between general lattices and structured ones.

The talk will be based on this article.

Joint work with Ronald Cramer and Benjamin Wesolowski.

24.01.2017 (organized by Hoeteck Wee)

Topic: lattice-based cryptographic constructions.
Location: ENS Paris.
Room: Amphi Rataud.

Tu 24/01, 10am-noon: Vinod Vaikuntanathan (MIT), Three Tricks to Rule them All: Advanced Cryptographic Constructions from Lattices

Many recent constructions of advanced lattice-based primitives such as attribute-based encryption, fully homomorphic encryption, fully homomorphic signatures, predicate encryption and constrained PRFs rely on a handful of techniques that play with LWE and lattice trapdoors. We will present them and show as many of these constructions as time permits.

Tu 24/01, 2pm-4pm: Zvika Brakerski (Weizmann Institute), Nipped in the Bud: Graded Encoding Schemes that Did Not Make It

I will present a few suggested constructions of (polynomial ring based) graded encoding schemes that turned out to be insecure at an early stage, and therefore were not widely published and might not be known to many.

15.12.2016 - 16.12.2016

Topic: Algorithms and assumptions.
Location: ENS Lyon, Monod campus.
Rooms: 115 on Thursday the 15th (main building, level 1, South aisle), Amphi G on Friday the 16th (ground floor, North aisle).
Work room, for around the talks: 316C.
Dates: This is indeed a Thursday and a Friday, not as usual!

Th 15/12, 9:30am-11:30am: Gottfried Herold (Ruhr-Universität Bochum), Improved Algorithms for the Approximate k-List Problem in Euclidean norm

We present an algorithm for the approximate k-List problem for the Euclidean distance that improves upon the Bai-Laarhoven-Stehle (BLS) algorithm from ANTS'16. The improvement stems from the observation that almost all the solutions to the approximate k-List problem form a particular conguration in n-dimensional space. Due to special properties of congurations, it is much easier to verify whether a k-tuple forms a conguration rather than checking whether it gives a solution to the k-List problem. Thus, phrasing the k-List problem as a problem of finding such congurations immediately gives a better algorithm. Furthermore, the search for configurations can be sped up using techniques from Locality-Sensitive Hashing (LSH). Stated in terms of configuration-search, our LSH-like algorithm offers a broader picture on previous LSH algorithms.

Joint work with Elena Kirshanova.

Th 15/12, 2:30pm-4:30pm: Léo Ducas (CWI), The closest vector problem in tensored root lattices of type A and in their duals

In this work we consider the closest vector problem (CVP) ---a problem also known as maximum-likelihood decoding--- in the tensor of two root lattices of type A (Am \tensor An), as well as in their duals (A*m \tensor A*n). This problem is mainly motivated by lattice based cryptography, where the cyclotomic rings Z[\zetac] (resp. its co-different) play a central role, and turn out to be isomorphic as lattices to tensors of A*lattices (resp. Aroot lattices). In particular, our results lead to solving CVP in Z[\zetac] and iits co-different for conductors of the form c=2\alpha_p \beta_q \gamma for any two odd primes p,q. For the primal case Am \tensor An, we provide a full characterization of the Voronoi region in terms of simple cycles in the complete directed bipartite graph Km+1,n+1. This leads ---relying on the Bellman-Ford algorithm for negative cycle detection--- to a CVP algorithm running in *polynomial time*. Precisely, our algorithm performs O(l m^2n^2 min{m,n}) operations on reals, where l is the number of bits per coordinate of the input target. For the dual case, we use a gluing-construction to solve CVP in sub-exponential time.

The talk will be based on this article.

Joint work with Wessel P.J. van Woerden.

Th 15/12, 4:30pm-5:30pm and Fr 16/12 9:30am-10:30am: Weiqiang Wen (ENS de Lyon), Learning With Errors and the Generalized Hidden Shift Problem

We give reductions between the Learning With Errors problem and a variant, introduced by Childs and van Dam at SODA'07, of the Hidden Shift Problem modulo an integer. The reductions are essentially sharp as the parameter degradations incurred by applying them back and forth are limited. They allow to better capture the (quantum) hardness of Learning With Errors in terms of the Hidden Shift Problem. From a technical viewpoint, the reductions are inspired by Regev's reductions from worst-case lattice problems to the Dihedral Coset Problem and to Learning With Errors.

Fr 16/12, 10:30am-12:30am: Zvika Brakerski (Weizmann Institute), Obfuscating Conjunctions under Entropic Ring LWE

We show how to securely obfuscate conjunctions, which are functions f(x1, ..., xn) = AND_{i in I} y_i, where I \subseteq [n] and each literal y_i is either just xi or NOT(xi). Whereas prior work of Brakerski and Rothblum (CRYPTO 2013) showed how to achieve this using a non-standard object called cryptographic multilinear maps, our scheme is based on an 'entropic' variant of the Ring Learning with Errors (Ring LWE) assumption. As our core tool, we prove that hardness assumptions on the recent multilinear map construction of Gentry, Gorbunov and Halevi (TCC 2015) can be established based on entropic Ring LWE. We view this as a first step towards proving the security of additional multilinear map based constructions, and in particular program obfuscators, under standard assumptions. Our scheme satisfies virtual black box (VBB) security, meaning that the obfuscated program reveals nothing more than black-box access to f as an oracle, at least as long as (essentially) the conjunction is chosen from a distribution having sufficient entropy.

The talk will be based on this article.

Joint work with Vinod Vaikuntanathan, Hoeteck Wee and Daniel Wichs.

23.11.2016 - 24.11.2016

Topic: Fully homomorphic encryption.
Location: ENS Lyon, Monod campus.
Rooms: 116 and then 115 (main building, level 1, South aisle).

Wed 23/11, 2:30pm-4:30pm: Ilaria Chillotti (UVSQ), Faster Fully Homomorphic Encryption: Bootstrapping in less than 0.1 Seconds

We revisit fully homomorphic encryption (FHE) based on GSW and its ring variants. We notice that the internal product of GSW can be replaced by a simpler external product between a GSW and an LWE ciphertext. We show that the bootstrapping scheme FHEW of Ducas and Micciancio (Eurocrypt 2015) can be expressed only in terms of this external product. As a result, we obtain a speed up from less than 1 second to less than 0.1 seconds. We also reduce the 1GB bootstrapping key size to 24MB, preserving the same security levels, and we improve the noise propagation overhead by replacing exact decomposition algorithms with approximate ones. Moreover, our external product allows to explain the unique asymmetry in the noise propagation of GSW samples and makes it possible to evaluate deterministic automata homomorphically as in (ePrint 2014/283) in an efficient way with a noise overhead only linear in the length of the tested word. Finally, we provide an alternative practical analysis of LWE based scheme, which directly relates the security parameter to the error rate of LWE and the entropy of the LWE secret key.

The talk will be based on this article.

Joint work with Nicolas Gama and Mariya Georgieva and Malika Izabachène.

Th 24/11, 10am - 12pm: Florian Bourse (ENS Paris), FHE Circuit Privacy Almost for Free

Circuit privacy is an important property for many applications of fully homomorphic encryption. Prior approaches for achieving circuit privacy rely on superpolynomial noise flooding or on bootstrapping. In this work, we present a conceptually different approach to circuit privacy based on a novel characterization of the noise growth amidst homomorphic evaluation. In particular, we show that a variant of the GSW FHE for branching programs already achieves circuit privacy; this immediately yields a circuit-private FHE for NC1 circuits under the standard LWE assumption with polynomial modulus-to-noise ratio. Our analysis relies on a variant of the discrete Gaussian leftover hash lemma which states that e^T G^{−1}(v)+small noise does not depend on v. We believe that this result is of independent interest.

The talk will be based on this article.

Joint work with Rafael Del Pino, Michele Minelli and Hoeteck Wee.

Th 24/11, 2pm-4pm: Eduardo Soria-Vazquez (U. of Bristol), More Efficient Constant-Round Multi-Party Computation from BMR and SHE

We present a multi-party computation protocol in the case of dishonest majority which has very low round complexity. Our protocol sits philosophically between Gentry's Fully Homomorphic Encryption based protocol and the SPDZ-BMR protocol of Lindell et al (CRYPTO 2015). Our protocol avoids various inefficiencies of the previous two protocols. Compared to Gentry's protocol we only require Somewhat Homomorphic Encryption (SHE). Whilst in comparison to the SPDZ-BMR protocol we require only a quadratic complexity in the number of players (as opposed to cubic), we have fewer rounds, and we require less proofs of correctness of ciphertexts. Additionally, we present a variant of our protocol which trades the depth of the garbling circuit (computed using SHE) for some more multiplications in the offline and online phases.

The talk will be based on this article.

Joint work with Yehuda Lindell and Nigel P. Smart.

24.05.2016 - 25.05.2016

Topic: Cryptographic constructions.
Location: ENS Lyon, Monod campus.
Room: A2 (main building, level 4, North aisle).

Warning: the meeting will be on Tuesday + Wednesday (instead of the usual Wednesday + Thursday).

Tu 24/05, 2:30pm - 5pm: Pooya Farshim (ENS Paris) Multilinear Maps from Obfuscation

We provide constructions of multilinear groups equipped with natural hard problems from indistinguishability obfuscation, homomorphic encryption, and NIZKs. This complements known results on the constructions of indistinguishability obfuscators from multilinear maps in the reverse direction. We provide two distinct, but closely related constructions and show that multilinear analogues of the DDH assumption hold for them. Our first construction is \emph{symmetric} and comes with a k-linear map e : G^k --> G_T for prime-order groups G and G_T. To establish the hardness of the k-linear DDH problem, we rely on the existence of a base group for which the (k - 1)-strong DDH assumption holds. Our second construction is for the \emph{asymmetric} setting, where e : G_1 x ... x G_k --> G_T for a collection of k + 1 prime-order groups G_i and G_T, and relies only on the standard DDH assumption in its base group. In both constructions the linearity k can be set to any arbitrary but a priori fixed polynomial value in the security parameter. We rely on a number of powerful tools in our constructions: (probabilistic) indistinguishability obfuscation, dual-mode NIZK proof systems (with perfect soundness, witness indistinguishability and zero knowledge), and additively homomorphic encryption for the group Z_N^{+}. At a high level, we enable "bootstrapping" multilinear assumptions from their simpler counterparts in standard cryptographic groups, and show the equivalence of IO and multilinear maps under the existence of the aforementioned primitives.

The talk will be based on this article.

Joint work with Martin R. Albrecht, Dennis Hofheinz, Enrique Larraia and Kenneth G. Paterson.

We 25/05, 9:am - 11:30am: Shota Yamada (AIST, Japan), Adaptively Secure Identity-Based Encryption from Lattices with Asymptotically Shorter Public Parameters

In this paper, we present two new adaptively secure identity-based encryption (IBE) schemes from lattices. The size of the public parameters, ciphertexts, and private keys are \tilde{O}(n2κ1/d), \tilde{O}(n), and \tilde{O}(n) respectively. Here, n is the security parameter, κ is the length of the identity, and d is a flexible constant that can be set arbitrary (but will affect the reduction cost). Ignoring the poly-logarithmic factors hidden in the asymptotic notation, our schemes achieve the best efficiency among existing adaptively secure IBE schemes from lattices. In more detail, our first scheme is anonymous, but proven secure under the LWE assumption with approximation factor n^{ω(1)}. Our second scheme is not anonymous, but proven adaptively secure assuming the LWE assumption for all polynomial approximation factors. As a side result, based on a similar idea, we construct an attribute-based encryption scheme for branching programs that simultaneously satisfies the following properties for the first time: Our scheme achieves compact secret keys, the security is proven under the LWE assumption with polynomial approximation factors, and the scheme can deal with unbounded length branching programs.

The talk will be based on this article.

We 25/05, 2pm-4pm, Daniel Masny (Ruhr-Universität Bochum, Germany), Chosen-Ciphertext Security from Subset Sum

We construct a public-key encryption (PKE) scheme whose security is polynomial-time equivalent to the hardness of the Subset Sum problem. Our scheme achieves the standard notion of indistinguishability against chosen-ciphertext attacks (IND-CCA) and can be used to encrypt messages of arbitrary polynomial length, improving upon a previous construction by Lyubashevsky, Palacio, and Segev (TCC 2010) which achieved only the weaker notion of semantic security (IND-CPA) and whose concrete security decreases with the length of the message being encrypted. At the core of our construction is a trapdoor technique which originates in the work of Micciancio and Peikert (Eurocrypt 2012).

The talk will be based on this article.

Joint work with Sebastian Faust and Daniele Venturi.

13.04.2016 - 14.04.2016

Topic: Towards making lattice-based crypto practical.
Location: ENS Lyon, Monod campus.
Room: Amphi K on the 13th, Amphi I on the 14th (main building, Level 0, North side).

We 13/04, 2pm - 4pm: Carlos Aguilar-Melchor (INP ENSEEIHT), NFLlib: NTT-based Fast Lattice Library

Recent years have witnessed an increased interest in lattice cryptography. Besides its strong security guarantees, its simplicity and versatility make this powerful theoretical tool a promising competitive alternative to classical cryptographic schemes. In this paper, we introduce NFLlib, an efficient and open-source C++ library dedicated to ideal lattice cryptography in the widely-spread polynomial ring Zp[x]/(x^n + 1) for n a power of 2. The library combines algorithmic optimizations (Chinese Remainder Theorem, optimized Number Theoretic Transform) together with programming optimization techniques (SSE and AVX2 specializations, C++ expression templates, etc.), and will be fully available under the GPL license. The library compares very favorably to other libraries used in ideal lattice cryptography implementations (namely the generic number theory libraries NTL and flint implementing polynomial arithmetic, and the optimized library for lattice homomorphic encryption HElib): restricting the library to the aforementioned polynomial ring allows to gain several orders of magnitude in efficiency.

The talk will be based on this article.

Joint work with Joris Barrier, Serge Guelton, Adrien Guinet, Marc-Olivier Killijian and Tancrède Lepoint .

We 13/04, 4:30pm - 5:30pm: Léo Ducas (CWI), Decoding algorithms for special lattice codes

The final rounding stage of decryption of many lattice-based schemes can be interpreted as analog decoding of the trivial lattice Z^n. It is well known that noise/signal gain can be achieved with better lattice code: this would translate into more compact or more secure cryptosystems. This idea has already been explored implicitly with the lattice D_2 and was made explicit in the protocol Newhope with the lattice D_4.The gain should increases as we switch to larger lattice codes. In this talk, we propose a brief introduction to decoding algorithms for special lattice code. While the literature tends to be quite ad-hoc, we wish to propose a few general lemmas to translate the decomposition (gluing, intersection with parity codes) of a lattice code into an algorithm. As an example, we revisit the Maximum-Likelyhood decoding (CVP) algorithm for the 24-dimensional Leech lattice avoiding the typical details on the Miracle Octade Genrators (MOG). If time permits, we may also show connections between ring of integers of cyclotomic number fields and the dual root lattices A_n^* and deduce CVP algorithms for those rings.

This is work in progress with Alex van Poppelen and Wessel van Woerden

Th 14/04, 10:15am-11:15am, Peter Schwabe (Radboud University), Post-quantum key exchange -- a new hope

At IEEE Security & Privacy 2015, Bos, Costello, Naehrig, and Stebila proposed an instantiation of Peikert's ring-learning-with-errors--based (Ring-LWE) key-exchange protocol (PQCrypto 2014), together with an implementation integrated into OpenSSL, with the affirmed goal of providing post-quantum security for TLS. In this talk I will present joint work with Alkim, Ducas, and Pöppelmann, in which we revisit their instantiation and stand-alone implementation. Specifically, we propose new parameters and a better suited error distribution, analyze the scheme's hardness against attacks by quantum computers in a conservative way, introduce a new and more efficient error-reconciliation mechanism, and propose a defense against backdoors and all-for-the-price-of-one attacks. By these measures and for the same lattice dimension, we more than double the security parameter, halve the communication overhead, and speed up computation by more than a factor of 9 in a portable C implementation and by more than a factor of 24 in an optimized implementation targeting current Intel CPUs. These speedups are achieved with comprehensive protection against timing attacks.

The talk will be based on this article.

Joint work with Erdem Alkim, Léo Ducas and Thomas Pöppelmann.

Th 14/04, 1:30pm-3:30pm, Martin Albrecht (Royal Holloway), Implementing Operations in Power-of-2 Cyclotomic Rings

The talk will be based on this article.

Joint work with Catalin Cocis, Fabien Laguillaumlie and Adeline Langlois.

02.03.2016 - 03.03.2016

Topic: Fast lattice reduction algorithms and applications
Location: ENS Lyon, Monod campus.
Room: 116 (main building, level 1, South aisle).

We 02/03, 2:45pm - 4:45pm: Damien Stehlé (ENS de Lyon), Faster LLL-type reduction of lattice bases

We describe a fast variant of the LLL lattice reduction algorithm. Our algorithm takes as input a basis $\vec{B} \in \mZ^{n \times n}$ of a Euclidean lattice~$L$ and returns a (reduced) basis~$\vec{C}$ of~$L$, whose first vector satisfies~$\|\vec{c}_1\| \leq (1+c) (4/3)^{(n-1)/4} (\det L)^{1/n}$ for any fixed~$c>0$. It terminates within~$O(n^{4+\eps} \beta^{1+\eps})$ bit operations for any~$\eps >0$, with~$\beta = \max_i \|\vec{b}_i\|$. It does rely on fast integer arithmetic but does not make use of fast matrix multiplication.

Joint work with Arnold Neumaier.

We 02/03, 5:00pm - 6:00pm: Jinming Wen (ENS de Lyon), Three Polynomial Time Algorithms for Optimally Solving a Shortest Vector Problem in Compute-and-Forward Design

In relay networks, compute-and-forward (CF) is a promising relaying strategy that can offer higher rates than traditional ones (e.g., amplify-and-forward, decode-and-forward), especially in the moderate signal-to-noise regime. To find the optimal coefficient vector that maximizes the computation rate at a relay in the CF scheme, a Shortest Vector Problem (SVP) needs to be solved. In this talk, I will present three polynomial time algorithms (including two linearithmic Time Algorithms) for optimally solving this SVP.

The talk will be based on this article and this article.

Joint work with Baojian Zhou, Wai Ho Mow and Xiao-Wen Chang.

Th 03/03, 9:00am-10:00am: Jinming Wen (ENS de Lyon), follow-up of previous talk

Th 03/03, 10:15am-11:15am, Fabrice Benhamouda (ENS Paris), Easing Coppersmith Methods using Analytic Combinatorics: Applications to Public-Key Cryptography with Weak Pseudorandomness

The \emph{Coppersmith methods} is a family of lattice-based techniques to find small integer roots of polynomial equations. They have found numerous applications in cryptanalysis and, in recent developments, we have seen applications where the number of unknowns and the number of equations are non-constant. In these cases, the combinatorial analysis required to settle the complexity and the success condition of the method becomes very intricate. We provide a toolbox based on \emph{analytic combinatorics} for these studies. It uses the structure of the considered polynomials to derive their generating functions and applies complex analysis techniques to get asymptotics. The toolbox is versatile and can be used for many different applications, including multivariate polynomial systems with arbitrarily many unknowns (of possibly different sizes) and simultaneous modular equations over different moduli. To demonstrate the power of this approach, we apply it to recent cryptanalytic results on number-theoretic pseudorandom generators for which we easily derive precise and formal analysis. We also present new theoretical applications to two problems on RSA key generation and randomness generation used in padding functions for encryption.

The talk will be based on this article.

Joint work with Céline Chevalier, Adrian Thillard, and Damien Vergnaud.

Th 03/03, 1:15pm-2:15pm, Fabrice Benhamouda (ENS Paris), follow-up of previous talk

Th 03/03, 2:45pm-4:45pm, Vincent Neiger (ENS de Lyon), Fast Coppersmith method over the polynomials: finding a reduced basis via approximation

After giving an overview of the analogue of the Coppersmith method over the polynomials and of some of its applications, we focus on the algorithmic aspects of the first step of the method. In the integer Coppersmith method, this step is commonly solved using lattice basis reduction: in the polynomial version of the method, we sketch the analogous solution which uses row reduction of a polynomial matrix. Then we present another, currently faster, approach for this first step, which reduces it to the problem of finding a (basis of) sufficiently small degree solution(s) to a system of modular polynomial equations. We will observe that the fastest known algorithms for both row reduction and modular system solving fundamentally rely on fast Hermite-Pade approximation.

21.01.2016 (organized by Hoeteck Wee)

Topic: functional encryption
Location: ENS Paris.
Room: W

10:30am - 12:00pm: Hoeteck Wee (ENS Paris), Predicate Encryption for Circuits from LWE.

In predicate encryption, a ciphertext is associated with descriptive attribute values $x$ in addition to a plaintext $\mu$, and a secret key is associated with a predicate $f$. Decryption returns plaintext $\mu$ if and only if $f(x) = 1$. Moreover, security of predicate encryption guarantees that an adversary learns nothing about the attribute $x$ or the plaintext $\mu$ from a ciphertext, given arbitrary many secret keys that are not authorized to decrypt the ciphertext individually. We construct a leveled predicate encryption scheme for all circuits, assuming the hardness of the subexponential learning with errors (LWE) problem. That is, for any polynomial function $d = d(\secp)$, we construct a predicate encryption scheme for the class of all circuits with depth bounded by $d(\secp)$, where $\secp$ is the security parameter.

The talk will be based on this article.

Joint work with Sergey Gorbunov and Vinod Vaikuntanathan.

2:00pm - 3:30pm: Benoît Libert and Damien Stehlé (ENS de Lyon), Fully Secure Functional Encryption for Inner Products, from Standard Assumptions

Functional encryption is a modern public-key paradigm where a master secret key can be used to derive sub-keys $SK_F$ associated with certain functions $F$ in such a way that the decryption operation reveals $F(M)$, if $M$ is the encrypted message, and nothing else. Recently, \mbox{Abdalla} {\it et al.} gave simple and efficient realizations of the primitive for the computation of linear functions on encrypted data: given an encryption of a vector $\vec{y}$ over some specified base ring, a secret key $SK_{\vec{x}}$ for the vector $\vec {x}$ allows computing $\langle \vec{x} ,\vec{y} \rangle$. Their technique surprisingly allows for instantiations under standard assumptions, like the hardness of the Decision Diffie-Hellman (DDH) and Learning-with-Errors (LWE) problems. Their constructions, however, are only proved secure against selective adversaries, which have to declare the challenge messages $M_0$ and $M_1$ at the outset of the game. In this paper, we provide constructions that provably achieve security against more realistic {\it adaptive} attacks (where the messages $M_0$ and $M_1$ may be chosen in the challenge phase, based on the previously collected information) for the same inner product functionality. Our constructions are obtained from hash proof systems endowed with homomorphic properties over the key space. They are (almost) as efficient as those of Abdalla {\it et al.} and rely on the same hardness assumptions. In addition, we obtain a solution based on Paillier's composite residuosity assumption, which was an open problem even in the case of selective adversaries. We also propose $\LWE$-based schemes that allow evaluation of inner products modulo a prime~$p$, as opposed to the schemes of Abdalla {\it et al.} that are restricted to evaluations of integer inner products of short integer vectors. We finally propose a solution based on Paillier's composite residuosity assumption that enables evaluation of inner products modulo an RSA integer $N = pq$. We demonstrate that the functionality of inner products over a prime field is very powerful and can be used to construct bounded collusion FE for all circuits.

The talk will be based on this article.

Joint work with Shweta Agrawal.

3:50pm - 5:20pm: Thomas Prest (Thales), Fast Fourier Orthogonalization

The classical Fast Fourier Transform (FFT) allows to compute in quasi-linear time the product of two polynomials, in the circular convolution ring R[x]/(x^d−1) --- a task that naively requires quadratic time. Equivalently, it allows to accelerate matrix-vector products when the matrix is circulant. In this work, we discover that the ideas of the FFT can be applied to speed up the orthogonalization process of a circulant matrix. We show that, when n is composite, it is possible to proceed to the orthogonalization in an inductive way, leading to a structured Gram-Schmidt decomposition. In turn, this structured Gram-Schmidt decomposition accelerates a cornerstone lattice algorithm: the Nearest Plane algorithm. The results easily extend to cyclotomic rings, and can be adapted to Gaussian Samplers. This finds applications in lattice-based cryptography, improving the performances of trapdoor functions.

The talk will be based on this article.

Joint work with Léo Ducas.

25.11.2015 - 26.11.2015

Topic: algorithms for hard problems on lattices and codes
Location: ENS Lyon, Monod campus.
Room: 116 (main building, level 1, South aisle).

We 25/11, 1:00pm - 3:00pm: Nicolas Gama (Inpher Switzerland and UVSQ France), Solving shortest and closest vector problems: The decomposition approach.

The talk will be based on this article.

Joint work with Anja Becker and Antoine Joux.

We 25/11, 3:30pm - 5:30pm: Ilya Ozerov (RUB), On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes

We propose a new decoding algorithm for random binary linear codes. The so-called information set decoding algorithm of Prange (1962) achieves worst-case complexity $2^{0.121n}$ . In the late 80s, Stern proposed a sort-and-match version for Prange's algorithm, on which all variants of the currently best known decoding algorithms are build. The fastest algorithm of Becker, Joux, May and Meurer (2012) achieves running time $2^{0.102n}$ in the full distance decoding setting and $2^{0.0494n}$ with half (bounded) distance decoding. In this work we point out that the sort-and-match routine in Stern's algorithm is carried out in a non-optimal way, since the matching is done in a two step manner to realize an {\em approximate matching} up to a small number of error coordinates. Our observation is that such an approximate matching can be done by a variant of the so-called High Dimensional Nearest Neighbor Problem. Namely, out of two lists with entries from $\F_2^m$ we have to find a pair with closest Hamming distance. We develop a new algorithm for this problem with sub-quadratic complexity which might be of independent interest in other contexts. Using our algorithm for full distance decoding improves Stern's complexity from $2^{0.117n}$ to $2^{0.114n}$. Since the techniques of Becker et al apply for our algorithm as well, we eventually obtain the fastest decoding algorithm for binary linear codes with complexity $2^{0.097n}$. In the half distance decoding scenario, we obtain a complexity of $2^{0.0473n}$.

The talk will be based on this article.

Joint work with Alexander May.

Th 26/11, 10:15am - 11:15am: Ludovic Perret (UPMC), Algebraic Algorithms for LWE

The Learning with Errors (LWE) problem, proposed by Regev in 2005, has become an ever-popular cryptographic primitive, due mainly to its simplicity, flexibility and convincing theoretical arguments regarding its hardness. Among the main proposed approaches to solving LWE instances --- namely, lattice algorithms, combinatorial algorithms, and algebraic algorithms --- the last is the one that has received the least attention in the literature, and is the focus of this paper. We present a detailed and refined complexity analysis of the original Arora-Ge algorithm, which reduced LWE to solving a system of high-degree, error-free polynomials. Moreover, we generalise their method and establish the complexity of applying Gr\"obner basis techniques from computational commutative algebra to solving LWE. As a result, we show that the use of Gr\"obner basis algorithms yields an exponential speed-up over the basic Arora-Ge algorithm. On the other hand, our results show that such techniques do not yield a subexponential algorithm for the LWE problem. We also apply our algebraic algorithm to the BinaryError-LWE problem, which was recently introduced by Micciancio and Peikert. We show that BinaryError-\LWE in dimension n can be solved in subexponential time given access to a quasi-linear number of samples m under a regularity assumption. We also give precise complexity bounds for BinaryError-LWE in function of the number of samples. The results in this work depend crucially on the assumption that the encountered systems have no special structure. We give experimental evidence that this assumption holds and also prove the assumptions in some special cases. Therewith, we also make progress towards proving Froberg's long-standing conjecture from algebraic geometry. The talk will be based on this article.

Joint work with Martin R. Albrecht, Carlos Cid and Jean-Charles Faugère.

Th 26/11, 1:00pm - 2:00pm: Ludovic Perret (UPMC), Algebraic Algorithms for LWE

(follow-up of previous talk)

Th 26/11, 2:30pm - 4:30pm: Léo Ducas (CWI), New directions in nearest neighbor searching with applications to lattice sieving

30.09.2015 - 01.10.2015

Topic: Lattice-based and code-based group signatures.
Location: ENS Lyon, Monod campus.
Room: 116 (main building, level 1, South aisle).

We 30/09, 2:30pm - 3:30pm: Benoît Libert (ENS Lyon), Tutorial on group signatures

The tutorial will give a self-contained description of the primitive and its security definitions for static groups. Examples of (both theoretical and practical) constructions will be given. The case of dynamic groups will be briefly outlined.

Suggested readings:

We 30/09, 4:00pm - 5:30pm: Khoa Nguyen (NTU), Group signatures from lattices: simpler, tighter, shorter, ring-based

We introduce a lattice-based group signature scheme that provides several noticeable improvements over the contemporary ones: simpler construction, weaker hardness assumptions, and shorter sizes of keys and signatures. Moreover, our scheme can be transformed into the ring setting, resulting in a scheme based on ideal lattices, in which the public key and signature both have bit-size soft-O(n log N), for security parameter n, and for group of N users. Towards our goal, we construct a new lattice-based cryptographic tool: a statistical zero-knowledge argument of knowledge of a valid message-signature pair for Boyen's signature scheme (Boyen, PKC'10), which potentially can be used as the building block to design various privacy-enhancing cryptographic constructions.

The talk will be based on this article. Joint work with San Ling and Huaxiong Wang.

Th 01/10, 10:15am - 11:15am: Khoa Nguyen (NTU), A provably secure group signature scheme from code-based assumptions

We solve an open question in code-based cryptography by introducing the first provably secure group signature scheme from code-based assumptions. Specifically, the scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise problem, and a variant of the Syndrome Decoding problem. Our construction produces smaller key and signature sizes than the existing post-quantum group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed the population of the Netherlands (approx 2^24 users). The feasibility of the scheme is supported by implementation results. Additionally, the techniques introduced in this work might be of independent interest: a new verifiable encryption protocol for the randomized McEliece encryption and a new approach to design formal security reductions from the Syndrome Decoding problem.

The talk will be based on this article. Joint work with Martianus Frederic Ezerman, Hyung Tae Lee, San Ling and Huaxiong Wang.

Th 01/10, 1:30pm - 3:00pm: Philippe Gaborit (U. Limoges), Dynamic traceable signature on lattices with non-frameability property

Traceable signature schemes were introduced in 2004 as a generalization of group signatures. In this talk we introduce the first traceable signature scheme based on lattices. Our scheme is conceptually simple and provides two other very nice features: dynamicity and non- frameability, which ensuse that the group manager can add new participants to the group and secondly, that he can not frame members of the group.

Joint work with Carlos Aguilar Melchor, Olivier Blazy and Jean-Christophe Deneuville.

Th 01/10, 3:30pm - 5:00pm: Fabrice Mouhartem (ENS Lyon), Lattice-based group signatures for dynamic groups

TBA Joint work with Benoît Libert.
Before 09/2015.