CIFRIS24 - an event by De Cifris
Venue: Banca d'Italia, Centro D. Menichella, Largo Guido Carli 1, Frascati (Roma)
Social dinner: September 25th, Satiricus, Via dei Corridori 58, Roma
September 25th, 26th, 27th 2024
Scientific Session
Description
The Scientific Session of CIFRIS24 is dedicated to advancing knowledge and fostering collaboration among researchers in the field of cryptography. This session features a series of invited and contributed talks, selected by the Chairs and the Programme Committee from submitted papers. Participants will have the opportunity to present and discuss their latest research findings, methodologies, and theoretical advancements. Covering a wide range of topics, from foundational cryptographic theories to practical applications, the Scientific Session aims to stimulate intellectual exchange and inspire innovative solutions to contemporary challenges in cryptography. This gathering serves as a vibrant forum for sharing cutting-edge research and forging new collaborations within the global cryptographic community.
Program
September 25th, 26th
Main Hall
September 25th (afternoon) - Scientific Session
Centro D. Menichella, Largo Guido Carli 1, Frascati (Rome) |
|---|
14:00
15:20 | Mini-session: Boolean functions
The focus of this mini-session is the precise design of symmetric cryptosystems, in order to have them provably secure. Boolean functions represent a key ingredient in the cryptosystem design. This mini-session will start with a keynote by Prof. Emeritus Claude Carlet, considered by many the world expert on Boolean functions.
- Claude Carlet, University of Paris VIII and LAGA (France)
Invited talk: Quadratic-like balanced functions and permutations Abstract The so-called (n,m)-functions have very nice properties when quadratic, which for instance ease the study of their almost perfect nonlinearity. But quadratic functions are weak against some other attacks. It is then important to study strict superclasses sharing some of these properties. In particular, when the block ciphers have a structure of substitution-permutation network (SPN), the substitution boxes must be permutations (m=n).
It is then essential to study superclasses of quadratic functions within the class of balanced functions. We shall introduce and study such a superclass, that of "quadratic-like balanced functions" ("permutations" when m=n). - Augustine Musukwa, University of Trento (Italy)
On second-order derivatives of Boolean functions and cubic APN permutations in even dimension Abstract The big APN problem is one of the most important challenges in the theory of Boolean functions, i.e. finding a new APN permutation in even dimension. Among this class of functions, those with the lowest possible degree are cubic. Yet, none has been found so far. In this paper, we introduce new parameters for Boolean functions and for vectorial Boolean functions, mostly derived from the behavior of their second-order derivatives. These parameters are particularly relevant for small-degree functions. They allow studying bent, semi-bent and APN functions of degrees two and three. In particular, they allow tackling the big APN problem for cubic permutations.
|
15:20
15:40 | Coffee break |
15:40
17:00 | Mini-session: Protocols and Zero-Knowledge
This mini-session focusses on the analysis and design of cryptographic protocols. Zero-knowledge proofs are a fundamental tool in the design of many of them, and have a wide range of applications. This mini-session will start with a keynote by Daniele Venturi, Full Professor at La Sapienza, Rome.
- Daniele Venturi, University of Roma La Sapienza (Italy)
Invited talk: 20 Years of Leakage-Resilient Cryptography Abstract Cryptographic schemes are usually analyzed under the assumption that the underlying secrets are fully hidden from the adversary. Unfortunately, history has taught us that many (otherwise provably secure) cryptosystems can be spectacularly broken by exploiting physical phenomena (the so-called side-channel attacks) resulting in partial information leakage about the underlying secret keys.
Leakage-resilient cryptography aims at closing the above gap by designing cryptosystems with provable guarantees even in the presence of attackers running different forms of side-channel attacks. This talk surveys the most important techniques behind leakage-resilient cryptography, since its introduction in the seminal works by Ishai, Sahai and Wagner (CRYPTO 2003) and Micali and Reyzin (TCC 2004). - Delaram Kahrobaei, City University of New York (USA)
Ludovic Perret, Sorbonne University & LIP6 (France)
Martina Vigorito, University of Salerno (Italy)
Security Analysis of ZKPoK based on MQ problem in the Multi-Instance Setting Abstract We will investigate the Multivariate Quadratic (MQ) problem, a well-known post-quantum hard problem, and introduce a new variant called the Differential Multivariate Quadratic Homogeneous (DiffMQH) problem. We present a polynomial-time algorithm that solves the DiffMQH problem by reducing it to finding collisions in a quadratic system. Our analysis demonstrates that while the MQ problem is challenging, the DiffMQH problem is significantly easier to solve, suggesting that this approach may not be secure for practical cryptographic applications.
|
September 26th
September 26th (morning) - Scientific Session
Centro D. Menichella, Largo Guido Carli 1, Frascati (Rome) |
|---|
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.
|
11:40
12:00 | Coffee break |
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.
|
13:00
14:00 | Lunch |
September 26th (afternoon) - Scientific Session
Centro D. Menichella, Largo Guido Carli 1, Frascati (Rome) |
|---|
14:00
15:40 | Mini-session: Theoretical cryptography
The security of cryptosystems heavily depends on their mathematical foundations. In this mini-session we start with a keynote by Prof. Gregor Leander, managing editor of the journal IACR Transaction of Symmetric Cryptography, and then we present two advanced schemes that provide security even when computations are performed in a hostile environment.
- Gregor Leander, Ruhr-University Bochum (Germany)
Invited talk: Low Latency Designs: Primitives and Beyond Abstract In this talk I will explain the different cryptographic primitives that have been developed in the area of symmetric cryptography that allow encryption with a very small latency. Applications are in particular memory encryption or cache-randomization. - Maria Ferrara, Paolo Santonastaso, Antonio Tortora and Ferdinando Zullo, University of Campania (Italy)
Polynomial functional encryption schemes Abstract In this talk, motivated by the construction of practically efficient functional encryption scheme supporting more than linear functionalities, we describe a new functional encryption scheme whose functionalities are polynomials. Such scheme is an extension of a known quadratic encryption scheme. - Massimo Giulietti, Paolo Martinelli and Marco Timpanella, University of Perugia (Italy)
Modern Techniques in Somewhat Homomorphic Encryption Schemes Abstract This paper emphasizes the transition from classic SWHE schemes to modern approaches utilizing lattice-based problems, such as Learning With Errors (LWE). LWE, introduced by Regev, is central to both SWHE and FHE due to its security reductions to hard lattice problems, which are conjectured to be resistant to quantum attacks. This makes LWE-based schemes particularly attractive for constructing secure and efficient homomorphic encryption systems.
|
15:40
16:00 | Coffee break |
16:00
16:40 | Mini-session: Applied Cryptography
The focus of this session is to show the importance of practical implementations of cryptography, while at the same time showing the deep link between theory and practice in this research field.
- Francesco De Sclavis, Giuseppe Galano, Sara Giammusso, Michela Iezzi, Antonio Muci and Matteo Nardelli, Bank of Italy (Italy)
Annalisa Cimatti and Marco Pedicini, Roma Tre University (Italy)
Dynamic-FROST: Schnorr Threshold Signatures with a Flexible Committee Abstract We will present Dynamic-FROST (D-FROST), an innovative extension of the FROST threshold signature scheme, which allows for dynamic changes in the committee and threshold without altering the group public key. By integrating FROST with CHURP, a Dynamic Proactive Secret Sharing scheme, D-FROST enables flexible committee adjustments and proactive share updates. This approach ensures continued security and confidentiality while avoiding the need for a central dealer or repeated key generation. We demonstrate how D-FROST maintains EUF-CMA security and provides a practical solution for evolving decentralized systems and blockchain applications. - Fadi Barbara and Enrico Guglielmino, Polytechnic University of Turin (Italy)
Nadir Murru, University of Trento (Italy)
Claudio Schifanella, University of Turin (Italy)
BTLE: Atomic Swaps with Time-Lock Puzzles Abstract In this talk, we introduce Broadcast Time-Lock Exchange (BTLE), a novel approach to cross-chain communication leveraging time-lock puzzles. Our method builds upon Rivest’s time-lock puzzle concept and extends it to a broadcast setting, enabling decentralized exchanges among multiple participants without requiring prior acquaintance. We propose a decentralized matching algorithm and a new type of time-lock puzzle based on Pell conics, which can be transformed into a Verifiable Delay Function. Our solution includes a comparative analysis with existing methods, an implementation of both the matching algorithm and exchange protocol, and a security proof in the hybrid ideal/real world simulation. This work aims to enhance cross-chain transactions in dynamic and decentralized environments.
|