Abstracts

Monday, 08.04.2024

10:00-10:30
Talk: Differential Privacy in the Large Composition Regime
Speaker: Flavio du Pin Calmon
We highlight recent findings at the interface of information theory and differential privacy. First, we introduce a new differential privacy (DP) accountant called the saddle-point accountant (SPA). Our approach is inspired by the saddle-point method -- a ubiquitous numerical technique in statistics. We then overview results on optimizing differential privacy mechanisms when data is queried many times, i.e., the "large-composition" regime. We describe two new family of privacy mechanisms optimized for this regime: "Cactus Mechanisms," which are found by solving a convex optimization problem,  and "Schrödinger mechanisms," which are analytical mechanisms optimized for the large composition and small sensitivity regime.

10:30-11:00
Talk: Decentralized Learning Algorithms via Random Walks on Graphs
Speaker: Salim El Rouayheb
Distributed learning algorithms, such as Federated Learning, rely critically on a central server, aka Parameter Server (PS),  to perform and send out model aggregation in each iteration. This makes the PS the Achilles heel of the system when it fails or is temporarily unavailable or when it presents security and privacy vulnerabilities. Moreover, the communication cost to the PS, typically in the cloud, can be the bottleneck especially in the case of large models. We study Random Walk (RW) learning as an alternative way to achieve distributed learning without the reliance on any central server. The setting consists of data that is distributed over the nodes of a graph. The goal is to learn a global model of the distributed data without the standard reliance on a central server. We study a decentralized SGD algorithm in which a random walk on the network carries a global model. The model is updated based on the local data of the current node being visited. We focus on different problems of designing the RW to speed up the convergence of the algorithm using importance sampling and Metropolis-Hastings algorithm with differential privacy guarantees.

14:30-15:00
Talk: Characterizing the Harms from Information Leakage in Communications
Speaker: Anand Sarwate
Classical models for communication channels either assume a worst-case or average-case models for the channel. For example, for binary input channels, the basic coding theory model allows errors/erasures to depend on the transmitted codeword whereas the basic Shannon theoretic DMC model assumes i.i.d. channel behavior. Arbitrarily varying channels (AVCs) allow us to interpolate between these models and have been extended to scenarios where the channel can have partial dependence on the transmitted codeword by introducing an information leakage model in which a eavesdropper can use the information they learn to affect the channel behavior. This introduces a new twist to the classic wiretap considerations: instead of a privacy/security concern about how much information is leaked to the eavesdropper, the issue becomes how well they can use the leaked information to make the main channel behavior worse. These models operationalize the harms of information leakage and exhibit some interesting dichotomies. This talk will discuss some of these structural results as well as approaches to construct computationally efficient codes suitable for this type of interference.
 

15:00-15:30
Talk: Private Read-Update-Write in Federated Learning
Speaker: Sennur Ulukus

Tuesday, 09.04.2024

09:30-10:00
Talk: New Directions in Private Computation
Speaker: Netanel Raviv
The interest in information/coding theoretic solutions for private computations has increased lately, due to rising concerns about data privacy. However, techniques such as private information retrieval and coded computing often fall short of accurately reflecting the nature of computations and systems used in practical applications.
In the area of private information retrieval (or more specifically, private computation), a user stores a file in a storage system, and at a later point in time wishes to retrieve a linear combination of that file while keeping the coefficients private. Previous works have addressed this problem when the coefficients are from a finite field, a setting which is rare in practical applications. We show that clear information-theoretic guarantees can be made by focusing on quantized real numbers, which are common in machine learning inference. Our results are tightly connected to a recently proposed complexity measure for quantized real numbers, which may be of independent interest.
In the area of coded computing, it has been traditionally assumed that the system administrator is trusted, and privacy guarantees have been given in terms of restricted collusion among worker nodes. This does not accurately reflect most data delegation scenarios, since usually the system’s administrator and the worker nodes form one cohesive entity which itself poses a privacy risk. We address this issue by leveraging the recently proposed notion of perfect subset privacy. Our scheme enables the user to delegate polynomial computation to a system administrator, which may further employ worker nodes that might straggle, while guaranteeing zero information leakage from every set of data entries up to a certain size. Our scheme relies on existing and new problems related to puncturing Reed-Muller codes. Joint work with Zirui (Ken) Deng, Vinayak Ramkumar, and Rawad Bitar.

10:00-10:30
Talk: Secure Distributed Matrix Multiplication with Precomputation
Speaker: Rafael D’Oliveira
We consider the problem of secure distributed matrix multiplication in which a user wishes to compute the product of two matrices with the assistance of honest but curious servers. We show how to construct polynomial schemes for the outer product partitioning which take advantage of the user's ability to precompute and provide bounds for our technique. We show that precomputation allows for a reduction in the order of the time complexity for the cases where the number of colluding servers is a fixed percentage of the number of servers. Furthermore, with precomputation, any percentage (less than 100%) of collusions can be tolerated, compared to the upper limit of 50% for the case without precomputation.

11:30-12:00
Talk: McEliece with Hints
Speaker: Alexander May
We study the problem of McEliece full secret key recovery from partial information, focussing on polynomial time attacks.

12:00-12:30
Talk: Algebraic and Combinatorial Algorithms for Equivalence Problems
Speaker: Monika Trimoska
Broadly, an equivalence problem considers two instances of the same mathematical object and asks if there exists a map between them that preserves some defined property. Two such problems will be looked at in detail in this talk. The matrix code equivalence problem takes as input two error-correcting codes in the rank metric and the map we are tasked to find is an isometry that preserves the rank of codewords. The second problem we are interested in is the alternating trilinear form equivalence, where we are given two alternating trilinear forms and the goal is to find an isomorphism between them. We first show how these two problems are similar, namely that an alternating trilinear form can be viewed as a matrix code with special properties, or that a matrix code can be viewed as a trilinear form without the alternating property. We then present a survey of recent advances in solving these two problems both with purely algebraic algorithms and with combinatorial algorithms that have algebraic system solving as subroutines. The rising interest in these problems is due to their aptness for building a zero-knowledge-based identification scheme. As such, these two problems, alongside the code equivalence problem in the Hamming metric, have been used as a hardness assumption in the design of the Fiat-Shamir-based digital signature schemes MEDS, ALTEQ, and LESS, which are candidates for standardization in the additional call for digital signatures by NIST.

14:30-15:00
Talk: Algebraic Attack for the Rank Decoding Problem
Speaker: Magali Bardet
I will present different algebraic modelings that solve the decoding problem for codes in Rank metric. I will describe algorithms that solve the modelings and provide a complexity analysis for random instances.

15:00-15:30
Talk: Analysis of the Decryption Failure Rate for the HQC Cryptosystem
Speaker: Nicolas Aragon
The Hamming Quasi-Cyclic (HQC) cryptosystem is a code-based public-key encryption scheme that is currently being evaluated in the round 4 of the NIST post-quantum cryptography standardisation process. In HQC, a public error-correcting code is needed to remove noise inherent to the decryption process. In this talk we present how to analyse the decryption failure rate (DFR) for the HQC cryptosystem, and show the results of this analysis when instantiating HQC with concatenated Reed-Muller and Reed-Solomon codes. We also provide lower bounds on the length of the public code that can be used for the HQC cryptosystem. Based on a joint work with Carlos Aguilar-Melchor, Jean-Christophe Deneuville, Philippe Gaborit, Jérôme Lacan and Gilles Zémor.

Wednesday, 10.04.2024

09:30-10:00
Talk: Code-Based Cryptography in the Lee Metric
Speaker: Anna-Lena Horlemann
Classically code-based cryptography uses the Hamming metric, and more recently also the rank metric. In general, the functionality of systems like the McEliece or Niederreiter cryptosystem are not dependent on the metric and it is hence straight-forward to replace the Hamming metric with (for example) the Lee metric. What does change by doing so is the security analysis (i.e., the difficulty of solving the syndrome decoding problem) and the efficiency (i.e. the decoding complexity) in this new metric. In this talk we give an overview of results in code-based cryptography with respect to the Lee metric. Furthermore, we show some connections to lattice-based cryptography and how techniques from there can be exploited to attack Lee metric code-based cryptosystems.

10:00-10:30
Talk: Lattices & Codes: Algorithmic Connections and New Constructions
Speaker: Elena Kirshanova
The talks will consist of two parts. In the first part, I present an algorithm for decoding random binary linear codes largely influenced by sieving algorithms for lattices. I explain how to translate the Locality Sensitive Hashing techniques from lattices to codes and what this gives as algorithmically. This part of the talk is based on joint work with Léo Ducas, Andre Esser, and Simona Etinski.
In the second part of my talk I show an explicit construction of an efficiently decodable family of n-dimensional lattices whose minimum distances achieve Omega(sqrt{n}/(log n)^{eps} which is the state-of-the-art largest lower bound on the minimum. The construction is a type-D lattice built from Garcia-Stichtenoth tower codes. This part is based on joint work with E. Malygina.

11:30-12:00
Talk: Coding-Based Hybrid Post-Quantum Cryptosystem for Non-Uniform Information
Speaker: Alejandro Cohen
In this talk, I will introduce for non-uniform messages a novel hybrid universal network coding cryptosystem (NU-HUNCC) in the finite block length regime that provides Post-Quantum (PQ) security at high communication rates. Recently, hybrid cryptosystems offered PQ security by premixing the data using secure linear coding schemes and encrypting only a small portion of it. The data is assumed to be uniformly distributed, an assumption that is often challenging to enforce. Standard fixed-length lossless source coding and compression schemes guarantee a uniform output in normalized divergence. Yet, this is not sufficient to guarantee security. I will present an efficient almost uniform compression scheme in non-normalized variational distance for the proposed hybrid cryptosystem, that by utilizing a uniform sub-linear shared seed, guarantees PQ security. Specifically, for the proposed PQ cryptosystem, first, I will show an end-to-end practical coding scheme, NU-HUNCC, for non-uniform messages. Second, I will demonstrate that NU-HUNCC is information-theoretic individually secured (IS) against an eavesdropper with access to any subset of the links. Third, I will introduce a modified security definition, individually semantically secure under a chosen ciphertext attack (ISS-CCA1), and show that against an all-observing eavesdropper, NU-HUNCC satisfies its conditions. Finally, I provide an analysis of the NU-HUNCC's high data rate, low computational complexity, and the negligibility of the shared seed size.

12:00-12:30
Talk: On the use of Canonical Forms for the Code Equivalence Problem
Speaker: Paolo Santini
The Code Equivalence Problem asks to find an equivalence between two linear codes. In the most common formulation of the problem, the equivalence is a linear isometry in the Hamming metric (i.e., a monomial transformation). The problem can be described in terms of cryptographic group actions and, as such, is a very natural candidate for building zero knowledge proofs and signatures.
In this talk we present the notion of Canonical Forms for the Code Equivalence Problem which, in practice, can be thought of as functions having some strong invariance properties. The use of canonical forms opens up for new features and research directions, such as new attacks and the possibility of achieving much more compact signatures.

14:30-15:00
Talk: On Rank Metric Based McEliece-like Encryption Schemes
Speaker: Pierre Loidreau
Post-Quantum cryptography is a very active actual research field. The standardisation process initiated by the NIST has initiated a second phase with the continuing study of KEM and digital signature proposals. Among all potential cryptographic solutions, the ones basing their security on problems of decoding in rank metric are of promising interest. Such solutions have a better size/security trade-off than the ones based on decoding in Hamming metric. The so-called unstructured solutions (not implying algebraic properties such as quasi-cyclicity for codes in the security analysis) are of particular interest, since the confidence in the security of structured solutions is not so great. Namely, national agencies such as BSI in Germany and ANSSI in France recommend to use unstructured solutions. In code-based cryptography for reasonable implementation parameters, this leaves essentially McEliece like architecture instantiated with unstructured families of codes.
In our talk we will present some potential directions for the design of McEliece like-rank metric based cryptosystem. We will also present the most up to date security analysis. Our presentation is essentially inspired from "LowMS: a new rank metric code-based KEM without ideal structure" and "Cryptanalysis of Rank-Metric Schemes Based on Distorted Gabidulin Codes".

15:00-15:30
Talk: Divide and Surrender: Exploiting Variable Division Instruction Timing in HQC Key Recovery Attacks
Speaker: Qian Guo
In this talk, we uncover a critical side-channel vulnerability in the Hamming QuasiCyclic (HQC) round 4 optimized implementation arising due to the use of the modulo operator. In some cases, compilers optimize uses of the modulo operator with compile-time known divisors into constant-time Barrett reductions. However, this optimization is not guaranteed: for example, when a modulo operation is used in a loop the compiler may emit division (div) instructions which have variable execution time depending on the numerator. When the numerator depends on secret data, this may yield a timing side-channel. We name vulnerabilities of this kind Divide and Surrender (DaS) vulnerabilities.
For processors supporting Simultaneous Multithreading (SMT) we propose a new approach called DIV-SMT which enables precisely measuring small division timing variations using scheduler and/or execution unit contention. We show that using only 100 such side-channel traces we can build a Plaintext-Checking (PC) oracle with above 90% accuracy. Our approach may also prove applicable to other instances of the DaS vulnerability, such as KyberSlash. We stress that exploitation with DIV-SMT requires co-location of the attacker on the same physical core as the victim.
We then apply our methodology to HQC and present a novel way to recover HQC secret keys faster, achieving an 8-fold decrease in the number of idealized oracle queries when compared to previous approaches. Our new PC oracle attack uses our newly developed Zero Tester method to quickly determine whether an entire block of bits contains only zero-bits. The Zero Tester method enables the DIV-SMT powered attack on HQC-128 to complete in under 2 minutes on our targeted AMD Zen2 machine.