Applied Crypto Group

Thursday, July 3rd, 2025, 11:00 AM: Quang Dao (CMU)

Room MNO 1.040, Belval Campus.

Title: Toward Compositional Verification of SNARKs with Interactive Oracle Reductions

Abstract: Succinct non-interactive arguments (SNARKs) are rapidly becoming critical infrastructure for blockchain and privacy applications. However, bugs in SNARK specifications and implementations are pervasive, highlighting the need for rigorous, end-to-end formal verification—a daunting task given the size and complexity of these protocols.

In this talk, I will present ongoing work on ArkLib, an open-source Lean library for formalizing and verifying SNARK constructions. ArkLib leverages Interactive Oracle Reductions (IORs), a recent abstraction that unifies reasoning about SNARK building blocks—such as polynomial IOPs and commitment schemes - within a single framework. By decomposing existing proof systems into a series of IORs between relations, ArkLib enables compositional specifications and security proofs: we can verify components in isolation and systematically lift these guarantees to full protocols.

I will share initial results on verifying the sum-check protocol with the above approach, and discuss ongoing efforts toward the full Spartan SNARK. Looking ahead, I will outline how Lean can enable large-scale, collaborative verification of cryptography, and what challenges remain to make this vision a reality.

Wednesday, June 25th, 2025, 11:00 AM: Barry van Leeuwen (KU Leuven)

Room MNO 1.010, Belval campus.

Title: FHEW and FINAL, The Underdog Story

Abstract: Over the past decade or so, Fully Homomorphic Encryption (FHE) has grown from a theoretical possibility to a practical inevitability. However, despite the existence of 4 "main" modern protocols: TFHE, CKKS, FHEW, and FINAL, most implementations in practice are done using only TFHE and CKKS. For a long time FHEW (and the NTRU-based FINAL) have struggled to get their feet on the ground when it comes to practical viability due to the complexity of the algorithms and the required compute power for their bootstrapping schemes. These schemes offer significant benefits compared to TFHE and CKKS which would make them prime candidates for large scale deployments if they can be made more efficient. In this talk we will be looking at these underdogs and modern advancements which have reinvigorated the interest in these schemes, as well as some of the troubles that FHE has yet to overcome to see mass adaptation in our modern society.

Wednesday, June 11th, 2025, 2:00 PM: Ilaria Chillotti (Desilo)

Room MNO 1.020, Belval campus.

Title: FHE - some recent results and new directions

Abstract: After a general introduction on existing FHE schemes, their leveled operations and bootstrapping, I will briefly present a recent result on TFHE. I will then talk about FHE applications and do a demo on how to use the DESILO FHE library to build a practical use case. I will conclude with some new directions for FHE.

Tuesday, April 22nd, 2025, 2:00 PM: Antonio Guimaraes (IMDEA)

Room MNO 1.020, Belval campus.

Title: Towards Practical Verifiable Homomorphic Encryption

Abstract: Homomorphic encryption (HE) enables a variety of privacy-preserving technologies by allowing computation to be performed directly over encrypted data. By itself, however, it provides no means of verifying whether an untrusted party performed some homomorphic computation correctly. Verifiable computation (VC) allows one to achieve such capability, but combining VC and HE is an intricate task for which few solutions are known to result in concretely practical performance. This talk covers two of the latest developments in Verifiable Homomorphic Encryption. In the first part, we introduce HE-IOPs [ACGS, Asiacrypt 24, eprint 2023/1949], a novel proof component construction that enables efficient VC-HE by homomorphically evaluating part of a proof system. Contrary to traditional approaches that work by proving ciphertext operations, an HE-IOP enables proofs for the computation happening in the underlying plaintext. In this way, many expensive HE operations (e.g., key switching, rescaling, and bootstrapping) become transparent and add no overhead to the proof. Conversely, HE-IOPs require HE schemes capable of efficiently providing Field arithmetic, notably excluding approximate schemes such as CKKS. In the second part of this talk, we go back to the traditional approaches and address the main challenges for providing efficient Verifiable Computation for Approximate Homomorphic Encryption Schemes [CCCFGS 25, eprint 2025/286]. We start by introducing a proof-friendly version of CKKS, which addresses most of the arithmetic incompatibilities between (full-RNS) CKKS and proof systems in a near-optimal way. Then, we introduce several proof components specifically crafted to work directly over the polynomial rings required by our proof-friendly CKKS. We implement and benchmark all components we introduce or improve, showing they can enable practical performance for verifiable CKKS and, more generally, RNS-based HE schemes.

Tuesday, October 8th, 2024, 11:00 AM: Marie Bolzer (INRIA Nancy)

Room MNO 1.020, Belval campus.

Title: Lightweight (AND, XOR) Implementations of Quadratic Vectorial Boolean Functions

Abstract : In symmetric cryptography, reducing the cost of iterated block ciphers is a significant area of focus. It is an important requirement for cryptographic functions that the implementation must be protected against side-channel attacks. This results in the S-box being the costliest part of block ciphers. The main objective in S-box optimisation is therefore to reduce the number of AND gates. A secondary objective is to reduce the AND depth, which determines the latency of hardware-protected implementations. In this presentation, we will introduce a new method for finding such implementations for quadratic functions up to dimension 9.

Tuesday, June 4th, 2024, 11:30 AM: Nicolas Bon (CryptoExperts)

Room MNO 1.040, Belval campus.

Title: Homomorphic Evaluation of Boolean Functions

Abstract: Fully Homomorphic Encryption (FHE) is a cryptographic technique that enables a server to perform computations on encrypted data without learning any information about it. After a general overview of the technology and the state of the art, we will delve into TFHE, one of the most efficient encryption schemes currently available. Subsequently, we will introduce a novel method for evaluating boolean functions more efficiently with TFHE and demonstrate the advantages of our technique through concrete examples of homomorphic evaluations of cryptographic primitives.

Thursday, May 16th, 2024, 2:00 PM: Thomas Prest (PQShield)

Room MNO 1.010, Belval campus.

Title: Threshold Raccoon: Practical Threshold Signatures from Standard Lattice Assumptions

Abstract: Threshold signatures improve both availability and security of digital signatures by splitting the signing key into N shares handed out to different parties. Later on, any subset of at least T parties can cooperate to produce a signature on a given message. While threshold signatures have been extensively studied in the pre-quantum setting, they remain sparse from quantum-resilient assumptions.

We present the first efficient lattice-based threshold signatures with signature size 13 KiB and communication cost 40 KiB per user, supporting a threshold size as large as 1024 signers. We provide an accompanying high performance implementation. The security of the scheme is based on the same assumptions as Dilithium, a signature recently selected by NIST for standardisation which, as far as we know, cannot easily be made threshold efficiently.

All operations used during signing are due to symmetric primitives and simple lattice operations; in particular our scheme does not need heavy tools such as threshold fully homomorphic encryption or homomorphic trapdoor commitments as in prior constructions. The key technical idea is to use one-time additive masks to mitigate the leakage of the partial signing keys through partial signatures.

Thursday, March 21st, 2024, 2:00 PM: Elias Suvanto (FHELab and Uni Luxembourg)

Room MNO 1.030, Belval campus.

Title: Attacks Against the IND-CPA-D Security of FHE Schemes

Abstract: Fully Homomorphic Encryption enables the evaluation of arbitrary circuits over encrypted data while maintaining the confidentiality of the underlying messages. It greatly enhances functionality but also comes with security challenges for some applications like Threshold FHE. While the standard IND-CPA security is sufficient against honest but curious adversaries, a stronger security notion called IND-CPA-D is required when the adversary can learn some decryption of ciphertexts obtained through honest encryptions and homomorphic evaluations. We present how such non-malicious adversary can recover the secret key of some popular exact and approximate FHE schemes, discuss mitigation strategies for such attacks and explore the close relationship between IND-CPA-D security and correctness. We successfully experimented our key-recovery-D attacks using the public API of libraries such as TFHE-rs and OpenFHE for ind-cpa secure parameters and demonstrate how to attack Threshold FHE schemes like Noah's Ark.

Thursday, March 14th, 2024, 11:00 AM: Jiayi Kang (KU Leuven)

Room MNO 1.020, Belval campus.

Title: Revisiting Oblivious Top-k Selection with Applications to Secure kNN Classification

Abstract: An oblivious Top-k algorithm selects the k smallest (or largest) elements from d elements while ensuring the sequence of operations and memory accesses do not depend on the input. In 1969, Alekseev proposed an oblivious Top-k algorithm with complexity O(d log^2 k), which was later improved by Andrew Yao in 1980 for small, constant k << sqrt(d). In this work, we will revisit these methods and propose another improvement of Alekseev's method independent of Yao's. This construction outperforms for large k = Omega(sqrt(d)). In addition, we propose a combined network to take advantage of both Yao's and our technique to achieve the best concrete performance, in terms of the number of comparators, for any k.

To demonstrate the efficiency of our combined Top-k network, we present a secure non-interactive k-nearest neighbors classifier using homomorphic encryption as an application. Compared with the work of Zuber and Sirdey (PoPETS~2021) where oblivious Top-k was realized with complexity O(d^2), our experimental results show a speedup of up to ~47 times (not accounting for difference in CPU) for d = 1000.

Tuesday, March 5th, 2024, 2:00 PM: Malika Izabachène

Room MSA 2.220, Belval campus.

Title: Plug-and-play sanitization for TFHE

Abstract: Fully Homomorphic Encryption allows evaluating an arbitrary function over encrypted data while preserving the privacy of the messages. This property has found numerous applications especially in the case where one would like to process data stored in the cloud. In this talk, we will focus on the privacy of the algorithm processed by the cloud. Fully Homomorphic Encryption sanitation guarantees that, all the information about how a ciphertext has been obtained is destroyed, except the associated message. In particular, it is impossible to say which computation has been processed in order to obtain a given ciphertext, even knowing the secret key. We will see how to build a sanitization algorithm from the TFHE bootstrapping (Asiacrypt 2016) and how it compares to the previous soak-and-spin strategy from Ducas and Stehlé (Eurocrypt 2016).

This is joint work with Florian Bourse.

Thursday, January 11th, 2024, 2:00 PM: Maxime Plançon (IBM Zurich)

Room MNO 1.040, Belval campus.

Title: Exploiting Algebraic Structures in Probing Security

Abstract: The so-called omega-encoding, introduced by Goudarzi, Joux and Rivain (Asiacrypt 2018), generalizes the commonly used arithmetic encoding. By using the additional structure of this encoding, they proposed a masked multiplication gadget (GJR) with quasilinear (randomness and operations) complexity. A follow-up contribution by Goudarzi, Prest, Rivain and Vergnaud in this line of research appeared in TCHES 2021. The authors revisited the aforementioned multiplication gadget (GPRV), and brought the IOS security notion for refresh gadgets to allow secure composition between probing secure gadgets.

In this paper, we propose a follow up on GPRV, that is, a region-probing secure arithmetic circuit masked compiler. Our contribution stems from a single Lemma, linking algebra and probing security for a wide class of circuits, further exploiting the algebraic structure of omega-encoding, and the extension field structure of the underlying field F. On the theoretical side, we propose a security notion for omega-masked circuits which we call Reducible-To-Independent-K-linear (RTIK). When the number of shares d is less than or equal to the degree k of F, RTIK circuits achieve region-probing security. Moreover, RTIK circuits may be composed naively and remain RTIK. We also propose a weaker version of IOS, which we call KIOS, for refresh gadgets. This notion allows to compose RTIK circuits with a randomness/security tradeoff compared to the naive composition.

To substantiate our new definitions, we also provide examples of competitively efficient gadgets verifying the latter weaker security notions. Explicitly, we give 1) two refresh gadgets that uses d-1 random field elements to refresh a length d encoding that is KIOS but not IOS, and 2) a multiplication gadget with bilinear multiplication complexity d^(log 3) that uses d random elements per run. Our compiler outperforms ISW asymptotically, but for our security proofs to hold, we do require that the number of shares d is less than or equal to the degree of F as an extension, so that there is sufficient structure to exploit.

Wednesday, September 27th, 2023, 3:00 PM: Ben Curtis (Zama)

Room MSA 4.410, Belval Campus

Title: Introduction to TFHE and applications

Abstract: In this talk, we will discuss the TFHE scheme (Chillotti, Gama, Georgieva, Izabachene) from the ground-up. In particular, we will discuss the capabilities of the TFHE scheme and outline how these can be leveraged in practice. After this, we will look at some applications which have been implemented using TFHE.

Thursday, September 21st, 2023, 3:00 PM: Mélissa Rossi (ANSSI)

Room MNO 1.020, Belval Campus

Title: High-Order Masking of Lattice Signatures in Quasilinear Time

Abstract: In recent years, lattice-based signature schemes have emerged as the most prominent post-quantum solutions, as illustrated by NIST's selection of Falcon and Dilithium for standardization. Both schemes enjoy good performance characteristics, and are especially fast. However, their efficiency dwindles in the presence of side-channel protections, in particular masking, one of the strongest generic side-channel countermeasures. Masking at order d-1 consists in randomizing any secret-dependent intermediate variable into d shares. More generally, existing lattice signatures have algorithmic features that are expensive to mask, making them quickly prohibitive for many practical use cases such as embedded systems. In this paper, we turn the problem upside-down: we design a lattice-based signature scheme that is always masked, and we optimize the masked efficiency as a function of the number of shares. Our design avoids costly operations such as conversions between arithmetic and Boolean encodings (A2B/B2A), masked rejection sampling, and does not require the use of masked SHAKE or other symmetric primitives. The resulting scheme is called Raccoon and belongs to the family of Fiat-Shamir with aborts lattice-based signatures. Raccoon is the first lattice-based signature whose running time scales quasilinearly with the increase of the masking order. In other words, the key generation and signature algorithm's running time only pay a O(d log(d)) multiplicative overhead with d being the number of shares. In contrast, prior schemes incurred quadratic overheads. Our portable C implementation confirms that Raccoon's performance is comparable to other state-of-the-art signature schemes, with the exception that increasing the number of shares has only a near-linear effect on its latency. We also present an FPGA implementation and perform a leakage assessment on it.

Thursday, June 1st, 2023, 2:00 PM: Hilder Vitor Lima Pereira (KU Leuven)

Room MSA 2.400, Belval Campus

Title: Amortized bootstrapping revisited: Simpler, asymptotically-faster, implemented

Abstract: The main operation in any fully homomorphic encryption (FHE) scheme is the bootstrapping, which reduces the noise of a ciphertext and allows us to evaluate arbitrary circuits on encrypted data. With respect to the bootstrapping, one can separate FHE schemes in two groups: (1.) schemes that pack several messages into "slots" of a large ciphertext and have slow bootstrapping procedures; (2.) schemes whose ciphertexts encrypt one single message and that have lightweight and fast bootstrapping. The first group requires large parameters, which means that the security is based on lattice problems with superpolynomial approximation factors. The second group requires very small parameters, but one has to use the bootstrapping after every gate when evaluating a circuit.

Micciancio and Sorrel (ICALP 2018) proposed an amortized bootstrapping that tries to combine the best of both worlds: it packs several messages into one single ciphertext so that one bootstrapping refreshes many messages at once, yet the cost of the bootstrapping is cheap, with sublinear homomorphic operations per message, and the security is based on worst-case lattice problems with polynomial approximation factor.

However, although their bootstrapping algorithm represents an important theoretical advance, it has basically no practical impact, due to its high cost hidden in the asymptotic notation. In this work, we propose a simpler amortized bootstrapping algorithm, we improve the number of homomorphic operations per refreshed message from O(3^rho*n^{1/rho}*log n) to O(rho*n^{1/rho}) and the noise growth from O(n^{2 + 3*rho}) to O(n^{1 + rho}), obtaining thus the first amortized bootstrapping algorithm that was practical enough to be implemented and even to have running times comparable to existing bootstrapping methods.

Tuesday, March 7th, 2023, 2:00 PM: Clement Hoffmann (UCL)

Room MNO 1.040, Belval Campus

Title: How costly is it to protect the CRYSTALS post-quantum finalists against side-channel attacks ?

Abstract: The side-channel cryptanalysis of post-quantum schemes has been a topic of intense activity over the last years. Many attacks relying on Simple Power Analysis (SPAs) and/or Differential Power Analysis (DPAs) have been shown to be powerful, targeting various parts of post-quantum schemes. Now that the NIST PQC process reaches its final phase, the two schemes developed by the CRYSTALS team appear like probable winners, one in the standardization for a Key Encapsulation Mechanism and the other for a Digital Signature protocol. In this talk, I will discuss the issues that are raised while trying to implement these schemes securely against side-channel. With Kyber, we evaluate the (high) cost of preventing attacks with masking and the extent to which different parts of an implementation could benefit from varying security levels using shortcut formulas. We also discuss tweaks to improve the situation and enable a better leveling of the countermeasures. With Dilithium, we use a different approach by classifying intermediate computations according their physical security requirements. This allows us to identify which parts of Dilithium must be protected against DPAs, which parts must be protected against SPAs and which parts can leak in an unbounded manner. This analysis allows us to provide an efficient secured implementation which offers the choice for a trade-off security vs. performance. This implementation also put forward that the randomized version of Dilithium can lead to significantly more efficient implementations (than its deterministic version) when side-channel attacks are a concern.

This talk is based on the two following papers:

Melissa Azouaoui, Olivier Bronchain, Clement Hoffmann, Yulia Kuzovkova, Tobias Schneider, Francois-Xavier Standaert - Systematic study of decryption and re-encryption leakage: the case of kyber - COSADE 2022 - https://eprint.iacr.org/2022/036.pdf

Melissa Azouaoui, Olivier Bronchain, Gaetan Cassiers, Clement Hoffmann, Yulia Kuzovkova, Joost Renes, Markus Schonauer, Tobias Schneider, Francois-Xavier Standaert, Christine van Vredendaal - Leveling Dilithium against Leakage: Revisited Sensitivity Analysis and Improved Implementations - preprint - https://eprint.iacr.org/2022/1406.pdf

Wednesday, September 28th, 2022, 11:00 AM: Robin Köstler (University of Freiburg, Germany)

Room MNO 1.030, Belval Campus

A survey on modern bootstrapping for fully homomorphic encryption (FHE)

Abstract: we present a survey on the mathematical details of FHE, focusing on the technique of blind rotations that is applicable to many nowadays used schemes (CKKS, BFV, BGV). We also describe an implementation based on BFV encoding, in order to provide an introduction to bootstrapping.

Source: eprint.iacr.org/2021/691.pdf

Thursday, March 24th, 2022, 11:00 AM: Benoit Cogliati (CISPA, Germany)

Room MNO 1.030, Belval Campus

Title: Mirror Theory and Cryptography

Abstract: In symmetric cryptography, one of the most common proof strategy is to rely on the H coefficients technique to transform a cryptographic problem (typically a distinguishing experiment) into a combinatorial problem. In particular, one often has to lower bound the number of solutions of some system of linear equalities that also satisfy some distinctness conditions. The study of such systems has been systematized by Jacques Patarin and dubbed Mirror Theory. In this talk, we present the first complete and streamlined proof of a fundamental Mirror Theory result, dubbed the Pi+Pj theorem for any ximax, along with a few cryptographic applications. In more details, we prove that the number of tuples of n-bit strings (P1,...,Pq) that are pairwise distinct and satisfy a system of equations of the form Pi xor Pj = lambda(i,j) is either 0, or greater than the average over all n-bit strings lambda(i,j).

Tuesday, March 8th, 2022, 2:00 PM: Gaëtan Cassiers (UCL, Belgium)

Room MNO 1.030, Belval Campus

Title: Composable masking schemes for side-channel security: the probe isolation approach.

Abstract: Masking is a well-known countermeasure against side-channel attacks. Over the last decade, the secure and efficient masking of block cipher implementations against side-channel attacks has been shown to be a difficult task. It is common practice to analyze the security of masking schemes in the probing model, or its robust variant which takes into account physical effects such as glitches and transitions. Such analysis in the (robust) probing model allows to avoid flaws in the countermeasure that are difficult to detect with other means such as leakage assessment techniques. In particular, the (robust) probing model allows to analyze complex computations such as block cipher evaluations or even asymetric cryptographic operations. Such analyzes are however challenging, since security in the probing model is not composable: putting probing-secure components together may break their security. In this talk, I will introduce the Probe-Isolating Non-Interference (PINI) approach to solve the composition problem. This approach is versatile and can be used in many contexts, from the implementation in hardware of block ciphers (where security against glitches and transitions is required) to implementation of lattice-based key ecapsulation mechanisms, where masking in multiple fields is required.

Wednesday, November 10th, 2021, 11:00 AM: Pierrick Méaux (University of Luxembourg)

Room MNO 1.030, Belval Campus

Title: Investigating the improved filter permutator paradigm and connected topics.

Abstract: In this talk I will present the improved filter permutator (IFP), a streamcipher paradigm designed for hybrid homomorphic encryption. After recalling the motivation behind hybrid homomorphic encryption and IFP, I will introduce the recent outcomes related to this construction. First, I will talk about the security of IFP, homomorphic evaluation of Boolean functions and efficiency of IFP. Then, I will focus on outcomes in the domain of Boolean functions: determination of the cryptographic parameters of two homomorphic-friendly families of Boolean functions, fast algebraic immunity of symmetric functions, and algebraic immunity of direct sums. Finally, I will get into the connection between IFP and local pseudorandom generators (PRG), focusing on the recent advances on the minimal locality of a secure local PRG.

Tuesday, September 15th, 2020, 11:00 AM: François Gérard (ULB, Belgium)

Room MSA 3.220, Belval Campus

Title: Lattice-based cryptography: Implementations and side-channel countermeasures

Abstract: The third round of the NIST post-quantum standardization project has just started. Now that the candidates have made a more or less definitive choice of design and parameters, only minor tweaks to the schemes should appear in the future and it is time to tackle more practical issues. Performances being mostly critical on embedded devices, cheap microcontrollers are a common target for optimized implementations. In the first part of the talk, we will describe how to implement efficiently some lattice-based schemes and discuss some optimizations on ARM Cortex-M4. Embedded devices tend also to be more vulnerable to side-channel attacks. Thus, implementing countermeasures and assessing side-channel resistance of the candidates will be of utmost importance for the later phases of the standardization process. In the second part of the talk, we will discuss a high order masking scheme for a lattice-based signature qTESLA that has been ejected after round 2 but has a design very similar to the round 3 candidate Dilithium.

Tuesday, February 25th, 2020, 10:00 AM: Claire Delaplace (Ruhr University Bochum, Germany)

Room MNO 1.030, Belval Campus

Title: Improved Low-Memory Subset Sum and LPN Algorithms via Multiple Collisions

Abstract: For enabling post-quantum cryptanalytic experiments on a meaningful scale, there is a strong need for low-memory algorithms. We show that the combination of techniques from representations, multiple collisions finding, and the Schroeppel-Shamir algorithm leads to improved low-memory algorithms. For random subset sum instances $(a_1, \ldots, a_n,t)$ defined modulo $2^n$, our algorithms improve over the Dissection technique for small memory $M < 2^{0.02n}$ and in the mid-memory regime $2^{0.13n} < M < 2^{0.2n}$. An application of our technique to LPN of dimension $k$ and constant error $p$ yields significant time complexity improvements over the Dissection-BKW algorithm from Crypto 2018 for all memory parameters $M< 2^{0.35 \frac{k}{\log k}}$. This is joined work with Andre Esser and Alexander May, published at IMACC 2019.

Thursday, January 9th, 2020, 10:00 AM: Ilaria Chillotti (KU Leuven)

Room MNO 1.030, Belval Campus

Title: Multi-Key Homomophic Encryption from TFHE (joint work with Hao Chen and Yongsoo Song).

Abstract: In this paper, we propose a Multi-Key Homomorphic Encryption (MKHE) scheme by generalizing the low-latency homomorphic encryption by Chillotti et al. (ASIACRYPT 2016). Our scheme can evaluate a binary gate on ciphertexts encrypted under different keys followed by a bootstrapping. The biggest challenge to meeting the goal is to design a multiplication between a bootstrapping key of a single party and a multi-key RLWE ciphertext. We propose two different algorithms for this hybrid product. Our first method improves the ciphertext extension by Mukherjee and Wichs (EUROCRYPT 2016) to provide better performance. The other one is a whole new approach which has advantages in storage, complexity, and noise growth. Compared to previous work, our construction is more efficient in terms of both asymptotic and concrete complexity. The length of ciphertexts and the computational costs of a binary gate grow linearly and quadratically on the number of parties, respectively. We provide experimental results demonstrating the running time of a homomorphic NAND gate with bootstrapping. To the best of our knowledge, this is the first attempt in the literature to implement an MKHE scheme.

Monday, December 2nd, 2019, 14:00: Romain Gay (University of California, Berkeley)

Room MNO 1.030, Belval Campus

Title: Functional Encryption: a bottom up approach

Abstract: This talk will present recent advances in Functional Encryption, a cryptographic object that allows users to perform selective computation on the encrypted data. Namely, in a Functional Encryption scheme, it is possible to derive a key associated with a function f, which allows users to recover from an encryption of the message m, the value f(m), and nothing else. We will see a series of work that aims at building Functional Encryption from the ground up; that is, practical schemes that rely on mathematically sound assumptions, for restricted classes of functions that we show have interesting applications. We will present the work of [BCFG18], which builds the first public-key Functional Encryption that supports the generation of keys associated with degree-2 polynomials, with succinct ciphertexts. We will show how such schemes can be used to perform private inference, as done in [RDGPP19]. Finally, we will talk about decentralizing Functional Encryption, as done in [CDGPP18].

[BCFG18]: https://eprint.iacr.org/2017/151 [RDGPP19]: https://arxiv.org/abs/1905.10214 [CDGPP18]: https://eprint.iacr.org/2017/989

Thursday, November 21st, 2019, 10:00 AM: Changmin Lee (ENS Lyon)

Room MNO 1.030, Belval Campus

Title: Cryptanalysis of FRS Obfuscation based on the CLT13 Multilinear Map

Abstract: We present classical polynomial-time attacks against the FRS branching program obfuscator of Fernando-Rasmussen-Sahai (Asiacrypt 17) (with one zerotest parameter), which is robust against all known classical cryptanalyses on obfuscators, when instantiated with the CLT13 multilinear map. To do that 1) We (heuristically) reproduce a new zerotest parameter from the original one and recover a secret message space. The new zerotest parameter mitigates parameter constraints of the message space recovering algorithm proposed by Coron and Notarnicola (Asiacrypt'19), so it enables us to directly apply the algorithm to the FRS obfuscation. 2) We propose two cryptanalyses of the FRS obfuscation based on the recovered message space. One analysis enables to obtain all secret elements of CLT13, but it requires extra parameter constraints. On the other hand, the other analysis shows that there exist two functionally equivalent programs such that their obfuscated programs are computationally distinguishable. Thus, the FRS scheme does not satisfy the desired security without any additional constraints.

Monday, November 11th, 2019, 10:00 AM: Benjamin Wesolowski (CWI)

Room MNO 1.030, Belval Campus

Title: Discrete logarithms in quasi-polynomial time in finite fields of small characteristic

Abstract: We prove that the discrete logarithm problem can be solved in quasi-polynomial expected time in the multiplicative group of finite fields of fixed characteristic. In 1987, Pomerance proved that this problem can be solve in expected subexponential time L(1/2). The following 30 years saw a number of heuristic improvements, but no provable results. The quasi-polynomial complexity has been conjectured to be reachable since 2013, when a first heuristic algorithm was proposed by Barbulescu, Gaudry, Joux, and Thome. We prove this conjecture, and more generally that this problem can be solved in the field of cardinality $p^n$ in expected time $(pn)^{2 log_2(n)+O(1)}$.

Friday, May 11th, 2018, 10:30 AM: Claire Delaplace (University of Rennes, France)

Room MNO-E03-25-110, Belval Campus.

Title: Revisiting and Improving Algorithms for the 3XOR Problem

Abstract: The 3SUM problem is a well-known problem in computer science and many geometric problems have been reduced to it. We study the 3XOR variant which is more cryptologically relevant. In this problem, the attacker is given black-box access to three random functions $F$, $G$ and $H$ and she has to find three inputs $x$, $y$ and $z$ such that $F(x) \oplus G(y) \oplus H(z) = 0$. The 3XOR problem is a difficult case of the more-general k-list birthday problem.

Wagner's celebrated k-list birthday algorithm, and the ones inspired by it, work by querying the functions more than strictly necessary from an information-theoretic point of view. This gives some leeway to target a solution of a specific form, at the expense of processing a huge amount of data. However, to handle such a huge amount of data can be very difficult in practice. This is why we first restricted our attention to solving the 3XOR problem for which the total number of queries to $F$, $G$ and $H$ is minimal. If they are $n$-bit random functions, it is possible to solve the problem with roughly $O(2^{n/3})$ queries. In this setting, the folklore quadratic algorithm finds a solution after $O(2^{2n/3})$ operations.

We present a 3XOR algorithm that generalizes an idea of Joux, with complexity $O(2^{2n/3} / n)$ in time and $O(2^{n/3})$ in space. This algorithm is practical: it is up to 3 times faster than the quadratic algorithm. Furthermore, we show that it is possible to adapt this algorithm to any number of queries, so that it will always be at least as good as, if not better than, Wagner's descendants in the same settings. We also revisit a 3SUM algorithm by Baran-Demaine-Patrascu which is asymptotically $n^2 / \log^2 n$ times faster than the quadratic algorithm when adapted to the 3XOR problem, but is otherwise completely impractical.

This is a joint work with Pierre-Alain Fouque and Charles Bouillaguet.

April 13th, 2018, 11:00 AM: Benoit Cogliati

Room MNO-E03-25-110, Belval Campus TItle: Provable security in symmetric cryptography

Abstract: Provable security is an essential part of both symmetric and public-key cryptography. Indeed, security proofs can increase confidence in the resistance of an algorithm against various types of attacks and justify its soundness. Moreover, theorems guide the choice of the security parameters in applications. In this context, tight security proofs are essential, since they prevent the use of unnecessarily high values for those parameters. In this talk, I will start by giving an overview of the indistinguishability notion and of the main theoretical models that are considered in symmetric cryptography. I will then illustrate these notions by presenting several results on the design of tweakable block ciphers, and on the construction of provably secure MACs based on block ciphers and tweakable block ciphers.

November 22nd, 2017, 10:30 AM: Tancrede Lepoint

Room MNO-E03-25-110, Belval Campus Title: Post-Quantum Cryptography using Module Lattices

Abstract: Recent advances in quantum computing and the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digital-signature, encryption, and key-establishment protocols, spurred on the design and analysis of many post-quantum cryptographic schemes. One of the most efficient quantum-resilient alternatives for the above basic primitives is that of lattice cryptography.

Many lattice cryptography schemes are based on the learning-with-error problem over a ring. Past works have described digital signature schemes, encryption schemes, and key encapsulation mechanisms in one of two ways. Either they set the ring as Z_q[x]/(x^n+1) or as Z_q^n. The former choice results in schemes based on the hardness of the Ring-LWE and Ring-SIS problems (or the NTRU problem), while the latter choice of parameters results in schemes based on the LWE and SIS problems. In this talk, we consider the general case of setting the ring to (Z_q[x]/(x^d+1))^m, and design schemes based on the Module-LWE and Module-SIS hardness assumption. First, we explain how module lattices enable to design cryptographic primitives that are not only simple to implement securely, conservatively designed, and have a small memory footprint, but are modular, i.e., easily enable to vary security while keeping the same core operations. Then, we present CRYSTALS, the Cryptographic Suite for Algebraic Lattices submitted to the NIST call for post-quantum standards, that includes Kyber (Bos et al., 2017), a key encapsulation mechanism, and Dilithium (Ducas et al., 2017), a digital signature.

LACS Crypto Day, June 13th, 2017, room MSA 4.410, Belval campus