Primary advisor: Daniel Augot, Inria (daniel.augot@inria.fr)

Co–advisor: Camilla Hollanti, Aalto University (camilla.hollanti@aalto.fi)

Keywords

Reed–Solomon codes, repair of codes, Shamir secret sharing scheme, secure multiparty computation, Fourier analysis.

Project description

In cryptography, secret sharing schemes are helpful in preventing side-channel attacks that use hardware probes. Somewhat surprisingly, they are themselves vulnerable to some side-channels attacks. Note also that secret sharing schemes are the basis of secure multiparty computation  (MPC) protocols. This vulnerability originates from a fact discovered in coding theory by Guruswami, who showed that a symbol of a Reed–Solomon codeword can be recovered with very low bandwidth from few bits from several other symbols. Since a Reed–Solomon codeword can be seen as the set of shares of a Shamir Secret Sharing Scheme, this result can be turned into a side-channel attack. This project will consist of analysing and extending such results, using coding theory and/or cryptography.

Secondment partner

Aalto University, Finland

Primary advisor: Alain Couvreur (Inria Saclay, France), alain.couvreur@inria.fr;

                           Co-advisor: Gary McGuire, (University College Dublin, Ireland), gary.mcguire@ucd.ie.

Key words:  Error-correcting codes, algebraic geometry codes, rings, additive combinatorics.

Project description

The objective of the project is to study error-correcting codes with a specific multiplicative structure. That is, from a code, we consider its “square” code. Our focus is the codes whose square has a low dimension compared to arbitrary codes. It has been observed that codes obtained by evaluating elements from a ring of polynomials or of functions on an algebraic variety (e.g. Reed– Solomon codes, Reed–Muller codes, Algebraic Geometry codes) have this feature. Then, by using analogies with additive combinatorics, we are interested in inverse theorems; i.e. classifying codes whose square has a “low” dimension. Applications to encryption or multiplicative secure secret sharing will be investigated.

Secondment Partners: UCD (Ireland)

Primary advisor: Camilla Hollanti, Aalto University (camilla.hollanti@aalto.fi)

Co–advisor: Eimear Byrne, University College Dublin (ebyrne@ucd.ie)

Keywords

Distributed computation, error-correcting codes, evaluation codes, matrix multiplication, tensors, secure computation.

Project description

This project is about application of information theory and the theory of error-correcting codes to secure computation. In particular, information-theoretically secure distributed matrix and tensor multiplication will be under study, providing an alternative to cost-heavy homomorphic encryption in a similar setting. We will consider both digital and analogue coding, i.e., computation schemes over finite fields as well as over the complex numbers. Various types of performance bounds, existence and capacity results, and explicit constructions are of interest. Particular attention will be paid to developing the mathematical foundations of secure distributed computation.

Secondment partner

University College Dublin, Ireland

Primary advisor: Camilla Hollanti, Aalto University (camilla.hollanti@aalto.fi)

Co–advisor: Françoise Levy-dit-Vehel, ESTA and Inria (levy@ensta.fr)

Keywords

Algebraic coding theory, information-theoretic security, private information retrieval, secure distributed computation.

Project description

Private information retrieval (PIR) considers the problem of retrieving a file from a possibly distributed storage system without revealing the identity of the file of interest. Recently, several schemes and related capacity results have been proposed and proven. Furthermore, the results achieved in PIR have turned out to be useful in other contexts as well, e.g., in secure distributed matrix multiplication (SDMM) and interference alignment. In this project, such synergies will be exploited further, and open questions related to capacity and in particular to the efficiency of PIR schemes will be studied. Considering PIR schemes with a preprocessing phase, as was recently proposed, can also improve their online cost. Another line of work is to exploit the so-called Function Secret Sharing (FSS) primitive, introduced by Gilboa and Ishai in 2014, and further improved by Boyle et al.: FSS has proven to yield low-communication (computationally secure) 2-server PIR. It would be interesting to investigate the performance of such a construction when generalized to k-server PIR.

Secondment partner

Inria Saclay Île de France, France

Primary advisor: Eimear Byrne, University College Dublin (ebyrne@ucd.ie)

Co–advisor: Alain Couvreur, Inria (alain.couvreur@inria.fr)

Keywords

Rank metric codes, tensor codes, tensor rank.

Project description

This project is about the rank of tensors linked to coding theory. A rank metric code can be identified with a 3-tensor and the rank of this tensor points to properties of the code in terms of encoding and storage efficiency. It is a natural invariant of rank metric codes. Links with Hamming metric codes have been known for some time but the explicit connections to matrix codes is more recent (see e.g. Byrne et al 2019, 2021). Extremality and optimality with respect to tensor rank bounds will be studied and existence questions on minimal tensor rank (MTR) codes will be addressed, with an emphasis on algebraic constructions. Structural properties of higher order tensors offers another research direction.

Secondment partner

Inria Saclay Île de France, France

Primary co-advisor: Eimear Byrne and John Sheekey, University College Dublin (ebyrne@ucd.ie, john.sheekey@ucd.ie)

Co–advisor: Elisa Gorla, University of Neuchâtel (elisa.gorla@unine.ch)

Keywords

Code equivalence, rank-metric codes, sum-rank metric, generalized tensor ranks.

Project description

The “Code Equivalence” problem is an important problem with current and future applications in cryptography. The difficulty of determining whether or not two codes are equivalent via an isometry depends heavily on the metric, and on linearity properties of the code. It has relations to longstanding difficult problems, including the graph isomorphism problem and the tensor equivalence problem.

This project will study aspects of this problem, examining invariants and identifiers for codes such as generalized weights and generalized tensor ranks, in different metrics including the Hamming, rank, and sum-rank metrics.

Secondment partner

Université de Neuchâtel, Switzerland

Primary co-advisor: Elisa Gorla, University of Neuchâtel (elisa.gorla@unine.ch)

Co–advisor: Camilla Hollanti, Aalto University (camilla.hollanti@aalto.fi)

Keywords

Submodule codes, matrix codes over principal ideal rings, invariants, extremal codes.

Project description

Gorla and Ravagnani in 2018 proposed to use submodule codes over principal ideal rings in the context of end-to-end physical-layer network coding (PNC). This project investigates the use of matrix codes in this context. After proposing a setup for matrix codes which is compatible with the submodule codes one, we will study the mathematical properties of matrix codes over principal ideal rings. This includes, but is not limited to, the study of invariants and extremal codes and will be complemented by the study of several examples.

Secondment partner

Aalto University, Finland

Primary co-advisor: Alberto Ravagnani, Eindhoven University of Technology (a.ravagnani@tue.nl)

Co–advisor: Elisa Gorla, University of Neuchâtel (elisa.gorla@unine.ch)

Keywords

Sum-rank metric, extremal codes, algebraic and combinatorial invariants.

Project description

This project is about the mathematical structure of linear codes endowed with the sum-rank metric and their applications. The primary goal of the project is to introduce and study a completely new class of invariants of sum-rank-metric codes, with respect to which optimal sum-rank-metric anticodes (rather than codes) are the extremal objects. This will shed new light on the invariant theory of codes and their MacWilliams-type transformations. Applications of the new invariants to code-based cryptography will be investigated.

Secondment partner

University of Neuchâtel, Switzerland