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.
Practical infos
Next sessions
-
Updatable Encryption from Group Actions
Speaker : Maxime Romeas - ANSSI
Updatable Encryption is a variant of symmetric encryption that allows to rotate the encryption key in the outsourced storage setting while minimizing the bandwith used. Indeed, any third party can update ciphertexts to the new key using a token provided by the key holder. UE schemes aim at providing strong confidentiality guarantees against adversaries that can corrupt keys and tokens. In this[…] -
Euclidean lattice and PMNS: arithmetic, redundancy and equality test
Speaker : Fangan Yssouf Dosso - Laboratoire SAS, École des Mines de Saint-Étienne
The Polynomial Modular Number System (PMNS) is an integer number system that aims to speed up arithmetic operations modulo a prime number p. This system is defined by a tuple (p, n, g, r, E), where p, n, g and r are positive integers, and E is a polynomial with integer coefficients, having g as a root modulo p. Arithmetic operations in PMNS rely heavily on Euclidean lattices. Modular reduction in[…]