• Coffe at 9:30
• Visio link
• 10:00. Pierrick Gaudry, CNRS,  LORIA, et  Emmanuel Thomé, INRIA Nancy

Title :  Factoring and solving discrete logarithms, 15 years after RSA-768

Abstract: In December 2009, the factorization of RSA-768 was announced.
This milestone, to which we participated, was then published at Crypto
and the article recently received a Test-of-Time award.

This is a good opportunity to look at what happened since then in the
area of the Number Field Sieve (NFS) algorithm. We will take a biased
point of view, looking in particular at the Cado-nfs software, which was
a young project in 2009 and the code was not used for the 768-bit
record.  It has now become the reference implementation, and was used to
set the current records for both factoring (250 decimal digits) and
discrete logarithm in finite fields (240 digits).

We will tell a few stories of our journey through NFS and computing
records. Theoretical questions in number theory meet deep algorithmic
questions to form the basis of the cado-nfs software, which would not
survive without a lot of software engineering.

• 11:00. Dung Bui, LIP6, Sorbonne Université

Title: Critical Rounds in Multi-Round Proofs: Proof of Partial Knowledge, Trapdoor Commitments, and Advanced Signatures

Abstract:  Zero-knowledge simulators and witness extractors, initially
developed for proving the security of proof systems, turned out to be
also useful in constructing advanced protocols from simple three-move
interactive proofs. However, in the context of multi-round public-coin
protocols, the interfaces of these auxiliary algorithms become more
complex, introducing a range of technical challenges that hinder the
generalization of these constructions.
  We introduce a framework to enhance the usability of zero-knowledge
simulators and witness extractors in multi-round argument systems for
protocol designs. Critical-round zero-knowledge relies on the ability to
perform complete zero-knowledge simulations by knowing the challenge of
just one specific round in advance. Critical-round special soundness
aims to address a stringent condition for witness extraction by
formalizing it to operate with a smaller tree of transcripts than the
one needed for extended extraction, which either outputs the intended
witness or solves the underlying hard problem in an argument system. We
show that these notions are satisfied by diverse protocols based on
MPC-in-the-Head, interactive oracle proofs, and split-and-fold arguments.
  We demonstrate the usefulness of the critical round framework by
constructing proofs of partial knowledge (Cramer, Damgård, and
Schoenmakers, CRYPTO’94) and trapdoor commitments (Damgård, CRYPTO’89)
from critical-round multi-round proofs. Furthermore, our results imply
advancements in post-quantum secure adaptor signatures and threshold
ring signatures based on MPC-in-the-Head, eliminating the need for
(costly) generic NP reductions.

https://eprint.iacr.org/2024/1766

• 13:45. Rachelle Heim Boissier, UCLouvain, Belgique

Title : Boolean Modeling and Analysis of LWR

Abstract : LWR has been introduced by Banerjee et al. in 2012 as a
deterministic variant of LWE. Since then, it has found many applications
in the design of symmetric primitives and post-quantum schemes. Despite
its deterministic nature, LWR is usually analyzed as LWE under the
(implicit) assumption that no improved attack can take advantage of the
additional structure it provides. In this talk, we will study to what
extent this assumption holds in the power-of-two moduli case.

We will provide an in-depth investigation of LWR modeled as a vectorial
Boolean function. We combine analyses of standard criteria such as the
algebraic degree and the number of monomials in the secret with an
analysis of the algebraic normal form, that we are able to express
exactly in a compact representation by leveraging group action theory.
Our results exhibit specificities in the structure of LWR that we are
able to exploit. They allow refining and strengthening the understanding
of this important problem, e.g. systematically improving over the
linearisation attack of Arora & Ge.

• 14:45.  Épiphane Nouetowa,  Université de Limoges

Title: A post-quantum encryption scheme based on linearized Reed-Solomon
codes

Abstract: Designing a McEliece-type scheme is often challenging, because
the secret codes involved are structured codes that are difficult to
hide effectively while still achieving a secure scheme with a small key
size. Regarding Gabidulin codes, Overbeck’s distinguisher is the main
tool used to attack schemes based on this family of codes. Linearized
Reed–Solomon codes generalize Gabidulin codes. However, to the best of
our knowledge, no polynomial-time analogue of Overbeck’s distinguisher
exists for this family of codes. Thus, using linearized Reed–Solomon
codes offers better protection against structural attacks compared to
Gabidulin codes.
In this presentation, I will discuss a new McEliece-type scheme based on
linearized Reed–Solomon codes in the sum-rank metric, in which the
scrambling matrix used is a homogeneous block-diagonal matrix. The key
sizes we obtain are competitive with those of other well-known schemes.

Les prochaines éditions du séminaire seront

• Le 26 juin ou le 3 juillet à Bordeaux
• Le 9 octobre à Paris

• 10:00 Hugues Randriam, ANSSI & Télécom Paris

Titre : Le distingueur par syzygies

Résumé : Dans cet exposé j’expliquerai comment un code alternant ou de Goppa peut être distingué d’un code aléatoire a u moyen des nombres de Betti gradués de l’anneau de coordonnées homogènes d’un raccourci du code dual. Le distingueur ainsi obtenu est de complexité sous-exponentielle en la capacité de correction du code — donc meilleure que celle des algorithmes de décodage génériques. De plus, il s’affranchit des fortes contraintes sur les paramètres nécessaires à d’autres distingueurs ou algorithmes de reconstruction structurelle récents : en particulier, il fonctionne (théoriquement) sur les codes utilisés par le candidat Classic McEliece à la standardisation en cryptographie post-quantique. Depuis son introduction en 1978, c’est la première fois qu’une analyse du système de McEliece franchit cette barrière exponentielle.

• 11:00 Guillaume Hanrot, Cryptolab.

Title: Homomorphic encryption with CKKS: a survey

Abstract: Since Gentry’s seminal work of 2009, homomorphic encryption has made a lot of progress. Numerous constructions of schemes have been proposed, handling arithmetic on various types of plaintexts, and major algorithmic efforts have drastrically improved the efficiency of homomorphic encryption computations.
In this talk, we shall survey the state of the art on those topics, focusing mainly on the CKKS (Cheon-Kim-Kim-Song) scheme, introduced in 2016 and handling homomorphically (approximate) arithmetic on complex numbers. We shall in particular describe the bootstrapping algorithm, which is the bottleneck of homomorphic computations in most applications. If time permits, we shall describe new ideas in this direction obtained jointly with Cheon, Kim, Stehlé and the speaker (Eurocrypt 2025) – related results have also been obtained by Coron, Köstler, Seuré (eprint 2025/651, 2025/886).

• 13:45 AnnaMaria Iezzi, Laboratoire Jean Kuntzmann, Université Grenoble Alpes

Title: Computational number-theoretic problems behind isogeny-based cryptography

Abstract: Isogeny-based cryptography is built upon several closely related hard problems in computational number theory, including the isogeny path problem, the endomorphism ring problem and the one endomorphism problem. After recalling the relevant mathematical background, in this talk we will explore the connections between these problems. We will focus in particular on recent developments concerning the one-endomorphism problem, that is, the problem of computing a nontrivial endomorphism of a given supersingular elliptic curve defined over a finite field.

• 14:45 Nihar Gargava, Institut de Mathématiques d’Orsay, Université Paris-Saclay

Title: Gaussian Heuristics for random ideal lattices and module lattices

Abstract: The Gaussian Heuristic is a heuristic principle that tells us how long one should expect the shortest vector of a random lattice. But what are some theorems that we can state? In this talk, I will talk about Siegel’s and Rogers’ integration formulas that can be used to estimate the shortest vector with hig
Le 26/06/2025 à 10:03, Daniel Augot a écrit :

11h30 Katharina Boudgoust (CR CNRS, LIRMM) : The Power of NAPs: Compressing OR-Proofs via Collision-Resistant Hashing

Abstract:

Proofs of partial knowledge allow for proving the validity of t out of n different statements without revealing which ones those are. In this presentation, we describe a new approach for transforming certain proofs system into new ones that allows for proving partial knowledge. The communication complexity of the resulting proof system only depends logarithmically on the total number of statements and its security only relies on the existence of collision-resistant hash functions. As an example, we show that our transformation is applicable to the proof systems of Goldreich, Micali, and Wigderson (FOCS’86) for the graph isomorphism and the graph 3-coloring problem.
Our main technical tool, which we believe to be of independent interest, is a new cryptographic primitive called non-adaptively programmable functions (NAPs). Those functions can be seen as pseudorandom functions which allow for re-programming the output at an input point, which must be fixed during key generation. Even when given the re-programmed key, it remains infeasible to find out where re-programming happened. Finally, as an additional technical tool, we also build explainable samplers for any distribution that can be sampled efficiently via rejection sampling and use them to construct NAPs for various output distributions.
The presentation starts with introducing the concepts of Sigma-protocols and OR-proofs. Then, the new NAP primitive is introduced and instantiated from one-way functions. Lastly, we explain how to use NAPs to efficiently compress Sigma-protocols.

Joint work with Mark Simkin, accepted at TCC’24.

13h45  Augustin Bariant (ANSSI) Polynomial-solving Attacks against Arithmetization-Oriented Primitives

Abstract:

Recent advanced protocols for zero-knowledge, multi-party computation or fast homomorphic encryption have been the subject of active research in the last decade. Many such protocols rely on symmetric cryptography primitives which are evaluated inside the protocol. The cost of these primitives depends on the operations allowed in the protocol, and these operations are often large finite field operations (+, x). Traditional symmetric primitives such as the AES are very costly when converted into these operations, therefore dedicated primitives have been proposed; they are called Arithmetization-Oriented (AO) primitives. AO primitives tend to minimize the number of multiplication in such protocols to lower their cost, and their security is mainly evaluated with algebraic cryptanalysis. In this talk, I give an introduction to polynomial-solving attacks, a special type of algebraic attack against AO primitives. I first recall the algebraic concepts involved in the attacks, and then show the principle of polynomial-solving attacks based on Groebner bases, with application to existing AO primitives. Finally, I will try to explain two recent threatening polynomial-solving attacks that do not follow the usual steps of Groebner basis attacks: the FreeLunch attack (CRYPTO 2024) and the resultant attack (EPRINT 2024).

14:45. Clémence Bouvier (CR Inria, Loria) : Some Applications of Algebraic Geometry to Linear Cryptanalysis

Abstract:

In this talk we will see how bounds on exponential sums derived from modern algebraic geometry can be used to upper bound the absolute correlations of linear approximations for cryptographic constructions of low algebraic degree. By applying theorems of Deligne, Denef and Loeser, as well as Rojas and León, we obtain correlation bounds for Feistel-like constructions, especially a generalization of the Butterfly construction, 3-round Feistel ciphers, and a generalization of the Flystel construction.
Such correlation bounds are relevant for the development of security arguments against linear cryptanalysis, and since the methods proposed in this talk are applicable to constructions defined over arbitrary finite fields, the results are also relevant for arithmetization-oriented primitives. In particular, we resolve a conjecture on the linear properties of Anemoi, a family of hash functions that uses S-boxes based on the Flystel construction.

Joint work with Tim Beyne.

16:00.  Alex Bredariol Grilo (CR CNRS, LIP6) : Computational Assumptions in the Quantum World

Abstract:

QKD is a landmark of how quantum resources allow us to implement cryptographic functionalities with a level of security that is not achievable only with classical resources. However, key agreement is not sufficient to implement all functionalities of interest, and it is well-known that they cannot be implemented with perfect security, even if we have access to quantum resources. Thus, computational assumptions are necessary even in the quantum world.
In this talk, I will cover recent examples that even in the computational setting, quantum resources may give an advantage in the required assumption. More concretely, I will talk about quantum implementations of multi-party computation and public-key encryption under weaker computational assumptions than their classical counterparts. Moreover, I will discuss new cryptographic assumptions that are inherently quantum, which have changed the landscape of the feasibility of cryptographic primitives in the quantum world.

10:00.  Henry Bambury (ENS Paris, Inria and DGA). Provably Reducing Near-Hypercubic Lattices.

Abstract: A recurring question in estimating parameters for lattice-based cryptography is the following: what is the largest dimension in which an attacker can be allowed to solve SVP in order for the scheme to remain secure? This question comes in two flavours: provable or heuristic. While we expect heuristic algorithms to perform better in practice, Ducas (DCC 2023) proposed a provable algorithm for reducing the hypercubic (Z^n) lattice that only requires SVP oracles in dimension n/2, bridging the gap between what is provable and what is heuristic. In this talk, we show that Ducas’ algorithm can be relaxed to sqrt(2)-approximate-SVP oracles, and provide an algorithm that reduces most n-dimensional NTRU lattices using SVP oracles in dimension n/2. This answers a conjecture of Gama, Howgrave- Graham and Nguyen from Eurocrypt 2006. If time allows, we compare the (provable) results with (heuristic) asymptotics for the primal attack.

Joint work with Phong Q. Nguyen

11:00 Julien Devevey (ANSSI).G+G: A Fiat-Shamir Lattice Signature based on Convolved Gaussians.

Abstract: Adapting Schnorr’s signature to the lattice setting has been a long standing problem. It was solved by Lyubashevsky in 2009 by introducing rejection sampling and the Fiat-Shamir with Aborts framework, which adds a layer of complexity to the scheme, as underlined by the fact that no correct proof of the framework was given before [D. et al., Crypto2023, Barbosa et al., Crypto 2023]. Getting rid of rejection sampling is possible, but  comes at a significant increase in signature size due to the use of flooding techniques (see, e.g., [Damgard et al., Crypto 2012]). In this talk we propose a new adaptation, which relies on Gaussian convolution rather than  flooding or rejection sampling as previous approaches. It does not involve any abort, can be proved secure in the ROM and QROM using existing analyses of the Fiat-Shamir transform, and enjoys smaller signature sizes  (both asymptotically and for concrete security levels).

Joint work with Damien Stehlé and Alain Passelègue

13:45. Geoffroy Couteau (CNRS, IRIF, Université Paris Cité). Fast Public-Key Silent OT and More from Constrained Naor-Reingold.

Abstract: Pseudorandom Correlation Functions (PCFs) allow two parties, given correlated evaluation keys, to locally generate arbitrarily many pseudorandom correlated strings, e.g. Oblivious Transfer (OT) correlations, which can then be used by the two parties to jointly run secure computation protocols.

In this work, we provide a novel and simple approach for constructing PCFs for OT correlation, by relying on constrained pseudorandom functions for a class of constraints containing a weak pseudorandom function (wPRF). We then show that tweaking the Naor-Reingold pseudorandom function and relying on low-complexity pseudorandom functions allow us to instantiate our paradigm. We further extend our ideas to obtain efficient public-key PCFs, which allow the distribution of correlated keys between parties to be non-interactive: each party can generate a pair of public/secret keys, and any pair of parties can locally derive their correlated evaluation key by combining their secret key with the other party’s public key.

In addition to these theoretical contributions, we detail various optimizations and provide concrete instantiations of our paradigm relying on the Boneh-Ishai-Passelègue-Sahai-Wu wPRF and the Goldreich-Applebaum-Raykov wPRF. Putting everything together, we obtain public-key PCFs with a throughput of 15k-40k OT/s, which is of a similar order of magnitude to the state-of-the-art interactive PCFs and about 4 orders of magnitude faster than state-of-the-art public-key PCFs.

As a side result, we also show that public-key PCFs can serve as a building block to construct reusable designated-verifier non-interactive zero-knowledge proofs (DV-NIZK) for NP. Combined with our instantiations, this yields simple and efficient reusable DV-NIZKs for NP in pairing-free groups.

Joint work with Dung Bui, GC, Pierre Meyer, Alain Passelègue, and Mahshid Riahinia

14:45.  Maxime Bombar (université de Bordeaux). From Structured Codes to Secure Computation, and Back Again.

Abstract: It is well-known that random linear codes are hard to decode, even with the help of quantum computers. In particular, they offer a compelling alternative to lattice-based post-quantum cryptography which has just been standardised. However, this traditional cryptography only protects data in transit, while a growing need today is to perform computations on that data. If lattices also enable (fully) homomorphic encryption, this still requires heavy computations which may not be suitable for all situations. In particular, when data is distributed among multiple users, secure MultiParty Computation (MPC) can offer a more practical solution. However, the main bottleneck in MPC protocols is often the cost of communications between all parties. Fortunately, it has long been known that extremely efficient online MPC protocols do exist, provided that all parties have access to a trusted source of correlated randomness, independent of the protocol’s inputs. Therefore, building efficient MPC protocols is reduced to distributing a large amount of correlated randomness to all the parties. To this end, new primitives known as Pseudorandom Correlation Generators (PCG) have been recently developed based on the hardness of decoding random linear codes having a specific algebraic structure. These are now considered to be one of the most promising approaches for performing MPC in this so-called “correlated randomness model”.

• 10:00. Martino Borello, Université Paris 8 – LAGA

The geometry of linear codes and some recent applications

It is well-known that a nondegenerate linear code of length n and dimension k can be associated with a set of n points (with multiplicities) in a projective space of dimension k-1. Some coding-theoretical properties can be interpreted geometrically. This perspective connects MDS codes to problems involving arcs in projective spaces (the famous MDS conjecture was initially formulated as a problem in projective geometry by Segre), covering problems to saturating sets, minimal codes to strong blocking sets, and so on. In this talk, we will illustrate some recent results obtained by using this geometrical approach for Hamming-metric codes and outline how this can be generalized to other metrics, such as the rank and sum-rank metrics.

La géométrie des codes linéaires et quelques applications récentes

Il est bien connu qu’un code linéaire non dégénéré de longueur n et de dimension k peut être associé à un ensemble de n points (avec multiplicités) dans un espace projectif de dimension k−1. Certaines propriétés des codes peuvent être interprétées géométriquement. Cette perspective relie les codes MDS aux problèmes impliquant des arcs dans les espaces projectifs (la fameuse conjecture MDS a été initialement formulée comme un problème de géométrie projective par Segre), les problèmes de recouvrement aux ensembles saturants, les codes minimaux aux ensembles bloquants forts, etc. Dans cette présentation, nous illustrerons certains résultats récents obtenus en utilisant cette approche géométrique pour les codes en métrique de Hamming et nous esquisserons à la fin comment cela peut être généralisé à d’autres métriques, telles que les métriques rang et somme-rang.

• 11:00. Antonin Leroux, DGA-MI et Université de Rennes

SQIsign2D-West The Fast, the Small, and the Safer

In this talk, we will present SQIsign2D-West, a variant of SQIsign using two-dimensional isogeny representations. SQIsignHD was the first variant of SQIsign to use higher dimensional isogeny representations with an unpractical eight-dimensional variant geared towards provable security, and a four-dimensional variant geared towards efficiency. In particular, it has significantly faster signing times than SQIsign, but slower verification owing to the complexity of the four dimensional representation.
A dimension 2 variant was already mentioned at the time but several obstacles remained to make it possible.
In this work, we introduce new algorithmic tools that make two-dimensional representations a viable alternative. These lead to a signature scheme with sizes comparable to SQIsignHD, slightly slower signing than SQIsignHD but still much faster than SQIsign, and the fastest verification of any known variant of SQIsign. We achieve this without compromising on the security proof: the assumptions behind SQIsign2D-West are similar to those of the eight-dimensional variant of SQIsignHD. Additionally, like SQIsignHD, SQIsign2D-West favourably scales to high levels of security. Concretely, for NIST level I we achieve signing times of 80 ms and verifying times of 4.5 ms, using optimised arithmetic based on intrinsics available to the Ice Lake architecture. For NIST level V, we achieve 470 ms for signing and 31 ms for verifying.

• 13:45. Cécile Pierrot, Inria / CNRS / Loria / Université de Lorraine

Y a-t-il encore, au XXI° siècle, de vieux documents historiques à déchiffrer ?

Aussi surprenant que cela puisse paraitre, oui. Il arrive que, dans un carton d’archives, l’historien butte soudainement sur un document chiffré resté tel qu’il a été envoyé. L’étonnant n’est pas de trouver ce genre de missive, et vous le savez-bien, nous chiffrons depuis des millénaires. Non, ce qui surprend, c’est que le destinataire officiel, soit n’ait pas procédé au déchiffrement, soit n’ait pas conservé et joint celui-ci. Les clefs des chiffres, également, ne sont pratiquement jamais jointes dans les archives, et si nous en trouvons encore avec émotion, elles ne comportent que rarement les mentions de leur propriétaire. De ce fait, de très nombreux documents historiques demeurent inexploités, car incompréhensibles. Ajoutez à ceci l’absence, pour le moment, de méthodes d’intelligence artificielle ad hoc capables de transcrire les dizaines de pages chiffrés par des glyphes propres à chaque auteur, ainsi que la perte des techniques de cryptanalyse au cours du temps, et enfin la difficulté à faire le pont entre plusieurs disciplines (histoire, linguistique, cryptographie, intelligence artificielle) ; vous comprendrez alors le chemin qu’il nous reste à parcourir. Cet exposé présentera des collaborations en cours à propos de lettres et de télégrammes du XVI° au XIX° siècle. Je vous emmènerai de l’Europe de Charles Quint à la guerre d’indépendance des Etats-Unis, en passant par les troubles post-indépendance du Brésil.

In the 21st century, are there still old historical documents to be deciphered?

Surprisingly, yes. Sometimes, in a box of archives, the historian suddenly comes across an encrypted document in the form in which it was sent. It’s not surprising to find this kind of missive – as you well know, we’ve been encrypting documents for thousands of years. No, what is surprising is that the official recipient either did not decrypt it, or did not keep it and attach it. The keys to the ciphers are almost never included in the archives, and if we still find some with emotion, they rarely include the name of their owner. As a result, many historical documents remain unexploited because they are incomprehensible. Add to this the absence, for the moment, of ad hoc artificial intelligence methods capable of transcribing the dozens of pages encrypted by glyphs specific to each author, as well as the loss of cryptanalysis techniques over time, and finally the difficulty of bridging several disciplines (history, linguistics, cryptography, artificial intelligence), and you will understand the road we still have to travel. This talk will present current collaborations on letters and telegrams from the 16th to the 19th century. I’ll be taking you from the Europe of Charles V to the American War of Independence, via the post-independence troubles in Brazil.

• 14:45. Jules Baudrin, Inria Paris.

Geometrical structures among known APN functions

An almost perfect non-linear (APN) function is a function offering optimal resistance against differential cryptanalysis, which is among the most powerful techniques to attack or assess the security of a block cipher. APN functions have therefore been carefully analyzed for many years but still remains under a cloud. As an example, only a few generic constructions of such functions are known, and connections between them are not well understood. Among them, the simpler APN monomials however seem to play an important role. In this presentation, we will first introduce all the necessary background knowledge, before moving on to our latest results. Those results bridge part of the gaps between the known constructions by observing that many of the infinite families of quadratic APN functions share a common geometrical structure known as “the subspace property”. This property was first observed on one of the most enigmatic APN function, the so-called “Kim mapping”, which is the only known APN function, with an even number of variables, that is CCZ-equivalent to a bijection. While attempts to find new APN functions having the subspace property were already carried out, this property was not clearly understood. We therefore clarify its nature by in particular pointing out its link with cyclotomic mappings, which generalize monomial functions. Joint work with Anne Canteaut & Léo Perrin.

La prochaine édition du séminaire se tiendra le vendredi 27 janvier à ENS de Lyon, site Descartes, bâtiment D8 Buisson, salle D01.
L’entrée du bâtiment D8 Buisson se situe au 19 allée de Fontenay, 69007 Lyon, à 3 minutes de la station Debourg du métro B (ligne directe depuis la gare de Part-Dieu – le métro se situe à l’extérieur de la gare, côté centre-ville (il faut sortir du côté de la voie A). Un accueil se situe derrière la porte et l’entrée est visible depuis la salle D01 qui se situe juste en face.

• • 10h45 : Johanna Loyer, INRIA Paris : Classical and quantum 3- and 4-sieves to solve SVP with low memory

Abstract: The Shortest Vector Problem (SVP) is at the foundation of lattice-based cryptography. The fastest known method to solve SVP in dimension d is by lattice sieving, which runs in time 2^{td+o(d)} with 2^{md+o(d)} memory for absolute constants t,m. Searching reduced vectors in the sieve is a problem reduced to the configuration problem, i.e. searching k vectors satisfying given constraints over their scalar products. In this work, we present a framework for k-sieve algorithms: we filter the input list of lattice vectors using a code structure modified from [BDGL16] to get lists centered around k codewords summing to the null-vector. Then, we solve a simpler instance of the configuration problem in the k filtered lists. Based on this framework, we describe classical sieves for k=3 and 4 that introduce new time-memory trade-offs. We also use the k-Lists algorithm [KPMP19] inside our framework, and this improves the time for k=3 and gives new trade-offs for k=4.

• • 12h : Victor Dyseryn, XLIM,Université de Limoges – On the security of the PSSI problem and the Durandal signature scheme (joint work with Nicolas Aragon and Philippe Gaborit)

Abstract: The Product Spaces Subspaces Indistinguishability (PSSI) was presented at EUROCRYPT 2019 and is one of the pillars of the security of the Durandal signature scheme, which is an efficient rank-metric signature scheme introduced in the same 2019 paper. In this work we present a new attack against the PSSI problem. It combines signatures two by two to recover subspaces containing products of a secret scalar with a public scalar and then uses a chain of intersections to recover the secret key. This new attack is efficient against a wide range of parameters. In the case of EUROCRYPT 2019 Durandal parameters, it would allow the recovery of the secret key in about 2^36 attempts (plus costs of linear algebra), using only a few dozens of signatures. We then investigate how to mitigate this new attack and propose new secure parameters for the Durandal signature scheme.

• • 14h30 : Bastien Pacifico, I2M, Aix-Marseille Université. Algorithmes de type Chudnovsky sur la droite projective pour la multiplication dans les corps finis.

Résumé : Il existe différents modèles permettant de mesurer la complexité d’un algorithme de multiplication dans une extension finie d’un corps fini.La complexité bilinéaire d’un tel algorithme est le nombre de multiplications bilinéaires, dépendant des deux éléments que l’on souhaite multiplier, qu’il exécute.La méthode de D.V. et G.V. Chudnovsky (1988) permet de construire des algorithmes ayant une bonne complexité bilinéaire. Ce sont des algorithmes d’évaluation/interpolation utilisant les points rationnels de courbes algébriques, i.e. les places rationnelles d’un corps de fonctions. Cette méthode a depuis été généralisée de différentes manières, et notamment à l’évaluation en des places de degrés arbitraires.Dans cet exposé, nous proposons une construction générique récursive d’algorithmes de type Chudnovsky sur le corps des fonctions rationnelles, évaluant sur des places de degrés croissants. Notre construction permet d’obtenir des algorithmes d’interpolation polynômiale constructibles en temps polynômial et ayant une complexité bilinéaire intéressante, pour un degré d’extension quelconque.D’autres part, nous verrons qu’il existe un profond lien entre ces algorithmes et les codes correcteurs d’erreurs géométriques.

Prépublication : https://arxiv.org/abs/2007.16082

• • 15h45 : Benjamin Wesolowski, CNRS & ENS de Lyon- Hard problems for isogeny-based cryptography

Abstract: Isogeny-based cryptography is one of the few branches of public-key cryptography
that promises to resist quantum attacks. The security of these cryptosystems relates to the
(presumed) hardness of a variety of computational problems: finding paths in large « isogeny
graphs », computing endomorphisms of elliptic curves, or inverting group actions. We present
these problems, analyse their hardness, and discuss their applications to post-quantum
cryptography.

La prochaine édition du séminaire se tiendra le vendredi 7 octobre en salle Jacques-Louis Lions à l’INRIA Paris.

• 10:00. Thomas Decru, imec-COSIC, KU Leuven, Belgium.

  An efficient key recovery attack on SIDH.

  Abstract: SIDH is an isogeny-based public key exchange protocol from 2011 conjectured to be resistant against attacks from both classical and quantum computers. SIKE, which is a key encapsulation based on SIDH, advanced to the 4th round of NIST’s post-quantum standardization process as alternative candidate for becoming a new standard for public key exchanges.

  In this talk we will discuss how the information from the SIDH protocol can be turned into an isogeny between scarce types of abelian surfaces, a so called “glue-and-split” isogeny in dimension two which stems from a theorem by Kani from 1997. This allows us to break the decisional version of the SIDH protocol, which in turn breaks the computational version. The attack requires certain assumptions, but is very practical and can break all the proposed NIST security levels of SIKE within a day on a regular desktop computer with one core.

  Joint work with Wouter Castryck.

• 11:10. Alexandre Wallet, INRIA Rennes.

  Mitaka – a simpler, parallelizable, maskable variant of Falcon.

  Résumé : Falcon est un schéma de signature fondé sur les réseaux euclidiens, et récemment sélectionné par le NIST comme futur standard post-quantique. En consommation de bande passante, Falcon est actuellement la meilleure alternative, et ses performances sont proches de celle de l’autre schéma sélectionné, Dillithium. Cependant, les choix de design de Falcon imposent des limites conceptuelles freinant son utilisation dans différents scénarios : 1) les jeux de paramètres sont très restreints ; 2) implémenter le schéma est un exercice délicat ; 3) protéger son implémentation actuelle a un coût prohibitif en plus d’être difficile.

  Les facteurs limitants du schéma sont principalement liés à son échantillonneur de vecteurs Gaussiens dans des réseaux euclidiens. Notre variante Mitaka, qui suit le design général de Falcon, évite les écueils précédents en utilisant un échantillonneur différent, appelé « hybride », et qui avait été mis de côté en raison d’un niveau de sécurité estimé plus faible. De manière générale, nos travaux ont montré que la sécurité apportée par l’hybride pouvait être équivalente à celle de Falcon, et que sa simplicité conceptuelle permet de plus grands choix de design et de protection, à faible coût. L’exposé présentera des techniques et outils qui nous ont permis d’obtenir ces résultats pour Mitaka, et mentionnera d’autres récentes améliorations générales pour hash-then-sign sur des réseaux.

  L’exposé sera inspiré de plusieurs travaux en collaboration avec Thomas Espitau, Pierre-Alain Fouque, François Gérard, Melissa Rossi, Akira Takahashi, Mehdi Tibouchi et Yang Yu.

• 13:45. Malika Izabachène, Cosmian, Paris, France. 

  Plug-and-play sanitization for TFHE.

  Résumé : Le chiffrement complètement homomorphe (FHE) permet d’évaluer une fonction arbitraire sur des messages chiffrés tout en préservant la confidentialité des messages. Cette propriété trouve de multiples applications, notamment lorsque l’on souhaite stocker des données sur le cloud tout en laissant la possibilité d’effectuer des calculs sur ces donnéesDans cet exposé, nous nous intéresserons à la confidentialité de l’algorithme opéré par le service du cloud.
  Une procédure d’assainissement (ou sanitization en anglais) d’un chiffré FHE garantit que toute l’information contenue dans ce chiffré, excepté le message associé, est détruite. En particulier, il est impossible de déterminer si des opérations, et lesquelles, ont été effectuées pour obtenir ce chiffré, même en connaissant la clé secrète.
  Nous verrons comment construire, à partir des bootstrappings de FHEW (Eurocrypt 2015) et TFHE (Asiacrypt 2016), une procédure qui permet d’apporter ces garanties de sécurité.

  Travail effectué en collaboration avec Florian Bourse.

• 14:45. Loïc Rouquette, INSA Lyon, LIRIS, CITI.

  Recherche de Distingueurs Boomerangs à l’aide de la Programmation par Contraintes

  Résumé : La cryptanalyse différentielle est une des techniques d’attaque les plus efficaces en cryptographie symétrique, elle repose sur l’exploitation de certaines propriétés statistiques des chiffrements. Plus précisément, il s’agit d’observer, pour un chiffrement E, la probabilité d’obtenir une différence en sortie δ_out = E_K(M) ⊕ E_K(M⊕δ_in) lorsqu’une différence δ_in est injectée en entrée. En 1999, David Wagner (FSE99) met au point une variante de l’attaque différentielle, plus efficace que cette dernière dans certains cas, qui consiste à décomposer la fonction de chiffrement en deux sous-fonctions : E_K = E_K⁰ ∘ E_K¹.

  Afin de s’assurer que les différences, propagées dans les deux sous-fonctions E_K⁰ et E_K¹, soient compatibles, Cid et co-auteurs (EuroCrypt18) ont introduit la notion de Boomerang Connectivity Table (BCT). Leur technique a ensuite été étendue et d’autres tables ont été introduites ; premièrement les tables UBCT et LBCT par Wang et Peyrin (ToSC19), puis la table EBCT par Delaune et co-auteurs (ToSC20).

  La complexité croissante des modèles découlant de ces techniques nécessite de mettre en oeuvre des techniques de résolution efficaces. Récemment les approches déclaratives (SAT, CP et (M)ILP) ont été appliquées avec succès à des problèmes de cryptanalyse différentielle.

  À l’aide de solveurs SAT et CP, nous proposons d’appliquer l’approche de résolution en deux étapes, qui commence par une analyse tronquée du chiffrement avant de passer à la version binaire, afin de calculer des caractéristiques différentielles boomerang sur Rijndael et Warp à partir des modèles de Delaune et co-auteurs (ToSC20) et de Gérault et co-auteurs (CP16). Dans un premier temps, nous montrons comment adapter le modèle de Delaune et co-auteurs (ToSC20) de Skinny à Rijndael et nous montrons également comment prendre en compte des différences dans la clé. Dans un second temps, nous montrons comment adapter la modélisation de Delaune et co-auteurs (ToSC20) aux schémas de Feistel et nous donnons nos résultats sur les chiffrements Warp, Twine et LBlock-S (ToSC22).

  Travail en commun avec Virgine Lallemand,  Marine Minier, Christine Solon

Exposés au séminaire C2 du vendredi 10 juin 2022

•  Clara Pernot, INRIA Paris, New Representations of the AES Key Schedule

Résumé : In this talk we present a new representation of the AES key schedule, with some implications to the security of AES-based schemes. In particular, we show that the AES-128 key schedule can be split into four independent parallel computations operating on 32 bits chunks, up to linear transformation. Surprisingly, this property has not been described in the literature after more than 20 years of analysis of AES. We show two consequences of our new representation, improving previous cryptanalysis results of AES-based schemes. First, we observe that iterating an odd number of key schedule rounds results in a function with short cycles. This explains an observation of Khairallah on mixFeed, a second-round candidate in the NIST lightweight competition. Our analysis actually shows that his forgery attack on mixFeed succeeds with probability 0.44 (with data complexity 220GB), breaking the scheme in practice. The same observation also leads to a novel attack on ALE, another AES-based AEAD scheme.

Our new representation also gives efficient ways to combine information from the first subkeys and information from the last subkeys, in order to reconstruct the corresponding master keys. In particular we improve previous impossible differential attacks against AES-128.

This is a joint work with Gaëtan Leurent.

• Thibauld Feneuil, CryptoExperts et Sorbonne Université –   Syndrome Decoding in the Head – Shorter Signatures from Zero-Knowledge proofs
  

Résumé : In this talk, I will present a new zero-knowledge proof of knowledge for the syndrome decoding (SD) problem on random linear codes. Instead of using permutations like most of the existing protocols, we rely on the MPC-in-the-head paradigm in which we reduce the task of proving the low Hamming weight of the SD solution to proving some relations between specific polynomials. Specifically, we propose a 5-round zero-knowledge protocol that proves the knowledge of a vector x such that y=Hx and wt(x)<= w and which achieves a soundness error closed to 1/N for an arbitrary N.

While turning this protocol into a signature scheme, we achieve a signature size of 11-12 KB for 128-bit security when relying on the hardness of the SD problem on binary fields. Using larger fields (like F_{256}), we can produce fast signatures of around 8 KB. This allows us to outperform Picnic3 and to be competitive with SPHINCS+, both post-quantum signature candidates in the ongoing NIST standardization effort. Since the security relies on the hardness of the syndrome decoding problem for random linear codes which is known to be NP-hard and for which the cryptanalysis state of the art has been stable for many years, it results in a conservative signature scheme. Moreover, our scheme outperforms all the existing code-based signature schemes for the common « signature size + public key size » metric.

Joint work with Antoine Joux and Matthieu Rivain.

• Fangan Yssouf Dosso, Ecole des Mines de Saint-Etienne, Département SAS – PMNS for efficient arithmetic and small memory cost

Résumé : The Polynomial Modular Number System (PMNS) is an integer number system which aims to speed up arithmetic operations modulo a prime p. Such a system is defined by a tuple (p, n, g, r, E), where p, n, g and r are positive integers, E is a monic polynomial with integer coefficients, having g as a root modulo p. Most of the work done on PMNS focus on polynomials E such that E(X) = X^n – l, where l is a nonzero integer, because such a polynomial provides efficiency and low memory cost, in particular for l = 2 or -2.

It however appeared that these are not always the best choices. In this presentation, we first start with the necessary background on PMNS. Then, we highlight a new set of polynomials E for very efficient operations in the PMNS and low memory requirement, along with new bounds and parameters. We show that these polynomials are more interesting than (most) polynomials E(X)=X^n – l. To finish, we see how to use PMNS to randomise arithmetic operations in order to randomise high level operations like elliptic curve scalar multiplication, to protect implementations against some advanced side channel attacks like differential power analysis (DPA).

Joint work with Jean-Marc Robert, Nadia EL MRABET,  Laurent-Stéphane DIDIER et Pascal Véron

• Ivan Pogildiakov,  IRMAR, Université Rennes 1 –  Binary codes, hyperelliptic curves, and the Serre bound

Résumé : Algebraic curves over finite fields have found nice applications in such areas as Coding theory and Cryptography. In that context, an object of this sort is meaningful only if its number of rational points is as close as possible to the celebrated Serre bound. However, the question regarding the existence of an algebraic curve having a prescribed number of rational points is of theoretical interest in its own right. There are different types of results in this direction in the literature such as, for example, providing explicit or non-explicit constructions in the case when either the definition field, or the genus, or the number of rational points varies.

In this talk, we propose a new approach for constructions of hyperelliptic curves over a fixed finite field of odd characteristic. As a main tool, a specific binary linear code defined by the field is used. A nice feature of the approach is that it allows one to translate the existence and the search problems of a hyperelliptic curve having desired parameters to that of a codeword of corresponding Hamming weight in a coset of the linear code. In some cases, by means of the machinery of the general theory of linear codes, we manage to find curves (having a fixed number of rational points) whose genera are reasonably close to the Serre bound.

For the sake of simplicity, the case of prime fields is mainly discussed. If time permits, as a by-product result, we will obtain new examples of curves with many points that improve upon some known lower bounds.

Le prochain séminaire C2 se tiendra en présentiel le vendredi 17 décembre 2021 à l’université de Rennes 1 dans l’amphithéâtre Métivier de l’IRISA sur le campus de Beaulieu

Lien visio à venir

Le programme est le suivant

• 9h30, Aurore Guillevic, Inria Nancy and Aarhus University – Elliptic curves for z-SNARKs

Joint work with Youssef El Housni, Consensys, Inria Saclay, ÉcolePolytechnique, and Diego Aranha, Aarhus University

Résumé : SNARK stands for Succinct Non-interactive ARgument of Knowledge and is a powerful tool in blockchains and cryptocurrencies. The most efficient at the moment is Groth’16 preprocessing SNARK, implemented with a pairing-friendly elliptic curve with a subgroup of prime order q of 255 bits (the BLS12-381 curve). It provides a zero-knowledge proof of an arithmetic circuit that performs arithmetic operations modulo q.

For a recursive SNARK, one applies again the strategy of arithmetisation and proof: a compiler produces an arithmetic circuit that performs some cryptographic computation (in Groth’16: computing pairings and checking an equation). This second circuit deals with arithmetic operations not modulo q but modulo p, the field of definition of the first curve. A second pairing-friendly elliptic curve is required, whose order should be this prime p: this is a chain of elliptic curves.

To achieve a recursive SNARK, and recursively prove proofs (a.k.a. bootstrapping proofs), in 2014, Ben-Sasson, Chiesa, Tromer, and Virza introduced a cycle of pairing-friendly curves: an MNT curve of prime
order q defined over a field GF(p), and a second MNT curve of prime order p defined over the prime field GF(q). That is, the field of definition of each curve is the order of the other curve. However, generating such curves takes a large computational effort: [BCTV14] spanned all curve discriminants up to 10^15 in 610 000 core-hours on a cluster to obtain two cycles: one of 298 bits, and a second one of 753 bits. Moreover, the pairing takes its values in a quartic extension for the first curve (1192 and 3012 bits respectively), which does not provide 128 bits of security anymore because of the TNFS algorithm computing discrete logarithms in extension fields (De Micheli et al. at Asiacrypt’21 present the first implementation). While a cycle of pairing-friendly curves is optimal for a recursive SNARK construction, it is very slow because of the many constraints on the curves. To date, no other cycle of pairing-friendly curves is known.

To circumvent the slowness of such cycles, one can instead use a chain of curves: the second (outer) curve has a subgroup of prime order being the field of definition of the first (inner) curve. Such a construction is much easier, and more pairing-friendly curves are possible. We generalise these constructions to families of SNARK-friendly 2-chains of pairing-friendly elliptic curves and compare their efficiency.

Finally, other cycles, half-cycles or chains of curves arise in variants of zero-knowledge proofs: cycles of non-pairing friendly curves such as Pallas-Vesta, half-pairing-friendly cycles such as Pluto-Eris. If time allows it, an overview of these alternative curves will be given.

• 10h45, Alexandre Wallet, Univ Rennes, CNRS, IRISA –   Vers le déploiement des schémas « Hash-and-sign » basés sur les réseaux Euclidiens

Résumé : La compétition de standardisation post-quantique du NIST arrive bientôt à sa fin. Parmi les trois finalistes principaux retenus pour les signatures numériques, on retrouve la proposition Falcon. Ce schéma correspond à une instanciation efficace du paradigme « GPV » (Gentry-Peikert-Vaikunthanatan), permettant de proposer des schémas de signatures numériques reposant sur la difficulté de problèmes de réseaux euclidiens structurés. En terme de vitesse et particulièrement de bande passante, Falcon semble surclasser ses concurrents directs. Cependant, le schéma souffre de limites conceptuelles pouvant freiner son utilisation dans différents scénarios : 1) les jeux de paramètres sont très restreints ; 2) implémenter le schéma est un exercice délicat ; 3) protéger l’implémentation, au moins vis-à-vis des « timing attacks »,
impacte sérieusement les performances du schéma (en plus d’être, là encore, techniquement exigeant).Dans cet exposé, je décrirai plus en détails les briques limitantes du schéma, principalement liées à l’échantillonnage de vecteurs Gaussiens dans des réseaux euclidiens. En effet, dans le cas de Falcon, c’est cette étape algorithmique qui décide de la sécurité théorique et concrète du schéma, mais c’est aussi une source de fuites du point de vue des attaques par canaux auxiliaires. Je présenterai ensuite Mitaka, une proposition alternative suivant le design de Falcon, permettant de s’affranchir des écueils précédents. Ainsi, notre schéma Mitaka est 1) conceptuellement plus simple, et instanciable via de grandes familles de paramètres ; 2) sensiblement plus rapide pour une sécurité et une consommation de bande passante équivalente ; 3) peut être masqué à un ordre arbitraire pour un coût modeste et avec des techniques standards. Enfin, il est possible d’implémenter Mitaka sans avoir recourt à de l’arithmétique en virgule flottante.

L’exposé sera inspiré de plusieurs travaux en collaboration avec T. Espitau, P.A. Fouque, F. Gérard, P. Kirchner, M. Rossi, A. Takahashi, M. Tibouchi et Y. Yu.

• 14h00 : Clara Pernot, INRIA Paris, New Representations of the AES Key Schedule

Résumé : In this talk we present a new representation of the AES key schedule, with some implications to the security of AES-based schemes. In particular, we show that the AES-128 key schedule can be split into four independent parallel computations operating on 32 bits chunks, up to linear transformation. Surprisingly, this property has not been described in the literature after more than 20 years of analysis of AES. We show two consequences of our new representation, improving previous cryptanalysis results of AES-based schemes. First, we observe that iterating an odd number of key schedule rounds results in a function with short cycles. This explains an observation of Khairallah on mixFeed, a second-round candidate in the NIST lightweight competition. Our analysis actually shows that his forgery attack on mixFeed succeeds with probability 0.44 (with data complexity 220GB), breaking the scheme in practice. The same observation also leads to a novel attack on ALE, another AES-based AEAD scheme.

Our new representation also gives efficient ways to combine information from the first subkeys and information from the last subkeys, in order to reconstruct the corresponding master keys. In particular we improve previous impossible differential attacks against AES-128.This is a joint work with Gaëtan Leurent.

• 15h15 : Victor Mollimard,  Univ Rennes, CNRS, IRISA – Efficient Methods to Search for Best Differential Characteristics on SKINNY

Résumé : Evaluating resistance of ciphers against differential cryptanalysis is essential to define the number of rounds of new designs and to mount attacks derived from differential cryptanalysis. In this paper, we propose automatic tools to find the best differential characteristics on the SKINNY block cipher. As usually done in the literature, we split this search in two stages denoted by Step 1 and Step 2. In Step 1, we aim at finding all truncated differential characteristics with a low enough number of active Sboxes. Then, in Step 2, we try to instantiate each difference value while maximizing the overall differential characteristic probability. We solve Step 1 using an ad-hoc method inspired from the work of Fouque et al. whereas Step 2 is modelized for the Choco-solver library as it seems to outperform all previous methods on this stage. Notably, for SKINNY-128 in the SK model and for 13 rounds, we retrieve the results of Abdelkhalek et al. within a few seconds (to compare with 16 days) and we provide, for the first time, the best differential related-tweakey characteristics up to 14 rounds for the TK1 model. Regarding the TK2 and the TK3 models, we were not able to test all the solutions Step 1, and thus the differential characteristics we found up to 16 and 17 rounds are not necessarily optimal.

Le prochain séminaire C2 se tiendra en présentiel le vendredi 15 octobre 2021 à l’INRIA Paris, 2 rue Simone Iff, Paris 12.

Le lien pour joindre la réunion en visio est :
https://univ-rennes1-fr.zoom.us/j/7058629792

Le programme est le suivant

• 10h00, Katharina Boudgoust, IRISA, Université Rennes 1, Hardness of Module Learning With Errors With Small Secrets

Résumé: This talk focuses on the module variant of the Learning With Errors problem (Module-LWE), a fundamental computational problem used in lattice-based cryptography nowadays. To highlight its importance for practical schemes, note that several finalists of the NIST standardization project rely on the hardness of Module-LWE, e.g., the signature scheme Dilithium and the key encapsulation mechanism Kyber.

More concretely, in this talk we consider Module-LWE, where the underlying secret is of small norm. Whereas several works prove the hardness of unstructured LWE with short secrets, only few was known for the module case. In this presentation I summarize our results that previously appeared at Asiacrypt 2020 and CT-RSA 2021, where we investigate the hardness of Module-LWE when the secret has coefficients in the set {0,1}, also called binary Module-LWE. Furthermore, I show that both results naturally generalize to secrets with bounded coefficients. The talk concludes with some interesting open questions related to the hardness of Module-LWE with non-uniform secrets.

This is a joint work with Corentin Jeuy, Adeline Roux-Langlois and Weiqiang Wen.

• 11h15, Magali Bardet, LITIS, Université de Rouen Normandie, Algebraic cryptanalysis of problems in code-based cryptography and applications

Abstract: Rank-metric code-based cryptography relies on the hardness of decoding a random linear code in the rank metric. This fundamental problem is called the Minrank problem, and is ubiquitous in rank metric (or even Hamming metric) code based cryptography as well as in multivariate cryptography. For structured instances arising in the former, their security rely on a more specific problem, namely the Rank Syndrome Decoding problem. There is also a generalization called the Rank Support Learning problem, where the attacker has access to several syndromes corresponding to errors with the same support. Those problems have various applications in code-based and multivariate cryptography (KEM and signature schemes), and a precise understanding of the complexity of solving them can help designers to create secure parameters.

In this talk, I will present the three problems and their relations to cryptographic schemes, their algebraic modeling and the recent improvements in the understanding of the complexity of solving those systems using algebraic techniques like Gröbner bases computations.

Joint works with Pierre Briaud, Maxime Bros, Daniel Cabarcas, Philippe Gaborit, Vincent Neiger, Ray Perlner, Olivier Ruatta, Daniel Smith-Tone, Jean-Pierre Tillich and Javier Verbel.

• 13h45 : Antonin Leroux, Grace, LIX et INRIA Saclay–Île-de-France, Séta: Supersingular Encryption from Torsion Attacks

Résumé : We present Séta, a new family of public-key encryption schemes with post-quantum security based on isogenies of supersingular elliptic curves. It is constructed from a new family of trapdoor one-way functions, where the inversion algorithm uses Petit’s so called torsion attacks on SIDH to compute an isogeny between supersingular elliptic curves given an endomorphism of the starting curve and images of torsion points. We prove the OW-CPA security of S´eta and present an IND-CCA
variant using the post-quantum OAEP transformation. Several variants for key generation are explored together with their impact on the selection of parameters, such as the base prime of the scheme. We furthermore formalise an “uber” isogeny assumption framework which aims to generalize computational isogeny problems encountered in schemes including SIDH, CSDIH, OSIDH and ours. Finally, we carefully select parameters to achieve a balance between security and run-times and present experimental results from our implementation

• 15h00 : Chloé Hébant, Cascade, ENS et INRIA Paris  Traceable Constant-Size Multi-Authority Credentials,

Abstract: Many attribute-based anonymous credential (ABC) schemes have been proposed allowing a user to prove the possession of some attributes, anonymously. They became more and more practical with, for the most recent papers, a constant-size credential to show a subset of attributes issued by a unique credential issuer. However, proving possession of attributes coming from K different credential issuers usually requires K independent credentials to be shown. Only attribute-based credential schemes from aggregatable signatures can overcome this issue.

In this paper, we propose new ABC schemes from aggregatable signatures with randomizable tags. We consider malicious credential issuers, with adaptive corruptions and collusions with malicious users. Whereas our constructions only support selective disclosures of attributes, to remain compact, our approach significantly improves the complexity in both time and memory of the showing of multiple attributes: for the first time, the cost for the prover is (almost) independent of the number of attributes and the number of credential issuers.

Whereas anonymous credentials require privacy of the user, we propose the first schemes allowing traceability.

We formally define an aggregatable signature scheme with (traceable) randomizable tags, which is of independent interest. We build concrete schemes from the recent linearly homomorphic signature scheme of PKC 20. As all the recent ABC schemes, our construction relies on signatures which unforgeability is proven in the bilinear generic group model.