seminar (2021-2022)

Monday, Jun 27, 2022 - 11:15 - ENS, Amphi Rataud (!!)

Fabien Laguillaumie

Efficient CCA Timed Commitments in Class Groups.

(Parisian Cryptography Seminar)

Timed commitments [Boneh and Naor, CRYPTO 2000] are the timed analogue of standard commitments, where the commitment can be non-interactively opened after a pre-specified amount of time passes. Timed commitments have a large spectrum of applications, such as sealed bid auctions, fair contract signing, fair multi-party computation, and cryptocurrency payments. Unfortunately, all practical constructions rely on a (private-coin) trusted setup and do not scale well with the number of participants. These are two severe limiting factors that have hindered the widespread adoption of this primitive.

In this work, we set out to resolve these two issues and propose an efficient timed commitment scheme that also satisfies the strong notion of CCA-security. Specifically, our scheme has a transparent (i.e. public-coin) one-time setup and the amount of sequential computation is essentially independent of the number of participants. As a key technical ingredient, we propose the first (linearly) homomorphic time-lock puzzle with a transparent setup, from class groups of imaginary quadratic order. To demonstrate the applicability of our scheme, we use it to construct a new distributed randomness generation protocol, where n parties jointly sample a random string. Our protocol is the first to simultaneously achieve (1) high scalability in the number of participants, (2) transparent one-time setup, (3) lightning speed in the optimistic case where all parties are honest, and (4) ensure that the output random string is unpredictable and unbiased, even when the adversary corrupts (n-1) parties. To substantiate the practicality of our approach, we implemented our protocol and our experimental evaluation shows that it is fast enough to be used in practice. We also evaluated a heuristic version of the protocol that is at least 3 orders of magnitude more efficient both in terms of communication size and computation time. This makes the protocol suitable for supporting hundreds of participants.

Monday, Jun 27, 2022 - 10:00 - ENS, Amphi Rataud (!!)

Geoffroy Couteau

Pseudorandom correlation generators - constructions and applications

(Parisian Cryptography Seminar)

In this talk, I will survey recent advances in the construction of pseudorandom correlation generators (PCG). A PCG generates a pair of short correlated seeds which can be locally stretched into long pseudorandom instances of a target correlation. Secure sources of random correlations are often used in secure computation, since they enable the use of very efficient MPC protocols in the preprocessing model. A PCG provides a silent way to generate such correlations, following a one-time short interaction. I will cover the basic principles underlying all modern constructions of PCGs, and explain the challenges that arise along the way. I will also survey some more advanced constructions of (variants of) PCGs and discuss their applications.

Tuesday, Jun 7, 2022 - 10:30 - ENS, Salle Simone Weil (!!)

Hoeteck Wee

Breaking the sqrt(N) Barrier in Pairing-Based Broadcast Encryption

(Parisian Cryptography Seminar)

We present the first pairing-based ciphertext-policy attribute-based encryption (CP-ABE) scheme for the class of degree 3 polynomials with compact parameters: the public key, ciphertext and secret keys comprise O(n) group elements, where n is input length for the function. As an immediate corollary, we obtain a pairing-based broadcast encryption scheme for N users with O(N^{1/3})-sized parameters, breaking the long-standing sqrt{N} barrier for pairing-based broadcast encryption. All of our constructions achieve adaptive security against unbounded collusions, and rely on the (bilateral) $k$-Lin assumption in prime-order bilinear groups.

Monday, May 16, 2022 - 11:45 - ENS, Salle des Actes (!!)

Marine Minier

Differential Analysis of a Cipher using Constraint Programming

(Parisian Cryptography Seminar)

The aim of this presentation is to show the problems raised by modeling a differential attack on a given cipher. The main obstacle lies on the difficulty of correctly modeling the XOR operator that increases the size of the search tree. For this, we will first use high-level the language Minizinc and a SAT solver then the constraint programming language written in Java, Choco.

Monday, May 16, 2022 - 10:30 - ENS, Salle des Actes (!!)

Yann Rotella

Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2

(Parisian Cryptography Seminar)

This paper presents the first publicly available cryptanalytic attacks on the GEA-1 and GEA-2 algorithms. Instead of providing full 64-bit security, we show that the initial state of GEA-1 can be recovered from as little as 65 bits of known keystream (with at least 24 bits coming from one frame) in time 240 GEA-1 evaluations and using 44.5 GiB of memory. The attack on GEA-1 is based on an exceptional interaction of the deployed LFSRs and the key initialization, which is highly unlikely to occur by chance. This unusual pattern indicates that the weakness is intentionally hidden to limit the security level to 40 bit by design.

In contrast, for GEA-2 we did not discover the same intentional weakness. However, using a combination of algebraic techniques and list merging algorithms we are still able to break GEA-2 in time 245.1 GEA-2 evaluations. The main practical hurdle is the required knowledge of 1600 bytes of keystream.

Joint work with Christof Beierle, Patrick Derbez, Gregor Leander, Gaëtan Leurent, Håvard Raddum, David Rupprecht, Lukas Stennes.

Thursday, May 12, 2022 - 14:00 - 24-25/509

Florette Martinez

Practical Seed Recovery of Fast Cryptographic Pseudo Random Number Generators

(ALMASTY Seminar)

Trifork is a family of pseudo-random number generators described in 2010 by Orue et al. It is based on Lagged Fibonacci Generators and has been claimed as cryptographically secure. In 2017 was presented a new family of lightweight pseudo-random number generators: Arrow. These generators are based on the same techniques as Trifork and designed to be light, fast and secure, so they can allow private communication between resource-constrained devices. The authors based their choices of parameters on NIST standards on lightweight cryptography and claimed these pseudo-random number generators were of cryptographic strength. We present practical implemented algorithms that reconstruct the internal states of the Arrow generators for different parameters given in the original article. These algorithms enable us to predict all the following outputs and recover the seed. These attacks are all based on a simple guess-and-determine approach which is efficient enough against these generators. We also present an implemented attack on Trifork, this time using lattice-based techniques. We show it cannot have more than 64 bits of security, hence it is not cryptographically secure.

Monday, Apr 25, 2022 - 11:15 - ENS, Salle des Actes (!!)

Magali Bardet

An Algebraic Attack on Rank Metric Code-Based Cryptosystems.

(Parisian Cryptography Seminar)

The Rank metric decoding problem is the main problem considered in cryptography based on codes in the rank metric. Very efficient schemes based on this problem or quasi-cyclic versions of it have been proposed recently, such as those in the submissions ROLLO and RQC currently at the second round of the NIST Post-Quantum Cryptography Standardization Process. While combinatorial attacks on this problem have been extensively studied and seem now well understood, the situation is not as satisfactory for algebraic attacks, for which previous work essentially suggested that they were ineffective for cryptographic parameters. In this paper, starting from Ourivski and Johansson’s algebraic modelling of the problem into a system of polynomial equations, we show how to augment this system with easily computed equations so that the augmented system is solved much faster via Groebner bases. This happens because the augmented system has solving degree r, r+1 or r+2 depending on the parameters, where r is the rank weight, which we show by extending results from Verbel et al. (PQCrypto 2019) on systems arising from the MinRank problem; with target rank r, Verbel et al. lower the solving degree to r+2, and even less for some favorable instances that they call superdetermined. We give complexity bounds for this approach as well as practical timings of an implementation using Magma. This improves upon the previously known complexity estimates for both Groebner basis and (non-quantum) combinatorial approaches, and for example leads to an attack in 200 bits on ROLLO-I-256 whose claimed security was 256 bits.

Joint work with Pierre Briaud, Maxime Bros, Philippe Gaborit, Vincent Neiger, Olivier Ruatta, Jean-Pierre Tillich.

Monday, Apr 25, 2022 - 10:00 - ENS, Salle des Actes (!!)

Alex Grilo

Oblivious Transfer is in MiniQCrypt

(Parisian Cryptography Seminar)

MiniQCrypt is a world where quantum-secure one-way functions exist, and quantum communication is possible. We construct an oblivious transfer (OT) protocol in MiniQCrypt that achieves simulation-security in the plain model against malicious quantum polynomial-time adversaries, building on the foundational work of Bennett, Brassard, Crépeau and Skubiszewska (CRYPTO 1991). Combining the OT protocol with prior works, we obtain secure two-party and multi-party computation protocols also in MiniQCrypt. This is in contrast to the classical world, where it is widely believed that one-way functions alone do not give us OT. In the common random string model, we achieve a constant-round universally composable (UC) OT protocol.

Joint work with Huijia Lin, Fang Song, Vinod Vaikuntanathan.

Thursday, Apr 21, 2022 - 14:00 - 24-25/405

Sarah Bordage

Fast proximity tests for algebraic linear codes

(ALMASTY Seminar)

Most constructions of probabilistically checkable proofs (as well as their interactive variants) involve a proximity testing problem for linear codes. Specifically, the goal is to determine whether an input word belong to a given linear code or is far from any codeword. In many cases, this problem corresponds to a low-degree testing problem, or a variant thereof.

In this talk, we will discuss proximity tests for multivariate polynomial codes and algebraic geometry codes, with linear-time proof generation and logarithmic verification time. Our constructions are inspired from a highly-efficient protocol which solves the Reed-Solomon proximity testing problem, called FRI protocol [Ben-Sasson, Bentov, Horesh, Riabzev. ICALP’2018]. We will first describe the FRI protocol for Reed-Solomon codes, which can be viewed as a univariate low-degree test. Then, we will show how to apply the same design principles in order to construct proximity tests with similar efficiency parameters for codes beyond Reed-Solomon codes.

Thursday, Apr 7, 2022 - 14:30 - 24-25/405

Octavio Perez Kempner

Improved Constructions of Anonymous Credentials From Structure-Preserving Signatures on Equivalence Classes

(ALMASTY Seminar)

Anonymous attribute-based credentials (ABCs) are a powerful tool allowing users to authenticate while maintaining privacy. When instantiated from structure-preserving signatures on equivalence classes (SPS-EQ) we obtain a controlled form of malleability, and hence increased functionality and privacy for the user. Existing constructions consider equivalence classes on the message space, allowing the joint randomization of credentials and the corresponding signatures on them.

In this work, we additionally consider equivalence classes on the signing-key space. In this regard, we obtain a signer-hiding notion, where the issuing organization is not revealed when a user shows a credential. To achieve this, we instantiate the ABC framework of Fuchsbauer, Hanser, and Slamanig (FHS, Journal of Cryptology ‘19) with a recent SPS-EQ scheme (ASIACRYPT ‘19) modified to support a fully adaptive NIZK from the framework of Couteau and Hartmann (CRYPTO ‘20). We also show how to obtain Mercurial Signatures (CT-RSA, 2019), extending the application of our construction to anonymous delegatable credentials.

To further increase functionality and efficiency, we augment the set-commitment scheme of FHS19 to support openings on attribute sets disjoint from those possessed by the user, while integrating a proof of exponentiation to allow for a more efficient verifier. Instantiating in the CRS model, we obtain an efficient credential system, anonymous under malicious organization keys, with increased expressiveness and privacy, proven secure in the standard model.

Monday, Apr 4, 2022 - 10:30 - ENS, Salle des Actes (!!)

Alice Pellet-Mary

On the Hardness of the NTRU Problem

(Parisian Cryptography Seminar)

The NTRU problem is an algorithmic problem over structured lattices that was introduced by Hoffstein, Pipher, and Silverman more than 20 years ago, and which has been used to construct various cryptographic primitives. However, its relations to other lattice problems is still not well understood.

In this talk, we will see different variants of the NTRU problem, and study how they compare to each other, and to other more classical lattice problems, in terms of reductions. More precisely, we will show that a search variant of the NTRU problem is at least as hard as the shortest vector problem (SVP) in ideal lattices; and that the decisional variant of NTRU is at least as hard as another search variant of NTRU. Unfortunately, the two search variants of NTRU that are considered in these reductions do not match, meaning that we cannot combine the reductions in order to obtain a reduction from the ideal shortest vector problem to the decisional NTRU problem.

Joint work with Damien Stehlé.

Thursday, Mar 31, 2022 - 14:00 - 24-25/405

Ambroise Fleury

Accélération du crible dans CADO-NFS via les arbres de factorisation

(ALMASTY Seminar)

Ma présentation concernera nos travaux sur l’accélération du crible dans CADO-NFS grâce à la factorisation par lot. CADO-NFS est l’implémentation du crible algébrique derrière les derniers records de factorisation RSA-240 (2019) et RSA-250 (2020). Son temps de calcul est dominé par le crible dont l’objectif est d’identifier rapidement un grand nombre d’entiers friables d’une certaine forme. Marquer les multiples des petits nombres premiers représente une fraction importante du temps total.

Nos travaux explorent l’utilisation d’un algorithme de factorisation par lots dû à Bernstein, qui avait suggéré de l’utiliser pour éviter de cribler les grands nombres premiers. Nous nous intéressons à l’idée inverse, c’est-à-dire l’utiliser pour éviter de cribler les petits premiers qui ne correspondent qu’à une petite partie des bits des nombres candidats et apportent donc peu d’information sur leur friabilité. Un crible partiel ne traitant pas les petits premiers permet d’effectuer un filtrage intermédiaire en ´eliminant les entiers candidats dont le produit des facteurs inconnus est trop grand, c’est `a dire les nombres ayant peu de chance d’être friable. Les arbres de factorisation sont finalement utilisés sur le petit ensemble des candidats survivants afin de compléter leur factorisation et d’éliminer alors une deuxième vague de mauvais candidats.

Nous avons réussi à trouver des bornes telles qu’un nombre assez grand de candidats soient éliminés avant la factorisation par lots pour obtenir un gain de temps mais qu’il y ait en contrepartie assez de survivants pour conserver l’essentiel des candidats. Ceci devrait permettre d’accélérer (un peu) la factorisation des grands entiers.

Thursday, Mar 17, 2022 - 14:30 - 55-65/211

Charles Bouillaguet

Les attaques cryptographique sophistiquées sont-elles toujours meilleures que la force brute ?

(Soutenance HDR)

Si la cryptographie est la science du secret, la cryptanalyse est l’art de casser des mécanismes cryptographiques. Un algorithme suffisamment efficace qui brise une propriété de sécurité offerte par un mécanisme cryptographique est une “attaque”. L’efficacité, donc la dangerosité des attaques cryptographiques est généralement évaluée dans le modèle calculatoire usuel des cours d’algorithmique : la Random Access Machine, (ou une de ses variantes) que personne ne se risque à définir précisément.

Dans cet exposé, je voudrais essayer de souligner qu’envisager des modèles de calculs plus réalistes, notamment le modèle AT en vogue dans l’étude des circuits VLSI dès la fin des années 1970 soulève un certain nombre de questions.

Quand on y réfléchit quelques minutes, on peut se rendre compte que, si jamais on essayait de les programmer, on trouverait que de nombreuses attaques cryptographiques sophistiquées sont inférieures dans la pratique à des idées très naïves (recherche exhaustive, etc.).

De plus, optimiser la complexité de certaines attaques dans le modèle AT est un objectif complètement différent de celui d’optimiser le nombre d’opérations. Cela aboutit à des résultats différents. Alors, quelle est la “bonne” manière de faire de la cryptanalyse ?

Thursday, Mar 10, 2022 - 14:00 - 24-25/405

Jules Maire

Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials (following Sakumoto, Shirai and Hiwatari)

(ALMASTY Seminar)

A problem of solving a system of multivariate quadratic polynomials over a finite field, which is called an MQ problem, is a promising problem in cryptography. A number of studies have been conducted on designing public-key schemes using the MQ problem, which are known as multivariate public-key cryptography (MPKC). However, the security of the existing schemes in MPKC relies not only on the MQ problem but also on an Isomorphism of Polynomials (IP) problem. In this talk, we present public-key identification schemes based on the conjectured intractability of the MQ problem under the assumption of the existence of a non-interactive commitment scheme. The schemes (due to Sakumoto, Shirai and Hiwatari) do not rely on the IP problem, and they consist of an identification protocol which is zero-knowledge argument of knowledge for the MQ problem. For a practical parameter choice, the efficiency of these schemes is highly comparable to that of identification schemes based on another problem including Permuted Kernels, Syndrome Decoding, Constrained Linear Equations, and Permuted Perceptrons. Furthermore, even if the protocol is repeated in parallel, the schemes can achieve the security under active attack with some additional cost.

Thursday, Feb 17, 2022 - 14:00 - 24-25/405

Paola de Perthuis

MyOPE - Malicious securitY for Oblivious Polynomial Evaluation

(ALMASTY Seminar)

Oblivious Polynomial Evaluation (OPE) schemes are interactive protocols between a sender with a private polynomial and a receiver with a private evaluation point where the receiver learns the evaluation of the polynomial in their point and no additional information. They are used in Private Set Intersection (PSI) protocols. We introduce MyOPE, a ``short-sighted’’ polynomial evaluation scheme in the presence of malicious senders. In addition to strong privacy guarantees, MyOPE enforces honest sender behavior and consistency by adding verifiability to the calculations.

The main tools are Verifiable Computation (VC) of inner products between committed vectors for honest behavior enforcement and Fully Homomorphic Encryption (FHE) for input privacy. While classical techniques in pairing-based settings allow generic succinct proofs for such evaluations, they require large prime order subgroups which highly impact the communication complexity, and prevent the use of FHE with practical parameters. MyOPE builds on generic secure encoding techniques for succinct commitments, that allow real-world FHE parameters and Residue Number System (RNS) optimizations, suitable for very high-degree polynomials.

Thursday, Feb 10, 2022 - 14:00 - 24-25/405

Abdul Rahman Taleb

IronMask - Versatile Verification of Masking Security

(ALMASTY Seminar)

This talk introduces IronMask, a new versatile verification tool for masking security. IronMask is the first to offer the verification of standard simulation-based security notions in the probing model as well as recent composition and expandability notions in the random probing model. It supports any masking gadgets with linear randomness (e.g. addition, copy and refresh gadgets) as well as quadratic gadgets (e.g. multiplication gadgets) that might include non-linear randomness (e.g. by refreshing their inputs), while providing complete verification results for both types of gadgets. We achieve this complete verifiability by introducing a new algebraic characterization for such quadratic gadgets and exhibiting a complete method to determine the sets of input shares which are necessary and sufficient to perform a perfect simulation of any set of probes. We report various benchmarks which show that IronMask is competitive with state-of-the-art verification tools in the probing model (maskVerif, scVerif, SILVER, matverif). IronMask is also several orders of magnitude faster than VRAPS –the only previous tool verifying random probing composability and expandability– as well as SILVER –the only previous tool providing complete verification for quadratic gadgets with non-linear randomness. Thanks to this completeness and increased performance, we obtain better bounds for the tolerated leakage probability of state-of-the-art random probing secure compilers.

Thursday, Jan 13, 2022 - 14:00 - 24-25/405

Léonard Assouline

Multi-Party PSM, Revisited - Improved Communication and Unbalanced Communication

(ALMASTY Seminar)

We improve the communication complexity in the Private Simultaneous Messages (PSM) model, which is a minimal model of non-interactive information-theoretic multi-party computation. The state-of-the-art PSM protocols were recently constructed by Beimel, Kushilevitz and Nissim (EUROCRYPT 2018). We present new constructions of k-party PSM protocols. The new protocols match the previous upper bounds when k=2 or 3 and improve the upper bounds for larger k. We also construct 2-party PSM protocols with unbalanced communication complexity. More concretely, - For infinitely many k (including all k≤20), we construct k-party PSM protocols for arbitrary functionality f:[N]^k→{0,1}, whose communication complexity is O_k(N^{(k−1)/2}). This improves the former best known upper bounds of O_k(N^{k/2}) for k≥6, O(N^{7/3}) for k=5, and O(N^{5/3}) for k=4. - For all rational 0<η<1 whose denominator is ≤20, we construct 2-party PSM protocols for arbitrary functionality f:[N]×[N]→{0,1}, whose communication complexity is O(N^η) for one party, O(N^{1−η}) for the other. Previously the only known unbalanced 2-party PSM has communication complexity O(log(N)),O(N).

Thursday, Jan 6, 2022 - 14:00 - 24-25/405

Quentin Meunier

LeakageVerif - Scalable and Efficient Leakage Verification in Symbolic Expressions

(ALMASTY Seminar)

Side-channel attacks are a powerful class of attacks targeting cryptographic devices. Masking is a popular protection technique to thwart such attacks as it can be theoretically proven secure. However, correctly implementing masking schemes is a non-trivial task and error-prone. If several techniques have been proposed to formally verify masked implementations, they all come with limitations regarding expressiveness, scalability or accuracy. In this work, we propose a symbolic approach, based on a variant of the classical substitution method, for formally verifying arithmetic and boolean masked programs. This approach is more accurate and scalable than existing approaches thanks to a careful design and implementation of key heuristics, algorithms and data structures involved in the verification process. We present all the details of this approach and the open-source tool called LeakageVerif which implements it as a python library, and which offers constructions for symbolic expressions and functions for their verification. We compare LeakageVerif to three existing state-of-the-art tools on a set of 46 masked programs, and we show that it has very good scalability and accuracy results while providing all the necessary constructs for describing algorithmic to assembly masking schemes. Finally, we also provide the set of 46 benchmarks, named MaskedVerifBenchs and written for comparing the different verification tools, in the hope that they will be useful to the community for future comparisons.

Friday, Dec 10, 2021 - 11:00 - 24-25/309

Thibauld Feneuil

Multi-Party Permutation for Syndrome Decoding - a new zk protocol and code-based signature

(ALMASTY Seminar)

Friday, Nov 26, 2021 - 11:00 - 24-25/405

Nicolas Bordes and Pierre Karpman

Fast Verification of Masking Schemes in Characteristic Two

(ALMASTY Seminar)

We revisit the matrix model for non-interference (NI) probing security of masking gadgets introduced by Belaïd et al. at CRYPTO 2017. This leads to two main results. 1) We generalise the theorems on which this model is based, so as to be able to apply them to masking schemes over any finite field – in particular F_2 – and to be able to analyse the strong non-interference (SNI) security notion. We also follow Faust et al. (TCHES 2018) to additionally consider a robust probing model that takes hardware defects such as glitches into account. 2) We exploit this improved model to implement a very efficient verification algorithm that improves the performance of state-of-the-art software by three orders of magnitude. We show applications to variants of NI and SNI multiplication gadgets from Barthe et al. (EUROCRYPT 2017) which we verify to be secure up to order 11 after a significant parallel computation effort, whereas the previous largest proven order was 7; SNI refreshing gadgets (ibid.); and NI multiplication gadgets from Gross et al. (TIS@CCS 2016) secure in presence of glitches. We also reduce the randomness cost of some existing gadgets, notably for the implementation-friendly case of 8 shares, improving here the previous best results by 17% (resp. 19%) for SNI multiplication (resp. refreshing).

Thursday, Nov 18, 2021 - 14:30 - 24-25/405

Claire Delaplace

Low-Memory Subset Sum and LPN Algorithms via Multiple Collisions

(ALMASTY Seminar)

For enabling post-quantum cryptanalytic experiments on a meaningful scale, there is a strong need for low-memory algorithms. We present low memory algorithms for subset-sum and LPN based on a combination of techniques from representations, multiple collision finding, and the Schroeppel-Shamir algorithm. For random subset sum instances 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 techniques 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 k/log k}$. This is a joint work with Andre Esser and Alexander May published at IMACC 2019.

Thursday, Nov 4, 2021 - 14:00 - 24-25/405

Simona Etinski

Classical and Quantum algorithms for generic Syndrome Decoding problems and applications to the Lee metric

(ALMASTY Seminar)

The security of code-based cryptography usually relies on the hardness of the syndrome decoding (SD) problem for the Hamming weight. The best generic algorithms are all improvements of an old algorithm by Prange, and they are known under the name of Information Set Decoding (ISD) algorithms. This work aims to extend ISD algorithms’ scope by changing the underlying weight function and alphabet size of SD. More precisely, we show how to use Wagner’s algorithm in the ISD framework to solve SD for a wide range of weight functions. We also calculate the asymptotic complexities of ISD algorithms both in the classical and quantum case. We then apply our results to the Lee metric, which currently receives a significant amount of attention. By providing the parameters of SD for which decoding in the Lee weight seems to be the hardest, our study could have several applications for designing code-based cryptosystems and their security analysis, especially against quantum adversaries.

Thursday, Oct 28, 2021 - 14:00 - 24-25/405

Charles Bouillaguet

Algorithms for the Sparse Random 3XOR Problem

(ALMASTY Seminar)

We present algorithms for variants of the 3XOR problem with lists consisting of random sparse n-bit vectors. We consider two notions of sparsity: low-density (each bit is independently biased towards zero) and low-weight (the Hamming weight of n-bit vectors is fixed). We show that the random sparse 3XOR problem can be solved in strongly subquadratic time, namely less than O(N^{2−epsilon}) operations for a constant epsilon > 0. This stands in strong contrast with the regular case, where it has not been possible to have the exponent drop below 2 − o(1). In the low-density setting, a very simple algorithm even runs in linear time with overwhelming success probability when the density is less than 0.0957. Our algorithms exploit the randomness (and sparsity) of the input in an essential way.

Thursday, Oct 14, 2021 - 14:00 - 24-25/405

Florette Martinez

Attacks on Pseudo-Random Number Generators Hiding a Linear Structure

(ALMASTY Seminar)

We introduce lattice-based practical seed-recovery attacks against two efficient number-theoretic pseudo-random number generators: the fast knapsack generator and a family of combined multiple recursive generators. The fast knapsack generator was introduced in 2009 by Von Zur Gathen and Shparlinski. It generates pseudo-random numbers very efficiently with strong mathematical guarantees on their statistical properties but its resistance to cryptanalysis was left open since 2009. The given attacks are surprisingly efficient when the truncated bits do not represent a too large proportion of the internal states. Their complexities do not strongly increase with the size of parameters, only with the proportion of discarded bits. A multiple recursive generator is a pseudo-random number generator based on a constant-recursive sequence. A combined multiple recursive generator is a pseudo-random number generator based on combining two or more multiple recursive generators. L’Écuyer presented the general construction in 1996 and a popular instantiation deemed MRG32k3a in 1999. We use algebraic relations of both pseudo-random generators with underlying algebraic generators to show that they are cryptographically insecure. We provide a theoretical analysis as well as efficient implementations.

Thursday, Oct 7, 2021 - 14:00 - 24-25/405

Abdul Rahman Taleb

On the Power of Expansion - More Efficient Constructions in the Random Probing Model

(ALMASTY Seminar)

The random probing model is a leakage model in which each wire of a circuit leaks with a given probability p. This model enjoys practical relevance thanks to a reduction to the noisy leakage model, which is admitted as the right formalization for power and electromagnetic side-channel attacks. In addition, the random probing model is much more convenient than the noisy leakage model to prove the security of masking schemes. In a recent work, Ananth, Ishai and Sahai (CRYPTO 2018) introduce a nice expansion strategy to construct random probing secure circuits. Their construction tolerates a leakage probability of 2^{−26}, which is the first quantified achievable leakage probability in the random probing model. In a follow-up work, Belaïd, Coron, Prouff, Rivain and Taleb (CRYPTO 2020) generalize their idea and put forward a complete and practical framework to generate random probing secure circuits. The so-called expanding compiler can bootstrap simple base gadgets as long as they satisfy a new security notion called random probing expandability (RPE). They further provide an instantiation of the framework which tolerates a 2^{−8} leakage probability in complexity O(κ^7.5) where κ denotes the security parameter. In this paper, we provide an in-depth analysis of the RPE security notion. We exhibit the first upper bounds for the main parameter of a RPE gadget, which is known as the amplification order. We further show that the RPE notion can be made tighter and we exhibit strong connections between RPE and the strong non-interference (SNI) composition notion. We then introduce the first generic constructions of gadgets achieving RPE for any number of shares and with nearly optimal amplification orders and provide an asymptotic analysis of such constructions. Last but not least, we introduce new concrete constructions of small gadgets achieving maximal amplification orders. This allows us to obtain much more efficient instantiations of the expanding compiler: we obtain a complexity of O(κ^3.9) for a slightly better leakage probability, as well as O(κ^3.2) for a slightly lower leakage probability.