Home

Publications

Research projects

Group meetings

Teaching

Contact

Applied Crypto Group

LACS Seminar, May 11th, 2018, 10:30 AM, room MNO-E03-25-110, Belval Campus.

Claire Delaplace (University of Rennes, France). 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.

LACS Seminar, April 13th, 2018, 11:00 AM, room MNO-E03-25-110, Belval Campus.

Benoit Cogliati. 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.

LACS Seminar, November 22nd, 2017, 10:30 AM, room MNO-E03-25-110, Belval Campus.

Tancrede Lepoint. 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

• 10:00: Aleksei Udovenko. On division property cryptanalysis.
• 10:30: Dmitry Khovratovich. BIP32-Ed25519: Hierarchical Deterministic Keys over a Non-linear Keyspace.
• 11:00: Benoit Cogliati: Security proofs for symmetric-key constructions
• 11:30: Jun Wang. vdNets: Applying Very Deep Neural Networks to Encrypted Data

  Abstract: Very deep neural networks have recently demonstrated start-of-the-art accuracy on very complex visual and speech recognition tasks. To those problems which involve sensitive data, e.g. medicine and finance, the privacy and security requirements may prevent the use of cloud-based machine learning service. To address this issue, a number of works have explored how to apply machine learning models, including neural networks, to encrypted data. Unfortunately, such works either focus on conventional machine learning models or shallow neural networks. In this paper, we describe the design and implementation of a secure multiparty computation (SMC) system called vdNets which allows performing a learned very deep and large neural network on encrypted data. We first demonstrate the ability of vdNets by applying GoogLeNet convolutional neural network \cite{szegedy2015going} to encrypted data, and analyze its computation and communication cost. GoogLeNet has 22 layers (approximately 100 independent sub-layers) and overall 1.5 billion multiply-adds at inference time. We further discuss the bottleneck of vdNets and introduce different methods to eliminate or alleviate it. Our results provide compelling evidence that an SMC approach to very deep and large neural networks is worth pursuing.

• 14:00: Moon Sung Lee. Attacks on Multilinear Maps
• 14:30: Vincenzo Iovino. The Simplest Oblivious Transfer Protocol.
• 15:00: Alfredo Rial Duran. UC Commitments for Modular Protocol Design and Applications to Revocation and Attribute Tokens

  Abstract: Complex cryptographic protocols are often designed from simple cryptographic primitives, such as signature schemes, encryption schemes, verifiable random functions, and zero-knowledge proofs, by bridging between them with commitments to some of their inputs and outputs. Unfortunately, the known universally composable (UC) functionalities for commitments and the cryptographic primitives mentioned above do not allow such constructions of higher-level protocols as hybrid protocols. Therefore, protocol designers typically resort to primitives with property-based definitions, often resulting in complex monolithic security proofs that are prone to mistakes and hard to verify.

  We address this gap by presenting a UC functionality for non-interactive commitments that enables modular constructions of complex protocols within the UC framework. We also show how the new functionality can be used to construct hybrid protocols that combine different UC functionalities and use commitments to ensure that the same inputs are provided to different functionalities.

  We further provide UC functionalities for attribute tokens and revocation that can be used as building blocks together with our UC commitments. As an example of building a complex system from these new UC building blocks, we provide a construction (a hybrid protocol) of anonymous attribute tokens with revocation. Unlike existing accumulator-based schemes, our scheme allows one to accumulate several revocation lists into a single commitment value and to hide the revocation status of a user from other users and verifiers.

  Co-authors: Jan Camenisch, Maria Dubovitskaya.