Description
11h30 Katharina Boudgoust (CR CNRS, LIRMM) : The Power of NAPs: Compressing OR-Proofs via Collision-Resistant Hashing
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
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).
14h45 Clémence Bouvier (CR Inria, Loria) : Some Applications of Algebraic Geometry to Linear Cryptanalysis
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.
16h00 Alex Bredariol Grilo (CR CNRS, LIP6) : Computational Assumptions in the Quantum World
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.
Prochains exposés
-
Combining Partial Sums and FFT for the Fastest Known Attack on 6‑Round AES
Orateur : Shibam Ghosh - Inria
The partial-sums technique introduced by Ferguson et al. (2000) achieved a 6‑round AES attack with time complexity 2^{52} S‑box evaluations, a benchmark that has stood since. In 2014, Todo and Aoki proposed a comparable approach based on the Fast Fourier Transform (FFT). In this talk, I will show how to combine partial sums with FFT to get "the best of both worlds". The resulting attack on 6[…]-
Cryptography
-
-
Lie algebras and the security of cryptosystems based on classical varieties in disguise
Orateur : Mingjie Chen - KU Leuven
In 2006, de Graaf et al. proposed a strategy based on Lie algebras for finding a linear transformation in the projective linear group that connects two linearly equivalent projective varieties defined over the rational numbers. Their method succeeds for several families of “classical” varieties, such as Veronese varieties, which are known to have large automorphism groups. In this talk, we[…]-
Cryptography
-
-
Some applications of linear programming to Dilithium
Orateur : Paco AZEVEDO OLIVEIRA - Thales & UVSQ
Dilithium is a signature algorithm, considered post-quantum, and recently standardized under the name ML-DSA by NIST. Due to its security and performance, it is recommended in most use cases. During this presentation, I will outline the main ideas behind two studies, conducted in collaboration with Andersson Calle-Vierra, Benoît Cogliati, and Louis Goubin, which provide a better understanding of[…] -
Wagner’s Algorithm Provably Runs in Subexponential Time for SIS^∞
Orateur : Johanna Loyer - Inria Saclay
At CRYPTO 2015, Kirchner and Fouque claimed that a carefully tuned variant of the Blum-Kalai-Wasserman (BKW) algorithm (JACM 2003) should solve the Learning with Errors problem (LWE) in slightly subexponential time for modulus q = poly(n) and narrow error distribution, when given enough LWE samples. Taking a modular view, one may regard BKW as a combination of Wagner’s algorithm (CRYPTO 2002), run[…]-
Cryptography
-
-
CryptoVerif: a computationally-sound security protocol verifier
Orateur : Bruno Blanchet - Inria
CryptoVerif is a security protocol verifier sound in the computational model of cryptography. It produces proofs by sequences of games, like those done manually by cryptographers. It has an automatic proof strategy and can also be guided by the user. It provides a generic method for specifying security assumptions on many cryptographic primitives, and can prove secrecy, authentication, and[…]-
Cryptography
-
-
Structured-Seed Local Pseudorandom Generators and their Applications
Orateur : Nikolas Melissaris - IRIF
We introduce structured‑seed local pseudorandom generators (SSL-PRGs), pseudorandom generators whose seed is drawn from an efficiently sampleable, structured distribution rather than uniformly. This seemingly modest relaxation turns out to capture many known applications of local PRGs, yet it can be realized from a broader family of hardness assumptions. Our main technical contribution is a[…]-
Cryptography
-