10:00
11:40 | Mini-session: Post-Quantum Cryptography
The focus of this mini-session are recent results on the design of ciphers that may resist attacks performed with quantum computers. Indeed, the quantum threat is among the most feared in modern cryptography. This mini-session will start with a keynote by Prof. Simona Samardjiska, a young brilliant expert in this controversial field.
- Simona Samardjiska, Radboud University (Netherlands)
Invited talk: Algorithms for solving the matrix code equivalence problem Abstract In the past few years, there has been an increased interest in hard equivalence problems, especially with NIST's announcement of a fourth round for new designs of digital signatures. On a high level, such a problem can be defined as follows: Given two algebraic objects, find - if any - an equivalence that maps one object into the other. Several instantiations have been considered for cryptographic purposes, for example - Isomorphism of polynomials (Pattarin '96), Code equivalence (Biasse et al. '20), Matrix Code equivalence (Chou et al. '22), Alternating trilinear form equivalence (Tang et al.'22), Lattice isomorphism (Ducas & van Woerden '22). All of these problems are believed to be hard even for quantum adversaries. Conveniently, they can generically be used to build a Sigma protocol and further a post-quantum secure signature using the Fiat-Shamir transform.
In this talk I will make a broad overview of algorithms for solving the matrix code equivalence problem and how they can be applied to related problems. In particular, I will focus on algebraic and graph-based algorithms which are currently the state-of-the-art for solving the problem. I will further argue that clever combination of the two technics often leads to the best, and sometimes surprising results. - Antonio J. Di Scala and Carlo Sanna, Polytechnic University of Turin (Italy)
Smaller public-keys for MinRank-based schemes Abstract In this talk, we will explore the MinRank problem, a well-established problem in linear algebra with significant relevance for post-quantum cryptography. We will focus on the search version of MinRank, which involves finding a non-trivial linear combination of given matrices whose rank is below a specified threshold. MinRank is particularly attractive for cryptographic applications due to its foundation in linear algebra, its NP-completeness, and the absence of efficient quantum algorithms that can solve it.
We will introduce a new key-generation algorithm for MinRank-based cryptographic schemes, which we call KeyGen3. This algorithm significantly reduces the size of the public key compared to existing methods, achieving a compression of about 50% relative to the current best approach, KeyGen2. Additionally, we will provide a rigorous proof that the security of KeyGen3 is closely related to that of KeyGen1, with a negligible security loss. Our results demonstrate that KeyGen3 offers a highly efficient and secure method for public key compression in MinRank-based cryptography. - Delaram Kahrobaei, City University of New York (USA)
Carmine Monetta, Maria Tota and Martina Vigorito University of Salerno (Italy)
Ludovic Perret, Sorbonne University & LIP6 (France)
Investigation of Metabelian Platform Groups for Protocols Based on the (Simultaneous) Conjugacy Search Problem Abstract We will cover advancements in the field of group-based cryptography, particularly focusing on the cryptanalysis of protocols using metabelian groups as the platform. Building on previous work, we will generalize the Field-Based Attack (FBA) to demonstrate how both the Conjugacy Search Problem (CSP) and Simultaneous Conjugacy Search Problem (SCSP) can be cryptanalyzed for certain classes of metabelian groups of the form G=M⋉NG=M⋉N, where both MM and NN are abelian. These groups naturally arise in linear algebra and ring theory.
Specifically, we will present two main results: a polynomial-time algorithm that breaks the Commutator Key-Exchange Protocol (AAG) and the non-commutative Diffie-Hellman Key-Exchange Protocol (Ko-Lee) for groups of this form. These results indicate that while metabelian groups have been proposed as secure platforms for these protocols, certain families must be avoided due to their vulnerability to efficient cryptanalysis.
|
12:00
13:00 | Mini-session: Public-key cryptography
In this session we discuss security and performance of (classical) public-key cryptography, which includes the most widely adopted cryptographic protocols in the Internet.
- Giordano Santilli, Agenzia per la Cybersicurezza Nazionale (Italy)
Daniele Taufer, KU Leuven (Belgium)
First-degree prime ideals of composite extensions Abstract We will present our findings on first-degree prime ideals within composite extensions of number fields. Building on the known methods for biquadratic fields, we generalize the approach to composite fields of any degree, showing that first-degree prime ideals can be effectively computed from norms in their minimal subfields. We demonstrate that this method preserves the divisibility of principal ideals, with only rare exceptions. These results provide a novel framework with significant implications for computational algebra, particularly in the context of large extensions constructed from smaller fields. - Marco Macchetti and Nils Amiet, Kudelski Group (Switzerland)
A Novel Related Nonce Attack for ECDSA Abstract We will introduce a novel cryptanalytic attack on the Elliptic Curve Digital Signature Algorithm (ECDSA) that exploits complex polynomial relationships among nonces. Unlike previous attacks that focused on linear relationships or simple biases in nonce generation, our approach addresses cases where nonces are related through higher-degree algebraic equations, such as those generated by quadratic or cubic congruential generators. We demonstrate how this attack can retrieve the private key from a small set of signatures, broadening the scope of vulnerabilities in ECDSA, including widely used implementations like secp256k1. - Dmitrii Koshelev, University of Lleida (Spain)
Application of Mordell-Weil lattices with large kissing numbers to acceleration of multiscalar multiplication on elliptic curves Abstract In this presentation, we explore the use of Mordell–Weil (MW) lattices to accelerate multi-scalar multiplication (MSM) on elliptic curves, specifically for curves with a j-invariant of 0. MSM is a crucial yet computationally expensive operation in elliptic curve cryptography. By leveraging MW lattices with large kissing numbers—indicative of high efficiency in evaluating points—we can significantly enhance the performance of MSM. The focus is on utilizing these lattices to optimize the generation of auxiliary points, particularly on j = 0 curves, where their structure provides optimal conditions for reducing computational overhead in cryptographic operations.
|
