rank-deficient. section 3.4 shows how to use this result to certify that for two given polynomial matrices A and B, the row space of A is contained in the row space of B, and then gives verification protocols for some classical normal forms of polynomial matrices. In section 3.5, we present verification protocols related to saturations and kernels of polynomial matrices. Finally, section 3.5.2 gives a conclusion and comments on a few perspectives.

Presentation and outline of this thesis

Scientific computation. Computation always played a major role in the history of sciences. The development of computers from the 1940s allowed for computations which were faster, easier to reproduce and less prone to errors. The diversity of applications in which computers could be used led to the development of various computation fields: simulations of physical systems could be performed using numerical computation, which aims at finding an approximation of the solution to a given problem; while domains such as cryptanalysis or experimental mathematics led to exact computation which aims at finding exact solutions to the problems it tackles. Through the second half of the twentieth century, the need to perform simulations of physical systems became dominating, which strongly influenced the development of architectures, software and algorithmics. Floating point arithmetic, for instance, became a standard in computers in 1985 (with IEEE 754). However, exact computation is essential to a large number of research fields in scientific computing. Cryptography, for instance, widely uses integer numbers or finite field elements and requires highly efficient exact computation algorithms. In some fields it is not possible to approximate a solution: this is the case for instance in experimental mathematics, in graph theory, number theory or combinatorics, which makes the use of efficient exact computation extremely important in these fields. Finally, formal methods also make extensive use of exact computation for instance with computer assisted proof. All these applications make the development of efficient exact computation methods paramount to a wide number of fields.

Linear algebra in computation. Amongst the many tools available to perform efficient computations, linear algebra presents several major advantages: the data structures (vectors, matrices) it uses and the operations performed are relatively easy to handle, allowing to develop algorithms which can be more easily fine tuned and optimised. Linear algebra also enables highly regular computations, allowing to take advantage of efficient parallel programming techniques such as vectorisation. Finally, linear algebra allows for high intensity computation: some operations, such as matrix multiplication have an asymptotically larger time complexity than their space complexity (cubic vs. quadratic). By grouping operations, one can ensure that numerous computations are performed on the same block of data, thus amortising the costly access to computer's memory. Because of these advantages, linear algebra is a central tool in scientific computation, both in fields using exact algebra such as algebraic geometry, graph theory, or cryptography and in numerical computation, for solving partial differential equations or optimisation problems. Thus, any improvement to one of its fundamental operations can be carried over to a large amount of applications, making progresses in linear algebra important to a large number of research fields.

High performance computing. The ability to perform computations as fast as possible, on as many data as possible is paramount in a wide array of applications: in experimental mathematics, for instance, in which being able to test a conjecture on a set of examples as large as possible is an extremely desirable feature, or in cryptography in which the security of the primitives directly depends on the computational power of the fastest available hardware. Many numerical applications require high performance computing, such as weather forecast models or aerospace simulations.

A lot of effort has thus been put in developing computing infrastructures and software able to handle such large problems and high performance computing remains an extremely active field to this day.

Computing infrastructures. Infrastructures able to tackle large computational tasks vastly evolved over the years. From the 1960s to the 1980s, the fastest infrastructures available were local machines, such as computing servers or clusters. The democratisation of the Internet and the personal computer from the 1990s has seen the emergence of decentralised infrastructures with the development of peer and volunteer computing, which connects geographically spread resources, owned by a myriad of peers. This new approach to computing gained popularity thanks to its cost model, redistributing the overall price of the infrastructure amongst its peers; its ease of use (as maintaining complex hardware was no longer necessary) and its fast first successes, such as the Mersenne1 prime number search. Finally, in the mid-2000s, very large companies started to buy state-of-the-art computing infrastructures and developed a pricing system to rent them by the hour to clients all over the Internet. These clients were able to access this hardware via a single transparent interface, allowing them to easily perform tasks on appropriate infrastructures. This model, known as cloud computing spread rapidly thanks to its versatility and ease of use. This evolution, from local, controlled computing hardware to global, outsourced or distributed over many geographically spread machines gave birth to new questions related to confidentiality, security and safety. The question of trust is central to this new model: as users cannot blindly trust the entities who perform computations for them, how can they efficiently verify their outsourced computations? Similarly, users who need to perform outsourced computations on confidential data need to be sure that their data will not be leaked to others. This last application is at the centre of many contemporary applications, such as confidential organ donor/recipient matching (see for instance [START_REF] Wueller | Privacy-preserving trade chain detection[END_REF], or the EAGER NSF award2 ) or blind auctions in goods trade [START_REF] Bogetoft | Secure multiparty computation goes live[END_REF]. In this context, designing efficient protocols both in terms of communication volume over the network and in client computational cost is essential, as users only have access to limited computational power and the liberal use of expensive mathematical tools could quickly lead to unbearably large client cost.

Our thesis and this document's structure. While the spread of third party-owned computing hardware is a fairly recent phenomenon, ensuring confidentiality and correctness concerns of computations performed on outsourced devices is not. Researchers such as L. Babai or S. Goldwasser started to work on outsourced computation verification as early as 1985 and A. Yao's Millionaire's Problem from 1982 is considered as the seminal work on secure multi-party computation. Numerous research followed, both on proving the validity or the privacy of outsourced computation. However, many of these research works aim at developing generic tools verifying any computation in a given class of problems. Such genericity usually comes with a heavy price: even if their asymptotic complexities are excellent, they often hide very large constant factors which undermine their practicality. Designing dedicated protocols, tailored to tackle specific problem has thus gained some popularity since 2011 [START_REF] Kaltofen | Quadratic-time certificates in linear algebra[END_REF], but a lot of work remain to be done in this area. In this context, we defend the following thesis:

Outsourced exact linear algebra computations do not have to rely on users' trust: we can now verify and ensure confidentiality of its main algorithms.

In this chapter, we formally introduce the notions summarized above. We define the setting of verification protocols for outsourced computation and secure multiparty computation, alongside the metrics used to evaluate their efficiency. We also propose an comparison between the two aforementioned approaches, generic protocols against dedicated ones and give an overview of existing dedicated protocols and assess their efficiency.

In Chapter 2, we present new dedicated protocols for the verification of the computation of a matrix invariant called the rank profile matrix. We achieve better computational and communication volume complexities than generic protocols on the same problem. Using some of the protocols we designed for this result, we also improve on the verification of classical linear algebra properties, matrix determinant and signature.

In Chapter 3, we still focus on verification protocols, but this time for univariate polynomial matrices. We propose dedicated protocols to verify numerous properties of such polynomial matrices, where some verified objects are specific to modules while some others also carry over the vector space whose coefficient domain is the set of rational fractions. In this context, we propose a central tool in a protocol to verify that a vector belongs to a module spanned by a polynomial matrix.

Finally, in Chapter 4, we focus on the privacy aspect with secure multiparty computation. We propose a secure protocol for the shared computation of matrix multiplication based on the recursive Strassen-Winograd algorithm. This new protocol allows us to improve on the state of the art for the communication volume required for multiparty matrix multiplication and has practical applications, as for instance in private trust evaluation.

Notations

Fields and rings We use F to indicate an arbitrary field, Frxs for the ring of polynomials in one variable x with coefficients in F, and Fpxq for the field of rational fractions, i.e., the fraction field of Frxs. The ring of m ˆn matrices, for example over Frxs, is denoted by Frxs mˆn .

Vectors and matrices

We use bold font and small letters to represent vectors, as v and bold font and capital letters for matrices A. Vectors are considered as columns by default, which means v P S n will be equivalent to v P S nˆ1 and that v T is a row vector. Regarding matrices, A i,j represents the element on the i-th row, j-th column of A, while A i,˚r epresents the i-th row of A. Given a set of row indices I and column indices J , A I,J denotes the submatrix extracted from A in these rows and columns.

Asymptotic complexity bounds

We use the "soft-oh" notation r

Op¨q to give asymptotic bounds hiding logarithmic factors. Precisely, for two cost functions f, g, having f P r

Opgq means that f P Opg logpgq c q for some constant c ą 0.

We write ω for the exponent of matrix multiplication over F, so that any two matrices A, B P F nˆn can be multiplied using Opn ω q field operations; we have 2 ă ω ď 3 and one may take ω ă 2.373 [START_REF] Coppersmith | Matrix multiplication via arithmetic progressions[END_REF][START_REF] François | Powers of tensors and fast matrix multiplication[END_REF].

For a given matrix A, we denote by µpAq the worst case arithmetic cost of multiplying A by a vector.

Protocols

In protocols, S is always a finite subset of the base field F which we use to sample field elements uniformly and independently at random. If F is finite and sufficiently large, one can use S = F. If #F is too small, then one may use a field extension, causing up to a logarithmic factor increase in the computation and communication costs.

Following [START_REF] Dumas | Essentially optimal interactive certificates in linear algebra[END_REF][START_REF] Dumas | Linear time interactive certificates for the minimal polynomial and the determinant of a sparse matrix[END_REF]Dumas et al., , 2017b) ) we use the notation x ? " y as a placeholder for If x ‰ y then abort and report failure to improve the brevity and readability of the protocols. Similarly, we use x ? ă y, x ? ě y, U ? Ď V , etc. to check inequalities and set inclusion. respectively the actions of drawing a field element uniformly at random from S and of drawing a vector of n field elements uniformly and independently at random from S.

Encryption and decryption Given a player P , we denote by pk P their public key and by sk P their secret key when using an asymmetric cryptosystem. The cleartext space associated with this player will be denoted by M P and the ciphertext space by C P .

Given some scalar u, we denote by tuu pk P the encryption of u using the public key of P . The action of encrypting (resp: decrypting) an element u P M P (resp: v P C P ) will be denoted by Epuq pk P (resp: Dpvq sk P ).

1.1

Verification protocols for outsourced computation

1.1.1

Overview

Let us consider the following situation: a client, with limited computational power, wants to perform some heavy computation. As it would take forever for our client to run this computation by themselves, they will instead rent a server over the Internet and ask this server to do the heavy work. After some time, the server sends a result to the client. While this scenario seems to solve the issue at hand, it contains a major flaw: as the client has absolutely no control over the remote server, they would like to verify the result the server sent back. However, their limited computational power forces them to use specific, efficient verification protocols. In this section, we will describe the so-called interactive proof systems, allowing our client to efficiently verify the result of an operation which has been performed by an untrusted resource. We will specifically present different approaches for verifiable computation, focusing on linear algebra problems, and discuss the metrics that can be used to evaluate the efficiency of such proof systems.

1.1.2

Interactive proof systems and verification protocols

Interactive proof systems A proof system, usually consisting in a theorem and a proof, allows to verify the theorem by checking the validity of the proof. An interactive proof system, for its part, models an exchange between two parties, the Prover whose goal is to provide the proof, and a Verifier who will check its veracity. The general flow of an interactive proof system is as follows:

1. at the beginning, the Prover and the Verifier share the knowledge of the result of a computation, which they have to verify, 2. the Verifier then sends a Challenge to the Prover, usually consisting of some uniformly sampled random values, to which 3. the Prover replies with a Response, used by the Verifier to ensure the validity of the commitment.

In some cases, several additional rounds of Challenge/Response might be necessary for the Verifier to accept an answer. This interactive approach has been presented by two independent teams in 1985: [START_REF] Babai | Trading group theory for randomness[END_REF] introduced Arthur-Merlin protocols (from the names he respectively affected to the Verifier and the Prover in his paper), where only one round of Challenge/Commitment was allowed and where the random values generated by the Verifier had to be public. [START_REF] Goldwasser | The knowledge complexity of interactive proof-systems[END_REF] proposed very similar proof systems, except they allowed several rounds of Challenge/Commitment and they forced the random choices of the Verifier to remain hidden. It was later

Chapter 1: Introduction proved than hiding or revealing the Verifier's random choices had no impact on the proof [START_REF] Goldwasser | Private coins versus public coins in interactive proof systems[END_REF][START_REF] Babai | Arthur-merlin games: A randomized proof system, and a hierarchy of complexity classes[END_REF]. Proof systems must satisfy two fundamental properties, completeness which states that the Verifier should not reject a true statement provided by the Prover and soundness which states that the Verifier should not accept a false statement. More precisely, a protocol is said complete if the probability that the Verifier rejects a true statement can be made arbitrarily small. If the Verifier never rejects such a statement, the protocol is said perfectly complete. Similarly, a protocol is sound if the probability that the Verifier accepts a false statement can be made arbitrarily small, and is perfectly sound if the Verifier never accepts a false statement. As all the protocols presented in this thesis will be perfectly complete, we will describe them just as complete. Note that in practice, a soundness of 1/2 is enough, as the protocol can be repeated several times, de facto reducing the probability that the Verifier accepts a wrong statement: a protocol for which the Verifier has probability 1/2 to accept a wrong statement, repeated only five times yields a probability of 1{2 5 « 0.03 for the Verifier to overall accept this wrong statement. These iterations can always be performed in parallel, so that there is a linear scaling in the communication, Verifier and Prover costs ( see next section for more details on these metrics), but not in the number of rounds in the protocol.

Finally, we briefly present a few results on problem solving by interactive proofs systems. It has been proven by [START_REF] Furer | On completeness and soundness in interactive proof systems[END_REF] that interactive proofs can be transformed in interactive proof with perfect completeness. They also show that only problems in N P have interactive proofs with perfect soundness. [START_REF] Shamir | IP = PSPACE[END_REF] proved that the class of problems solvable by an interactive proof (IP) was equal to PSPACE. Finally, the fundamental PCP theorem states that every decision problem from the N P class has probabilistically checkable proofs, with the verification algorithm using a constant number of bits from the proof and a logarithmic amount of random bits [START_REF] Babai | Checking computations in polylogarithmic time[END_REF][START_REF] Arora | Approximating clique is np-complete[END_REF][START_REF] Arora | Proof verification and the hardness of approximation problems[END_REF].

Verification protocols

In this thesis, we will focus on dedicated verification protocols, a particular representation of such proof systems. Their initial name, certificate carries different meanings in particular in linear algebra: a certificate often is an algorithm proving the correctness of the output of a randomized algorithm, thus allowing to "transform" a Monte-Carlo algorithm, into a Las Vegas one. Monte-Carlo are randomized algorithms which might silently fail with a certain probability, producing a wrong output; while Las Vegas are randomized algorithms which cannot fail but that use random choices while running which leads to impredictable runtimes. Such certificates have been developed, for instance by [START_REF] Storjohann | Integer matrix rank certification[END_REF][START_REF] Mulders | Certified dense linear system solving[END_REF]) based on early work by [START_REF] Mark | Certifying inconsistency of sparse linear systems[END_REF]. However, the name certificates implied that they are static objects. With their generalisation as interactive proof systems does not allow this terminology anymore, we will instead use the name verification protocol throughout this thesis.

Here, we will focus on verification protocols as Prover/Verifier protocols, where the Prover is modelled as a computationally unbounded adversary and where the Verifier has a typically limited amount of computational power. Generic techniques briefly introduced above prove the evaluation of a boolean or an arithmetic circuit and require that the Verifier either knows the circuit itself or computes certain properties of it. More details on these techniques can be found in Section 1.1.5. The original definition of certificates, was proposed in [START_REF] Kaltofen | Quadratic-time certificates in linear algebra[END_REF][START_REF] Kaltofen | Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients[END_REF][START_REF] Dumas | Essentially optimal interactive certificates in linear algebra[END_REF] andfollows: Definition 1.1.1. An interactive certificate for a problem that is given by input/output is an input-dependent data structure and an algorithm that computes from that input and its certificate the specified output, and that has lower computational complexity than any known algorithm that does the same when only receiving the input. Correctness of the data structure is not assumed but validated by the algorithm in the adversary-verifier model. This definition is not suitable for the verification protocols proposed in this thesis: it states that the Verifier has no a priori knowledge of the output of the algorithm. In Chapter 3, we deal with matrices over polynomial rings, which are large data structures. In this particular context, considering that the Prover sends the output of the computation to the Verifier automatically leads to large communication bounds (one of the key efficiency metrics of such certificates, see Section 1.1.3 for more details) which will dominate the responses of the Prover. To circumvent this issue, we consider the output of the computation as an input of the verification protocol, which leads us to this new definition: Definition 1.1.2. A verification protocol for a problem P given by input/output I{O is a boolean algorithm which states whether O is a valid solution for P on input I. It has a lower computational complexity that any known algorithm that solves P. The verification is done in the adversary-verifier model, in which an untrusted entity provides a set of elements used by the verification protocol to state whether O is a valid solution for P or not.

Such verification protocols can either be non interactive (the Prover sends data to the Verifier only once, and this data is sufficient to verify and/or compute the output), or interactive (following the interaction flow presented at the beginning of this section). Protocol 1.1 gives the generic template we will use in this thesis to represent verification protocols.

Note that our verification protocols might resemble another category of protocols, called Σ-Protocols (Damgård, 2010, Section 2), which present the same communication structure. However, Σ-Protocols are closely related to proofs of knowledge, as such protocols always prove that the Prover knows the result that it verifies (Damgård, 2010, Theorem 1). As the verification protocols presented in this thesis have the data structure to verify as part of the public input, there is no proof of knowledge to provide here.

Protocol 1.1: Template for verification protocol

Public: An algorithm A, a set of input I to A and a data structure O Certifies: O is the output to ApIq Prover Verifier

1.

Generate a challenge c 1 from public elements c 1 Ð ÝÝÝÝÝÝÝÝ Ý 2. Compute an answer a 1 to c 1 a 1 Ý ÝÝÝÝÝÝÝÝ Ñ . . .

O

? " ApIq from the set of answers pa 1 , . . . , a n q 1.1.3

Evaluation of the efficiency of a verification protocol

When designing verification protocols, one should be careful of several metrics that are used to assess their efficiency, namely:

Communication: this can be measured using two elements: the volume of data exchanged throughout, without taking into account the input and output of the computation, and the number of Challenge/Response rounds required by the protocol. This duality is necessary to reflect real world constraints: users with a good bandwidth but a poor latency would indeed favour verification protocols with a small (ideally constant) number of rounds. Communication volume can either be measured in number of bits or in field elements. In this thesis, protocols often work over finite fields in which these two units are equivalent. For protocols presented in Chapter 3 which are over a polynomial ring, we will measure communication in field elements. Finally, note that a recent result (Reingold et al., 2016, Theorem 1) shows that any problem which can be solved in bounded space and polynomial time (in the size of the input) can be verified by complete and sound interactive proofs in constant rounds and polynomial communication volume;

Verifier cost: the worst-case number of arithmetic operations performed by the Verifier in the protocol, regardless of the data the Prover sent. Another element to look at for the Verifier efficiency is the minimal size of the field from which the randomly generated challenges are sampled: soundness usually depends on the input field size and some protocols require this field to have a size which depends on the input data size. Note that the cost of an honest Verifier depends only on the public information -that is, the parameters of the statement being verifiedand even a malicious Prover cannot cause the Verifier to do more work than this. However, in the case of very large (or even infinite) fields, the Prover may essentially execute a denial of service attack by sending arbitrary large field elements in the protocol. In this thesis, our analysis is generic in terms of field operations, is not able to capture this weakness, and does not attempt to address it;

Prover cost: the number of operations performed by an honest Prover throughout the protocol. Note that the type of algorithm the Prover runs is also to consider: if there is no deterministic algorithm for the Prover, the random algorithm should be Las Vegas as a Monte Carlo algorithm could lead an honest Prover to handle wrong responses to the Verifier.

As a side note, verification protocols could also be used locally to verify the implementation of a given algorithm. This presents several advantages over the usual testing methods, which often rely on testing against trusted implementations or comparing results against a pre-computed set of inputs/outputs. In this context, there is no longer a Prover and the communication cost metric is replaced by a memory cost: the number of rounds can be seen as the number of memory accesses required to perform the protocol while the volume is the additional memory space required by the verification protocol.

1.1.4

From interactive to non interactive protocols and public verifiability

In practice, it might not always be possible for the Verifier to interact directly with the Prover: for instance, a Verifier would like to check the veracity of an already published result of the computation but has no access to a server whatsoever. Then, it is possible to transform any interactive verification protocol into a non-interactive one, using for instance Fiat-Shamir heuristic (Fiat and Shamir, 1987): random values produced by the Verifier are replaced by cryptographic hashes of the input and the previous messages, and the Prover publishes once both the Commitment and Response to the de-randomized challenge. This also solves the issue of public verifiability: the fact that anyone can verify and be convinced by the Prover's answers. Indeed, if only the communications between the Prover and the Verifier were made public, one could argue that the Prover and the Verifier might be colluding and crafted the challenges. Using Fiat-Shamir heuristic, doing that would be as hard as breaking the cryptographic hash function. Some efficient dedicated protocols that focus on public verifability do exist : as they are not the main focus of this thesis, we will not focus on them here. Protocols for linear algebra could for instance be found in [START_REF] Elkhiyaoui | Efficient techniques for publicly verifiable delegation of computation[END_REF].

1.1.5

Paradigms for verification protocols

In this section, we go through the major approaches developed for verification protocols. We start by giving an overview of what we call generic approaches, whose goal is to propose multi-purpose protocols which are able to certify a wide range of computations. These approaches usually carry large constant factors on the Prover or the Verifier computation time. We then focus on algorithm-based approaches, whose goal is to develop protocols for one specific computation, hence trading generality for better efficiency. Finally, we present one intermediate approach, which is able to certify any linear algebra computation reducing to matrix multiplication.

Generic approaches

Circuit verification techniques These generic approaches come from [START_REF] Goldwasser | Delegating computation: Interactive proofs for muggles[END_REF] work, in which they propose a protocol able to verify any problem that can be solved on a parallel computer, that is any problem from the N C or AC complexity class.

In a nutshell, the idea here is that the Prover and the Verifier agree on a multilayered arithmetic circuit C. The Prover first commits a claim on the value of the output layer of this circuit. The Verifier cannot verify this claim without evaluating the circuit, which is very expensive and thus what they want to avoid. What the Verifier will do instead is to engage in an iterative verification sequence, in which a claim on the values at the output of each layer of the circuit can be reduced to a claim about the values on the previous layer of the circuit. The Verifier will use a sum-check protocol [START_REF] Lund | Algebraic methods for interactive proof systems[END_REF] to perform this reduction, and proceeding backwards from the output layer to the input layer of C, the Verifier eventually needs to only verify a claim on the input of the circuit.

Initially, considering inputs of size n and a circuit of size Spnq, depth d, with Prover runtime for this protocol polynomial in Spnq and verifier time r

Opn `d logpSpnqqq. This has been refined by [START_REF] Cormode | Practical verified computation with streaming interactive proofs[END_REF], who managed to achieve a better Prover in OpSpnq logpnqq time. [START_REF] Thaler | Time-optimal interactive proofs for circuit evaluation[END_REF] managed to reduce the Prover time complexity to OpSpnqq, but only for regular circuits.

QAP-based approach

Another approach has been proposed by [START_REF] Parno | Pinocchio: Nearly practical verifiable computation[END_REF] with a system called Pinocchio but this time based on converting a circuit into a structure called a quadratic arithmetic program (QAP). In a nutshell, a QAP is a representation of the circuit which contains three sets L, R, O of size n of polynomials and a target polynomial T of degree d. These sets respectively encode the left input of every gate in the circuit, their right input and their output. The target polynomial is associated to the function the circuit is supposed to evaluate and is used to verify that the circuit indeed computes the output of this function. To be more specific, to verify if a set of constants pc 1 , . . . , c n q (called an assignment) satisfies the QAP, one needs to compute three polynomials L " Σ n i"1 c i ¨Li , R " Σ n i"1 c i ¨Ri and O " Σ n i"1 c i ¨Oi and P " LR´O. If T divides P , meaning if there exists a polynomial H such that P " HT , then the assignment satisfies the QAP. In the context of verifiable computation, this can be applied as follows: the Prover and the Verifier agree on a circuit to evaluate and on the target polynomial T and the Prover computes the four polynomials L, R, O and H.

The Verifier then samples a random evaluation point s which they send to the Prover. The Prover replies with the evaluation of their four polynomials at s and the Prover just needs to check that the equality LpsqRpsq´Opsq " T psqHpsq holds. The soundness comes from DeMillo/Lipton/Zippel-Schwartz lemma which states that the probability of P psq " HpsqT psq with P ‰ HT is small. However, this is not enough to prove that the assignment indeed satisfies the QAP: the former verifications only guarantee that the polynomials L, R and O have degree at most d and verify L ˆR ´O " T ˆH, but not necessarily that they were produced from the assignment. In order to verify that the Prover did not just forge suitable polynomials, the Verifier will create a new polynomial F " L `Xd`1 ˆR `X2pd`1q ˆO. This new polynomial has been constructed such that its coefficients in degree less than d `1 are exactly the coefficients of L, the nextd `1 coefficients are exactly those of R, and the last d `1 are the ones of O. Now, combining the polynomials from the sets L, R and O in a similar manner gives a set of n new polynomials F such that F i P F " L i `Xd`1 ˆRi `X2pd`1q ˆOi for some i P t1, . . . , nu. Now, if F is a linear combination of the F i polynomials, it means that L, R and O were indeed produced from the assignment. This can be verified by random evaluation: the Verifier picks a random evaluation point s 1 , and sends s 1 ˆF1 psq, . . . , s 1 ˆFn s to the Prover who has to reply with s 1 ˆF psq. It they succeed, it means they know how to write F as a linear combination of the F i , which implies that the L, R and O indeed come from the assignment.

It has been proven by [START_REF] Gennaro | Quadratic span programs and succinct nizks without pcps[END_REF] that any arithmetic circuit can be converted into a QAP whose size (the number of polynomials in each set) depends on the number of multiplication gates and input/output elements in the circuit to transform. This representation is quite powerful, as addition and multiplication by a constant gates can be considered free (they do not impact the size of the QAP) and the correctness of the QAP can be checked by performing cheap polynomial operations. This approach has been further improved in 2015 by [START_REF] Costello | Geppetto: Versatile verifiable computation[END_REF] whose Geppetto compiler improves on Pinocchio by enabling more efficient Provers.

Linear algebra computations Both these approaches can be used to compute classical linear algebra properties, like the rank or the determinant of a matrix, or operations like the matrix-matrix product. However, the additional logarithmic factors take a toll on the Prover time. This cost is illustrated, for instance in [START_REF] Walfish | Verifying computations without reexecuting them[END_REF] which Figure 5 shows the Prover overhead on two computational tasks (matrix multiplication and PAM clustering -similar to k-means computation) and exhibits a massive overhead (from 1.5 to 9 orders of magnitude) for generic techniques against a native C implementation.

Algorithm-based approaches

In this section, we go through the major verification protocols using algorithm-based techniques to verify linear algebra properties.

We start by the first linear algebra protocol, due to [START_REF] Rūsin | Fast probabilistic algorithms[END_REF], which allows to verify the computation of a matrix-matrix product. Given two matrices A, B and a matrix C, such that A ˆB " C, the idea is to perform a right projection using a random vector. If the projection of A ˆB and the projection of C are equal, then, with high probability, A ˆB " C. This verification protocol is given in Protocol 1.2. In Freivalds' original version, the random projection vector v contained only 1 and ´1s, hence yielding a failure probability of 1{2. (Kimbrel and Sinha, 1993, algorithm 4) proposed a variant to Freivalds' protocol, in which, instead of picking a random t´1, 1u vector, the Verifier randomly sampled a single element x from S and used v " p1, x, x 2 , . . . , x n´1 q as the projection vector instead. This variant requires only logpnq random bits, as S needs at least n elements. Note that in what follows, we will use Freivalds' protocol as proposed in Protocol 1.2 and not original t´1, 1u version or the Kimbrel-Sinha variant.

For the rest of this section, we will give an overview of existing verification protocols using algorithm-based strategies for verifying classical linear algebra properties. Information of the efficiency of these protocols has been summarized in Table 1.1, and improvements over the state of the art alongside the new verification protocols developed in Chapter 2 are presented in Table 2.2.

Matrix rank A first matrix rank dedicated verification protocol was given in 2011 by (Kaltofen et al., 2011, Theorem 2) for square integer matrices, based on the existence of an LU decomposition for the input matrix modulo a random prime. This protocol has Opn 3 q communication cost and Opn 2 q verification cost. More recently, (Dumas and Kaltofen, 2014, Corollary 3, Theorem 5) proposed a verification protocol for the rank of both integer matrices and matrices over a finite field. For a matrix A P F mˆn , their protocol asks the Prover to commit the rank r of A, compute two projection matrices, I P F rˆm and J P F nˆr such that IAJ is non singular, which can be verified, certifying that r is a lower bound on the rank of A. They then propose a protocol for an upper bound on the rank of a matrix, which applied to r effectively certifies the rank of A. [START_REF] Eberly | A new interactive certificate for matrix rank[END_REF] proposes a variant of these protocols in which the Prover is asked to certify the lower bound on the rank r by recovering a linear combination on r independent columns on the matrix. The upper bound is then proved by the Prover's ability to generate a random vector of the image of A using a linear combination of r columns of A. The previous two verification protocols have roughly equivalent complexities, with [START_REF] Dumas | Essentially optimal interactive certificates in linear algebra[END_REF] having a less costly Prover in the case of structured or sparse matrices but slightly more expensive communication and Verifier cost overall. Detailed complexities can be found in Table 1.1.

Determinant A first algorithm-based determinant verification protocol was proposed in (Kaltofen et al., 2011, Theorem 3) for dense integer matrices, in which the Prover computes and transmits several LU decompositions of the input matrix A modulo several prime numbers. The verification then consists either in checking the rank of the input matrix if the LU decomposition is not full rank, or in checking the zero equivalence of A and LU and that the product of diagonal coefficients of U is the determinant the Prover provided. This protocol yields a cubic communication volume and a soft quadratic verification time. Then, (Dumas et al., 2016, Theorem 13, 14) proposed an improvement based on minimal polynomial computation. This version is especially efficient in the sparse case where it is Prover optimal, while yielding a linear communication volume and a verification time bounded by the cost of applying a vector to the input matrix. It also retains interesting complexities for structured and dense matrices. Finally, in Section 2.4.1 we will propose new verification protocols for dense matrices with no Prover overhead and the same communication volume and verification time than the latter protocol. (Kaltofen et al., 2011, Theorem 4) proposed a first verification protocol for the characteristic polynomial based on similarity residue system and computation modulo prime numbers. This protocol once again yields cubic communication volume and quadratic verification time. (Dumas and Kaltofen, 2014, Section 3) improved on the Frobenius normal form computation, which, combined with the previous protocol, allowed them to reach quadratic communication volume. Finally (Dumas et al., 2016, Section 5) proposed a verification protocol for the minimal polynomial of structured/sparse matrices, in linear communication volume and linear verification time.

Characteristic and minimal polynomial

Signature

The signature of a symmetric matrix is the triple pn `, n ´, n 0 q respectively indicating the number of positive, negative and zero eigenvalues. [START_REF] Kaltofen | Quadratic-time certificates in linear algebra[END_REF], Corollary 1) verify the signature of a matrix by analyzing the characteristic polynomial of the input matrix. The characteristic polynomial approach can be straightforwardly applied to the signature verification protocol, hence yielding the same communication volume and verification time cost. In Chapter 2, we propose another approach based on the LDLT decomposition which allows the get better practical computation time for the Prover.

1.1.6

Linear algebra intermediate approach

The two approaches presented in previous sections either chose to sacrifice some efficiency in order to gain generality, or to focus on a specific algorithm to achieve better protocols. Here, we describe another technique, proposed in (Kaltofen et al., 2011, Theorem 5) for linear algebra computations which reduce to matrix multiplication. The idea is that the Prover will perform the required computations as normal, but that every time they will need to compute a matrix product, they will store the result of this operation. The Prover's commitment will be all the matrix products' results. The Verifier will then rerun the algorithm the Prover ran, and every time a matrix product needs to be performed, they will verify it using Freivalds' check on the data the Prover provided instead of performing it. This technique yields very interesting properties: while requiring a soft quadratic communication volume, it does not yield any Prover overhead and the verification cost is quadratic. It is also a non interactive protocol. The generic shape of this protocol is given in Protocol 1.

Overview of existing state of the art algorithm-based verification protocols

We finally give in Table 1.1 a summary of the efficiency of the best protocols to verifying the elements described above. We focus on the metrics which were presented in Section 1.1.3. We denote by A the input matrix, which has size m ˆn and rank r.

Note that signature or characteristic polynomial verification protocols do not appear in the table per se. This is because they have the same characteristics as the determinant protocol from [START_REF] Dumas | Linear time interactive certificates for the minimal polynomial and the determinant of a sparse matrix[END_REF] and then can be read on the same line as the latter on our table.

1.2

Multi-party computation protocols

1.2.1

Overview

We now consider a new situation, where several people, each of them owning some data want to compute a function which takes of all their data as input. We could imagine those people being owners of databases who want to execute a request on all of their data, bidders at an auction who want to know who made the highest bid or hospitals needing to compute compatibility rate between hosts and donor for organ transplant. They could obviously go public and reveal all their data to each other and then perform the requested computation, but for privacy reasons, they want to perform computations without revealing their input data. Such protocols allowing people to perform such shared computations are called secure multiparty computation protocols (abridged MPC in what follows). This has first been investigated by [START_REF] Andrew | Protocols for secure computations[END_REF], regarding the famous millionaires problem in which two people wants to know who is the richest of them all without revealing their actual wealth to one another. Since then, a lot of effort has been put on this field, and this section will present the major techniques that can be used and discuss their efficiency. As for the previous section on verification protocols, we will focus on the two concurrent paradigms, generic protocols and algorithm-based protocols.

1.2.2

Definitions

An MPC protocol involves a given number of participants (often designated as players or parties) P 1 , . . . , P n , each with their own private data (or input) x 1 , . . . , x n . Players seek to compute the output y of an n-variate public function f , while keeping their own input secret. Note that depending on the structure of y, it can be either public or private: y could for instance be a vector of size n and player i only learns the i-th element of y. In order to perform such a computation securely, two conditions must be satisfied: correctness, meaning that the correct value of y is computed, and privacy meaning that players learn nothing but the output of f .

Chapter 1: Introduction Regarding the construction of such protocols, it has been proven by [START_REF] Goldreich | How to play any mental game[END_REF] that any function can be securely computed. However, early protocols were not efficient enough to be practical and significant effort has been put in designing protocols that could be used in practice ever since. In the rest of this section, we first present the metrics to consider when designing MPC protocols. We then follow a similar outline to the previous section by first describing classical tools that are used in many protocols and then presenting and comparing concurrent approaches for protocols design.

1.2.3

Evaluation of the efficiency of an MPC protocol

The following metrics should be carefully considered when designing an MPC protocol:

Communication: the volume of data exchanged throughout the protocol. For the same bandwidth vs. latency reasons explained in Section 1.1.3, one should take into account the number of communication rounds required to complete the execution of a protocol.

Computation cost: the worst-case number of arithmetic operations performed by all the players during the execution of the protocol. Another parameter to keep in mind while designing such protocol is computation cost balancing between players: are some players performing much more computations than others? Such discrepancy could be problematic as there is no way to guarantee that the players whose role forces them to perform more computations are using faster machines than the other ones, which could lead to possibly large waiting phases during the protocol. Ideally, computations should be balanced amongst all players.

Security: the type of adversaries against whom the protocol is secure and the optional countermeasures that one needs to deploy to ensure this security. There are two major types of adversaries: semi-honest who are not allowed to tamper with the protocol, but can (and will) perform any additional computation on the data they know to try to learn secret information, and malicious adversaries (a la [START_REF] Dolev | On the security of public key protocols[END_REF])) who are allowed to not follow the protocol. They can, for instance, alter the distribution of the random value they provide or pick any element they want for their input. Furthermore, these adversaries can be working alone, or they can be colluding in which case they will share any information they own. Note that the adversaries can be static in which case they remain adversaries during the whole protocol, or dynamic which means players can become adversaries at any time during the execution of the protocol (there is usually a bound on the number of adversaries existing at the same time). In this thesis, we will only consider static adversaries. Finally, a word on the aforementioned countermeasures: some protocols might require the deployment of Chapter 1: Introduction additional techniques to achieve a given security. These countermeasures usually have a cost (either in communication or computation -maybe both) and should ideally be avoided. One can for instance cite secure channels, which guarantee authenticity and integrity of a message, but force digital signature of every message, which induces additional computation cost to verify every message.

1.2.4

Paradigms for MPC protocols

A simple idea for designing MPC protocols could be to assume that there exists some independent, honest and impossible to corrupt entity called a trusted third party. All players could send their private input to this party, who will perform the required computations and send the output back to the players. This solution is both generic and extremely efficient. However, the existence of such an entity is a very strong security model and might not be suitable to some applications. Hence, a lot of effort has been put in designing MPC protocols that do not resort to such trusted parties. In this section, we describe the two main paradigms for MPC protocols design. As for verification protocols, they are split between generic approaches aiming at designing protocols that can be applied to a wide array of problems, and algorithm-based approaches which focus on one specific computation and use its specificities in order to get a very efficient protocol. We will start by giving an overview of the main used tools for designing MPC protocols, before describing the two aforementioned paradigms.

Widely used tools

Secret Sharing. Secret sharing refers to techniques allowing to distribute a secret amongst a group of parties, each receiving one part (or share) of the secret. The idea is that the secret can only be reconstructed if a sufficient number of shares are put together. This originates from [START_REF] Shamir | How to share a secret[END_REF], who developed a protocol based on polynomial interpolation: given a secret s to be shared amongst n players, and setting the reconstruction threshold to t ă n, generate a polynomial function f of degree t ´1 whose degree 0 coefficient is s. Now, each player receives a distinct random evaluation of f , and by Lagrange interpolation t players are needed to reconstruct f , thus revealing s. Other techniques exists, such as one based on plane equations [START_REF] Blakley | Safeguarding cryptographic keys[END_REF] or Chinese remainder theorem [START_REF] Mignotte | How to share a secret[END_REF][START_REF] Asmuth | A modular approach to key safeguarding[END_REF].

Secret sharing is widely used for MPC applications, usually using a different approach: here, a player will split their input s into as many additive shares as there are players (for n players, s " Σ n i"1 s i ) and distribute these shares amongst players. In order to be secure against trivial collusion attacks, it is necessary to add some extra randomness: consider a protocol with n players, where P i needs to secretly share their input s i . Each player P j , j ‰ i will generate a random element r j that they will send to P i . P i will compute r " Σ j r j and broadcast s i ´r. Finally, each party will set their share to s i ´r `rj . This mechanism allows to securely perform arithmetic operations: an addition can be straightforwardly performed on shares of its operands (if two ele-ments a and b are split into ta i u and tb i u, a `b " Σ i a i `Σi b i ). For multiplication, things are a bit more complicated and require to generate so called "multiplicative triples", a set of three non-reusable elements, in order to be performed. We will not go into details here, but the interested reader can report to [START_REF] Beaver | Efficient multiparty protocols using circuit randomization[END_REF] for details on this method.

Oblivious Transfer. Oblivious transfer protocols allow one player, called the sender, to transfer one piece of information they own (amongst possibly many) to another player, the receiver, while remaining oblivious to what piece has been transferred. The first oblivious transfer protocol has been introduced by (Rabin, 2005) and refined by [START_REF] Even | A randomized protocol for signing contracts[END_REF], who designed a new protocol with MPC applications in mind. These first protocols were called 1-2 oblivious transfer as the sender owns two pieces of data and the receiver gets one. A short description of Even et al's protocol could be done as follows: using a public key cryptosystem, the sender generates their key pair and sends the public key to the receiver. They also generate two random messages x 0 , x 1 , which they send to the receiver. The receiver then picks the random message corresponding to the information they want (say, x 0 for m 0 and scrambles x 0 into v by using a random element k. The sender receives v and uses it to compute two possible values for k, k 0 and k 1 . One of these will be the same as the k the receiver picked, but the sender has no way to say which one it is. They will finally generate two messages m 1 0 " m 0 `k0 and m 1 1 " m 1 `k1 and send these to the receiver, who can learn the message they wanted by subtracting their original k to the message they wanted. Since then, these protocols have been generalized into 1´n oblivious transfer, as for instance in [START_REF] Aiello | Priced oblivious transfer: How to sell digital goods[END_REF][START_REF] Kolesnikov | Efficient batched oblivious prf with applications to private set intersection[END_REF], or even k ´n oblivious transfer [START_REF] Brassard | All-or-nothing disclosure of secrets[END_REF][START_REF] Ishai | Private simultaneous messages protocols with applications[END_REF] but for what follows we will only be interested in 1-2 oblivious transfer protocols.

Homomorphic Cryptography. Homomorphic cryptography refers to cryptosystems allowing to perform computation on ciphertexts which behaves as if the operation has been performed on the plaintext. This ability is crucial when its deployed in MPC protocols, as it allows players to perform computations on ciphered data without getting information on the clear data. We distinguish three major types of homomorphic cryptosystems: fully homomorphic supports an unbounded number of arithmetic operations, somewhat homomorphic supports a bounded number of arithmetic operations and semi-homomorphic supports only one type of arithmetic operation, the other one taking one plaintext and one ciphertext as operands. Without going into much detail here, we will only mention that the first two are usually considered to be too expensive to be practical, while the latter can be used in practice. The interested reader may refer to sections 3 and 6 of [START_REF] Mohassel | Efficient and secure delegation of linear algebra[END_REF] to get an overview of several homomorphic cryptosystems. A recent comparison of several modern somewhat homomorphic cryptosystems can be found in [START_REF] Costache | Which ring based somewhat homomorphic encryption scheme is best?[END_REF]. Finally, another interesting reference is the standardisation document from the Homomorphic Encryption Standardization Consortium [START_REF] Albrecht | Homomorphic encryption security standard[END_REF] which describes fully homomorphic Chapter 1: Introduction cryptosystems and gives recommended parameters to efficiently set them in practice. We will present the specificities of the cryptosystems we used for our work in Chapter 4.

Generic approaches

We present here the main classes of generic approaches, which are both based on circuits.

Secret sharing-based approaches These approaches rely on arithmetic circuit computation, and work as follows: at the beginning of the protocol, each player will split their input into shares and send shares to other players as described above. Then, they will run the algorithm locally, using the shares they received as input to the arithmetic gates, send the output to the appropriate players who can recompose the output of the circuit by using all their shares. These approaches are often split into two phases: the shares generation and exchange, and the actual circuit evaluation. Such secretsharing based schemes have been widely used and implemented into several libraries over the past decade, see for instance [START_REF] Bendlin | Semihomomorphic encryption and multiparty computation[END_REF][START_REF] Damgård | Constant-overhead secure computation of boolean circuits using preprocessing[END_REF]. A recent and highly regarded library using this technique is SPDZ (Damgård et al., 2013), which proposes a quite efficient version of this scheme, with security against active adversaries. This implies the use of zero-knowledge proofs techniques and message authentication codes in order to guarantee that players have been honest regarding their shared values and that they did not corrupt data computed while evaluated the arithmetic circuit. They also use somewhat homomorphic encryption techniques to generate the multiplicative triples required to perform multiplication on shares. This step was improved in the most recent work in line, MASCOT [START_REF] Keller | Mascot: Faster malicious arithmetic secure computation with oblivious transfer[END_REF], which proposed faster oblivious transfer-based techniques for the multiplicative triples generation. However, these approaches still suffer from large overheads: the preprocessing phase requires to compute one distinct triple per multiplication gate per player, which is a time and memory consuming process, and the exchange of shares and gate output amongst players also require a lot of communication. Note that as the preprocessing phase is by far the costlier element of these protocols, communication is not the bottleneck of these approaches.

Garbled circuits These techniques apply to boolean circuit, and were initially developed as two party protocols. The idea is that one player will be in charge of obfuscating (garbling) the information passed through the circuit while the other player will be in charge of performing the computation. The first garbled circuit protocol has been proposed by [START_REF] Andrew | How to generate and exchange secrets[END_REF]. The security of this proposal relies on symmetric cryptography and oblivious transfer and works as follows: for a given gate, let us consider two players Alice and Bob, where Alice is in charge of the garbling. She will start by generating four symmetric keys corresponding to each possible input for the gate, pk 0 A , k 1 A q, pk 0 B , k 1 B q and will use these four keys to cipher the four possible output of the gate. For example, she will use k 0 A , k 0 B to cipher the output corresponding to 0, 0. She will then send to Bob the four ciphertexts alongside the key corresponding to her input. Now, Bob needs to get the key corresponding to his input without revealing what it is to Alice, which will be done using a 1-2 oblivious transfer protocol. Bob will now try to decipher each ciphertext, and the one that can be properly deciphered is the actual output to the gate. In order to perform a full evaluation, our players needs to repeat that for all gates in the circuit.

Another garbled circuit approach is due to [START_REF] Goldreich | How to play any mental game[END_REF] and is also a two party protocol. This time, however, instead of using symmetric cryptography to hide the intermediate values computed during circuit evaluation, secret sharing techniques are used: each party splits their inputs into two shares, sending one to the other party and keeping the second to themselves. They will then locally perform the evaluation of each gate, using the shares they own as input. This idea applies straightforwardly to (X)OR or NOT gates, but requires a bit more work for AND gates: in this particular case, the same oblivious transfer-based technique as above has to be performed.

While initially only designed as two-party protocols secure against semi-honest adversaries, both approaches for garbled circuits have been widely studied and improved since then: practicality of Yao's garbled circuits have been proven with, for instance, its Fairplay implementation [START_REF] Malkhi | Fairplay-a secure twoparty computation system[END_REF] and a secure version against malicious adversaries has been achieved in [START_REF] Kreuter | Billion-gate secure computation with malicious adversaries[END_REF]. At first glance, Goldreich et al.'s approach might seem more expensive than Yao's: the latter runs in constant rounds and requires oblivious transfer for only one of the players, while the former requires an oblivious transfer per AND gate (which can be replaced by the use of the aforementioned multiplicative triples for multiplicative secret sharing). However, in [START_REF] Choi | Secure multi-party computation of boolean circuits with applications to privacy in on-line marketplaces[END_REF], the authors propose an n-party implementation of the aforementioned Goldreich et al. scheme which outperforms Yao-based techniques for computations involving more than three players. This improvement has been carried out for two players schemes in [START_REF] Schneider | Yao? efficient secure two-party computation with low depth circuits[END_REF]. Security against malicious adversaries has been achieved in [START_REF] Buus Nielsen | A new approach to practical active-secure two-party computation[END_REF].

Despite their genericity making them extremely appealing, these techniques once again involve some large overhead as the need to engage in an oblivious transfer protocol for each gate implies a lot of communication between the two parties.

1.2.5

Algorithm-based approaches

Designing MPC protocols for specific tasks seems to be quite less of fashion than working on generic solutions, and there are not that many articles that focus on this dedicated approach. Nonetheless, we present here a summary of existing algorithm-based approaches for two linear algebra problems, matrix multiplication (and the underlying dot product computation) and linear system solving.

Scalar and matrix product

We need to open this presentation by a fairly long disclaimer: Comparing algorithmbased approaches for these operations is a difficult task. Protocols were designed with different, often incompatible target application in mind which led to very specific models. Initially, researchers were interested in conducting statistical analysis between private data sets (for instance customers buying behaviours or employees HR information). Initially, This model usually involved only two players (see (Du and Atallah, 2001a;[START_REF] Du | Privacy-preserving multivariate statistical analysis: Linear regression and classification[END_REF][START_REF] Amirbekyan | A new efficient privacy-preserving scalar product protocol[END_REF]), each owning the same input data structure (vector or matrix) but was later extended to support N players [START_REF] Goethals | On private scalar product computation for privacy-preserving data mining[END_REF]. In that case, N -party vector product means computing the sum of all the partial coefficient-wise products. Finally, a new model was introduced for partial trust computation (see [START_REF] Dolev | Computing multi-party trust privately: In o(n) time units sending one (possibly large) message at a time[END_REF]Dumas et al., 2017a)) in which N players want to perform dot product, one players owning one full vector of size N ´1 and the other N ´1 players each own only one coefficient of the other vector. This last model is the one we use in the work presented in Chapter 4.

Thus, considering the difficulty of comparing those approaches, we propose here to summarily describe them, give their main advantages and drawbacks and only focus on their communication cost as it is the usual bottleneck in MPC applications (see Chapter 4 for more details on that point).

The first dedicated protocol for scalar product applied to confidential statistical analysis was proposed by (Du and Atallah, 2001a). As mentioned, their protocol was for two parties only (each party knows a vector) and it was only secure against semihonest adversaries. They propose two solutions to achieve this result, one based on oblivious transfer and the other one on homomorphic encryption. With security parameter λ, and vectors of size n, the total communication cost for their protocol is 4λn field elements. In 2004, Du et al. extended this result, now allowing matrixmatrix product in a semi-honest two-party setting (each players knows a matrix) [START_REF] Du | Privacy-preserving multivariate statistical analysis: Linear regression and classification[END_REF]. Their communication cost is only the size of the input matrix, m ˆn field elements. [START_REF] Goethals | On private scalar product computation for privacy-preserving data mining[END_REF] proposed a first n-player dot product protocol Their solution uses homomorphic encryption and masking techniques to achieve security against semi-honest players, and can use very costly zero-knowledge proofs to achieve security against malicious adversaries. While this new protocol is comparable to the previous ones on communication volume, requiring to exchange npN ´1q field elements (with N players and vectors of size n), its (N ą 2)-player version present the drawback of having asymmetric roles for the players. One "master" player is trusted with the private key to the homomorphic cryptosystem and has to be honest to guarantee privacy. Then, [START_REF] Amirbekyan | A new efficient privacy-preserving scalar product protocol[END_REF] proposed another scalar product protocol, in 4n field elements communication volume (for vectors of size n), but back to the initial two-player only model and achieving only security against semihonest adversaries.

On trust computation, [START_REF] Dolev | Computing multi-party trust privately: In o(n) time units sending one (possibly large) message at a time[END_REF] propose an N-player protocol for weighted average achieving security against any number of semi-honest adversaries at the communication cost of OpN 3 q field elements. Finally, (Dumas et al., 2017a) propose an improvement of the former in OpN 2 q field elements. This allowed them to achieve a communication cost of OpN 3 q for a matrix product protocol in which a given player P i knows the i-th row of the input matrices.

Linear system solving

Algorithm-based approaches for solving a linear system of equations Ax " b can be split in two distinct problems: the first one focuses on two party protocols where each party brings an entire matrix and vector as their input, and aim at solving the aforementioned system in which A and b are formed by addition or concatenation of the two parties' inputs. A first solution has been proposed by (Du and Atallah, 2001b) in 2001, and is heavily based on oblivious transfer protocols. The authors are only interested in improving on communication cost and achieve a complexity of Opµ ˆN 2 q for matrices of size N and security parameter µ. This has been improved several times since (see for instance [START_REF] Wu | Discovering multivariate linear relationship securely[END_REF][START_REF] Yang | Privacy-preserving cooperative linear system of equations protocol and its application[END_REF], with the latest improvement proposed by [START_REF] Ramon Troncoso-Pastoriza | Secure direct and iterative protocols for solving systems of linear equations[END_REF]. All these protocols are only secure against semi-honest adversaries.

The second class of problems are more in-line with the core of this thesis, as they focus on n-party protocols where each party knows one subset of coefficients of the input matrix A and a set of coefficients of b. On this topic, we can cite a protocol by [START_REF] Dagdelen | A multi-party protocol for privacy-preserving cooperative linear systems of equations[END_REF]. This protocol requires at least three players and can be summarized that way: one player will be in charge of performing computations, one will be in charge of interacting with the former, and the others will be mostly passive. The idea is that the master player will engage into a protocol in which they will learn a masked version A 1 of the full input matrix A, and a masked vector b 1 where the "interacting" player will be in charge of picking the masks. The master will then solve the system A 1 x " b 1 and send the result to the "interacting player", who can remove the masks and broadcast the solution to the system. The fact that the interacting player is able to gather the inputs of the other players in order to form A 1 is based on oblivious transfer techniques. This protocol presents nice complexities, with a communication complexity of Opl `kq and a computational complexity of OpN 2 pn `µqq where n is the number of players, µ the security parameter and N the input matrix size. However it does have some disadvantages: the imbalance in player roles forces the master player to perform most of the computation and the security relies on the master player as well: should they be corrupted and colluding with any other party and the players' inputs will immediately be leaked. This protocol is also only secure against semi-honest adversaries.

In the rest of this thesis, we will propose new efficient linear algebra protocols to verify outsourced computation and securely perform multi-party computations. As we showed in this first chapter, these two aspects, verified and secure multi-party computations are two sides of outsourced computation which have many common features, such as their cost metrics, the requirement to interact between several parties Chapter 1: Introduction in order to compute a result, and several underlying linear algebra techniques.

Technical summary and overview of this chapter

Focus This chapter focuses on the design of a verification protocol for the computation of a matrix invariant called the rank profile matrix. Given a matrix A, its rank profile matrix carries the information on the pivots of A and of all the pivots of its leading submatrices. These pivots can be used when performing a Gaussian elimination over A. As the Gaussian elimination is a central tool for linear algebra and is used in many applications, an efficient dedicated verification protocol for the rank profile matrix is an important for verified computing in linear algebra. The articles associated with this chapter are (Dumas et al., 2017b[START_REF] Dumas | Eliminationbased certificates for triangular equivalence and rank profiles[END_REF].

Model We propose verification protocols as defined in Definition 1.1.2, whose efficiency is measured based on the metrics given in Section 1.1.3.

State of the art -main competition

There were no dedicated verification protocols for the rank profile matrix prior to this work. We will thus compare our new protocols to the ones that can be obtained by applying the intermediate approach of [START_REF] Kaltofen | Quadratic-time certificates in linear algebra[END_REF] over the rank profile matrix computation algorithm of Dumas et al. (2017c). For a m ˆn matrix of rank r, this gives a verification protocol with a deterministic Prover in Opmnr ω´2 q, r Opmnq communications and r Opmnq Verifier cost. State of the art dedicated verification protocols for the determinant were presented Section 1.1.5 and their cost is given in Table 1.1.

Results

We present two verification protocols for the rank profile matrix. The first one has quadratic communication volume and Verifier complexity and thus slightly improves on the state of the art. However, it is a non-interactive certificate, which has the advantage of being straightforwardly publicly verifiable. The second one is the main result of this chapter: a new interactive verification protocol in linear communication volume and quadratic Verifier complexity. This protocol relies on a sub-protocol verifying the triangular equivalence of matrices: two matrices A and B are said triangular equivalent if there exists a triangular matrix T such that AT " B. The structure used in the data exchange for this protocol appear to be a central tool to which several problems could be reduced to. Using this observation, we also provide new, more efficient than the state of the art verification protocols for the determinant and the signature of a matrix.

Outline

We first present in Section 2.1 non-interactive verification protocols for the column/row rank profile and the rank profile matrix. Then, we describe and prove in Section 2.2 a new interactive protocol for the rank profile matrix, and its subprotocols, based on the triangular equivalence problem. After that, in Section 2.3, we show how to have a constant number of communication rounds for our row/column rank profile protocol.

Introduction

Gaussian elimination is a central tool used in a wide array of applications in computer algebra, as in the LU decomposition (itself used for linear system solving, or determinant and rank computation), or the computation of basis of vector spaces.

In this chapter, we consider a rectangular matrix A P F mˆn of rank r. The row rank profile (abridged RRP) is the lexicographically minimal sequence of r indices of independent rows of A. The column rank profile (CRP) is defined similarly on the columns of A. These two sequences describe the shape of the row/column echelon form of A and give the position of row/column pivots that can be used when performing a Gaussian elimination over A. The matrix is said to have generic row (resp. column) rank profile if its row (resp. column) rank profile is p1, . . . , rq. This information is contained on an invariant of A, called its rank profile matrix (RPM). The rank profile matrix also contains the information on the row-and column-rank profile of every leading submatrix of A. Formally, the rank profile matrix of A is the unique m ˆn {0-1}-matrix with r nonzero entries of which every leading submatrix has the same rank as the corresponding submatrix of A. This invariant can be computed, either using a deterministic algorithm in Opmnr ω´2 q, or a Monte-Carlo probabilistic algorithm in pr ω `m `n `µpAqq 1`op1q (Dumas et al., 2017c).

A bottom-line verification protocol from the computation of the rank profile matrix can be immediately derived by applying KNS11 on (for instance) the results of (Dumas et al., 2017c(Dumas et al., , 2013)). However, this approach yields logarithmic factors in the communication volume and the verification cost. Thus, there is room for improvement in designing dedicated protocols for the rank profile matrix. To build our rank profile matrix verification protocol, we show that it comes down to certifying a matrix property called the triangular equivalence, which is, for two matrices A, B P F mˆn , the existence of a triangular matrix T P F nˆn such that AT " B. We then propose a generalisation of this protocol allowing to verify the generic rank profile-ness of a matrix and the D and P matrices of an LDUP decomposition. Finally, combining these protocols, it is possible to verify the column rank profile and the rank profile matrix of an invertible matrix. Subsequently, by combining these pieces, we propose a rank profile matrix verification protocol for any matrix. Finally, the D and P from LDUP verification, initially built with the rank profile matrix verification in mind allows us to propose more efficient protocols for the determinant and the signature of a matrix.

We introduce some notations that will be used throughout this chapter: the symmetric group and the group of permutation matrices of size n will be denoted by S n . D n pFq is the group of invertible diagonal matrices over the field F, while D p2q n pFq represents block diagonal matrices with 1 or 2-dimensional diagonal blocks. Finally, we denote by P the set of prime numbers.

2.1

Non interactive and quadratic communication verification protocols

In this section, we propose two verification protocols, the first one for the column (resp. row) rank profile of a given matrix, and the second one for the rank profile matrix of a given matrix. While those protocols have a quadratic communication complexity, they have the advantage of being non interactive.

2.1.1

Column rank profile verification protocol

This verification protocol is based on the P , L, U , Q decomposition of the input matrix A. The main idea here is that the column rank profile of A can be extracted from its PLUQ decomposition if U Q is in row echelon form, which will be proved in Lemma 2.1.1. The Prover will hence commit the entire PLUQ decomposition to the Verifier, who will verify that A " P LU Q using Freivalds' check (Freivalds) and that U Q is row echelonised. This is proposed in details in NonInteractiveColumnRankProfile.

Protocol 2.1: NonInteractiveColumnRankProfile

Public: A P F mˆn , I P p1, . . . , nq Certifies: The colum rank profile of A Prover Verifier

1. Compute a PLUQ decom- position of A s.t. U Q is in row echelon form P , L, U , Q Ý ÝÝÝÝÝÝÝÝ Ñ 2.
Check that U Q is in row echelon form

3.

Freivalds(A, P LU Q)

I

? " pQr1s, . . . , Qrrsq Lemma 2.1.1. Let A " P LU Q be the P , L, U , Q decomposition of an m ˆn matrix A of rank r. If U Q is in row echelon form, then pQr1s, . . . , Qrrsq is the column rank profile of A. Proof. Write A " P " L 1 L 2 ‰ r U 1 U 2 s Q,
where L 1 and U 1 are r ˆr lower and upper triangular respectively. If U Q is in echelon form, then R "

" Ir U ´1 1 U 2 0 pm´rqˆn ı is in reduced echelon form. Now " U ´1 1 I m´r  " L 1 L 2 I m´r  ´1 P T A " " U ´1 1 U Q 0 pm´rqˆn  " R
is left equivalent to A and is therefore the echelon form of A. Hence the sequence of column positions of the pivots in R, that is pQr1s, . . . , Qrrsq, is the column rank profile of A.

Theorem 2.1.2. Let A P F mˆn with r " rankpAq. Protocol 2.1 is a complete and probabilistically sound non interactive protocol. It requires Oprpm `nqq communications and Verifier cost Oprpm `nqq. The probability that the Verifier incorrectly accepts is at most 1{#S. There is a deterministic algorithm for the Prover, which costs Opmnr ω´2 q

Proof. If U Q is in row echelon form, the Verifier will never reject it, and if A " P LU Q, as Freivalds' protocol is complete, the Verifier will systematically accept the Prover commitment, hence ensuring the completeness of this protocol. If U Q is not in row echelon form, this will be caught by the Verifier with probability 1. If A ‰ P LU Q, the Verifier will accept with probability 1{#S (Freivalds' check), hence the soundness of NonInteractiveColumnRankProfile.

Now, for the complexities: the Prover needs to find a P LU Q decomposition of A, where U Q is in row echelon form. Using algorithms provided in [START_REF] Jeannerod | Rank-profile revealing gaussian elimination and the cup matrix decomposition[END_REF], Prover complexity will be Opmnr ω´2 q. Verifier checks can be done in Oprpm `nqq by Freivalds' check. Finally, communication cost is the one of sending P and Q, two permutations matrices and L and U , which are respectively m ˆr and r ˆn matrices, hence the cost of Oprpm `nqq.

Note that this holds for the row rank profile of A: in that case, the Verifier has to check if P L is in column echelon form.

2.1.2

Non interactive Rank Profile Matrix verification protocol

Lemma 2.1.3. A decomposition A " P LU Q reveals the rank profile matrix, namely R A " P r Ir 0 s Q, if and only if P r L 0 s P T is lower triangular and

Q T r U 0 s Q is upper triangular.
Proof. The only if case is proven in (Dumas et al., 2017c, Th. 21). Now suppose that P r L 0 mˆpm´rq s P T is lower triangular. Then we must also have that L " P "

L 0 I m´r ‰ P T is lower triangular and non-singular. Similarly suppose that Q T r U 0 s Q is upper trian- gular so that U " Q T " U 0 I n´r ‰ Q is non-singular upper triangular. We have A " LP r Ir 0 s QU .
Hence the rank of any pi, jq leading submatrix of A is that of the pi, jq leading submatrix of P r Ir 0 s Q, thus proving that R A " P r Ir 0 s Q. We use this characterization to verify the computation of the rank profile matrix in the following protocol: Once the Verifier receives P , L, U and Q, they have to check that A " P LU Q, using Freivalds' check Protocol 1.2, and check that L is echelonised

Protocol 2.2: NonInteractiveRankProfileMatrix

Public: A P F mˆn , R A P F mˆn Certifies: R A is the rank profile matrix of A Prover Verifier

1. Compute a P LU Q de- composition of A reveal- ing R A P , L, U , Q Ý ÝÝÝÝÝÝÝÝ Ñ 2. A ? " P LU Q 3.
Check that P LP T is upper triangular 4.

Check that

Q T U Q is lower triangular 5. R A ? " P " Ir 0 pm´rqˆpn´rq ı Q by P and U T by Q T .
If successful, the Verifier can just compute the rank profile matrix of A from P and Q, as shown in NonInteractiveRankProfileMatrix.

Theorem 2.1.4. NonInteractiveRankProfileMatrix is a complete and probabilistically sound non interactive protocol. It requires Oprpm `nqq communications, and has verifier cost Oprpm `nq `µpAqq The probability that the verifier incorrectly accepts is at most 1{#S.

There is a deterministic algorithm for the Prover in Opmnr ω´2 q Proof. If A " P LU Q, the Verifier will never reject it. If P LP T is upper triangular and Q T U Q is lower triangular, the Verifier will always accept them and by Lemma 2.1.3, the Verifier will successfully extract the rank profile matrix, ensuring the completeness of NonInteractiveRankProfileMatrix. Now if A ‰ P LU Q, the Verifier will reject that with probability 1{#S by Freivalds' check. And finally, if the provided P LU Q decomposition does not reveal the rank profile matrix of A, Lemma 2.1.3 implies that either P LP T or Q T U Q will not have the expected shape, which the Verifier will always detect. Now, for the complexities: the Prover needs to find a rank profile matrix-revealing P LU Q decomposition of A, which can be computed in Opmnr ω´2 q operations using algorithms provided in (Dumas et al., 2013). Verifier checks can be done in Oprpm `nqq `µpAq. Finally, communication cost is the one of sending P and Q, two permutations matrices and L and U , which are respectively m ˆr and r ˆn matrices, hence the cost of Oprpm `nqq.

2.2

An interactive verification protocol for the rank profile matrix

2.2.1

Triangular one sided equivalence

Two matrices A, B P F mˆn are right (resp. left) equivalent if there exists an invertible n ˆn matrix T such that AT " B (resp. T A " B). If in addition T is a lower triangular matrix, we say that A and B are lower triangular right (resp. left) equivalent. The upper triangular (resp. left) equivalence is defined similarly. We propose a protocol verifying that two matrices are left or right equivalent. These two matrices, A and B, will be the input of the protocol. We force A to be a regular (full rank) matrix. A naive protocol would be the matrix T itself, and the Verifier would check that AT " B using Freivalds' check. However, this protocol requires a quadratic amount of communication. Here, we instead propose a protocol allowing to verify triangular equivalence in a linear (2n) amount of communication. We essentially use Freivalds' check, but with a constrained interaction pattern in the way the challenge and response vectors are communicated. This pattern imposes a triangular structure in the way the Prover's responses depend on the Verifier's challenges.TriangularEquivalence shows the full protocol.

Theorem 2.2.1. TriangularEquivalence is a complete and probabilistically sound interactive protocol. It requires 2n communications, and has Verifier cost µpAq `µpBq. The probability that the Verifier incorrectly accepts is at most 1{#S. There is a deterministic algorithm for the Prover in Opmn ω´1 q.

Proof. If T exists, then the Prover can compute it, and answer with appropriate y i , such that the Verifier check Ay " Bx will always hold, hence the completeness of this protocol. Now, if there is no such matrix, we have two distinct cases: either AT ‰ B for any T , or there exists at least one such T , but it is not triangular. In the rest of this proof, we replace the random values x 1 , . . . , x n by algebraically independent variables X 1 , . . . , X n .

In the first case, if AT ‰ B, then there is at least one inconsistent column in B (say the j-th). Thus, there exists a Farkas' certificate of inconsistency (a vector z such that z T A " 0 and z T B ˚,j ‰ 0 for that column. This means that there exists a vector z such that z T Ay " 0 for any y, but z T BrX 1 , . . . , X n s T is a not identically zero polynomial (at least the coefficient of X j is non zero) of degree 1. Therefore, by the DeMillo-Lipton/Schwartz/Zippel lemma [START_REF] Demillo | A probabilistic remark on algebraic program testing[END_REF][START_REF] Zippel | Probabilistic algorithms for sparse polynomials[END_REF][START_REF] Jacob | Fast probabilistic algorithms for verification of polynomial identities[END_REF], its evaluation will be zero with probability at most 1{#S.

In the second case, AT " B but T is not triangular. Since A is regular, there is a unique n ˆn matrix T (that is, T " A ´1 left B, for any A ´1 left left inverse of A). For the same reason, the equality Ay " Bx " AT x implies y " T x. if T is not lower triangular, there is a row index i such that the entry t i,jm ‰ 0 for some j m ą i. The test y " T x only succeeds if y i " ř n j"0 t i,j x j . Now the Prover selects y i before x jm is

Protocol 2.3: TriangularEquivalence

Public: A, B P F mˆn A is regular, and m ě n. T exists Certifies: There exists a matrix T such that AT " B Prover Verifier

1. Find a lower triangu- lar matrix T such that AT " B 2. x i $ Ð Ý S x 1 Ð ÝÝÝÝÝÝÝÝ Ý 3. y 1 " T 1,˚" x 1 0 . . .  y 1 Ý ÝÝÝÝÝÝÝÝ Ñ . . . . . . 4. x n Ð ÝÝÝÝÝÝÝÝ Ý 5. y n " T n,˚" x 1 . . . xn  y n Ý ÝÝÝÝÝÝÝÝ Ñ 6.
y " ry 1 . . . y n s T Ay ? " Bx revealed. Therefore, with probability no more than 1{#S the Verifier selects the field element x jm " 1{t i,jm py i ´řj‰jm t i,j x j q, and the test succeeds for a wrong T . Now for the complexities: the Verifier has to Ay and By, whose computational cost is µpAq `µpBq. The Prover has to compute T , which can be done by a PLUQ elimination on A followed by a triangular system solve, both in Opmn ω´1 q. Then, y " T x requires only Opn 2 q operations, hence the cost given on the theorem statement. Finally, this verification protocol requires to transmit x and y two size n vectors, for a total communication volume of 2n.

Note that the case where T is upper triangular works similarly: the Verifier needs to transmit n in reverse order, starting by x n .

2.2.2

Generic rank profile-ness

Here, we propose a verification protocol which verifies whether a non-singular input matrix A P F mˆn has generic rank profile. As this matrix needs to be non-singular, one needs to verify that beforehand, which can be achieved using the protocol proposed in (Dumas and Kaltofen, 2014, Fig. 2) or RankLowerBound thereafter. A matrix A has generic rank profile if and only if it has an LU decomposition A " LU , with L (resp. U ) a non-singular lower (resp. upper) triangular. This protocol picks random vectors φ, ψ, λ and asks the Prover to provide the vectors z T " λ T L, x " U φ, y " U ψ on the fly, while receiving the coefficients of φ, ψ, λ one at a time. The Verifier will then check that these vectors satisfy the fundamental equations z T x " λAφ and z T y " λ T Aψ. NonSingularGenericRankProfile gives an overview of this verification protocol.

Theorem 2.2.2. NonSingularGenericRankProfile is a complete and probabilistically sound interactive protocol. It requires 6n communications, and has Verifier cost µpAq `8n. The probability that the Verifier incorrectly accepts is at most 1 ´p1 ´1{#Sq 2n . There is a deterministic algorithm for the Prover in Opmn ω´1 q.

Proof. If A has generic rank profile, then A " LU , thus z T "

x y

‰ " λ T LU " φ ψ ‰ " λ T A " φ ψ ‰
, which means the Verifier will never reject the Prover's answer. This proves the completeness of NonSingularGenericRankProfile. Now, for any i such that the pi ´1q ˆpi ´1q leading submatrix of A has generic rank profile, we can write a partial LU decomposition of A with the following notations:

A " " L xiy 0 B xiy I n´i`1  loooooooomoooooooon B " U xiy V xiy 0 C xiy  loooooomoooooon C , (2.2.1)
where L xiy P F pi´1qˆpi´1q is non-singular lower triangular, U xiy P F pi´1qˆpi´1q is nonsingular upper triangular, B xiy P F pn´i`1qˆpi´1q , V xiy P F pi´1qˆpn´i`1q , C xiy P F pn´i`1qˆpn´i`1q .

Protocol 2.4: NonSingularGenericRankProfile

Public: A P F mˆn , non-singular, A has generic rank profile Certifies: A indeed has generic rank profile Prover Verifier

1. A " LU for i from n to 1 2. pφ i , ψ i q $ Ð Ý S 2 φ i , ψ i Ð ÝÝÝÝÝÝÝÝ Ý 3. " x y ‰ " U " φ ψ ‰ x i , y i Ý ÝÝÝÝÝÝÝÝ Ñ 4. λ i $ Ð Ý S λ i Ð ÝÝÝÝÝÝÝÝ Ý 5. z T " λ T L z i Ý ÝÝÝÝÝÝÝÝ Ñ 6. z T " x y ‰ ? " pλ T Aq " φ ψ ‰ Let v ri...ns " rv i , .
. . , v n s T P F 1ˆn´i`1 for a vector v P F nˆ1 , and let η i " pλ ri...ns q T C xiy φ ri...ns , ξ i " pλ ri...ns q T C xiy ψ ri...ns .

(2.2.2)

Consider the following predicate:

H i : η i "pz ri...ns q T x ri...ns and ξ i "pz ri...ns q T y ri...ns .

(2.2.3)

Note that H 1 is what the Verifier checks because then B " I n . Note also that when A is in generic rank profile with A " LU and z T " λ T L and x " U φ and y " U ψ then H i is true for all i. To see this consider an LU-factorization C xiy " Lxiy Ū xiy and the identity

A " " L xiy 0 B xiy I n´i`1  " U xiy V xiy 0 C xiy  " " L xiy 0 B xiy Lxiy  " U xiy V xiy 0 Ū xiy  " LU . (2.2.4)
Then pz ri...ns q T " pλ ri...ns q T Lxiy and x ri...ns " Ū xiy φ ri...ns and y ri...ns " Ū xiy ψ ri...ns verify H i .

Note that the conditions are only tested by the Verifier for i " 1.

At stage i, let Λ i , Φ i and Ψ i be variables for the random choices for λ i , φ i and ψ i and Z i be a variable for the Prover's choice of z i . Then H i in Equation (2.2.3) expands as:

$ ' ' ' ' ' ' ' ' & ' ' ' ' ' ' ' ' % x i Z i " ´dΦ i `e hkkkkkkkkikkkkkkkkj n ÿ j"i`1 C xiy 1,j´i`1 φ j ¯Λi `aΦ i `f, y i Z i " ´dΨ i `n ÿ j"i`1 C xiy 1,j´i`1 ψ j loooooooomoooooooon g ¯Λi `aΨ i `h, (2.2.5) where d " C xiy 1,1 and a " ř n k"i`1 λ k C xiy k´i`1,1 , or equivalently " ´pdΦ i `eq x i ´pdΨ i `gq y i  " Λ i Z i  " " aΦ i `f aΨ i `h . (2.2.6)
Suppose now that A is not in generic rank profile, and let i 0 be minimal such that the leading i 0 ˆi0 minor of A is equal to 0. On any corresponding partial LU decomposition this means that d " C xi 0 y 1,1 " 0. Furthermore, because A is assumed to be non-singular, there exist indices k 0 with 2 ď k 0 ď n ´i0 `1, and j 0 with 2 ď j 0 ď n ´i0 `1 such that

C xi 0 y k 0 ,1 ‰ 0 and C xi 0 y 1,j 0 ‰ 0.
We will now prove the two following statements:

1. H i 0 is false with probability ě p1 ´1{#Sq 4 ; 2. If H i`1 is false then H i is false with probability ě p1 ´1{#Sq 2 for 1 ď i ă i 0 .
Informally, this means that the Prover cannot achieve H i 0 with any choice of returned values x 1 , . . . , z i 0 , with high probability and then this failure propagates with high probability to H 1 which is checked by the Verifier. By induction, this leads to a probability of ě p1 ´1{#Sq 4`2pi 0 ´1q that the Verifier check will fail when the matrix A is not in generic rank profile. Since A is non-singular, i 0 ď n ´1, and therefore this probability is ě p1 ´1{#Sq 2n .

First, we prove Statement 1, that is the case when d " 0. The Verifier selects a random λ i 0 , and then the Prover a z i 0 . If the coefficient matrix in Equation (2.2.6) is non-singular, there is a unique solution for Λ i 0 , which the Verifier will choose with probability ď 1{#S. Otherwise, the coefficient matrix is singular and the only way for the system to have a solution is that the determinant

∆ " ˇˇˇ´e aΦ i 0 `f ´g aΨ i 0 `h ˇˇˇ" ´epaΨ i 0 `hq `gpaΦ i 0 `f q
is equal to 0, which exactly happens in the three following cases: a. " e g ‰ "

" 0 0 ‰ , which happens with probability ď 1{#S 2 as C xi 0 y 1,j 0 ‰ 0; b. a " 0 (which happens with probability ď 1{#S as C xi 0 y k 0 ,1 ‰ 0) and ˇˇˇ´e f ´g h ˇˇˇ" 0;
c. otherwise, ea ‰ 0 or ga ‰ 0 and ∆ is a nonzero polynomial of degree 1 in Φ i 0 , Ψ i 0 and evaluates to 0 for the random choices

φ i 0 , ψ i 0 with probability ď 1{#S. Overall, H i 0 is false with probability ě `1 ´1 #S 2 ˘`1 ´1 #S ˘3 ě `1 ´1 #S ˘4 ě 1 ´4 #S
based on the random choices of the Verifier: φ j 0 , ψ j 0 yield " e g ‰ ‰ " 0 0 ‰ ; λ k 0 yields a ‰ 0; φ i 0 , ψ i 0 yield ∆ ‰ 0; λ i 0 avoids the unique solution to Equation (2.2.6).

For Statement 2, consider the predicate H i Equation (2.2.3) at i ă i 0 , that is d ‰ 0. Similarly, if the coefficient matrix in Equation (2.2.6) is non-singular, there is a unique solution for Λ i , which the Verifier will choose with probability ď 1{|S|. Otherwise, the coefficient matrix is singular and the only way for the system to have a solution is that the following determinant is equal 0:

0 " ∆ " ˇˇˇ´p dΦ i `eq aΦ i `f ´pdΨ i `gq aΨ i `h ˇˇˇ" pdf ´aeqΨ i ´pdh ´agqΦ i ´eh `gf.
We block decompose the bottom right block in the incomplete right factor in Equa-

tion (2.2.1) C xiy " " d r T s W  , where d " C xiy 1,1 ‰ 0. We have C xi`1y " W ´1 d sr T
. Now since a " pλ ri`1...ns q T s, e " r T φ ri`1...ns , we have ae " pλ ri`1...ns q T sr T φ ri`1...ns and f ´ae d " pλ ri`1...ns q T C xi`1y φ ri`1...ns ´pz ri`1...ns q T x ri`1...ns " η i`1 ´pz ri`1...ns q T x ri`1...ns .

Similarly, h ´ag d " ξ i`1 ´pz ri`1...ns q T x ri`1...ns , and these two quantities are not equal to 0 simultaneously, for otherwise H i`1 would be true. Therefore ∆ is a nonzero polynomial of degree 1 in Φ and Ψ. It is equal to 0 with probability ď 1{#S. Overall, H i is false with probability ě p1 ´1{#Sq 2 based on the random choices for λ i , φ i and ψ i made by the Verifier.

Finally, for the complexity, the Prover needs one Gaussian elimination to compute LU in time Opn ω q, then her extra work is just three triangular solve in Opn 2 q. The extra communication is six vectors, φ, ψ, λ, x, y, z, and the Verifier's work is four dotproducts and one multiplication by the initial matrix A (certifying the transposed to have a single matrix times λ-vector product).

2.2.3

LDUP decomposition

With NonSingularGenericRankProfile, when the input matrix does not have generic rank profile, any attempt to prove that it has generic rank profile will be detected with high probability, as this protocol is sound. However, when it does have generic rank profile, the Verifier will accept many possible vectors x, y, z: any scaling of z i by α i and x i , y i by 1{α i would be accepted, for any non zero constant α i . This slack corresponds to our lack of specification on the diagonals in the LU decomposition. Indeed, for any diagonal matrix with non zero elements, LD ˆD´1 U is also a valid LU decomposition and yields x, y and z scaled as above. As specifying these diagonals was not necessary to prove generic rank profile-ness, we left it as is for NonSingularGenericRankProfile.

However, for the determinant or the rank profile matrix verification protocols which follow ( Section 2.4.1, InvertibleRankProfileMatrix) we need to ensure that this scaling is independent from the choice of vectors φ, ψ, λ. Hence, we propose an updated protocol where L has to be unit triangular and the Prover has to first commit the main diagonal D of U .

For a non-singular upper triangular matrix U with diagonal D " Diagpd 1 , . . . , d n q, the matrix U 1 " D ´1U is unit triangular. Thus, for any ψ " " ψ 1 r ψ

 P F nˆ1 : U ψ " DU 1 ψ " D ´ψ `" Ă U 1 r ψ 0
ı¯, where Ă U 1 " pU 1 ´In q t1,...,n´1u,t2,...,nu upper triangular in F n´1ˆn´1 . So the idea is that the Prover will commit D beforehand, and that within a generic rank profile verification protocol, the Verifier will only communicate r φ, r ψ and r λ to obtain z " r λ T r L, x " r U 1 r φ and y " r U 1 r ψ, where r L " pL ´In q t2,...,nu,t1,...,n´1u lower triangular in F n´1ˆn´1 . Then the Verifier will compute by himself the complete vectors. This ensures that L is unit triangular and that U " DU 1 with U 1 unit triangular. Finally, if an invertible matrix does not have generic rank profile, we note that it is also possible to incorporate the permutations, by committing them in the beginning and reapplying them to the matrix during the checks. The full verification protocol is given in Protocol LDUP. A " LDU 1 P Ă U 1 " pU 1 ´In q t1,...,n´1u,t2,...,nu r L " pL ´In q t2,...,nu,t1,...,n´1u

P

? P S n , D ? P D n pF ˚q for i from n to 2 3. φ i , ψ i $ Ð Ý S 2 φ i , ψ i Ð ÝÝÝÝÝÝÝÝ Ý 4. " x y ‰ " r U 1 " r φ r ψ ı x i´1 , y i´1 Ý ÝÝÝÝÝÝÝÝ Ñ 5. λ i $ Ð Ý S λ i Ð ÝÝÝÝÝÝÝÝ Ý 6. z " r λ T r L z i´1 Ý ÝÝÝÝÝÝÝÝ Ñ 7. φ 1 , ψ 1 , λ 1 $ Ð Ý S 3 " x y ‰ " " φ ψ ‰ `"x y 0 0  z T " `λT `"z T 0 ‰z T D " x y ‰ ? " pλ T AqP T " φ ψ ‰
probability that the verifier incorrectly accepts is at most 1 ´p1 ´1{#Sq 2n . There is a deterministic algorithm for the Prover in Opn ω q.

Proof. If A has an LDUP decomposition, then A " LU P " LDU 1 P , so that for any choice of λ and ψ we have: λ T AP T ψ " λ T LDU 1 ψ, that is:

z T Dy " pλ T `"z T 0 ‰ qD ˆψ `"y 0 " " λ 1 r λ T ı `I `" 0 0 r L 0 ‰˘D `" 0 Ă U 1 0 0 ‰ `I˘" ψ 1 r ψ  .
The same is true for λ and φ, which proves the completeness. Now, the last part of Protocol LDUP is actually a verification that AP T has generic rank profile, in other words that there exists lower and upper triangular matrices L ånd U ˚such that AP T " L ˚U ˚. This verification is sound by Theorem 2.2.2. Next, the multiplication by the diagonal D is performed by the Verifier, in order to be actually convinced that there exists lower and upper triangular matrices L ˚and U 1 such that AP T " L ˚DU 1 . Finally, the construction of the vectors with the form a `" r b 0 ‰ is also done by the Verifier, in order to have in fact a guarantee that L ˚and U 1 are unit triangular.

Overall, if the matrix AP T does not have generic rank profile, the Verifier will catch him with the probability of Theorem 2.2.2.

Finally, for the complexity bounds, the extra communications are the 6 vectors r λ, r φ, r ψ and z, x and y. That is 6pn ´1q field elements. The arithmetic computations of the Verifier are one multiplication by a diagonal matrix, 3 vector sums, 4 dot-products and one vector-matrix multiplication by A (for pλ T Aq), that is n `3pn ´1q `4p2n ´1q.

We also give the following proposition, which, while not being need to prove Protocol LDUP, gives some guaranties on the values of D and x, y, z.

Proposition 1. In Protocol LDUP, if AP T is not in generic rank profile, or else if the committed diagonal D does not correspond to the unique decomposition

AP T " LDU 1 or " x y ‰ ‰ U 1 " φ ψ ‰ or z T ‰ λ T L,
then the verification will fail with probability ě p1 ´1 #S q 2n , and therefore Protocol LDUP is sound.

Proof. If A does not have an LDUP decomposition, either (i) AP T is not in generic rank profile, then Protocol LDUP will detect it with the probability of Theorem 2.2.3; (ii) or the Prover could still try to send modified vectors x, y, z or diagonal D. Let then D ˚, x ˚" φ `r x 0 s " U 1 φ, y ˚" ψ `" y 0 ‰ " U 1 ψ and z ˚" r z 0 s `λ " L T λ be the expected diagonal and vectors. Let also i 0 ď n be the largest index such that there is at least one discrepancy in d i 0 , x i 0 , y i 0 or z i 0 that makes at least one of them respectively different from d i0 , x i0 , y i0 or z i0 (x n " x n " 0, y n " y n " 0, z n " z n " 0 by default). Then H i of Equation (2.2.3) is true for all i such that n ě i ą i 0 , and thus in particular H i 0 `1 is true (H n`1 is true by default). Now, H i 0 is also true if and only if we have both:

# z i 0 d i 0 x i 0 " z i0 d i0 x i0 , z i 0 d i 0 y i 0 " z i0 d i0 y i0 . (2.2.7)
Indeed, H i 0 is pz ri 0 ...ns q T D ri 0 ...ns x ri 0 ...ns " pz ˚ri 0 ...ns q T D ri 0 ...ns x ˚ri 0 ...ns and similarly H i 0 `1 is pz ri 0 `1...ns q T D ri 0 `1...ns x ri 0 `1...ns " pz ˚ri 0 `1...ns q T D ri 0 `1...ns x ˚ri 0 `1...ns . Further, Equation (2.2.7), with a " z i0 d i0 x i0 ´zi 0 d i 0 x i 0 , and b " z i0 d i0 y i0 ´zi 0 d i 0 y i 0 , is equivalent to:

# λ i 0 φ i 0 pd i 0 ´di 0 q `λi 0 pd i 0 x i 0 ´di 0 x i0 q `φi 0 pd i 0 z i 0 ´di 0 z i0 q ´a " 0, λ i 0 ψ i 0 pd i 0 ´di 0 q `λi 0 pd i 0 y i 0 ´di 0 y i0 q `ψi 0 pd i 0 z i 0 ´di 0 z i0 q ´b " 0.
(2.2.8)

However, λ i 0 , φ i 0 , ψ i 0 are chosen by the Verifier after d i 0 , x i 0 , y i 0 and z i 0 have been committed. Hence, on the one hand, if d i 0 ‰ d i0 then the coefficient of λ i 0 in one of the two polynomials is not equal to 0 for a random φ i 0 with probability ě 1 1{#S 2 and then that polynomial does not vanish for a random λ i 0 with probability ě p1 ´1{#S 2 qp1 ´1{#Sq, based on the random choices made by the Verifier, and H i 0 is violated.

On the other hand, if d i 0 " d i0 ‰ 0, they can be removed from Equation (2.2.8) which then simplifies (for i 0 ă n) as:

# λ i 0 px i 0 ´xi 0 q `φi 0 pz i 0 ´zi 0 q ´pz i0 x i0 ´zi 0 x i 0 q " 0, λ i 0 py i 0 ´yi 0 q `ψi 0 pz i 0 ´zi 0 q ´pz i0 y i0 ´zi 0 y i 0 q " 0.
(2.2.9)

When there is at least one discrepancy with the expected vector coefficients, then Equation (2.2.9) can be considered as 2 polynomials that are not simultaneously identically zero. Thus they both vanish with probability ď 1{#S based on the random choices made by the Verifier. H i 0 is thus false with probability ě p1 ´1{#Sq. As in the proof of Theorem 2.2.2, this propagates with high probability, to H 1 and the dishonest Prover is detected with probability ě p1 ´1{#Sq 2pn´1q p1 ´1{#S 2 qp1 ´1{#Sq ě p1´1{#Sq 2n . Overall, both (i), AP T is not GRP, or (ii), AP T is GRP but some diagonal or vector elements is wrong, are detected with probability ě p1 ´1{#Sq 2n .

2.2.4

Column or row rank profile verification protocol

Here, we start by recalling two linear time and space verification protocol for an upper and lower bound on the rank of a matrix (RankUpperBound and RankLowerBound). These two protocols combined make a rank verification protocol. We chose to present the variants proposed in (Eberly, 2015, paragraph 2) of the protocol from [START_REF] Dumas | Essentially optimal interactive certificates in linear algebra[END_REF]. An upper bound R on the rank is certified by the ability for the Prover to generate any vector sampled from the image of A by a linear combination of R columns of A (}γ} H denotes the Hamming weight of the vector γ). A lower bound ρ is certified by the Prover ability to recover the unique coefficients of ρ linearly

Protocol 2.6: RankUpperBound

Public: A P F mˆn , a positive integer R Certifies: R is an upper bound on the rank of A Prover Verifier

1. v $ Ð Ý S n , w " Av w Ð ÝÝÝÝÝÝÝÝ Ý 2. Aγ " w γ Ý ÝÝÝÝÝÝÝÝ Ñ 3.
}γ} H ? " R Aγ ? " w independent columns of A. LIN SY Sprq denotes a complexity bound for solving a linear system of rank r.

Theorem 2.2.4. RankUpperBound is a complete and probabilistically sound interactive protocol. It requires m`n communications, and has Verifier cost 2µpAq`n. The probability that the Verifier incorrectly accepts is at most 1{#S. There is a deterministic algorithm for the Prover in LIN SY Sprq.

Protocol 2.7: RankLowerBound

Public: A P F mˆn , a set J of ρ column indices of A Certifies: ρ is a lower bound on the rank of A Prover Verifier

1. α " # α c j $ Ð Ý S 0 otherwise v " Aα v Ð ÝÝÝÝÝÝÝÝ Ý 2. Solve Aβ " v β Ý ÝÝÝÝÝÝÝÝ Ñ 3. β ? " α
Theorem 2.2.5. RankLowerBound is a complete and probabilistically sound protocol. It requires m `ρ communications, and has Verifier cost µpAq `ρ. The probability that the Verifier incorrectly accepts is at most 1{#S. There is a deterministic algorithm for the Prover in LIN SY Sprq.

Note that the communication in RankLowerBound involves sending m field elements for vector v, and only ρ field elements for vector β, as it has only ρ non-zero coefficients which positions are already indicated by J . Hence the total communication cost is m `ρ.

We now consider a column rank profile verification protocol: the Prover is given a matrix A, and answers the column rank profile of A, J " pc 1 , . . . , c r q. In order to certify this column rank profile, we need to certify two properties:

1. the columns given by J are linearly independent; and 2. the columns given by J form the lexicographically smallest set of independent columns of A. Property 1 is verified by RankLowerBound, as it checks whether a set of columns are indeed linearly independent. Property 2 could be certified by successive applications of RankUpperBound: at step i, checking that the rank of A ˚,p0,...,c i ´1q is at most i ´1 would certify that there is no column located between c i´1 and c i in A which increases the rank of A. Hence, it would prove the minimality of J . However, this method requires Opnrq communication space.

Instead, one can reduce the communication by seeding all challenges from a single n dimensional vector, and by compressing the responses with a random projection. The right triangular equivalence verification protocol plays here a central role, ensuring the lexicographic minimality of J . More precisely, the Verifier chooses a vector v P F n uniformly at random and sends it to the Prover. Then, for each index c k P J the Prover computes the linear combination of the first c k ´1 columns of A using the first c k ´1 coefficients of v and has to prove that it can be generated from the k ´1 columns c 1 , . . . , c k´1 . This means, find a vector γ pkq solution to the system:

" A ˚,c 1 A ˚,c 2 . . . A ˚,c k´1 ‰ γ pkq " A » - - - v 1 . . . v c k ´1 0 . . . fi ffi ffi fl .
Equivalently, find an upper triangular matrix Γ such that: (2.2.10) Note that V " Diagpv 1 , . . . , v n qW where W " r1 iăc j`1 s i,j (with c r`1 " n `1 by convention) In order to avoid having to transmit the whole rˆr upper triangular matrix Γ, the Verifier only checks a random projection x of it, using the triangular equivalence TriangularEquivalence. We then propose this verification protocol in ColumnRankProfile.

" A ˚,c 1 A ˚,c 2 . . . A ˚,c r´1 ‰ Γ " A » - - - - - - - - - - v 1 v 1 ¨¨¨¨¨¨v 1 . . . . . . . . . . . . . . . v c 1 ´1 . . . . . . . . . . . .

Protocol 2.8: ColumnRankProfile

Public: A P F mˆn , a set J of r column indices for A Certifies: J is the column rank profile of A Prover Verifier

1. RankLowerBound(A, J ) 2. v $ Ð Ý S n W " r1 iăc j`1 s P F nˆr v Ð ÝÝÝÝÝÝÝÝ Ý 3. V " Diagpv 1 , . . . , v n qW Γ upper tri. s.t. A ˚,tc 1 ,..,cru Γ " AV 4.
TriangularEquivalence(A ˚,tc 1 ,. Proof. If J is the column rank profile of A, ColumnRankProfile corresponds first to an application of Theorem 2.2.5 to certify that J is a set of independent columns. This protocol is perfectly complete. Second the protocol also uses challenges from RankUp-perBound, which is perfectly complete, together with TriangularEquivalence, which is perfectly complete as well. The latter verification protocol is used on A ˚,J , a regular submatrix, as J is a set of independent columns of A. The final check then corre-sponds to ApDpW xqq ´A˚,tc 1 ,..cru y ? " 0 and, overall, ColumnRankProfile is perfectly complete. Now, if J is not the CRP of A, then either the set of columns in J are not linearly independent, which will be caught by the Verifier with probability at least 1 ´1 #S , from Theorem 2.2.5, or J is not lexicographically minimal, or the rank of A is not r. If the rank is wrong, it will not be possible for the Prover to find a suitable Γ. This will be caught by the Verifier verifier with probability 1´1 #S , from Theorem 2.2.1. Finally, if J is not lexicographically minimal, there exists at least one column c k R J , c i ă c k ă c i`1 for some fixed i such that tc 1 , . . . , c i u Y tc k u form a set of linearly independent columns of A. This means that rankpA ˚,1,...,c i`1 ´1q " i`1, whereas it was expected to be i. Thus, the Prover cannot reconstruct a suitable triangular Γ and this will be detected by the Verifier also with probability 1 ´1 #S , as shown in Theorem 2.2.1.

The Prover's time complexity is that of computing a PLUQ decomposition of A. The transmission of v, x and y yields a communication cost of n `2r, which adds up to the m `r communication cost of RankLowerBound. Finally, in addition to RankLowerBound, the Verifier computes W x as a prefix sum with r ´1 additions, multiplies it by D, then subtracts y i at the r correct positions and finally multiplies by A for a total cost bounded by 2µpAq `n `3r ´1.

2.2.5

Rank profile matrix verification protocol

We propose an interactive protocol for the rank profile matrix based on (Dumas et al., 2017c, Algorithm 4): first computing the row and column support of the rank profile matrix, using ColumnRankProfile twice for the row and column rank profiles, then computing the rank profile matrix of the invertible submatrix of A lying on this grid.

In the following we then only focus on a verification protocol for the rank profile matrix of an invertible matrix. It relies on an LUP decomposition that reveals the rank profile matrix. From Lemma 2.1.3, this is the case if and only if P T U P is upper triangular. InvertibleRankProfileMatrix thus gives an interactive protocol that combines Protocol LDUP for a LDUP decomposition with a check that P T U P is upper triangular. The latter is achieved by TriangularEquivalence showing that P T and P T U are left upper triangular equivalent, but since U is unknown to the Verifier, the verification is done on a random right projection with the vector φ used in Protocol LDUP.

Theorem 2.2.7. InvertibleRankProfileMatrix is a complete and probabilistically sound protocol. It requires 8n communication and has Verifier cost µpAq `16n `opnq. The probability the Verifier incorrectly accepts is 1 ´p1 ´1{#Sq 2n . There is a deterministic algorithm for the Prover in Opn ω q.

Proof. If P is the rank profile matrix of A, then P T U P is upper triangular, and this protocol is complete by the completeness of its sub-protocols Now, if P is not the rank profile matrix of A and U " P T U P is not upper triangular, then let pi, jq be the lexicographically minimal coordinates such that i ą j and U i,j ‰ 0. TriangularEquivalence(P T , P T U ) 4. U " P T U P for i from 1 to n:

5. e i $ Ð Ý S e 1 , . . . , e n Ð ÝÝÝÝÝÝÝÝ Ý 6. f T " e T U f 1 , . . . , f n Ý ÝÝÝÝÝÝÝÝ Ñ 7. Protocol LDUP(A, U , P ) 8. Learns φ, ψ, x, y from the call to Protocol LDUP " x y ‰ is U " φ ψ ‰ 9. e T P T x ? " f P φ Now either " x y ‰ ‰ U " φ ψ ‰
, and the verification will then fail to detect it with probability less than p1 ´1 #S q 2n , from Proposition 1. Or one can write e T P T x f T P T φ " pe T U ´f T qP φ " 0. If e T P T U P ´f T " 0.

(2.2.11)

is not satisfied, then a random φ will fail to detect it with probability less than 1 #S , since e, U and f are set before choosing for φ. At the time of committing f j , the value of e i is still unknown, hence f j is constant in the symbolic variable E i . Thus the j-th coordinate in (2.2.11) is a nonzero polynomial in E j and therefore vanishes with probability 1{#S when sampling the values of e uniformly. Hence, overall if P T U P is not upper triangular, the verification will detect it with probability ě p1 ´1 #S q 2n . The Verifier's cost is that of Protocol LDUP with two additional dot products for the last step, which is µpAq `16n `opnq. Similarly, the communication cost is that of Protocol LDUP plus the size of e and f for a total of 8n. The Prover remains unchanged.

Finally, we use (Dumas et al., 2017c, Algorithm 4) to certify the rank profile matrix of any matrix, even a singular one. To do so, we need to verify the row rank profile and the column rank profile of the input matrix, which can be done with two applications of ColumnRankProfile. Then, we certify the rank profile matrix of the r ˆr selection of lexicographically minimal independent rows and columns we obtained before. This is done by an application of InvertibleRankProfileMatrix. We now define E m,ti 1 ,...,inu as the m ˆn matrix whose j-th column is the i j -th vector of the m-dimensional canonical basis. This verification protocol is detailed in RankProfileMatrix, in the case where m ď n. If n ă m, one should first apply ColumnRankProfile on A to compute its column rank profile, and then apply the verification steps of the same protocol for the row rank profile of A. The application of InvertibleRankProfileMatrix remains unchanged.

Theorem 2.2.8. RankProfileMatrix is a complete and probabilistically sound protocol. It requires m`n`minpm, nq`15r communications and has Verifier cost 4µpAq`m`n`21r. The probability the Verifier incorrectly accepts is 1 ´p1 ´1{#Sq 2n . The is a deterministic algorithm for a Prover, which costs Opmnr ω´2 q.

Proof. If the Prover is honest, I is the row rank profile of A and J is the column rank profile of A. Then, the application of InvertibleRankProfileMatrix will output the correct rank profile matrix of A I,J which will lead the Verifier to the correct rank profile matrix of A, as described in (Dumas et al., 2017c, Theorem 37). Note that one only needs to verify the lower bound on the rank of A once, which is why ColumnRankProfile is fully executed once, while the second run only verifies that the committed rank profile is a rank profile indeed. Now, for the soundness, Prover has a probability ě 1 ´1{#S to be caught when cheating while running ColumnRankProfile, and a probability ě p1 ´1 #S q 2n to be caught when cheating while running InvertibleRankProfileMatrix. Overall, this makes a probability ě p1 ´1 #S q 2n for the Verifier to catch a cheating Prover during the execution of RankProfileMatrix.

For the complexities, Prover time complexity is bounded by the complexity of performing a PLUQ decomposition of the input matrix, Opmnr ω´2 q. The Verifier complexity is the one of one full application of ColumnRankProfile and one application of ColumnRankProfile without applying RankLowerBound, which makes 3µpAq`n`m`5r, plus one application of InvertibleRankProfileMatrix over an r ˆr matrix for a cost of µpAq `16r `oprq, the computation of R A only consists of memory operations, hence a total cost of 4µpAq `m `n `21r `oprq field operations. Communication space is computed as follows: a full application of ColumnRankProfile on A if m ě n, on A T otherwise, an application of the same Protocol without the underlying RankLower-Bound which makes n `m `minpm, nq `7r and the same application of InvertibleR-ankProfileMatrix as above, for a cost of 8r, hence a total communication space of m `n `minpm, nq `15r.

Protocol 2.10: RankProfileMatrix

Public: A P F mˆn , m ď n, R A P F mˆn Certifies: R A is the rank profile matrix of A Prover Verifier

1.

Extract the row support of R A as I, its column support as J

2.

ColumnRankProfile(A T , Iq

3.

ColumnRankProfile(A, J q without its Step 1

4. R r " A I,J R r Ý ÝÝÝÝÝÝÝÝ Ñ 5. InvertibleRankProfileMatrix(A I,J , R r ) 6. R A ? " E m,I R r E T n,J

2.3

Constant rounds verification protocols

As previously mentioned in Section 1.1.3, if the network has a poor latency, it is interesting to reduce the number of rounds atop the overall communication volume. We therefore propose in this section a protocol with a constant number of rounds for triangular equivalence, still preserving Prover efficiency as well as linear communication volume and Verifier cost. This applies directly, as previously shown, to row or column rank profiles. However, it fails to apply to the generic rank profile, at least in a straightforward manner, and we were unable to produce such a verification protocol in constant rounds for this task.

2.3.1

Representative Laurent polynomial of a matrix Following a technique in [START_REF] Mulmuley | A fast parallel algorithm to compute the rank of a matrix over an arbitrary field[END_REF], we first define the representative Laurent polynomial, P A pXq of an mˆn matrix A as :

P A pXq " " 1 X X 2 . . . X m´1 ‰ ¨A ¨» - - - - 1 X ´1 . . . X 1´n fi ffi ffi ffi fl " m ÿ i"1 n ÿ j"1 A i,j X i´j
Therefore, if a matrix is lower triangular, then its representative Laurent polynomial cannot have negative powers and it is therefore a polynomial of degree at most m ´1. The converse is not true, consider for instance an upper diagonal with two opposite coefficients : A i,i`1 " 0 for all i except A 1,2 " ´A2,3 . Generically, if one pre-multiplies A on the right by a random non-zero diagonal matrix, these cancellations will not occur as in general

d 1 A 1,2 ‰ ´d2 A 2,3 unless A 1,2 " A 2,3 " 0.

2.3.2

Constant rounds triangular equivalence verification protocol

From this representation, we can obtain a triangular equivalence protocol that requires only a constant number of rounds: the Prover commits the Laurent polynomial of the triangular matrix, then the Verifier will evaluate it a random and compare this to the actual projections. However, the field size must be sufficiently large so that the polynomial identity testing does not fail. The full protocol is given in ConstantRoundTri-angularEquivalence. It requires that the Prover solves a regular system (this is checked deterministically by reapplying the resulting vector), and a diagonal preconditioning on the triangular matrix needs to be applied to prevent cancellations.

Theorem 2.3.1. ConstantRoundTriangularEquivalence is a complete and probabilistically sound protocol. It requires 3n `1 communications and has Verifier cost µpAq `µpBq 7n. The probability the Verifier incorrectly accepts is at most 2pn ´1q{#S. There is an algorithm for the Prover in Opmn ω´1 q.

Proof. Let x " D » - - - - 1 λ ´1 . . . λ 1´n fi ffi ffi ffi fl . If L exists,
D $ Ð Ý D n pSzt0uq D Ð ÝÝÝÝÝÝÝÝ Ý 3. gpXq " P LD pXq gpXq Ý ÝÝÝÝÝÝÝÝ Ñ 4. g ? P FrXs ěn´1 λ $ Ð Ý S λ Ð ÝÝÝÝÝÝÝÝ Ý 5. y, s.t. A ¨y " B ¨D ¨» - - - - 1 λ ´1 . . . λ 1´n fi ffi ffi ffi fl y Ý ÝÝÝÝÝÝÝÝ Ñ 6. A ¨y ? " B ¨D ¨» - - - - 1 λ ´1 . . . λ 1´n fi ffi ffi ffi fl gpλq ? " " 1 λ . . . λ n´1 ‰ ¨y LD » - - - - 1 λ ´1 . . . λ 1´n
fi ffi ffi ffi fl " P LD pλq which proves the correctness.

Now, if L does not exist:

• As A is regular, there is only one solution y to Ay " Bx, thus that check ensures that y is correct, unless not all columns in B are in the column space of A, which is handled as in the proof of Theorem 2.2.1.

• If L is not triangular then its upper part is not identically zero. Therefore by considering D as a diagonal matrix of indeterminates, at least one coefficient of negative degree of the representative rational fraction LD will be non identically zero. As those are of degree 1 in the indeterminates of D, for a random diagonal D, the representative rational fraction of LD will not be a polynomial with probability at least 1 ´1 #S´1 .

• If g is not a polynomial of degree at most n ´1, it is not the representative of a triangular matrix.

• If g is not the representative polynomial of LD then by the DeMillo-Lipton/ Schwartz/Zippel lemma [START_REF] Demillo | A probabilistic remark on algebraic program testing[END_REF][START_REF] Zippel | Probabilistic algorithms for sparse polynomials[END_REF][START_REF] Jacob | Fast probabilistic algorithms for verification of polynomial identities[END_REF], its evaluation at λ will fail with probability 1 ´2n´1 #S (since X n´1 pg ṔLD qpXq is a polynomial of degree at most 2pn ´1q).

For the complexity, the Prover computes L, in Opmn ω´1 q. Then P LD pXq requires one pass over the coefficients of L, and finally y " LD » ----

1 λ ´1 . . . λ 1´n fi ffi ffi ffi fl
. The communication cost is D, gpXq, y all of size n, and λ. The Verifier cost is, µpAq`µpBq to apply A and B, as well as 2n ´3 to compute " 1 λ . . . λ n´1 ‰ and their inverses, n ´2 to multiply by D, 2pn´1q to evaluate g, and 2pn´1q to compute the dotproduct " 1 λ . . . λ n´1 ‰ ¨y.

2.3.3

Constant round verification protocols for the row and column rank profiles

Now we can combine the lower rank RankLowerBound, with the constant-round Con-stantRoundTriangularEquivalence for triangular equivalence, as a replacement of

1. RankLowerBound(A, J ) 2. v $ Ð Ý S n W " r1 iăc j`1 s P F nˆr V " Diagpv 1 , . . . , v n qW v Ð ÝÝÝÝÝÝÝÝ Ý 3.
W " r1 iăc j`1 s P F nˆr V " Diagpv 1 , . . . , v n qW

4.

ConstantRoundTriangularEquivalence(A ˚,J , AV ) 5.

Learns D, g, λ and y from the call to ConstantRoundTriangu-larEquivalence 6.

z "

Diagpv i qW D » - - - - 1 λ ´1 . . . λ 1´r fi ffi ffi ffi fl z c j " z c j ´yj for j " 1..r Az ? " 0 gpλq ? " " 1 λ . . . λ r´1 ‰ y

2.4

Some additional verification protocol

In this final section, we present two new protocols for classical linear algebra problems, the determinant of a matrix and the signature of a symmetric matrix. Using the protocols presented before, our new verification protocols achieve better practical Prover costs than the existing ones for the same problems.

2.4.1

Linear communication verification protocols for the determinant

Existing protocols for the determinant are either optimal for the Prover in the dense case, using the strategy of (Kaltofen et al., 2011, Theorem 5) over a PLUQ decomposition, but quadratic in communication; or linear in communication, using (Dumas et al., 2016, Theorem 14), but using a reduction to the characteristic polynomial. In the sparse case the determinant and the characteristic polynomial both reduce to the same minimal polynomial computations and therefore the latter protocol is currently optimal for the Prover. Now in the dense case, while the determinant and characteristic polynomial both reduce to matrix multiplication, the determinant, via a single PLUQ decomposition is more efficient in practice [START_REF] Pernet | Faster algorithms for the characteristic polynomial[END_REF]. Therefore, we propose here an alternative in the dense case: use only one PLUQ decomposition for the Prover while keeping linear extra communications and Opnq `µpAq operations for the Verifier, for a square matrix A of size n. The idea is to extract the information of an LDUP decomposition without communicating it: one uses Protocol LDUP for A " LDU P with L and U unit diagonal, but kept on the Prover side, and then the Verifier only has to compute detpAq " detpDq detpP q, with n ´1 additional field operations.

Corollary 2.4.1. For an nˆn matrix, there exists a sound and perfectly complete protocol for the determinant over a field using less than 8n extra communications and with computational cost for the Verifier bounded by µpAq `13n `opnq.

As a comparison, the protocol of (Dumas et al., 2016, Theorem 14) reduces to CHAR-POLY instead of PLUQ for the Prover. In theory, both approaches are similar: Prover asymptotic cost is the same, Opn ω q, Verifier time is the same and communication volume is 8n for PLUQ and 5n for CHARPOLY. Moreover, CHARPOLY is better than PLUQ on the number of rounds (constant rounds against Opnq) while PLUQ works on smaller fields than CHARPOLY (minimum size 2 against n 2 ). However, PLUQ is much more efficient in practice. Table 2.1 shows timings for PLUQ and CHARPOLY computations using the FFLAS-FFPACK library (version 2.3.1) (The FFLAS-FFPACK group, 2019) on an Intel i7-6700U@3.4GHz. Communications were measured between two workstations over an Ethernet Cat. 6@1GB/s network cable. On 50k ˆ50k matrices, the characteristic polynomial of a random dense matrix can be computed in about 134 minutes, while it takes approximately 5.5 less time to perform the PLUQ decomposition (24 minutes). The Verifier time, which is the one of performing a matrix-vector multiplication (the fgemv routine) is approximately 1s.

2.4.2

Verification protocol for the signature of an integer matrix

The signature of a symmetric matrix is the triple pn `, n ´, n 0 q indicating the number of positive, negative, and zero eigenvalues, respectively. Just like (Dumas and Kaltofen, 2014, Theorem 5), the idea is that the Prover commits the list of eigenvalues, and then certifies it modulo a Verifier chosen prime. This works directly for the signature algorithm in [START_REF] Kaltofen | Quadratic-time certificates in linear algebra[END_REF], Corollary 1) together with the CHARPOLY protocol of (Dumas et al., 2016, Theorem 14). As in Section 2.4.1, in the dense case we propose here to replace the CHARPOLY computation with a symmetric Gaussian elimination.

Over the rationals, an algorithm for the Prover could be to first compute and certify the rank of A, and to compute a permutation matrix P such that P T AP has generic rank profile: for instance compute a P L p ∆ p L T p P T factorization modulo a sufficiently large prime p. A symmetric matrix always has such a decomposition, where ∆ is a block diagonal matrix with square blocks of size 1 or 2 [START_REF] Bunch | Some stable methods for calculating inertia and solving symmetric linear systems[END_REF]. Then B " rI r |0sP T AP r Ir 0 s is symmetric and non-singular. It is then sufficient to lift or reconstruct only the block diagonal matrix ∆ over Q of a non-pivoting symmetric factorization of B (the unit triangular matrix over Q need not be computed). Compared to an integer characteristic polynomial computation this gains in practice an order of magnitude in efficiency for the Prover as shown on the logscale Figure 2.1, using FFLAS-FFPACK-2.3.1, LinBox-1.5.1 (The LinBox group, 2019) on a single core of an Intel i7-6700U@3.4GHz.

For the verification, the block diagonal matrix ∆, and the permutation P are committed. The Verifier then randomly chooses a prime q and enters an interactive certification process for P and ∆ mod q using Protocol LDUP, as shown on Protocol Signature.

From (Dumas and Kaltofen, 2014, Theorem 5), we let h " log 2 p ? n n ||A|| n 8 q be the logarithm of Hadamard's bound for the invariant factors of A. There cannot be more than h primes reducing the rank. Therefore it is possible to sample c ¨h distinct primes of magnitude bounded by Oph logphqq for any constant c ą 2 and select q 1 from that set S 1 . Once the rank is certified, the Prover can compute the permutation and lift the diagonal. Finally the rational P L∆L T P T factorization of the full rank matrix can be similarly verified modulo a prime q 2 . As for the determinant, no more than h primes can reduce the rank of ∆ and q 2 can be selected from the same kind of set. We have Protocol 2.13: Protocol Signature Public: A P Z nˆn , symmetric, a triple of integers pn `, n ´, n 0 q Certifies: The signature of A is pn `, n ´, n 0 q Prover Verifier

1. I " RRP pAq I Ý ÝÝÝÝÝÝÝÝ Ñ 2. q 1 $ Ð Ý S Ă P q 1 Ð ÝÝÝÝÝÝÝÝ Ý

3.

ColumnRankProfile(A mod q 1 , I)

4.
Is convinced that I is the RRP and CRP of A mod q 1

Is convinced that |I| " rankpAq mod q 1 5. A " P L∆L T P T P , ∆ Ý ÝÝÝÝÝÝÝÝ Ñ

P

? P S r , ∆ ? P D p2q r pQq q 2 $ Ð Ý S 2 Ă P 7.
Protocol LDUP(P T A I,I P mod q 2 , I r , ∆q Learns x, y, z, λ, ψ, φ from the call to Protocol LDUP 8.

z T ∆ " xy ‰ ? " pλ T P T A I qP " φ ψ ‰ mod q 2 9.
Compare pn `, n ´, n 0 q with the number of positive, negative and zero elements in ∆ proven:

Corollary 2.4.2. For a symmetric matrix A P Z nˆn , Protocol Signature for its signature is sound and perfectly complete.

The communication comprise that of the Protocol LDUP, the permutation matrix P , all of size n, as well as small primes bounded by h, and finally ∆. Just like that of the characteristic polynomial, the size of ∆ can be quadratic and therefore the whole protocol is not linear. Thus a simpler quadratic protocol communicating the triangular matrix L modulo q 2 , and checking the decomposition A ´L∆L T via Freivalds' check might also work. But then the communication and Verifier time would always be quadratic. Instead, Protocol Signature, just like the Protocol using the characteristic polynomial, is better if the size of the determinant is small, as then the size of ∆ might be much less than that of L (for instance linear if the determinant is a constant). Protocol Signature is also interesting if µpAq is less than quadratic.

Conclusion

A summary of our contributions is given in Table 2.2. In this chapter, we provided verification protocols that can save overall computational time for the Prover, and an order of magnitude in terms of communication volume or number of rounds. In particular, in Table 2.1 which compares both linear and quadratic communication and sub-cubic or quadratic matrix operations, one can see that it is interesting to use linear space protocols even when they have quadratic verification time. This table also exhibits a practical factor of about 5 between PLUQ and CHARPOLY computations.

The key idea of this chapter was to certify the existence of a triangular matrix in an equivalence relation, by having an n round protocol where data dependency matches the triangular shape of the unknown matrix factor. This approach was adapted to the verification of generic rank profile-ness in the LU decomposition, where two triangular unknown factors are considered.

Mulmuley's Laurent's polynomial representation of a matrix successfully replaces the former technique to certify triangular equivalence, and consequently row or column rank profiles, reducing the number of rounds from linear to constant. However, we were unable to adapt this technique for the generic rank profile-ness protocol and the rank profile matrix protocol.

The use of symmetric Gaussian elimination allowed us to achieve a more practical protocol for the signature of symmetric integer matrices. Even though it is based on LDLT verification with linear communication modulo a prime, the diagonal of rational eigenvalues remains quadratic in size, and full precision was required to recover their sign. Designing a linear communication and Prover efficient protocol for the signature is the other major open problem which should be investigated.

Technical summary and overview of this chapter

Focus This chapter focuses on the design of verification protocols for various computations on matrices over the ring of univariate polynomials over a field F. The article associated with this chapter is [START_REF] Lucas | Verification Protocols with Sub-Linear Communication for Polynomial Matrix Operations[END_REF].

Model

We propose verification protocols as defined in Definition 1.1.2, whose efficiency is measured based on the metrics given in Section 1.1.3.

State of the art -main competition

There were no dedicated verification protocols for the properties we consider on polynomial matrices prior to this work.

Results

The first part of this chapter focuses on verification protocols for classical linear algebra properties of matrices such as the rank, the determinant or the singularity. We also give verification protocols for matrix product and system solving. As these properties can be seen as vector space problems, the protocols we propose are heavily based on evaluation techniques: we evaluate the polynomial matrix at a random point and use vector space verification problems for the property to verify. These protocols are thus similar to those of [START_REF] Kaltofen | Quadratic-time certificates in linear algebra[END_REF], in which they were using similar techniques of reduction modulo a prime number for integer matrices. In the second part of this chapter, we focus on module problems. For these problems, the evaluation technique no longer works and we can no longer rely on vector space verification protocols. We first present a new verification protocol to verify that a given vector belongs to the row space of a given full row rank polynomial matrix. Using this new protocol, we then design a verification protocol for the same problem for matrices of arbitrary rank. This new row space membership verification protocol proves to be a central tool for the verification of many module properties of polynomial matrices: it allows us to verify that the row space of a matrix is contained in the row space of another, which in turn leads to verifying the row space equality of two matrices. With this, we can in turn verify normal forms of polynomial matrices, such as the Hermite form or the shifted Popov form. Finally, we verify properties related to the saturation and the kernels of polynomial matrices.

Outline

After giving some preliminary material in section 3.1, we propose verification protocols for classical properties of polynomial matrices -singularity, rank, determinant and matrix product -with sub-linear communication cost with respect to the input size (section 3.2). Those protocols are based on evaluating considered matrices at random points, which allows us to reduce the communication space and to use existing verification protocols for matrices over fields. Then, in section 3.3 we give the main result of this chapter, which is certifying that a given polynomial row vector is in the row space of a given polynomial matrix, which can either have full rank or be

Introduction

In this chapter, we propose new verification protocols for computations performed on univariate polynomial matrices. Generically, we consider protocols where a Prover performs computations and provides additional data structures to or exchanges with a Verifier, who will use these to check the validity of a result, at a lower cost than by recomputing it. This chapter deals with computations on matrices whose entries are univariate polynomials. While certification for matrices over fields and over integer rings have been studied over the past twenty years, there are only few results on polynomial matrices [START_REF] Dumas | Proof-of-work certificates that can be efficiently computed in the cloud (invited talk)[END_REF][START_REF] Giorgi | Certification of minimal approximant bases[END_REF].

A polynomial matrix is a matrix M P Frxs mˆn whose entries are univariate polynomials over a field F. There is an isomorphism with matrix polynomials (univariate polynomials with matrices as coefficients) which we will sometimes use implicitly, such as when considering the evaluation M pαq P F mˆn of M at a point α P F.

One general approach for computing with polynomial matrices is based on evaluation and interpolation. The basic idea is to first evaluate the polynomial matrix, say M P Frxs nˆn at a set of points α 1 , α 2 , . . . P F in the ground field, then to separately perform the desired computation on each M pα i q over F nˆn , and finally reconstruct the entries of the result using fast polynomial interpolation. This kind of approach works well for operations such as matrix multiplication (Bostan and Schost, 2005, Section 5.4) or determinant computation. These computations essentially concern the vector space in the sense that M may as well be seen as a matrix over the fractions Fpxq without impact on the results of the computations.

Other computational problems with polynomial matrices intrinsically concern Frxsmodules and thus cannot merely rely on evaluation and interpolation. Classic and important such examples are that of computing normal forms such as the Popov form and the Hermite form [START_REF] Vasile | Invariant description of linear, time-invariant controllable systems[END_REF][START_REF] Villard | Computing popov and hermite forms of polynomial matrices[END_REF][START_REF] Neiger | Computing Popov and Hermite forms of rectangular polynomial matrices[END_REF] and that of computing modules of relations such as approximant bases [START_REF] Beckermann | A uniform approach for the fast computation of matrix-type Padé approximants[END_REF][START_REF] Giorgi | On the complexity of polynomial matrix computations[END_REF][START_REF] Neiger | Computing canonical bases of modules of univariate relations[END_REF]. The algorithms in this case must preserve the module structure attached to the matrix and thus deal with the actual polynomials in some way; in particular, an algorithm which works only with evaluations of the matrix at points α P F is oblivious to this module structure.

A summary of our contributions is given in table 3.1, based on the following notations: the input matrix has rank r and size n ˆn if it is square or m ˆn if it can be rectangular; if there are several input matrices, then r stands for the maximum of their ranks, m for the maximum of their row dimensions, and n for the maximum of their column dimensions. Where appropriate, r is the maximum of the actual ranks of the matrices and the claimed rank by the Prover. We write d for the maximum degree of any input matrix or vector.

The Prover and Verifier costs are in arithmetic operations over the base field F. We use r

Op¨q for asymptotic cost bounds with hidden logarithmic factors, and ω ď 3 is the exponent of matrix multiplication, so that the multiplication of two nˆn matrices over F uses Opn ω q operations in F; see Section 3.1 for more details and references.

The last column indicates the smallest size of the ground field F needed to ensure both perfect completeness of the protocol and soundness with probability at least 1 2 . If this lower bound is not met, an extension field may be agreed on in advance by the Prover and Verifier, for a (logarithmic) increase in arithmetic and communication costs. For all protocols, an arbitrary low probability p of failure can be achieved by simply iterating the protocol at most rlog 2 p1{pqs times.

3.1

Preliminaries

Asymptotic complexity bounds We complete the notations and notions given in Chapter 1, with specific details for polynomial matrices. [START_REF] Cantor | On fast multiplication of polynomials over arbitrary algebras[END_REF] have shown that multiplying two univariate polynomials of degree ď d over any algebra uses r

Opdq additions, multiplications, and divisions in that algebra. In particular, multiplying two matrices in Frxs nˆn of degree at most d uses r

Opn ω dq operations in F.

Rational fractions

For a rational fraction f P Fpxq, define its denominator denompf q to be the unique monic polynomial g P Frxs of minimal degree such that gf P Frxs.

Correspondingly, define its numerator numerpf q " f ¨denompf q. Note that denompaq " 1 if and only if a P Frxs. More generally, for a matrix of rational fractions A P Fpxq mˆn , define denompAq to be the unique monic polynomial g P Frxs of minimal degree such that gA P Frxs mˆn , and again write this polynomial matrix gA as numerpAq. Note that we have the identity denompAq " lcm i,j pdenompA i,j qq.

Row space, kernel, and row basis For a given matrix A P Frxs mˆn , two basic sets associated to it are its row space RowSp Frxs pAq " tpA, p P Frxs 1ˆm u, and its left kernel tp P Frxs 1ˆm | pA " 0u.

Accordingly, a row basis of A is a matrix in Frxs rˆn whose rows form a basis of the former set, where r is the rank of A, while a left kernel basis of A is a matrix in Frxs pm´rqˆn whose rows form a basis of the latter set. We use similar notions and notations for column spaces and column bases, and for right kernels and right kernel Table 3.1: Summary of the contributions. The first column states whether the Prover's algorithm is deterministic or not. The costs are given in number of arithmetic operations over the base field and the communication is in number of elements in the base field F. The last column reports the minimum size size of F needed to ensure perfect completeness and soundness with probability at least 1 2 .

bases. We will also often consider the rational row space or Fpxq-row space of A, denoted by RowSp Fpxq pAq, which is an Fpxq-vector space. Matrices which preserve the row space under left-multiplication, that is, U P Frxs mˆm such that the Frxs-row space of U A is the same as that of A, are said to be unimodular. They are characterized by the fact that their determinant is a nonzero constant; or equivalently that they have an inverse (with entries in Frxs).

3.1.1

Some probability bounds.

Many of our protocols rely on the fact that when picking an element uniformly at random from a sufficiently large finite subset of the field, this element is unlikely to be a root of some given polynomial. This was stated formally in [START_REF] Jacob | Fast probabilistic algorithms for verification of polynomial identities[END_REF][START_REF] Zippel | Probabilistic algorithms for sparse polynomials[END_REF][START_REF] Demillo | A probabilistic remark on algebraic program testing[END_REF] and is often referred to as the DeMillo-Lipton-Schwartz-Zippel lemma.

Specifically, it states that for any nonzero k-variate polynomial f px 1 , . . . , x k q with coefficients in a field F, and any finite subset S Ď F, if an evaluation point pα 1 , . . . , α k q P F k has entries chosen at random uniformly and independently from S, then the probability that f pα 1 , . . . , α k q " 0 is at most d{#S, where d is the total degree of f .

The following consequence is a standard extension of the soundness proof of Freivalds' algorithm (1979). Lemma 3.1.1. Let A P F mˆn be a matrix with at least one nonzero entry and let S Ď F be a finite subset. For a vector of scalars w P S nˆ1 chosen uniformly at random, we have PrrAw " 0s ď 1{#S.

Proof. Consider each of the n entries of w as an indeterminate. Because A is not zero, Aw has at least one nonzero entry, which is a nonzero polynomial in n variables with total degree 1. Then a direct application of the DeMillo-Lipton-Schwartz-Zippel lemma gives the stated result.

The next lemma will also be frequently used when analyzing protocols: it bounds the probability of picking a "bad" evaluation point. Lemma 3.1.2. Let A P Frxs mˆn with rank at least r. For any finite subset S Ď F and for a point α P S chosen uniformly at random, the probability that rankpApαqq ă r is at most r degpAq{#S.

Proof. Any r ˆr minor of A has degree at most r degpAq, and at least one must be nonzero since rankpAq ě r. On the other hand, rankpApαqq ă r if and only if α is a root of all such minors.

3.2

Linear algebra operations

In this section, we give some verification protocols for the computation of classical linear algebra properties on polynomial matrices: singularity, rank, and determinant of a matrix, as well as system solving and matrix multiplication.

The protocols we present here all rely on the same general idea, which consists in picking a random point and evaluating the input polynomial matrix (or matrices) at that point. This allows us to achieve sub-linear communication space. Note that this technique has been used before by [START_REF] Kaltofen | Quadratic-time certificates in linear algebra[END_REF] to certify the same properties for integer matrices: in that setup, computations were performed modulo some prime number, while, in our context, this translates into evaluating polynomials at some element of the base field.

In several of our protocols, the Prover has to solve a linear system over the base field. For a linear system whose matrix is in F mˆn and has rank r, this can be done in Opmnr ω´2 q operations in F (see Jeannerod et al., 2013, Algorithm 6).

3.2.1

Singularity and nonsingularity

We start by certifying the singularity of a matrix. Here, the Verifier picks a random evaluation point and sends it to the Prover, who evaluates the input matrix at that point and sends back a nontrivial kernel vector, which the Prover will always be able to compute since a singular polynomial matrix is still singular when evaluated at any point. Then, all the Verifier needs to do is to check that the vector received is indeed a kernel vector. Note that the evaluation trick here is really what allows us to have a sub-linear -with respect to the input size -communication cost, as the answer the Prover provides to the challenge is a vector over the base field, and not over the polynomials.

Protocol 3.1: Protocol Singularity

Public: A P Frxs nˆn Certifies: A is singular Prover Verifier

1. α $ Ð Ý S α Ð ÝÝÝÝÝÝÝÝ Ý 2. Find v P F 1ˆn zt0u s.t. vApαq " 0 v Ý ÝÝÝÝÝÝÝÝ Ñ 3. v ? ‰ 0 vApαq ? " 0
In the next theorem, and for the remainder of the section, for convenience we write d " maxp1, degpAqq. Theorem 3.2.1. Protocol 3.1 is a complete and probabilistically sound interactive protocol which requires Opnq communication and has Verifier cost Opn 2 dq. The probability that the Verifier incorrectly accepts is at most nd{#S. If A is singular, there is an algorithm for the Prover with cost Opn 2 d `nr ω´1 q.

Proof. If A is singular, Apαq must also be singular and there exists a nontrivial nullspace vector that the Verifier will accept.

If A is nonsingular, then the Prover will be able to cheat if the Verifier picked an α such that Apαq is singular, which happens only with probability nd{#S according to lemma 3.1.2. Now, for the complexities: the Prover will have to evaluate A at α, which costs Opn 2 dq and to find a nullspace vector over the base field, which costs Opnr ω´1 q, hence the Prover cost. The Verifier computes the evaluation and a vector-matrix product over F, for a total cost of Opn 2 dq operations. Finally, a vector over F n and a scalar are communicated, which yields a communication cost of Opnq.

We now present a verification protocol for nonsingularity. This relies on the same evaluation-based approach, with one variation: here, we let the Prover provide the evaluation point. Indeed, if the Verifier picked a random point, they could choose an "unlucky" point for which a nonsingular matrix evaluates to a singular one, and in that case, the protocol would be incomplete as the Prover will not be able to convince the Verifier of nonsingularity. Instead, we let the Prover pick a point as they have the computational power to find a suitable point (Step 1 in Protocol NonSingularity). Once this value is committed to the Verifier, in Steps 2 to 4 we use the protocol verifying nonsingularity over a field due to Dumas and Kaltofen (2014, Theorem 3). Theorem 3.2.2. Protocol 3.2 is a probabilistically sound interactive protocol and is complete assuming that #S ě nd `1. It requires Opnq communication and has Verifier cost Opn 2 dq. The probability that the Verifier incorrectly accepts is at most 1{#S. There is an algorithm for the Prover with cost r

Opn ω dq.

Proof. If A is nonsingular, then, as the field is large enough, there exists an α for which the rank of Apαq does not drop, and as Steps 2 to 4 form a complete verification protocol, Protocol NonSingularity is complete. If A is singular, it is not possible to find an α such that Apαq is nonsingular. This means the Prover successfully cheats if they manage to convince the Verifier that Apαq is nonsingular, which only happens with probability 1{#S (Dumas and Kaltofen, 2014, Theorem 3), hence the soundness of Protocol NonSingularity. Now, for the complexities: the Prover needs to find a suitable α. The Prover first computes detpAq P Frxs using the deterministic algorithm of Labahn et al. (2017, Theorem 1.1)

in r

Opn ω dq time. Then, using fast multipoint evaluation, the determinant is evaluated at nd `1 points from S in time r

Opndq (von zur Gathen and Gerhard, 2013, Corollary 10.8); since degpdetpAqq ď nd, at least one evaluation will be nonzero. Computing this determinant dominates the later cost for the Prover to evaluate Apαq and solve a linear system over the base field, hence a total cost of r

Opn ω dq.

Protocol 3.2: NonSingularity

Public: A P Frxs nˆn Certifies: A is nonsingular Prover Verifier

1. Find α P F s.t. detpApαqq ‰ 0 α Ý ÝÝÝÝÝÝÝÝ Ñ 2. b $ Ð Ý S nˆ1 b Ð ÝÝÝÝÝÝÝÝ Ý 3. Find w P F nˆ1 s.t.
Apαqw " b w Ý ÝÝÝÝÝÝÝÝ Ñ

Apαqw

? " b

The Verifier needs to evaluate A at α and to perform a matrix-vector multiplication over the base field, hence a cost of Opn 2 dq. Finally, total communications are two vectors of size n over the base field and a scalar, hence the cost of Opnq.

3.2.2

Matrix Rank

From the protocol for nonsingularity, we immediately infer one for a lower bound ρ on the rank: the Prover commits a set of row indices and a set of column indices which locate a ρ ˆρ submatrix which is nonsingular, and then the protocol verifying nonsingularity is run on this submatrix. Theorem 3.2.3. Let r be the actual rank of A. Protocol 3.3 is a probabilistically sound interactive protocol and is complete assuming #S ě ρd `1 in its subprotocol. It requires Opρq communication and has Verifier cost Opρ 2 dq. If we indeed have r ě ρ, then there is a Las Vegas randomized algorithm for the Prover with expected cost Opmnr ω´2 `mndq. Otherwise, the probability that the Verifier incorrectly accepts is at most 1{#S.

Proof. If ρ is indeed a lower bound on the rank of A, there exist two sets I Ď t1, . . . , mu and J Ď t1, . . . , nu of size ρ such that A I,J is nonsingular, and since Protocol NonSingularity is complete, so is this protocol. Note that the completeness of the sub-protocol is ensured only if #S ě ρd `1.

If ρ is not a lower bound on the rank of A, meaning rankpAq ă ρ, then the Prover will not be able to find suitable I and J and hence the sets provided by a cheating Prover yield a singular submatrix A I,J . Now, if the Prover provided sets which do not Use Protocol NonSingularity(A I,J ) contain ρ elements or which contain elements outside the allowed dimension bounds, this will always be detected by the Verifier. If the Prover provided sets with enough elements, the Verifier incorrectly accepts with the same probability as in Protocol Non-Singularity, which is 1{#S.

Regarding the complexities, the Prover has to find a ρ ˆρ nonsingular submatrix of an m ˆn degree d matrix. This can be achieved in a Las Vegas fashion, by evaluating the matrix A at a random α in time Opmndq, and computing the rank profile matrix (or a rank profile revealing PLUQ decomposition) of Apαq, see for instance [START_REF] Dumas | Computing the rank profile matrix[END_REF]. The cost of this computation is Opmnr ω´2 q, with r the actual rank of A.

As ρ ď r, running Protocol 3.2 on a ρ ˆρ matrix does not dominate the complexity, hence the total Prover cost of Opmnr ω´2 `mndq. From theorem 3.2.2, the Verifier cost is Opρ 2 dq. Finally, here two sets of ρ integers are transmitted, which with the communications in Protocol NonSingularity adds up to a communication cost of Opρq. Now, we give a protocol verifying an upper bound on the rank. Note that Steps 2 and 3 of Protocol 3.4 come from the protocol verifying an upper bound on the rank for matrices over a field (see Dumas and Kaltofen, 2014, Theorem 4). In this protocol, we use the notation | ¨|H to refer to the Hamming weight: |γ| H ď ρ means that the vector γ as at most ρ nonzero entries. Theorem 3.2.4. Let r be the actual rank of A. Then, Protocol 3.4 is a complete and probabilistically sound interactive protocol which requires Opnq communication and has Verifier cost Opmndq. If we indeed have r ď ρ, then there is an algorithm for the Prover with cost bound Opmnr ω´2 `mndq. Otherwise, the probability that the Verifier incorrectly accepts is at most prd `1q{#S.

Protocol 3.4: RankUpperBound

Public: A P Frxs mˆn , ρ P N Certifies: rankpAq ď ρ Prover Verifier

1. α $ Ð Ý S v $ Ð Ý S nˆ1 α, v Ð ÝÝÝÝÝÝÝÝ Ý 2. Find γ P F nˆ1 such that Apαqγ " Apαqv and |γ| H ď ρ γ Ý ÝÝÝÝÝÝÝÝ Ñ 3. |γ| H ? ď ρ Apαqγ ? " Apαqv
Proof. If ρ is indeed an upper bound on the rank of A, then, whichever evaluation point the Verifier picked, ρ will be an upper bound on the rank of Apαq and, as the protocol from (Dumas and Kaltofen, 2014, Theorem 4) is complete, this protocol is complete.

If ρ is not an upper bound on the rank of A, there are two possibilities of failure. Either the Verifier picked an evaluation point for which the rank of A drops, which happens with probability at most rd{#S by Lemma 3.1.2; or the Prover managed to cheat during the execution of Steps 2 and 3 which happens with probability at most 1{#S (Dumas and Kaltofen, 2014, Theorem 4). Then, the union bound gives a total probability of prd `1q{#S for the Verifier to accept a wrong answer.

The Prover has to evaluate the matrix at α for a cost of Opmndq. Then to find the vector γ, the Prover can for instance first compute a PLUQ decomposition Apαq "

P " L 1 L 2  " U 1 U 2 ‰
Q for a cost of Opmnr ω´2 q. Then, the Prover computes the vector

" w 1 w 2  " Qv,
where w 1 has size r, and computes γ " Q

" w 1 `U ´1 1 U 2 w 2 0  . This
vector has Hamming weight at most r (recall that Q is a permutation matrix) and satisfies Apαqγ " P

" L 1 L 2  " U 1 w 1 `U2 w 2 ‰ " Apαqv.
The Verifier has to evaluate the matrix at α and to perform two matrix-vector products over the base field, which yields a cost of Opmndq. The communication cost is the one of sending a scalar and two vectors of size n over the base field, that is, Opnq.

From these protocols verifying upper bounds and lower bounds on the rank, we directly obtain one for the rank (Protocol 3.5). Otherwise, the probability that the Verifier incorrectly accepts is at most prd `1q{#S.

Protocol 3.5: Rank

3.2.3

Determinant

We follow on with a protocol verifying the determinant of a polynomial matrix, using a similar evaluation-based approach: after the Verifier has checked that the degree of the provided determinant is suitable, a random evaluation point is sampled and the actual verification occurs on the evaluated input. The check on the degree of the provided determinant is to allow that the DeMillo-Lipton-Schwartz-Zippel Lemma applies and produces the claimed probability of the success. There are two choices available for the protocol to use over the base field: either the one from (Dumas et al., 2016, Section 2), which runs in a constant number of rounds but requires a minimum field size of n 2 , or the one from (Dumas et al., 2017b, Section 4.1) which runs in n rounds but has no requirement on the field size. Whichever protocol is chosen here, this has no impact on the asymptotic complexities which are the same for both, or on the completeness as both are perfectly complete.

Theorem 3.2.6. Protocol 3.6 is a complete and probabilistically sound interactive protocol which requires Opnq communication and has Verifier cost Opn 2 dq. If δ is indeed the determinant of A, there is an algorithm for the Prover which costs Opn 2 d `nω q.

Otherwise, the probability that the Verifier incorrectly accepts is at most pnd `1q{#S.

Proof. Let g " detpAq P Frxs be the actual determinant of A.

If δ " g, then it must be the case that degpδq ď nd. Then, as FieldDeterminant is complete, the final check will be positive.

Protocol 3.6: Determinant

Public: A P Frxs nˆn , δ P Frxs Certifies: detpAq " δ

Prover Verifier

1.

degpδq ? ď nd α $ Ð Ý S β Ð δpαq α Ð ÝÝÝÝÝÝÝÝ Ý 2.
Use FieldDeterminant(Apαq, β)

If δ ‰ g, there are two possibilities of failure. If the Verifier has picked an α which is a root of δ ´g, then δpαq " gpαq and the checks from FieldDeterminant will always pass; by the DeMillo-Lipton-Schwartz-Zippel lemma, this happens with probability at most nd{#S. Otherwise, the Verifier has picked an α such that δpαq ‰ gpαq which means they will accept δ as the determinant with the probability of failure of FieldDeterminant, that is, 1{#S. Overall, by the union bound, the probability that the Verifier accepts a wrong statement is at most pnd `1q{#S.

The Prover has to evaluate the matrix at α and to compute a determinant over the base field, which yields the cost of Opn 2 d `nω q; the Verifier has to evaluate A at α, hence a cost of Opn 2 dq; and the communication cost is the one of FieldDeterminant, that is, Opnq.

3.2.4

Protocols based on matrix multiplication

Finally, we propose verification protocols related to matrix multiplication. While they are once again based on evaluation techniques, unlike the above protocols the ones given in this section are non-interactive and thus have no Prover or communication cost. We first consider linear system solving; recall that when working over Frxs, given a nonsingular matrix A and a vector b, this problem consists in finding a solution vector v over Frxs together with a nonzero polynomial δ P Frxs such that δ ´1v " A ´1b (see for example [START_REF] Gupta | Triangular x-basis decompositions and derandomization of linear algebra algorithms over Krxs[END_REF]. Theorem 3.2.7. Let d be an upper bound on the degree of A, v, b, and δ. Then, Protocol 3.7 is a complete and probabilistically sound non-interactive protocol which has Verifier cost Opmndq. The probability that the Verifier incorrectly accepts is at most 2d{#S.

Proof. If Av " δb, then the same holds when evaluating at α, hence the completeness of this protocol.

Protocol 3.7: SystemSolve

Public: A P Frxs mˆn , b P Frxs mˆ1 , v P Frxs nˆ1 , δ P Frxs Certifies: degpδq ď minpm, nq degpAq and Av " δb Prover Verifier

1. α $ Ð Ý S Apαqvpαq ? " δpαqbpαq
Otherwise, we have Av ´δb " ∆ for some nonzero vector ∆ P Frxs mˆ1 , and the Verifier incorrectly accepts if and only if the Verifier picked an α such that ∆pαq " 0. Using lemma 3.1.2 with the vector ∆ of rank 1 and degree at most 2d, it follows that the Verifier picked such an α with probability at most 2d{#S.

The dominating step in the Verifier's work is evaluating A at α, which costs Opmndq operations in F.

Remark that when solving linear systems over Frxs one is often interested in the case of a nonsingular matrix A with m " n. In this context, one usually seeks a solution pv, δq with δ of minimal degree (see (Storjohann, 2003, Section 9) and [START_REF] Gupta | Triangular x-basis decompositions and derandomization of linear algebra algorithms over Krxs[END_REF], Section 7)); this implies degpδq ď degpdetpAqq ď n degpAq and degpvq " degpδA ´1bq ď pn ´1q degpAq `degpbq. In this particular case, these bounds could be checked by the Verifier at the beginning of the protocol; the probability that the Verifier incorrectly accepts becomes pnd A `db q{#S; and the Verifier's work costs Opn 2 d A `nd b q operations.

Similarly, we propose a protocol verifying matrix multiplication following an approach attributed to Freivalds (1979).

is a complete and probabilistically sound non-interactive protocol which has Verifier cost

Opmnd A `n d B `m d C q. The probability that the Verifier incorrectly accepts is at most pd A `dB `1q{#S.

Proof. Let D be the actual product D " AB, and let ∆ " D ´C. Note that the final check of the Verifier is equivalent to ∆pαqv ? " 0. If C " D, then ∆ " 0 and whichever evaluation point α the Verifier picked, we have ∆pαq " 0. The degree bound checked initially by the Verifier is also valid whenever AB " C, hence this protocol is complete.

Otherwise, ∆ is a nonzero matrix with degree at most d A `dB . There are two events that would lead to the Verifier accepting incorrectly. First, if the Verifier picked an evaluation point such that ∆pαq " 0, which happens with probability at most pd A `dB q{#S by lemma 3.1.2 (with rank lower bound 1), then whichever verification vector v is picked afterwards, the Verifier will always accept. Otherwise, the Verifier picked an evaluation point for which ∆pαq ‰ 0 but they picked a unlucky verification vector v, that is, v is in the right kernel of ∆pαq, which happens with probability at most 1{#S according to lemma 3.1.1. The union bound gives the stated bound for the probability that the Verifier incorrectly accepts.

The cost for the Verifier comes from evaluating all three matrices at α and then performing three matrix-vector products over F.

Verifying a matrix inverse is a straightforward application of the previous protocol. Corollary 3.2.9. For A P Frxs nˆn and B P Frxs nˆn , there exists a non-interactive protocol which certifies that B is the inverse of A in Verifier cost Opn 2 dq, where d " maxp1, degpAq, degpBqq. If B ‰ A ´1, the probability that the Verifier incorrectly accepts is at most p2d `1q{#S.

3.3

Row space membership

In this section we present the main tool for verification problems that are essentially about Frxs-modules, which is to determine whether a given row vector v P Frxs 1ˆn is in the Frxs-row space of a given matrix A P Frxs mˆn .

The approach has two steps. First, FullRankRowSpaceMembership shows how to solve the problem in case A has full row rank. Then, in RowSpaceMembership, we extend this to the general setting by designing a reduction to several calls to the full row rank case.

3.3.1

Full row rank case

For this case, we propose Protocol 3.9. Before studying its properties, we emphasize that its soundness crucially depends on the fact that A has full row rank. To see why, let A " rx ´xs and v " r1s, and write c " rc 1 c 2 s for the random vector chosen Protocol 3.9: FullRankRowSpaceMembership Public: A P Frxs mˆn , v P Frxs 1ˆn Certifies: v P RowSp Frxs pAq and rankpAq " m Prover Verifier

1. RankLowerBound(A, m) 2. Is convinced that rankpAq ? ě m 3. c $ Ð Ý S mˆ1 c Ð ÝÝÝÝÝÝÝÝ Ý 4. u P Frxs 1ˆm s.t. uA " v g Ð uc g Ý ÝÝÝÝÝÝÝÝ Ñ 5. degpgq ? ď m degpAq `degpvq α $ Ð Ý S α Ð ÝÝÝÝÝÝÝÝ Ý 6. w Ð upαq P F 1ˆm w Ý ÝÝÝÝÝÝÝÝ Ñ

wApαq

? " vpαq wc ? " gpαq by the Verifier. Here, A does not have full row rank and v is not in the row space of A; it is however in the rational row space of A. This allows a dishonest Prover to make the Verifier accept by means of forging a rational vector u such that uA " v and uc P Frxs: the Verifier cannot detect that u was not over Frxs, since they only receive uc and an evaluation of u. Indeed, any vector of the form u " rx ´1 `f pxq f pxqs for some f P Fpxq is such that uA " v. In the likely event that c 1 `c2 ‰ 0, the Prover can choose any polynomial g P Frxs and define f " pc 1 `c2 q ´1pg ´c1 x ´1q; then uc " g is a polynomial.

Remark that if A has full row rank and v belongs to the rational row space of A, then we have uniqueness of the (rational) vector u such that uA " v and thus there is no flexibility for the Prover on the choice of u. In this case, the following lemma plays a key role in the soundness of Protocol 3.9. Lemma 3.3.1. Let u P Fpxq 1ˆn be a rational fraction vector with denompuq ‰ 1 and let S Ď F be a finite subset. For a vector of scalars c P S nˆ1 chosen uniformly at random, the probability that the inner product uc is a polynomial, i.e., that denompucq " 1, is at most 1{#S.

Proof. Write f " denompuq and û " numerpuq. By the condition of the lemma we know that degpf q ě 1. We see that the inner product of u and c is a polynomial if and only if the inner product of û and c is divisible by f . Now let h be any irreducible factor of f , and consider the inner product ûc with û seen as a vector over the extension field Frxs{xhy. Because h | denompuq, we know that û mod h is not zero; otherwise the degree of the denominator f is not minimal. Then, since S Ď F Ď Frxs{xhy, the stated bound follows from lemma 3.1.1.

Another ingredient for our full row rank space membership protocol is a subroutine the Prover may use to actually compute the solution u to the linear system, shown in algorithm 1. More precisely, this algorithm computes the numerator û and the corresponding minimal denominator f . This algorithm will also be used in the protocol for arbitrary-rank matrices presented in the next section.

As above, to simplify the cost bounds we write d A " maxp1, degpAqq and d v " maxp1, degpvqq.

Lemma 3.3.2. Algorithm 1 uses r

Opm ω´1 nd A `mω´1 d v q operations in F. If A has rank less than m, then LOW_RANK is returned. If A has rank m and v R RowSp Fpxq pAq, then NO_SOLUTION is returned. Otherwise, the algorithm returns p û, f q such that ûA " f v and f has minimal degree; in particular, degpf q ď m degpAq and degp ûq ď pm 1q degpAq `degpvq.

Proof. (Zhou, 2012, Chapter 11) presents a deterministic algorithm to compute the column rank profile on line 1 using r Opm ω´1 nd A q field operations. This guarantees that LOW_RANK is returned whenever A does not have full row rank. Now assume that rankpAq " m. Then B is nonsingular, and [START_REF] Gupta | Triangular x-basis decompositions and derandomization of linear algebra algorithms over Krxs[END_REF] showed how to solve the linear system on line 5 deterministically using r

Opm ω d A `

Algorithm 1: Linear system solving with full row rank Input: A P Frxs mˆn , v P Frxs 1ˆn Output: Either LOW_RANK, or NO_SOLUTION, or p û, f q P pFrxs 1ˆm ˆFrxsq such that ûA " f v and f has minimal degree 1 r, i 1 , . . . , i r Ð column rank profile of A 2 if r ă m then return LOW_RANK // below, r " m 3 B P Frxs rˆr Ð columns i 1 , . . . , i r from A 4 y P Frxs 1ˆr Ð columns i 1 , . . . , i r from v 5 Compute p û, f q P pFrxs 1ˆm ˆFrxsq such that f ´1 û " yB ´1 and f has minimal degree, using [START_REF] Gupta | Triangular x-basis decompositions and derandomization of linear algebra algorithms over Krxs[END_REF], Algorithm RationalSystemSolve) 6 if ûA ‰ f v then return NO_SOLUTION 7 return û m ω´1 d v q operations; precisely, this cost bound is obtained from the results in [START_REF] Gupta | Triangular x-basis decompositions and derandomization of linear algebra algorithms over Krxs[END_REF], Section 7) applied with d " maxpd A , md v q. The degree bounds on û and f follow from Cramer's rule. Let p û, f q be the system solution computed on line 5. If v R RowSp Fpxq pAq, then we must have ûA ‰ f v and thus NO_SOLUTION is returned. Now assume that v P RowSp Fpxq pAq, that is, there exists w P Fpxq 1ˆm such that wA " v. Then we have in particular wB " y. But because B is nonsingular, we have w " yB ´1 " f ´1 û; hence ûA " f v.

Finally, we present the main result of this subsection. Theorem 3.3.3. Protocol 3.9 is a complete and probabilistically sound interactive protocol which requires Opmd A `dv q communication and has Verifier cost Opmnd A `nd v q. If rankpAq " m and v P RowSp Frxs pAq, there is an algorithm for the Prover with cost r Opnm ω´1 d A `mω´1 d v q. Otherwise, the probability that the Verifier incorrectly accepts is at most p3md A `dv `1q{#S.

Proof. If rankpAq ă m, then from theorem 3.2.3, the probability that the Verifier incorrectly accepts is at most 1{#S, less than the stated bound in the theorem. And if v is the zero vector, then the protocol easily succeeds when the Prover sends all zeros for g and w; remark that u " 0 is the only solution to uA " v when A has full row rank. So for the remainder of the proof, assume that v is nonzero and A has full row rank m.

The rank check entails 2m `1 field elements of communication, and the degree check by the Verifier assures that g contains at most md A `dv `1 field elements, bringing the total communication in the protocol to at most mpd A `4q `dv `3 field elements.

The work of the Verifier is dominated by computing the evaluations Apαq and vpαq on the last step. Using Horner's method the total cost for these is Opmnd A `nd v q, as claimed.

We now divide the proof into three cases, depending on whether v is in the polynomial row space of A (as checked by the protocol), the rational row space of A, or neither.

Case 1: v P RowSp Frxs pAq Here we want to prove that an honest Prover and Verifier succeed with costs as stated in the theorem.

The vector u as defined in Step 4 must exist by the definition of RowSp Frxs , and computing u can be completed by the Verifier according to lemma 3.3.2 in the stated cost bound.

If the computations of u and g at Step 4 and of w at Step 6 are performed correctly by the Prover, then the Verifier's checks on Step 7 will succeed for any choice of α. Note also that in this case, degpgq " degpucq ď degpuq, and degpuq ď m degpAq `degpvq holds (see lemma 3.3.2), hence the degree check at Step 5.

This proves the completeness of the protocol.

Case 2: v P RowSp Fpxq pAqz RowSp Frxs pAq In this case, the assertion being verified is false, and we want to show probabilistic soundness. Let c P F mˆ1 be the random vector chosen by the Verifier on Step 3. Since A has full row rank, there is a unique rational solution u P Fpxq 1ˆm such that uA " v, and by the assumption of this case we have denompuq ‰ 1; besides, lemma 3.3.2 ensures degpdenompuqq ď md A and degpnumerpuqq ď pm ´1qd A `dv . Then, lemma 3.3.1 tells us that the probability that uc is a polynomial is at most 1{#S. Let g be the polynomial sent by the Prover at Step 4. If uc is not a polynomial, then uc´g is a nonzero rational fraction with numerator degree at most maxpdegpnumerpuqq, degpgq `degpdenompuqqq ď 2md A `dv .

(3.3.1)

From lemma 3.1.2, the probability that Apαq does not have full row rank is at most md A {#S. Otherwise, the vector w " upαq is the unique solution to wApαq " vpαq, so the Prover is obliged to send this w on Step 6.

Then, if the Verifier incorrectly accepts, we must have wc " gpαq, which means upαqc " gpαq, or in other words, α is a root of uc ´g. The degree bound in eq. (3.3.1) gives an upper bound on the number of such roots α P F.

Therefore the Verifier accepts only when either uc P Frxs, or Apαq is singular, or α is a root of uc´g, which by the union bound has probability at most p3md A `dv `1q{#S, as stated.

Case 3: v R RowSp Fpxq pAq Again, the assertion being verified is false, and our goal is to prove probabilistic soundness. As with the last case, assume by way of contradiction that the Verifier accepts.

Consider the augmented matrix

à " " A v  P Frxs pm`1qˆn .
By the assumption of this case, rankp Ãq " rankpAq `1 " m `1. But the vector w provided at Step 7 is such that wApαq " vpαq: it corresponds to a nonzero vector r´w 1s in the left kernel of Ãpαq, which therefore has rank at most m. Since all pm `1q ˆpm `1q minors of à have degree at most md A `dv , the proof of lemma 3.1.2 shows that the probability that rankp Ãpαqq ď m is at most pmd A dv q{#S.

3.3.2

Arbitrary rank case

Now we move to the general case of a matrix A with arbitrary rank r.

The idea behind our protocol is inspired by [START_REF] Mulders | Certified dense linear system solving[END_REF]. We make use of the full row rank case by considering a matrix C P Frxs rˆm such that CA has full row rank. Thus CA has the same rational row space as A, and if v P RowSp Frxs pAq, then there is a unique rational vector w P Fpxq 1ˆr such that wCA " v. In particular, for f " denompwq we have f v P RowSp Frxs pAq, and therefore if f " 1 the verification is already complete.

Although it might be that w has a nontrivial denominator f , this approach can still be used for verification by considering several such matrices C 1 , . . . , C t and rational vectors w 1 , . . . , w t with denominators f 1 , . . . , f t . Indeed, we will see that these matrices can be chosen such that the greatest common divisor of f 1 , . . . , f t is 1; as we show in the next lemma, this implies v P RowSp Frxs pAq. Lemma 3.3.4. Let A P Frxs mˆn and v P Frxs 1ˆn . Let f 1 , . . . , f t P Frxs be such that f i v P RowSp Frxs pAq for 1 ď i ď t. If gcdpf 1 , . . . , f t q " 1, then v P RowSp Frxs pAq.

Proof. The gcd assumption implies that there exist u 1 , . . . , u t P Frxs such that u 1 f 1 ùt f t " 1. It directly follows that v " u 1 pf 1 vq`¨¨¨`u t pf t vq belongs to RowSp Frxs pAq.

Before giving the full protocol for row membership, we first present a subprotocol CoPrime to confirm that the greatest common divisor of a set of polynomials is 1. Lemma 3.3.5. Let d " max i degpf i q, and suppose #S ě 2d. Then Protocol 3.10 is a complete and probabilistically sound interactive protocol which requires Opd `tq communication and has Verifier cost Opdtq. If gcdpf 1 , . . . , f t q " 1, then there is a Las Vegas randomized algorithm for the Prover with expected cost bound r Opdtq. Otherwise, the probability that the Verifier incorrectly accepts is at most p2d ´1q{#S.

Proof. The communication and Verifier costs are clear.

Write g " gcdpf 1 , . . . , f t q, and suppose first that g ‰ 1. Since g divides f 1 s 1 hs 2 , the polynomial f 1 s 1 `hs 2 ´1 is nonzero and has degree at most 2d ´1. If the Verifier incorrectly accepts, then α must be a root of this polynomial, which justifies the probability claim.

If g " 1, then a well-known argument (von zur Gathen and Gerhard, 2013, Theorem 6.46) says that, for β 3 , . . . , β t chosen randomly from a subset S Ď F, the probability that Protocol 3.10: CoPrime Public: t ě 2 polynomials f 1 , . . . , f t P Frxs Certifies: gcdpf 1 , . . . , f t q " 1 Prover Verifier 1.

Compute polynomials s 1 , s 2 P Frxs and scalars β 3 , . . . , β t P F s.t. f 1 s 1 `hs 2 " 1, degps 1 q ă degphq, and degps 2 q ă degpf 1 q, where h "

f 2 `řt i"3 β i f i s 1 , s 2 , β 3 , . . . , β t Ý ÝÝÝÝÝÝÝÝÝÝÝ Ñ 2. degps 1 q ? ă max iě2 degpf i q degps 2 q ? ă degpf 1 q α $ Ð Ý S h α Ð f 2 pαq `řt i"3 β i f i pαq f 1 pαqs 1 pαq `hα s 2 pαq ? " 1 gcdpf 1 , hq ‰ gcdpf 1 , . . . , f t q is at most d{#S.
Based on the assumption that #S ě 2d, the Prover can find such a tuple β 3 , . . . , β t after expected Op1q iterations. Then computing the Bézout coefficients s 1 , s 2 is done via the fast extended Euclidean algorithm on f 1 and h, which costs r Opdtq.

Protocol 3.11 shows an interactive protocol verifying row space membership. For free (and as a necessary aspect of the protocol), the rank ρ is also verified.

The Prover first selects t matrices C i P F rˆm such that C i A has full row rank r " rankpAq and the corresponding denominators f i of the rational solutions to wC i A " v have no common factor.

The Verifier then confirms that the gcd of all denominators is 1 using CoPrime. Using FullRankRowSpaceMembership, the Verifier also confirms that each C i A has full rank and each f i v is in the row space of C i A and therefore in the row space of A as well; by lemma 3.3.4 this ensures that v is itself in the row space of A.

To save communication costs, the matrices C i have a certain structure: Definition 3.3.6. A matrix C P F mˆn is a sub-Toeplitz matrix if m ď n and C consists of m rows selected out of a full n ˆn Toeplitz matrix.

Note that we can always write such a matrix C as a sub-permutation matrix S P t0, 1u mˆn times the full Toeplitz matrix T P F nˆn , i.e., C " ST1 . The benefit for us is in the communication savings:

Lemma 3.3.7. An m ˆn sub-Toeplitz matrix C can be sent with Opnq communication.

Proof. Writing C " ST as above, simply send the 2n ´1 entries of the full Toeplitz matrix T and the m row indices selected by S.

The number t of sub-Toeplitz matrices sent must be large enough, according to the field size, so that the Prover can actually find them with the required properties (see algorithm 2 below). This value t is computed by the Verifier and Prover independently as shown in Step 3, where we use the slight abuse of notation that, when F is infinite, log #F α " 0 for any positive finite value α.

We now proceed to show how the Prover can actually find the values required on Step 4. We write r " rankpAq; if the Prover is honest, then in fact r " ρ. The next lemma is inspired from [START_REF] Mulders | Certified dense linear system solving[END_REF]). Lemma 3.3.8. Let A P Frxs mˆn with rank r; v P RowSp Frxs pAq; S P t0, 1u rˆm be a selection of r out of m rows; p P Frxs be an irreducible polynomial; and T P F mˆm be a Toeplitz matrix with entries chosen independently and uniformly at random from a finite subset S of F. Then either ST A always has rank strictly below r, or for any rational solution w P Fpxq 1ˆr to wST A " v, the probability that rankpST Aq ă r or that p divides denompwq is at most r{#S.

Proof. Let T be a generic m ˆm Toeplitz matrix, defined by 2m ´1 indeterminates z 1 , . . . , z 2m´1 . Because I m is an evaluation of T , then clearly rankp T Aq " rankpAq " r, and furthermore rankpS T Aq " r if and only if S selects r linearly independent rows from T A.

So for the remainder assume that rankpS T Aq is nonsingular over pFrxsqrz 1 , . . . , z 2m´1 s; otherwise rankpST Aq ă r for any choice of T , and we are done.

The structure of the proof is as follows. We first show the existence of a unimodularcompletable matrix U P Frxs nˆr such that ST A and ST U are closely related: in particular, they both have full rank r if and only if the latter has non-zero determinant, and p divides w only when this determinant is divisible by p. The proof proceeds to demonstrate these properties, as well as the fact that S T U has nonzero determinant generically, and therefore with high probability for a random choice of T .

Let P P t0, 1u nˆr be a sub-permutation matrix which selects r linearly independent columns from S T A. Then rankpAP q " r and we consider a factorization AP " U B, where • B P Frxs rˆr is a row basis of AP (and therefore B is nonsingular); and

• U P Frxs mˆr can be completed to a square unimodular matrix, meaning there exists some matrix V P Frxs mˆpm´rq such that detprU | V sq P Fzt0u. From this factorization and the fact that B is nonsingular, we know that rankpAP q " rankpS T AP q " rankpS T U Bq " rankpS T U q " r over the ring pFrxsqrz 1 , . . . , z 2m´1 s. Now because rU | V s is unimodular, it is always nonsingular over the extension field Frxs{xpy, and therefore rankpU q " r over Frxs{xpy. Since the entries of S T do not contain x and from the rank condition above, this means that S T U is nonsingular over pFrxs{xpyqrz 1 , . . . , z 2m´1 s for any choice of the polynomial p.

The determinant detpS T U q is therefore a nonzero polynomial in z 1 , . . . , z 2m´1 over Frxs{xpy with total degree at most r. Then, by the DeMillo-Lipton-Schwartz-Zippel lemma, the probability that detpST U q mod p " 0 is at most r{#S.

Connecting this back to A, if p detpST U q, then we have r " rankpST U q " rankpST U Bq " rankpST AP q ď rankpST Aq ď r, and hence ST A has full row rank r.

Finally, we show that denompwq divides detpST U q; this implies p denompwq. Recall that B is nonsingular with the same Frxs-row space as AP ; then, because v P RowSp Frxs pAq, we have vP P RowSp Frxs pBq, so there exists y P Frxs 1ˆr such that yB " vP . In addition, since ST U is nonsingular, there exists an adjugate matrix D P Frxs rˆr such that detpST U qpST U q ´1 " D. Putting these facts together, we have wST A " v wST AP " vP wST U B " yB wST U " y w detpST U q " yD.

Because the right-hand side of the last equation has entries in Frxs, then so does the left-land side, which means that detpST U q is a multiple of denompwq. Hence denompwq is divisible by p only if detpST U q is divisible by p, which we already established occurs with probability at most r{#S.

Repeatedly applying the previous lemma, involving calls to the rational linear solver of algorithm 1, leads to a Las Vegas randomized algorithm for an honest Prover.

Here we require the Prover to know a finite subset S Ď F. Because this set is never communicated nor part of the public information, it is not necessarily the same as any subset S used by the Verifier in other protocols. In order to match with Protocol 3.11, the Prover should choose S " F if F is finite, and otherwise #S ě 2r 2 degpAq.

If the rank conditions being verified on Steps 1 and 7 are true, then all matrices C i A have full row rank equal to the rank of A, that is, rankpC i Aq " ρ " r. And if the statements verified on Steps 6 and 7 are true as well, then we have v P RowSp Frxs pAq according to lemma 3.3.4. Therefore the soundness of this protocol depends only on the probabilistic soundness of those subprotocols.

For the remainder of the proof, we assume that v R RowSp Frxs pAq and we want to know an upper bound on the probability that the Verifier incorrectly accepts. For this, we divide into cases depending on which subprotocol incorrectly accepted:

Case 1: rankpAq ą ρ According to theorem 3.2.4, the probability that the Verifier incorrectly accepts in RankUpperBound on Step 1 is at most prd A `1q{#S.

Case 2: rankpAq ď ρ and gcdpf 1 , . . . , f t q ‰ 1 We know that each degpf i q ď rd A , where r is the true rank of A. By lemma 3.3.5, the probability that the Verifier incorrectly accepts in subprotocol CoPrime is at most p2 max i pdegpf i qq ´1q{#S, which is at most p2rd A ´1q{#S.

Case 3: rankpAq ď ρ and gcdpf 1 , . . . , f t q " 1 Then, by lemma 3.3.4, there exists i P t1, . . . , tu such that f i v R RowSp Frxs pAq, and thus either rankpC i Aq ă ρ or f i v R RowSp Frxs pC i Aq. That is, the statement being verified by FullRankRowSpaceMembership on the ith iteration of Step 7 is false.

Because of the degree checks on Step 5, we know that degpf i vq ď rd A `dv . Therefore from theorem 3.3.3, the probability that the Verifier incorrectly accepts in Full-RankRowSpaceMembership is at most p4rd A `dv `1q{#S.

Observe that the three cases are disjoint and cover all possibilities. In every case, the probability that the Verifier incorrectly accepts is at most that in Case 3, which proves the last claim in the Theorem statement.

We note that it is always possible to conduct the checks on Step 7 of RowSpaceMembership in parallel, so that the total number of rounds of communication in the protocol is Op1q.

A crucial factor in the communication and Verifier costs as seen in theorem 3.3.10 is the value of t, which in any case satisfies t P Oplogpminpm, nqqq due to the condition on the size of S, so this adds only a logarithmic factor to the cost. Indeed, when the set S of field elements is large enough, t can be as small as 2. For clarity, we state as a corollary a condition under which this logarithmic factor can be eliminated.

3.4

Row spaces and normal forms

In this section, we use the row space membership protocol from the previous section in order to certify the equality of the row spaces of two matrices. Along with additional non-interactive checks by the Verifier, this can also be applied to prove the correctness of certain important normal forms of polynomial matrices.

3.4.1

Row space subset and row basis

We will use RowSpaceMembership to give a protocol for the certification of row space subset; by this we mean the problem of deciding whether the row space of A is contained in the row space of B, for two given matrices A and B.

Our approach is the following: take a random vector λ and certify that the row space element λA is in the row space of B, the latter being done via row space membership (section 3.3). We will see that taking λ with entries in the base field is enough to ensure good probability of success. Lemma 3.4.1. Let A P Frxs mˆn and B P Frxs ˆn. Let R P tFrxs, Fpxqu. Then the following statement holds: Assuming that

RowSp R pAq Ę RowSp R pBq, then the F-vector space V " λ P F 1ˆm | λA P RowSp R pBq (
has dimension at most m ´1. For λ P F 1ˆm with entries chosen independently and uniformly at random from a finite subset S Ď F then λA P RowSp R pBq with probability at most 1 #S . Proof. Suppose that the vector space V has dimension at least m. Then V is the entire space F 1ˆm , and every row of A is in RowSp R pBq; hence RowSp R pAq Ď RowSp R pBq, a contradiction. Then the probability that the uniformly random vector λ belongs to the proper subspace V Ĺ F 1ˆm follows from lemma 3.1.1.

In the following, let r A and r B denote respectively the ranks of A and B, and let d A " maxp1, degpAqq and d B " maxp1, degpBqq. Theorem 3.4.2. Protocol 3.12 is a probabilistically sound interactive protocol, and is complete assuming #S ě 2 d B in its subprotocols. It requires Opn `p d B `dA q logp qq communication and has Verifier cost Opp nd B `nd A q logp q `mnd A q.

If RowSp Frxs pAq Ď RowSp Frxs pBq, there is a Las Vegas randomized algorithm for the Prover with expected cost

r O ` nr ω´2 B d B `rω´1 B d A `mnd A ˘.

Protocol 3.12: RowSpaceSubset

Public: A P Frxs mˆn , B P Frxs ˆn, ρ P N Certifies: RowSp Frxs pAq Ď RowSp Frxs pBq and rankpBq " ρ Prover Verifier

1. λ $ Ð Ý S 1ˆm 2. v Ð λA v Ð ÝÝÝÝÝÝÝÝ Ý 3. RowSpaceMembership(B, v)
Otherwise, the probability that the Verifier incorrectly accepts is at most

4r B d B `dA `2 #S .
Proof. If RowSp Frxs pAq " RowSp Frxs pBq, there is a Las Vegas randomized algorithm for the Prover with expected cost r Oppm ` qnr ω´2 dq. Otherwise, the probability that the Verifier incorrectly accepts is at most p4rd `d `2q{#S.

From RowSpaceEquality, we deduce a protocol verifying the property that B is a row basis of A, that is, a matrix which has the same row space as A and which has full row rank. If B is a row basis of RowSp Frxs pAq, there is a Las Vegas randomized algorithm for the Prover with expected cost r Opmn ω´2 dq, with " r A in this case. Otherwise, the probability that the Verifier incorrectly accepts is at most p4rd `d `3q{#S.

3.4.2

Normal forms

Here, we give protocols for certifying normal forms of polynomial matrices, including the Hermite form [START_REF] Hermite | Sur l'introduction des variables continues dans la théorie des nombres[END_REF][START_REF] Colton | The Theory of Matrices[END_REF] and the Popov form [START_REF] Vasile | Invariant description of linear, time-invariant controllable systems[END_REF][START_REF] Kailath | Linear Systems[END_REF]. These forms are specific row bases with useful properties such as being triangular for the former or having minimal degrees for the latter, and being unique in the sense that a given matrix in Frxs mˆn has exactly one row basis in Hermite (resp. Popov) form.

Roughly speaking, the Hermite form is a row echelon form that stays within the underlying ring. Definition 3.4.5. A matrix B " rb i,j s P Frxs rˆn with r ď n is in Hermite form if there are pivot indices 1 ď k 1 ă ¨¨¨ă k r ď n such that: (i) (Pivots are monic, hence nonzero) b i,k i is monic for all 1 ď i ď r, (ii) (Entries right of pivots are zero) b i,j " 0 for all i ď i ď r and k i ă j ď n, (iii) (Entries below pivots have smaller degree)

degpb i 1 ,k i q ă degpb i,k i q for all 1 ď i ă i 1 ď r.
Each entry at row i and column k i is called a pivot. Observe that these conditions guarantee B has full row rank, hence the use of the notation r for the row dimension. For a matrix A P Frxs mˆn , its Hermite form B P Frxs rˆn is the unique row basis of A which is in Hermite form.

Protocol HermiteForm certifies that a matrix B P Frxs ˆn is the Hermite form of A. It first checks that B is in Hermite form, and then it checks that B and A have the same row space using RowSpaceEquality from section 3. Check that B satisfies definition 3.4.5

2.

RowSpaceEquality(A, B) Theorem 3.4.6. Let r " maxpr A , r B q and d " maxpd A , d B q. Protocol 3.15 is a probabilistically sound interactive protocol and is complete assuming #S ě 2 maxpmd A , d B q in its subprotocol. It requires Opmd logpmq `nq communication and has Verifier cost Opmnd logpmqq. If B is the Hermite form of A, there is a Las Vegas randomized algorithm for the Prover with expected cost r Opmnr ω´2 dq. Otherwise, the probability that the Verifier incorrectly accepts is at most p4rd `d `2q{#S.

Proof. To check that B is in Hermite form at Step 1, the Verifier first computes the pivot indices as the index of the first nonzero on each row, then checks the degree conditions specified in definition 3.4.5. (If any row is zero, B is not in Hermite form.) This is a deterministic check with complexity only Op nq.

As discussed previously, the fact that B is in Hermite form immediately implies that it has full row rank , and hence checking the row space equality is sufficient to confirm that B is a row basis for A.

The subprotocol RowSpaceEquality dominates the complexity and is also the only possibility for the Verifier to incorrectly accept when the statement is false; hence the stated costs follow directly from theorem 3.4.3.

While the Hermite form has an echelon shape, it is also common in polynomial matrix computations to resort to the Popov form, for which the pivot of a row is no longer the rightmost nonzero entry but rather the rightmost entry whose degree is maximal among the entries of that row. This form loses the echelon shape, but has the advantage of having smaller-degree entries than the Hermite form.

Here we consider the more general shifted forms [START_REF] Van Barel | A general module theoretic framework for vector M-Padé and matrix rational interpolation[END_REF][START_REF] Beckermann | Normal forms for general polynomial matrices[END_REF], which encompass Hermite forms and Popov forms via the use of the following degree measure. For a given tuple s " ps 1 , . . . , s n q P Z n , the s-degree of the row vector v " rv 1 ¨¨¨v n s P Frxs 1ˆn is deg s pvq " maxpdegpv 1 q `s1 , . . . , degpv n q `sn q.

We use the notation B i,˚t o denote the ith row of the matrix B. Definition 3.4.7. Let s " ps 1 , . . . , s n q P Z n . A matrix B " rb i,j s P Frxs rˆn with r ď n is in s-Popov form if there are indices 1 ď k 1 ă ¨¨¨ă k r ď n such that, (i) (Pivots are monic and determine the row degree) b i,k i is monic and degpb i,k i q `sk i " deg s pB i,˚q for all 1 ď i ď r, (ii) (Entries right of pivots do not reach the row degree) degpb i,j q `sj ă deg s pB i,˚q for all 1 ď i ď r and k i ă j ď n, (iii) (Entries above and below pivots have lower degree)

degpb i 1 ,k i q ă degpb i,k i q 1 ď i 1 ‰ i ď r.
The usual Popov form corresponds to the uniform shift s " p0, . . . , 0q. Furthermore, one can verify that, specifying the shift as s " pnt, . . . , 2t, tq for any given t ą degpBq, then the Hermite form is the same as the s-Popov form (Beckermann et al., 2006, Lem. 2.6).

For a matrix A P Frxs mˆn , there exists a unique row basis B P Frxs rˆn of A which is in s-Popov form (Beckermann et al., 2006, Thm. 2.7); B is called the s-Popov form of A. Generalizing Protocol 3.15 to this more general normal form yields Protocol 3.16 (although the former could be derived as a particular case of the latter for a specific shift s, we preferred to write both explicitly for the sake of clarity).

The next result is identical to Theorem 3.4.6, in both statement and proof. The only difference in the protocol is determining the indices of each pivot column in order to confirm the conditions of s-Popov form; this can be accomplished in linear time by first computing the s-degree of the row and then finding the rightmost column which determines this shifted row degree.

Protocol 3.16: ShiftedPopovForm

Public: A P Frxs mˆn , s " ps 1 , . . . , s n q P Z n , B P Frxs ˆn Certifies: B is the s-Popov form of A Prover Verifier

1.

Check that ps, Bq satisfies Definition 3.4.7

2.

RowSpaceEquality(A, B) Theorem 3.4.8. Let r " maxpr A , r B q and d " maxpd A , d B q. Protocol 3.16 is a probabilistically sound interactive protocol and is complete assuming #S ě 2 maxpmd A , d B q in its subprotocol. It requires Opmd logpmq `nq communication and has Verifier cost Opmnd logpmqq. If B is the s-Popov form of A, there is a Las Vegas randomized algorithm for the Prover with expected cost r Opmnr ω´2 dq. Otherwise, the probability that the Verifier incorrectly accepts is at most p4rd `d `2q{#S.

3.5

Saturation and kernel bases

In this section, we use the protocols described in previous sections to design protocols verifying computations related to saturations and kernels of polynomial matrices.

3.5.1

Saturation and saturated matrices

The saturation of a matrix over a principal ideal domain is a useful tool in computations; we refer to (Bourbaki, 1972, Section II. §2.4) for a general definition of saturation. It was exploited for example in [START_REF] Zhou | Computing column bases of polynomial matrices[END_REF] where a matrix is factorized as the product of a column basis times some saturation basis, and in [START_REF] Neiger | Computing Popov and Hermite forms of rectangular polynomial matrices[END_REF] in order to find the location of pivots in the context of the computation of normal forms. The saturation can be computed from the Hermite form, as described in (Pernet and Stein, 2010, Section 8) for integer matrices, and alternatively it can be obtained as a left kernel basis of a right kernel basis of the matrix as we prove below (lemma 3.5.3). Definition 3.5.1. The saturation of a matrix A P Frxs mˆn is the Frxs-module SaturationpAq " Frxs 1ˆn X RowSp Fpxq pAq; it contains RowSp Frxs pAq and has rank r " rankpAq. A saturation basis of A is a matrix in Frxs rˆn whose rows form a basis of the saturation of A. A matrix is said to be saturated if its saturation is equal to its Frxs-row space.

Two matrices with the same saturation may have different Frxs-row spaces. For example, the matrices

» - 1 1 x 2 x 2 `x x x fi fl and " 1 1 `x2 0 x 2
 have the same saturation Frxs 1ˆ2 , but the Frxs-row space of the former matrix contains r0 xs which is not in the Frxs-row space of the latter matrix. We also remark that all nonsingular matrices in Frxs nˆn have saturation equal to Frxs 1ˆn . The saturation is defined in terms of the Fpxq-row space of the matrix: two matrices have the same saturation if and only if they have the same Fpxq-row space. In particular, A is saturated if and only if any row basis of A is saturated. This yields the following characterization for matrices having full column rank. Lemma 3.5.2. Let A P Frxs mˆn have full column rank. Then A is saturated if and only if RowSp Frxs pAq " Frxs 1ˆn .

Proof. Since A has full column rank, its row bases are nonsingular n ˆn matrices, or equivalently, RowSp Fpxq pAq " Fpxq 1ˆn . Hence the saturation of A is Frxs 1ˆn , and the equivalence follows by definition of being saturated. Thus, in this case, verifying that A is saturated boils down to verifying that Frxs 1ˆn is a subset of RowSp Frxs pAq, which can be done using RowSpaceSubset.

To obtain a similar result in the case of matrices with full row rank, we will rely on the following characterization of the saturation using kernel bases. Lemma 3.5.3. Let A P Frxs mˆn have rank r, and let K P Frxs nˆpn´rq be a basis for the right kernel of A. Then, SaturationpAq is the left kernel of K. In particular, the saturation bases of A are precisely the left kernel bases of K.

Proof. Each row of A is in the left kernel of K, hence so is any polynomial vector v P Frxs 1ˆn which is an Fpxq-linear combination of rows of A, that is, any v P SaturationpAq.

For the other direction, it is enough to prove that each row of a given left kernel basis B P Frxs rˆn of K is in SaturationpAq. Let  P Frxs rˆn be a set of r linearly independent rows of A; since these rows are in the left kernel of K, we have  " U B for some nonsingular U P Frxs rˆr . Thus each row of B " U ´1  is an Fpxq-linear combination of rows of A.

Combining this with (Zhou and Labahn, 2013, Lemma 3.3), it follows that for any saturation basis B P Frxs rˆn of A and any factorization A " CB with C P Frxs mˆr , then C is a column basis of A. If A has full row rank we obtain that C is nonsingular, and that A is saturated if and only if C is unimodular, or equivalently ColSp Frxs pAq " Frxs mˆ1 . For the sake of completeness, we now present a concise proof of this characterization (lemma 3.5.5); we will need the following standard result which essentially says that any kernel basis is saturated (see for example (Giorgi and Neiger, 2018, Lemma 2.2) for a proof).

Concerning the certification of a saturation basis of A, our protocol will rely on the following characterization. Lemma 3.5.7. Let A P Frxs mˆn . Then, a matrix B P Frxs ˆn is a saturation basis of A if and only if the following conditions are satisfied: (i) RowSp Fpxq pAq Ď RowSp Fpxq pBq, (ii) rankpBq " and rankpAq ě , (iii) B is saturated.

Proof. If B is a saturation basis of A, then by definition B is saturated; B has full row rank with " rankpBq " rankpAq; and RowSp Fpxq pBq " RowSp Fpxq pAq.

Conversely, assume that the three items hold. The first two items together imply " rankpBq " rankpAq, and hence RowSp Fpxq pAq " RowSp Fpxq pBq. This means SaturationpAq " SaturationpBq, and the latter saturation is equal to RowSp Frxs pBq since B is saturated by the third item. Hence B has full row rank and Frxs-row space equal to the saturation of A.

Protocol 3.18: SaturationBasis

Public: A P Frxs mˆn , B P Frxs ˆn Certifies: B is a saturation basis of A Prover Verifier

Check

? ď minpm, nq 2.

RankLowerBound(A, )

$ Ð Ý S λ $ Ð Ý S 1ˆn v Ð λApαq P F 1ˆn α, v Ð ÝÝÝÝÝÝÝÝ Ý 4. 3. α
Find γ P F 1ˆn such that γBpαq " v. γ Ý ÝÝÝÝÝÝÝÝ Ñ

γBpαq

? " v 6.

Saturated(B) otherwise the probability that the Verifier incorrectly accepts is at most p4 d B `2q{#S.

Proof. The check on Step 1 has no arithmetic cost, but ensures that is less than or equal to m and n. Steps 3 to 5 certify that RowSp Fpxq pAq Ď RowSp Fpxq pBq. Note that this only communicates Opnq field elements, and that the Verifier's cost at these steps amounts to the evaluation of A and B at α as well as two scalar vector-matrix products, hence a total of Opmnd A ` nd B q operations. Then the Verifier and Prover's costs follow from theorems 3.2.3 and 3.5.6. Note that rankpAq ě and RowSp Frxs pAq Ď RowSp Frxs pBq imply that rankpBq " , so that the precondition for the Saturated protocol on Step 6 is valid unless one of the previous checks failed.

For the probability bound, we consider each of the checks in Steps 2, 5 and 6. By theorem 3.2.3, the Verifier incorrectly accepts an A with rank ă with probability at most 1{#S. By theorem 3.5.6, the Verifier incorrectly accepts an unsaturated B with probability at most p4 d B `2q{#S.

For Step 5, assume now that rankpAq ě and B is saturated, and in particular rankpBq " , but that RowSp Fpxq pAq Ć RowSp Fpxq pBq. By lemma 3.4.1, then for a random λ P S 1ˆm we have λA P RowSp Fpxq pBq with probability at most 1 #S . Consider now that λA R RowSp Fpxq pBq. Let P be an n ˆn permutation matrix such that BP " rB 0 | B 1 s with B 0 P Frxs ˆ and full rank. Let u P Fpxq 1ˆ be the unique vector such that λAP " ruB 0 | âs, for some â P Fpxq 1ˆpn´ q . Then there is some index i of â that differs from index i of uB 1 . By Cramer's rule the entries of u can be written with common denominator detpBq and numerators of degree at most p ´1qd B . Hence the entries of uB 1 have denominators and numerators of degree at most d B each. Hence λApαq and upαqBpαq agree at index i for at most 2 d B choices of α P F, and we conclude that the Verifier incorrectly accepts in this case with probability at most

2 d B {#S.
Summing up, the worst case is the check at Step 6, where the Verifier incorrectly accepts with probability at most p4 d B `2q{#S.

3.5.2

Kernel bases and unimodular completability

Here, we derive two protocols which follow from the ones concerning the saturation. The second protocol is for the certification of kernel bases, while the first protocol is about matrices that can be completed into unimodular matrices.

The fast computation of such completions was studied by [START_REF] Zhou | Unimodular completion of polynomial matrices[END_REF]. We say that A P Frxs mˆn is unimodular completable if m ă n and there exists a ma- Proof. The costs follow from theorems 3.2.3 and 3.5.6, noting that the protocol aborts early if m ě n, and therefore m is an upper bound on the rank in the Saturated subprotocol. The probability of the Verifier incorrectly accepting here is the same as in Saturated from theorem 3.5.6.

Finally, Protocol 3.20 for the certification of kernel bases will follow from the characterization in the next lemma. Lemma 3.5.10. Let A P Frxs mˆn and let B P Frxs ˆm. Then, B is a left kernel basis of A if and only if

(i) rankpBq " and rankpAq ě m ´ , (ii) BA " 0, (iii) B is saturated.
Proof. If B is a left kernel basis of A, then we have rankpBq " " m ´rankpAq as well as BA " 0; the third item follows from fact 3.5.4 and lemma 3.5.5. Now assume that the three items hold. Consider some left kernel basis K of A. Then, rankpKq " m ´rankpAq ď by the first item, while the second item implies that the row space of B is contained in the row space of K, hence " rankpBq ď rankpKq; therefore rankpKq " . As a result, B " U K for some nonsingular U P Frxs ˆ . Item piiiq implies ColSp Frxs pBq " Frxs ˆ1 according to lemma 3.5.5, hence I " BV " U KV for some V P Frxs mˆ . Then, U must be unimodular, and thus B " U K is a left kernel basis of A. If B is a left kernel basis of A, then there is a Las Vegas randomized algorithm for the Prover with expected cost

r O `m ω´1 d B `mnpm ´ q ω´2 d A ˘;
otherwise the probability that the Verifier incorrectly accepts is at most

maxpd A `dB `1, 4 d B `2q #S .
Proof. The costs follow from lemma 3.5.10 and theorems 3.2.3, 3.2.8 and 3.5.6. As before, the worst case for the Verifier is that only one of the three checked statements is wrong, and the resulting maximum of probabilities comes either from Step 2 or Step 4.

Conclusion and perspectives

We have developed interactive protocols verifying a variety of problems concerning polynomial matrices. For rank, determinant, system solving, and matrix multiplication (section 3.2), these amount to evaluating at some random point(s) and reducing to field-based verifications. For row bases, saturation, normal forms, and kernel basis computations (sections 3.4 and 3.5), the verifications essentially reduce to testing row space membership of a single vector (section 3.3) and testing that ranks are the expected ones.

Our protocols are efficient. The volume of data exchanged in communications is roughly the size of a single row of the matrix. The time complexity for the Verifier is linear (or nearly-linear) in the size of the object being checked, and the time for the Prover is roughly the same as it would take to perform the computation being verified.

Still, there is some room for improvement in these costs. It would be nice to remove the logarithmic factors in the complexities of most later protocols for the Verifier time and communication cost; these come from the number of repetitions t required in the RowSpaceMembership protocol.

Our protocols also require to work over sufficiently large fields, to ensure soundness of the randomized verification. For smaller fields, a classic workaround is to resort to a field extension, increasing the arithmetic and communication cost by a logarithmic factor. An alternative is to increase the dimension in the challenges and responses, e.g. verifying a block of vectors instead of a single vector of field elements. A further study on whether this approach is applicable and competitive here is required.

Another possibility for improvement in our complexities would be to have the same costs where d is the average matrix-vector degree, rather than the maximum degree. Such complexity refinements have appeared for related computational algorithms, frequently by "partial linearization" of the rows or columns with highest degree (Gupta et al., 2012, Section 6), and it would be interesting to see if similar techniques could work here. This would be especially helpful in more efficiently verifying an unbalanced shifted Popov form, and the Hermite form in particular, of a nonsingular matrix.

The protocols presented here do not assume that the Prover has computed the result to be verified. This is however likely to be the case in many instances of verified computing, and it would then be relevant to identify which intermediate results in a Prover's computation of the solution (such as the rank profile matrix, the weak Popov form, etc), could be reused in a certificate for verifying this solution. Though more constraining on the Prover's choice of an algorithm, such information would help reducing the leading constant in the arithmetic cost of its computation.

While we have presented protocols for a variety of basic problems on polynomial matrices, there are still more for which we do not know yet whether any efficient verification exists. These include:

• high-order terms in expansion of the inverse (see the high-order lifting algorithm of Storjohann ( 2003));

• univariate relations, generalizing Hermite-Padé approximation [START_REF] Beckermann | Fraction-free computation of matrix rational interpolants and matrix gcds[END_REF][START_REF] Neiger | Computing canonical bases of modules of univariate relations[END_REF];

• Smith form (see [START_REF] Storjohann | High-order lifting and integrality certification[END_REF] for the fastest known algorithm).

We also do not know in all cases how to prove the negation of our statements -for example, that a vector is not in the row space of a polynomial matrix. It seems that some similar techniques to those we have used may work, but we have not investigated the question deeply. Perhaps the most interesting direction for future work would be to adapt our protocols to the case of Euclidean lattices, i.e., integer matrices and vectors. It seems that most of our protocols in section 3.2 should translate when we replace evaluation at a point α with reduction modulo a sufficiently-large prime p, but the analysis in terms of bit complexity rather than field operations will likely be more delicate. Another seeming hurdle is in our central protocols in section 3.3 on deciding row membership: while the general ideas of these protocols might translate to integer lattices, the proof techniques we have used are particular for polynomials.

Technical summary and overview of this chapter

Model We consider the product of square N ˆN matrices, further denoted as A and B. Our protocol supports up to N players, and each player knows one row (or one block of consecutive rows) of A, the corresponding row (or block of rows) of B and learns the corresponding row (or block of rows) of C " A ˆB. Our protocol is proven secure against non-colluding, semi-honest adversaries as defined in Section 1.1.3. We require communication between players to be performed over secure channels, meaning that, for any communication between two players, only these two players will know the piece of information that were communicated. The main tool used to secure our protocol is semi-homomorphic cryptography (such as defined in Section 1.2.4) supporting homomorphic additions. We focus on improving the communication volume of multiparty matrix product. Theoretical communication costs given in this chapter are based on the number of field elements exchanged between players, while practical communication costs are a direct measure of the total communication volume in (Giga)Bytes.

State of the art -main competition

We primarily compare our work to the protocol of Dumas et al. (2017a), which is the state of the art for multiparty matrix multiplication with the same data repartition model. Their protocol, called YTP-SS, is based on textbook matrix multiplication and consists of sequential secure multiparty dot products. For input matrices of size N , they achieve a communication cost of OpN 3 q field elements. Their protocol, however, has stronger security than ours, as it supports colluding malicious adversaries. They manage to achieve such security by splitting input elements in k shares for each dot product performed, and repeating each dot product k times. As this security measure requires many exchanges between players, we will propose a relaxed version of YTP-SS, stripped of these additional security measures. This simplified protocol, which we call MP-PDP, has the same security than ours and will thus be a fairer comparison than YTP-SS.

Results

The main contribution of this chapter is a new recursive multiparty matrix multiplication protocol based on Strassen-Winograd algorithm. By taking full advantage of the recursive structure of the algorithm, we manage to achieve a better communication cost than the state of the art, OpN 2.81 q for input matrices of size N . We show that, with this improvement, our protocol has cheaper communication cost than MP-PDP for matrices of size N " 96 and larger. We implemented our solution and practical experiments confirm that our protocol has less communications than MP-PDP. To achieve this result, we designed a data layout which, associated with the new sub-protocols we propose, ensures that no information is leaked during the execution. Furthermore, we also propose a variant of our protocol based on proxy re-encryption techniques that allows us to improve the communication cost of our solution even more. Finally, we compare estimated runtimes of our protocol and a fully homomorphic version of Strassen-Winograd algorithm based on a simplified setting

Introduction

Secure multiparty computations (MPC) allows n players to compute together the output of some function, using private inputs without revealing them. This is useful, e.g., for a distributed evaluation of trust, as defined in [START_REF] Jøsang | Probabilistic logic under uncertainty[END_REF][START_REF] Dumas | Matrix powers algorithms for trust evaluation in public-key infrastructures[END_REF]. In this context, players compute a confidence level by combining their mutual degrees of trust. This aggregation of trust amongst players can be represented as a matrix product C " A ˆB, where each player knows one row of the matrix containing their partial trust towards their neighbours and the network has to compute a distributed matrix exponentiation, which reduces to several matrix multiplications. In this chapter, we thus focus on this particular layout of data, and on multiparty matrix multiplication of dimension N ˆN with N players.

As was described in Section 1.2, several tools exist to design MPC protocols, like Shamir's secret sharing scheme [START_REF] Shamir | How to share a secret[END_REF], homomorphic encryption [START_REF] Goethals | On private scalar product computation for privacy-preserving data mining[END_REF], oblivious transfer [START_REF] Dagdelen | A multi-party protocol for privacy-preserving cooperative linear systems of equations[END_REF] or using a Trusted Third Party [START_REF] Du | A practical approach to solve secure multi-party computation problems[END_REF]. Then, several MPC implementations are available1 . Some of them are for two parties only and most of the others are generic and transform programs into circuits or use oblivious transfer [START_REF] Demmler | ABY -A framework for efficient mixed-protocol secure two-party computation[END_REF][START_REF] Rindal | Faster malicious 2-party secure computation with online/offline dual execution[END_REF][START_REF] Damgård | The tinytable protocol for 2-party secure computation, or: Gate-scrambling revisited[END_REF][START_REF] Jarecki | Efficient covert two-party computation[END_REF]Mishra et al., 2018/663). For instance the symmetric system solving phase of the LINREG-MPC software is reported in [START_REF] Gascón | Privacy-preserving distributed linear regression on high-dimensional data[END_REF] to take about 45 minutes for n " 200, while, in (Dumas et al., 2017a), a secure multiparty specific algorithm, YTP-SS, developed for matrix multiplication, requires about a hundred seconds to perform an n " 200 matrix multiplication. These timings, however, do not take into account communications, but for multiparty matrix multiplication, the number of communications and the number of operations should be within the same order of magnitude. Our goal is thus to improve on existing algorithms, primarily in terms of this number of communications (we do not minimize the number of messages, as in [START_REF] Ishai | On the message complexity of secure multiparty computation[END_REF], but instead consider the overall volume). Our idea is to use an algorithm with a lower time and communication complexity for matrix multiplication. Strassen's algorithm [START_REF] Volker Strassen | Gaussian elimination is not optimal[END_REF] was the first sub-cubic time algorithm, with an exponent log 2 7 « 2.81 leading to a complexity of Opn2.81 q. As Strassen is one of the simplest matrix multiplication algorithm, and one of the only practically efficient ones, we construct an MPC protocol based Winograd's variant of this algorithm which carries the aforementioned complexity over the communication volume. 2 (Aho et al., 1974, Ex.6.5).

We need to preserve input privacy throughout the computation, which can be achieved by the use of homomorphic cryptography. Such ciphers allow to perform arithmetic operations over ciphertexts, which will help to maintain privacy in our setting. There exists two major families of homomorphic cryptosystems, fully-homomorphic and semihomomorphic ones. While the former are usually considered more expensive than the latter, their ability to use all arithmetic operations over ciphertexts make them far less constrained than the others (see Section 1.2.4 for a few more details and references on the topic). Table 4.1 shows a comparison of basic cryptographic (encryption, decryption) and arithmetic (addition, multiplication) operations between semi-homomorphic cryptosystems and two fully homomorphic libraries. Naccache-Stern and Paillier cryptosystems are our own C++ implementations, based on Givaro (Givaro group, 2020), SEAL is the Microsoft SEAL fully homomorphic encryption library (Microsoft Research, 2019) based on Brakerski/Fan-Vercauteren scheme [START_REF] Fan | Somewhat practical fully homomorphic encryption[END_REF][START_REF] Brakerski | Fully homomorphic encryption without modulus switching from classical gapsvp[END_REF] and HElib is the IBM Helib fully homomorphic encryption library (hel, 2019), based on Brakerski-Gentry-Vaikuntanathan scheme [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF]. Timings were measured on a workstation with an Intel i5-7300U @2.60 GHz, 16GB of RAM, with parameters set to have a security level of λ " 130. Accordingly to recommendations given in the libraries documentation, SEAL timings were made for a plaintext space of 20 bits and HElib timings for a plaintext space of 64 bits. While a few fully homomorphic operations are faster (SEAL decryption) or competitive (SEAL encryption vs. Paillier) with semi-homomorphic cryptosystems, the former are still faster in most situations.

We will hence use partial homomorphic encryption scheme [START_REF] Cramer | Secure Multiparty Computation and Secret Sharing[END_REF] as they allow to perform the operations we need, namely:

1. D sk pE pk pm 1 q ˆEpk pm 2 qq " m 1 `m2 (Additive homomorphism) 2. D sk pE pk pm 1 q m 2 q " m 1 ˆm2

(Cipher/clear multiplicative homomorphism) Several cryptosystems do satisfy these, e.g., the ones designed by Naccache-Stern or Paillier [START_REF] Naccache | A new public key cryptosystem based on higher residues[END_REF][START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]. The former is usually costlier than the latter. However, as the former allow parties to agree on a common message block size, which solves the issue of defining a consistent message space among them, we

‰

. Each recursive call consists in 22 block operations: • 8 additions:

S 1 Ð A 21 `A22 S 2 Ð S 1 ´A11 S 3 Ð A 11 ´A21 S 4 Ð A 12 ´S2 T 1 Ð B 12 ´B11 T 2 Ð B 22 ´T1 T 3 Ð B 22 ´B12 T 4 Ð T 2 ´B21
• 7 recursive multiplications:

R 1 Ð A 11 ˆB11 R 2 Ð A 12 ˆB21 R 3 Ð S 4 ˆB22 R 4 Ð A 22 ˆT4 R 5 Ð S 1 ˆT1 R 6 Ð S 2 ˆT2 R 7 Ð S 3 ˆT3
• 7 final additions:

U 1 Ð R 1 `R2 U 2 Ð R 1 `R6 U 3 Ð U 2 `R7 U 4 Ð U 2 `R5 U 5 Ð U 4 `R3 U 6 Ð U 3 ´R4 U 7 Ð U 3 `R5
• The result is the matrix:

C " " U 1 U 5 U 6 U 7 ‰ .
Although the recursion could be run down to products of 1 ˆ1 matrices, it is commonly stopped at a fixed dimension threshold, where a classical cubic time algorithm is then used, in order to reduce the overhead of recursion on small dimension instances. For the sake of simplicity, we consider henceforth that the initial input matrices are of dimension N ˆN , with N " b2 , so that up to recursive calls can be made without having to deal with padding with zeroes nor with peeling thin rows or columns.

4.1.2

Data layout and encryption

We consider the setting where the two input matrices A and B have dimension N ˆN and each of the N players stores one row of A and the corresponding row of B and learns the corresponding row of C " AˆB. In this setting, the YTP-SS Algorithm (Dumas et al., 2017a, Algorithm 15) can compute C by encrypting the rows of A only and then relying on homomorphic multiplications of encrypted coefficients of A by plain coefficients of B.

However, Strassen's algorithm, considered here, requires adding and subtracting submatrices of B of distinct row index sets (e.g. T 3 Ð B 22 ´B12 ). These operations on non-ciphered rows of B would automatically leak information. We therefore impose that the rows of both operands A and B, of the result C and of any intermediate matrix are encrypted by the public key of a player who is not the one hosting the row. We therefore introduce the notion of location and key sequences for a matrix, to identify the roles of the players in this data layout: Definition 4.1.1. An n ˆn matrix A of ciphered values has location sequence L " pl 1 , l 2 , . . . , l n q and key sequence K " pk 1 , k 2 , . . . , k n q if player P l i stores row i of A, that was encrypted with the public key pk k i of player P k i for all 1 ď i ď n.

Example 1. For n " 3, consider the location sequence L " p2, 3, 1q and key sequence K " p3, 1, 2q. This means that player P 2 stores row 1 of A encrypted with the public key of player P 3 ; player P 3 stores row 2 of A encrypted with the public key of player P 1 and finally player P 1 stores row 3 of A encrypted with the public key of player P 2 .

In the matrix multiplication algorithms presented in the later sections, the location and key sequences of operand A and C will always be identical. On the other hand the location and key sequences of B may equal those of A (in the first recursive call), or differ, but then they must have an empty intersection with those of A.

A recursive step in Strassen-Winograd algorithm splits the matrices A, B and C into four quadrants of equal dimensions. Hence their key and location sequences are split into two sub-sequences: for X P tA, B, Cu, L X " pL X U , L X L q and K X " pK X U , K X L q such that pL X U , K X U q are the location and key sequences for the upper half of X and pL X L , K X L q are the location and key sequences for the lower half of X.

Figure 4.1 summarizes the notations we use on the input/output operands in Strassen-Winograd algorithm. More formally, we present in Definition 4.1.2 the two distinct data layouts used in our algorithms: one for the recursive levels of Strassen-Winograd, and one for its base case. Definition 4.1.2. Let N P N, n ď N and A and B two n ˆn matrices with location and key sequences pL A , K A q P pt1..N u n q 2 and pL B , K B q P pt1..N u n q 2 . 1. pL A , K A , L B , K B q is a valid data layout if a) @i P t1..nu, L Aris ‰ K Aris and L Bris ‰ K Bris . b) @i, j P t1..nu with i ‰ j, L Aris ‰ L Arjs and L Bris ‰ L Brjs c) @i, j P t1..nu with i ‰ j, K Aris ‰ K Arjs and K Bris ‰ K Brjs 2. pL A , K A , L B , K B q is a base case or a 0-recursive data layout if it is a valid data layout and pL

A U A L C L C U Key sequences B U B L K A U K A L L A L L A U L B U L B L K B L K B U Location sequences "
A Y K A q X pL B Y K B q " H. 3. pL A , K A , L B , K B q is a -recursive data layout if it is a valid data layout and a) pL A U Y K A U q X pL A L Y K A L q " H " pL B U Y K B U q X pL B L Y K B L q b) pL A U , K A U , L B L , K B L q and pL A L , K A L , L B U , K B U q
" k i " i
for 0 ď i ă N l ib`j " ib `pj `1 mod bq for 0 ď i ă N {b, and 0 ď j ă b (4.1.1)

For instance, for a product of dimension 12, with base case dimension b " 3, this gives; L A " L B " L C " p1, 2, 0, 4, 5, 3, 7, 8, 6, 11, 9, 10q and 3, 4, 5, 6, 7, 8, 9, 10, 11q.

K A " K B " K C " p0, 1, 2,

4.1.3

Homomorphic encryption

Naccache-Stern cryptosystem.

In the following, we use [START_REF] Naccache | A new public key cryptosystem based on higher residues[END_REF] partially homomorphic cryptosystem, with security parameter 1 λ , set up as follows:

Setupp1 λ q : Select 2k small primes p 1 , . . . , p 2k ; compute u " ś k i"1 p i and v " ś 2k i"k`1 p i ; let σ " u¨v; uniformly select two large prime numbers a and b of size λ{2; find f 1 and f 2 such that p " f 1 ¨a¨u `1 and q " f 2 ¨b¨v `1 are primes; let m " p¨q and randomly choose g of order aubv in Z m. The private key is SK " pp 1 , . . . , p 2k , p, qq, the public key is P K " pσ, g, mq.

Encrypt P K pxq : for x P Z σ , randomly choose r P Z m and encrypt x as c " E P K pxq " r σ ¨gx mod m.

Decrypt SK pcq : let φ " pp ´1qpq ´1q, c i " c φ{p i mod m and recover, by exhaustive search (p i is small), x i mod p i such that x i " log g φ{p i pc i q mod m. Finally reconstruct x with the Chinese remaindering, x " CRT ptx i , p i uq mod σ.

For the rest of this chapter, cleartexts will be elements of Z σ while elements are elements of Z m . As σ is shared by all players, the cleartext space is the same for all the players and we will hence denote this common message space by M. However, there is a distinct modulus Z m for each player, otherwise they would have to share their private keys. Consequently, each player has their own ciphertext space, which we will denote by C P . A plain text matrix then has coefficients in M but in a layout where each row is encrypted using a different key pk i , its encryption is no longer a matrix but a sequence of rows over distinct rings Z m rpk i s. We will abusively refer to this ciphered data as the ciphered matrix. Finally, for a key sequence K and a matrix A over M, the ciphered matrix obtained by encrypting row i of A by Kris is denoted by tAu K . Row i of tAu K is over C Kris .

4.1.4

Multiparty protocols security

Here, we recall some widely used notations and results for the security of multiparty protocols. Definition 4.1.4 [START_REF] Goldreich | Foundations of Cryptography[END_REF]). Let f be a n-ary functionality, where f i px 1 , ..., x n q denotes the i th element of f px 1 , ..., x n q. For I " ti 1 , ..., i t u Ă rns " t1, ..., nu, we denote by f I px 1 , ..., x m q the subsequence f i 1 px 1 , ..., x n q, ..., f it px 1 , ..., x n q. We let x I " px i 1 , ..., x it q. Let Π be a n-party protocol for computing f . The view of the i th party during an execution of Π on x " px 1 , ..., x n q is denoted view Π i pxq, and for I, we let view Π I pxq " pI, view Π i 1 pxq, ..., view Π it pxqq. We say that Π securely computes f if there exist a probabilistic polynomial time algorithm, such that, with S a simulator for Π, for every I Ă rns:

tS I ppx I q, f I pxqq, f pxqu x C " tview Π I pxq, output Π pxqu x , where C
" denotes the computational indistinguishability between two ensembles. Definition 4.1.5. Let f 1 , ..., f ppnq be functionalities, and let Π be a protocol. We say that the protocol Π is executed in the f 1 , ..., f ppnq -hybrid mode if Π uses ideal calls to a trusted party to compute f 1 , ..., f ppnq . Theorem 4.1.6 (from [START_REF] Lindell | How to Simulate It -A Tutorial on the Simulation Proof Technique[END_REF]). Let p(n) be a polynomial, let f 1 , ..., f ppnq be functionalities, and let π 1 , ..., π ppnq be protocols such that each π i securely computes f i in the presence of semi-honest adversaries. Let g be a functionality, and let Π be a protocol that securely computes g in the f 1 , ..., f ppnq -hybrid model. Then, the protocol Π π 1 ,...,π ppnq securely computes g in presence of semi-honest adversaries.

We will also need a function, which, given a small input is able to securely and deterministically produce a stream of uniformly generated random values. We will achieve this by using classical mask generation functions, as defined in (Kaliski and Staddon, 1998, Section 10.2): a function which takes two parameters, a seed s and a length l and returns a random string of length l. We will then split the output string in as many fragments as needed, and use each of these fragments as a mask. Such function achieve an output indistinguishable property: if the seed is unknown, it is impossible to distinguish between the output of a mask generation function and a truly random string. Such secure functions exist, see for instance the one given in [START_REF] Kaliski | RSA Cryptography Specifications[END_REF] and in what follows, we will denote by MGF any function that have the aforementioned security properties. Finally, for the rest of this chapter, our functionalities follow the input/output specification described in the protocols they realize.

4.1.5

Relaxing an existing algorithm: YTP-SS

The matrix multiplication algorithm using the secure dot-product protocol YTP-SS (Dumas et al., 2017a, Algorithm 15) is secure against semi-honest adversaries over insecure communication channels. In order to analyse the difference with our proposition, MP-SW, we extract here the core of the former protocol, i.e., without the securization of the channel (that is we remove the protection of the players private elements by random values, and the final communications to derandomize the results). The resulting simplification is called MP-PDP and its costs are given in Theorem 4.1.7. More details can be found in (Dumas et al., 2017a, Algorithm 15) Theorem 4.1.7. For n players, (Dumas et al., 2017a, Algorithm 15), without the channel securization, requires 2pn ´1q communications. When used to compute a classical matrix product, it requires n 3 `npn ´1q operations overall.

4.2

Toolbox

4.2.1

Initialization Phase

Before the actual computation, the involved parties need to agree on the location and key sequences they will use, generate their key pairs, share their associated public keys, cipher their input data and communicate it where needed. Parties know their identifier, which is the index of the row they own, and use Equation ( 4.1.1) to compute the location/key sequences. SW-Setup shows how the input data is initially ciphered and dispatched: each party, identified as P i , i P t1..N u starts with the i-th row of A and B, and, after generating its own key pair, ciphers its row according to the key sequence.

Finally, the protocol sends the ciphered row to the party hosting this row, designated by the location sequence. For input matrices of size N , SW-Setup requires 2N 2 communications.

4.2.2

Multiparty copy

In the various subroutines that compose our algorithm, we will often need to copy and recipher a vector from one Party to another following location and key sequences. This is done by masking and decryption, as shown in MP-Copy. For a given ciphered element x hosted by Bob and encrypted for Dan, to its new location at Alice and encrypted for Charlie. A schematic version of this protocol focusing on data exchanges is given in Figure 4.2. Here, Dan is in charge of performing the decryption and the re-encryption of the element. To prevent Dan from learning the value of x, Bob masks it additively with a random value. Bob therefore needs to clear out this random mask on the value re-encrypted by Dan, with Charlie's key, before sending it to Alice. This protocol uses a total of 3 communications.

4.2.3

Classical Matrix Multiplication base case

We describe in this section an algorithm to perform classical matrix multiplications in the data and encryption layout of P K " ta i,k b k,j u P K , where P K is the public key that has been used to cipher the element. Therefore, the coefficient b k,j should first be deciphered, and to avoid leaking information, it should also be masked beforehand by some random value.

MaskAndDecrypt takes care of masking and deciphering a whole column of B. There, player Charlie is the only one able to decrypt the masked value β k,j " tb k,j `tk,j u C . For this we require a stream of uniformly random values t k,j , that can be sent. To reduce communications, we here instead use a mask generating function (MGF) that generates this stream from a small seed. Then only the seed need to be communicated to remove the mask. All players have of course to agree beforehand on a choice for this mask generating function.

PointwiseProducts shows how player Alice can then recover the ciphertext of one product ta i,k b k,j u D . Alice sends her value ta i,k u D to player Charlie who then performs the exponentiation, corresponding to a multiplication on the plaintexts, and sends it back to Alice. Meanwhile Alice has received the seed and generated the masking values t k,j to clean out the product. Finally each coefficient tc i,j u D of the result is computed during a reduction step where player Alice simply multiplies together all corresponding point-wise products.

Overall, BaseCase schedules these three operations. In the calls to Protocols MaskAnd-Decrypt and PointwiseProducts, Alice is incarnated by Player P L A ris , Bob by P L B rks , Char-Protocol 4.3: MaskAndDecrypt Input: Two parties, further denoted as Bob and Charlie. They both know their own private key, public keys of all the parties involved, the security parameter λ P N and the modulus m P N. Moreover, Bob knows a seed s k P N and a ciphered vector of size n, tb k,˚uC , whose elements pb k,j q P M n have been ciphered using Charlie's public key. Output: Charlie learns the additively masked plaintext of Bob's input vector. Goal: Perform the additive masking of Bob's input vector, and let Charlie learn it.

1. Mask Bob's input: a) Generate randoms: Bob performs MGF(s k , bitsize(σ)ˆn) and splits the output in n shares of size bitsize(σ), denoted as t k,j for j P t1..nu. b) Mask vector: for j P t1..nu, Bob computes β k,j " tb k,j u C ¨gt k,j P C C . c) Communication: for j P t1..nu, Bob sends β k,j to Charlie. 2. Finalise: a) Decipher: for j P t1..nu, Charlie performs NaccacheSternDecrypt(sk C , β k,j ) and stores the results in u k,j " b k,j `tk,j P M.

Protocol 4.4: PointwiseProducts

Input: Four parties, further denoted as Alice, Bob, Charlie and Dan. Alice knows a ciphered ta i,k u D P C D for given i and k, ciphered using Dan's public key. Bob knows a seed s k P N and Charlie knows a masked vector pu k,˚q P M n (each coefficient is masked by a random value). Output: Alice learns all the ciphertexts ta i,k b k,j u D for j P t1..nu. Goal: Compute the point-wise products for naive matrix product on a given row.

1. Communication: Alice sends ta i,k u D to Charlie 2. Multiplication: for j P t1..nu, Charlie computes δ i,k,j " ta i,k u u k,j D , δ i,k,j P C D 3. Communication: for j P t1..nu, Charlie sends δ i,k,j to Alice. 4. Send seed: Bob sends s k to Alice 5. Generate and remove masks: Alice performs MGF(s k , bitsize(σ)ˆn) and splits the output in n shares of size σ, denoted as t k,j for j P t1..nu.

For j P t1..nu, Alice computes:

i,k,j " δ i,k,j { ´ta i,k u t k,j D ¯" ta i,k pb k,j `tk,j q ´ai,k t k,j u D P C D .
lie by P K B rks and Dan by P K A ris .

Protocol 4.5: BaseCase

Input: two n ˆn matrices tAu K A and tBu K B distributed and ciphered according to a base-case data layout pL A , K A , L B , K B q P pt1..N u n q 4 among parties pP 1 , . . . , P N q as in Definition 4.1.2. Output: Matrix C " A ˆB is distributed and ciphered among parties pP 1 , . . . , P N q according to the location and key sequences pL A , K A q. Goal: Compute C " A ˆB distributed and ciphered in the same way as A is. Proof. Correctness stems first from the fact that c i,j " ř n k"1 a i,k b k,j is obtained "in the exponents" by the homomorphic properties (4). Second the masks applied in MaskAndDecrypt are all removed in PointwiseProducts. Now, the communication cost in number of ring element is n for MaskAndDecrypt and n `1 for PointwiseProducts. MaskAndDecrypt and PointwiseProducts also send one seed, which, for simplicity, we consider smaller than a modular integer. Overall this yields a communication cost lower than npn `1q `n2 pn `2q " n 3 `3n 2 `n modular integers for BaseCase.

As an illustration,we give in Figure 4.3 an illustration of the scheduling of BaseCase in a scenario with 4 players.

4.2.4

Security Analysis

From the formalization of the different protocols we can state the security of the overall base case for matrix multiplication in the following Theorem 4.2.2. Theorem 4.2.2. If players share a 0-data-layout, BaseCase is secure against one semihonest adversary.

Alice pA 1 q Bob pA 2 q Charlie pB 1 q Dan pB 2 q " pt uP K A ris q where i is the output of a call to F P W P . The simulator S i executes: for each k P t1..N u: from BaseCase output in the ideal world, it picks N ´1 random shares in M (denoted 1 i , i P t1..N ´1u), and ciphers them using P k K A ris. Then, it chooses the last share

Input: ta 1,1 u A2 , ta 1,2 u A2 ta 2,1 u A1 , ta 2,2 u A1 tb 1,1 u B2 tb 2,1 u B1 random s 1 random s 2 t 1,1 " MGFps 1 q.nextpq t 2,1 " MGFps 2 q.nextpq β 1,1 " tb 1,1 u t1,1 B2 β 2,1 " tb 2,1 u t2,1 B1 β 1,1 / / β 2,1 o o u 2,1 " D B1 pβ 2,1 q u 1,1 " D B2 pβ 1,1 q s 1 o o t 1,1 " MGFps 1 q.nextpq ta 1,1 u A2 / / δ 1,1,1 " ta 1,1 u u1,1 A2 δ 1,1,1 o o ε 1,1,1 " δ t ´1 1,1 1,1,1 s 1 o o t 1,1 " MGFps 1 q.nextpq ta 2,1 u A1 / / δ 2,1,1 " ta 2,1 u u1,1 A1 δ 2,1,1 o o ε 2,1,1 " δ t ´1 1,1 1,1,1 s 2 o o t 2,1 " MGFps 2 q.nextpq ta 1,2 u A2 / / δ 1,2,1 " ta 1,2 u u2,1 A2 δ 1,2,1 o o ε 1,2,1 " δ t ´1 2,1 1,2,1 s 2 o o t 2,1 " MGFps 2 q.nextpq ta 2,2 u A1 / / δ 2,2,1 " ta 2,2 u u2,1 δ 2,2,1 o o ε 2,2,1 " δ t ´1 2,1 2,2,1 tc 1,1 u A2 " ε 1,1,1 ˆε1,2,1 tc 2,1 u A2 " ε 2,1,1 ˆε2,2,1 Output: ta 1,1 b 1,1 `a1,2 b 2,2 u A2 ta 2,1 b 1,1 `a2,
1 n such that: 1 n ˚śn´1 k"1 1 i . If 1
n belongs to C K Aris , then it outputs each component of 1 , otherwise it redoes the process from the beginning for the k th step. The definition of the data layout ensures that P L A ris ‰ P K A ris , so that i and 1 i are indistinguishable as long as the encryption scheme is IND-CPA. Moreover, since the choice of each share is consistent with the output of the protocol (i.e., their product is equal to the output), the adversary is not able to computationally distinguish between the real and the simulated execution.

P L B ris is corrupted: the view of P L B ris is: tview BaseCase P L B ris " puqu. The output of the protocol is empty for this player. The simulator picks n random values from M, andoutputs each of them to form u 1 . In the real world, each u i is masked by a random value (unknown by P L B ris since P L B ris ‰ P K B ris ), so that u i and u 1 i are then perfectly indistinguishable.

Finally, we apply the composition Theorem 4.1.6: since we have proven the security of BaseCase in the pF M &D , F P W P q-hybrid model, and that PointwiseProducts and MaskAndDecrypt are secure, and that each call to both of these protocols are sequentially made, we conclude that BaseCase is secure against one semi-honest adversary. Moreover, the 0-data layout ensures that the seed sharing does not leak information.

4.3

Multiparty Strassen-Winograd

4.3.1

Operation schedule in MP-SW

The 22 operations in a recursive step of Strassen-Winograd's algorithm is composed by 15 matrix additions and 7 recursive calls. The matrix additions are performed using component-wise homomorphic additions, denoted by Hom-Mat-Add: each player performs locally a simple homomorphic addition of the rows of the two input operands that she stores. Homomorphic subtraction, denoted by Hom-Mat-Sub, works similarly. However, this requires that the two operands share the same key and location sequences. To ensure this, some matrices will be copied from one key-location sequence to another, using a multiparty matrix copy, denoted by MP-Mat-Copy. The location sequences of the input an output are non-intersecting (and therefore so are the related key sequences). These operations are achieved by n 2 instances of MP-Copy as shown in MP-Mat-Copy. Input: An n ˆn matrix tAu K A distributed and ciphered according to a location and a key sequence pL A , K A q P pt1..N u n q 2 among parties pP 1 , . . . , P N q following Definition 4.1.2 and a location-key sequence pL 1 , K 1 q. Output: A copy tAu K 1 is distributed and ciphered among parties pP 1 , . . . , P N q according to the location and key sequences pL 1 , K 1 q. For all i, j P t1..nu 2 Parties P L 1 ris , P Lris , P K 1 ris and P Kris run MP-Copy to copy ta i,j u Kris to ta i,j u K 1 ris

We only give a sketch of the proof, since its very similar to the one for the MaskAnd-Decrypt protocol within the proof of Theorem 4.2.2.

Proof. First, we prove that MP-Copy is secure against one semi-honest adversary: from the data layout or the added randomness, each players only see ciphers or additively masked values so that it does not lean anything from the execution. Then, we prove the security in an hybrid model where calls to MP-Copy are replaced by an equivalent ideal functionality. Since the output is ciphered accordingly to the data layout, a simulation by ciphering random values is computationally indistinguishable from the real execution. Finally, by sequentially composing calls to the MP-Copy protocol, we apply the sequential composition theorem to conclude.

We propose in MP-SW a scheduling of these operations and data movement ensuring that all additions can be made homomorphically, that the key and location sequences for all seven recursive calls satisfy the requirements for a base-case datalayout (Definition 4.1.2) and finally that the output matrix also follows the location and key sequences of the first operand. The last three columns in MP-SW indicate the location sequences of the input and output operands for each operation.

Figure 4.4 also presents the data exchange between groups of players in one recursive level of MP-SW.

Note that the initial problem requires that both operands A and B share the same key and location sequences (so that matrix squaring is possible). However, the base case protocol ( BaseCase) requires that these sequences are non-intersecting. In order to satisfy these two constraints the recursive Strassen-Winograd algorithm is presented with a location and key sequence for A (L A and K A ) and a location and key sequence for B (L B and K B ). The algorithm does not require that they are non intersecting, but ensures that from the first recursive call, they will always be, so as to fit with the requirement of the base case, BaseCase. Input: two n ˆn matrices tAu K A and tBu K B , distributed and ciphered according to an -recursive data layout pL A , K A , L B , K B q P pt1..N u n q 4 among parties pP 1 , . . . , P N q following Definition 4.1.2, where n " b2 . Output: tCu K A " tA ˆBu K A , distributed and ciphered among parties pP 1 , . . . , P N q according to the location and key sequences pL A , K A q.

1. If " 0: Parties in pL A , K A q and pL B , K B q run BaseCase on tAu K A and tBu K B 2. Else In1 loc. In2 loc. Out loc. Proof. otherwise. We need to prove that for any corrupted player, its real view is indistinguishable from the simulated one. From the inputs described as in MP-SW (implicit in the following), the outputs for the player P L A X ris are the rows of the following matrices, ciphered with P k K A X ris , with X P tU, Lu. output MP-SW A U pU 1 , U 5 q and output MP-SW A L pU 6 , U 7 q. Using the same notations, we obtains the following views:

tS 1 u K A L Ð Hom-Mat-Add ptA 21 u K A L , tA 22 u K A L q L A L L A L L A L tA 1 11 u K A L Ð MP-Mat-Copy ptA 11 u K A U , pL A L , K A L q q L A U L A L tS 2 u K A L Ð Hom-Mat-Sub ptS 1 u K A L , tA 1 11 u K A L q L A L L A L L A L tS 3 u K A L Ð Hom-Mat-Sub ptA 1 11 u K A L , tA 21 u K A L q L A L L A L L A L tS 1 2 u K A U Ð MP-Mat-Copy ptS 2 u K A L , pL A U , K A U q q L A L L A U tS 4 u K A U Ð Hom-Mat-Sub ptA 12 u K A U , tS 1 2 u K A U q L A U L A U L A U tT 1 u K B U Ð Hom-Mat-Sub ptB 12 u K B U , tB 11 u K B U q L B U L B U L B U tB 1 22 u K B U Ð MP-Mat-Copy ptB 22 u K B L , pL B U , K B U q q L B L L B U tT 2 u K B U Ð Hom-Mat-Sub ptB 1 22 u K B U , tT 1 u K B U q L B U L B U L B U tT 3 u K B U Ð Hom-Mat-Sub ptB 1 22 u K B U , tB 12 u K B U q L B U L B U L B U tB 1 21 u K B U Ð MP-Mat-Copy ptB 21 u K B L , pL B U , K B U q q L B L L B U tT 4 u K B U Ð Hom-Mat-Sub ptT 2 u K B U , tB 1 21 u K B U q L B U L B U L B U tR 1 u K A L Ð MP-SW ptA 1 11 u K A L , tB 11 u K B U q L A L L B U L A L tR 2 u K A U Ð MP-SW ptA 12 u K A U , tB 21 u K B L q L A U L B L L A U tR 3 u K A U Ð MP-SW ptS 4 u K A U , tB 22 u K B L q L A U L B L L A U tR 4 u K A L Ð MP-SW ptA 22 u K A L , tT 4 u K B U q L A L L B U L A L tR 5 u K A L Ð MP-SW ptS 1 u K A L , tT 1 u K B U q L A L L B U L A L tR 6 u K A L Ð MP-SW ptS 2 u K A L , tT 2 u K B U q L A L L B U L A L tR 7 u K A L Ð MP-SW ptS 3 u K A L , tT 3 u K B U q L A L L B U L A L tR 1 1 u K A U Ð MP-Mat-Copy ptR 1 u K A L , pL A U , K A U q q L A L L A U tU 1 u K A U Ð Hom-Mat-Add ptR 1 1 u K A U , tR 2 u K A U q L A U L A U L A U tU 2 u K A L Ð Hom-Mat-Add ptR 1 u K A L , tR 6 u K A L q L A L L A L L A L tU 3 u K A L Ð Hom-Mat-Add ptU 2 u K A L , tR 7 u K A L q L A L L A L L A L tU 4 u K A L Ð Hom-Mat-Add ptU 2 u K A L , tR 5 u K A L q L A L L A L L A L tU 1 4 u K A U Ð MP-Mat-Copy ptU 4 u K A L , pL A U , K A U q q L A L L A U tU 5 u K A U Ð Hom-Mat-Add ptU 1 4 u K A U , tR 3 u K A U q L A U L A U L A U tU 6 u K A L Ð Hom-Mat-Sub ptU 3 u K A L , tR 4 u K A L q L A L L A L L A L tU 7 u K A L Ð Hom-Mat-Add ptU 3 u K A L , tR 5 u K A L q L A L L A L L A L 3. End result tCu K A Ð " tU 1 u K A U tU 5 u K A U tU 6 u K A L tU 7 u K A L  L A U L A L L B U L B L tA 11 u,
u A L tT 1 u B U tA 11 u A U / / tS 2 u A L , tS 3 u A L tT 3 u B U , tT 2 u B U tB 22 u B L o o tS 4 u A U tS 2 u A L o o tT 4 u B U tB 21 u B L o o tR 1 u A L tB 11 u B U o o tR 2 u A U tB 21 u B L o o tR 3 u A U tB 22 u B L o o tR 4 u A L tT 4 u B U o o tR 5 u A L tT 1 u B U o o tR 6 u A L tT 2 u B U o o tR 7 u A L tT 3 u B U o o tU 1 u A U tR 1 u A L o o tU 2 u A L , tU 3 u A L , tU 4 u A L tU 5 u A U tU 4 u A L o o tU 6 u A L , tU 7 u A L
view MP-SW L A U = pS 1 2 , S 4 , R 1 1 , R 2 , R 3 , U 1 4 q, view MP-SW L A L = pS 1 , A 1 11 , S 2 , S 3 , R 1 , R 4 , R 5 , R 6 , R 7 , U 2 , U 3 , U 4 q, view MP-SW L B U = pT 1 , B 1 22 , T 2 , T 3 , T 4 q, view MP-SW L B L
" p´q We construct a generic simulator, where differences depending on the corrupted player are explicitly detailed. The simulator S iPt1..N u takes two random matrices in α and β both in M pN ˆN q . Then, it replaces the rows for the corrupted player with its actual inputs (i.e., the rows of A and B owned by the corrupted player). The remaining coefficients are ciphered accordingly to the data layout. The first part of the protocol (i.e. the computation of S i and T i , i P t1..4u) is simulated using the inputs and ideal calls to F Copy . This simulates the views for the L B cases. Then, there are two cases.

P L A U ris is corrupted: From the output, the simulator S L A U ris takes N {2 random values from C A U ris to obtain the simulation of the row of U 4 . Then, it computes the row of R 3 " Hom-Mat-SubpU 5 , U 4 q. Similarly, it take the row R 1 1 at random, and computes R 1 " Hom-Mat-SubpU 1 , R 1 1 q. P L A L ris is corrupted: S L A L ris samples 3N {2 random values from C A L ris to simulate the row of U 2 , R 1 and R 7 . Next, it computes: R 6 " Hom-Mat-SubpU 2 , R 1 q, U 3 " Hom-Mat-AddpU 2 , R 7 q, R 4 " Hom-Mat-SubpU 3 , U 6 q, R 5 " Hom-Mat-SubpU 7 , U 3 and U 4 " Hom-Mat-AddpU 2 , R 5 q.

We now prove that the simulated view is indistinguishable from the real one. The proof relies on a sequence of hybrid games, where each transition is based on indistinguishability.

H 0 : The first game represents the view of a real protocol execution in the pF Copy , F BaseCase , F MP-SW N {2 q-hybrid model. H 1 : for each call to F Copy , we replace the output of the functionality by random numbers, accordingly ciphered with the data layout. i.e.: @j P t1..N u, r i $ Ð M and tr j u K X rjs with X P tA L , B U u. As only one player is corrupted, and pL A , K A , L B , K B q is a l-recursive data layout which verifies pL X U Y K X U q X pL X L Y K X L q " H, X P tA, Bu, then the player obtains ciphers which it cannot decipher. Then, the IND-CPA security of the cryptosystem ensures that H 0 and H 1 are indistinguishable.

H 2 : In this game, we replace the output obtained from:

F BaseCase if N ď T ; or F MP-SW N {2
otherwise; by the previously detailed simulation for the R i , i P t1..N u. From the data layout, the corrupted player (P L A U ris or P L A L ris ) in the real case gets undecipherable values that cannot be guessed from the inputs of the adversary (which knows one row of each matrix in the worst case) so that the simulation is computationally indistinguishable. Then, H 1 C " H 1 2 . H 3 : In this game, we replace the U i of the real view with the simulated ones U i , i P t2..4u. Each of the simulated values is directly computed from the output, so that as long as the adversary is not able to distinguish ciphers, the simulation is computationally indistinguishable from the real execution.

H 3 represents the simulated view for N players. We have then proven that MP-SW is secure against one semi-honest adversary in the pF Copy , F BaseCase , F MP-SW N {2 q-model.

Second, we prove that if we assume a l-data layout between the players, MP-SW is secure against one semi-honest adversary under a sequential composition of the subprotocols MP-Mat-Copy and BaseCase. By induction, we suppose that MP-SW is secure with N {2 players, and we show that MP-SW for N players.

Base Case : N ď T . In this case, MP-SW calls are replaced by calls to BaseCase. By construction, the data layout is now 0-recursive. Then, the corrupted player cannot act as more than one player in the execution, so that the security of the protocol against one-semi honest is enough.

Induction : N ą T . In this case, each call to MP-SW is assumed secure from the induction hypothesis. Then, each of these calls can be sequentially realized.

Then, since all sub-protocols calls can be realized sequentially, and since we have proven that MP-SW is secure in the F BaseCase , F Copy , F MP-SW N {2 -hybrid model, the sequential composition theorem ensures that the protocol obtained by composition is also secure. Henceforth, by induction, we have proven that from F MP-SW N {2

, we are able to construct a secure execution of MP-SW. In conclusion, MP-SW is secure against one semi-honest adversary.

4.3.2

Finalisation step

Finally, there remains to decipher and distribute each row of tCu K A to the party who has to learn it. By setting the key sequence to K A " p1, 2, 3 . . . q as in Lemma 4.1.3, this player is able to perform the decryption himself. This finalisation step is formally described in SW-Finalise and uses N 2 communications.

Finally, Theorem 4.3.3 asserts the security of MP-SW and the sequential execution of (SW-Setup; MP-SW; SW-Finalise) that of the whole process.

We now compare the cost of MP-SW with the cost of MP-PDP, C MP-PDP pnq " n3 ǹpn ´1q. We also recall that the initialization step SW-Setup costs C init " 2n 2 and the finalisation step SW-Finalise costs C final " n 2 . The crossover point where our full algorithm improves over MP-PDP in communication cost is obtained by solving the equation: Cpnq `3n 2 ď n 3 `npn ´1q which yields n ą 94, with one recursive call. This means that for any instance of dimension larger than 96, the proposed MP-SW algorithm has a better communication cost than MP-PDP.

4.4

Experiments

We implemented the algorithms under study to demonstrate their behavior in practice and compared them to the state of the art implementations of other solutions. In the following SPDZ 2 k refers to a run of a textbook matrix multiplication algorithm performed with the general purpose library SPDZ 2 k (Cramer et al.) 3 , YTP-SS refers to n 2 applications of (Dumas et al., 2017a, Algorithm 15); MP-PDP refers the relaxation and improvement of this algorithm to the current setting; MP-SW refers to our implementation of MP-SW using BaseCase as a basecase with threshold set to n " 56. The Naccache-Stern cryptosystem is set with public keys of size 2048 bits and message space of 224 bits (using 14 primes of 16 bits).

Please note that, while MP-PDP and MP-SW share the same security model, YTP-SS and SPDZ 2 k achieve better security: malicious adversaries over insecure channels. Also, SPDZ 2 k uses a different approach based on oblivious transfer and secret sharing. However, as they were the only state of the art implementations available, we still chose to include them in our comparisons.

Figure 4.5 presents the volume of communication performed by these four variants. Communication-wise, for n " 100 players, MP-SW is 4% cheaper than MP-PDP (271 vs. 261 MB), but becomes 24% cheaper for n " 400 (15.3 vs. 11.7 GB) and up to 27.8% for n " 528 (35.2 vs. 25.4 GB). Note that the cross-over point of n " 96 between MP-PDP and MP-SW is confirmed experimentally. For SPDZ 2 k , computations were performed for small matrices only because of computational power requirements: on a workstation with 16 GB of RAM and an Intel i5-7300U @2.60GHz, computations stalled for any matrices larger than 37 ˆ37.

To reach this communication improvement, the price to pay is that of some computational slowdown, as shown in Table 4.2

Finally, as there is same order of magnitude for the computational cost and the communication cost, communications should be largely dominant. Therefore, the improvement in communication volume is the one that matters.

4.5

Variant of MP-SW using proxy re-encryption

In this section we show how the use of proxy re-encryption schemes can improve the communication cost of MP-SW. Proxy re-encryption, abriged proxy in the rest of this document, are cryptosystems which allow to convert a ciphertext for one key into the same ciphertext but for another key. Formally introduced by Blaze et al. in [START_REF] Blaze | Divertible protocols and atomic proxy cryptography[END_REF], the initial definition of a proxy involved the use of a trusted third party which is entrusted with a so-called proxy key allowing it to perform the reencryption. While the original proxy scheme (Blaze et al., 1998, Section 3) was based on ElGamal encryption, techniques evolved as new needs arose, and modern proxy protocols with more properties (for instance the unidirectionality of the proxy function or the resistance to collusion) were developed (see for instance [START_REF] Ateniese | Improved proxy re-encryption schemes with applications to secure distributed storage[END_REF], [START_REF] Green | Identity-based proxy re-encryption[END_REF], [START_REF] Ivan | Proxy cryptography revisited[END_REF], [START_REF] Hohenberger | Securely obfuscating re-encryption[END_REF]). However, these new approaches are usually based on expensive cryptographic tools, as pairings.

The main tool we use for all the recursive phases of MP-SW, MP-Copy is actually a proxy scheme in disguise: (reusing the naming conventions of MP-Copy), its goal is to recipher an element owned by Bob and protected with Dan's key to Charlie's key and send it to Alice. In order to save some communications, we propose to use proxy re-encryption instead of the masking and reciphering technique proposed in MP-Copy.

Given our security model, we can use one of the less expensive proxy solutions avail-able and we will hence use the aforementioned Blaze et al. proxy scheme. However, the native ElGamal cryptosystem used in this scheme requires that ciphered elements remain small in order to be deciphered. As we extensively use random masking techniques, particularly in our BaseCase protocol, ensuring this requirement is not possible. While picking small masks is an option, thus limiting the growth of ciphered elements, it would however compromise the security of our protocol, as players would be able to tackle discrete logarithm computations on these new small ciphertexts.

We instead propose to rely on a variant by Castagnos and Laguillaumie [START_REF] Castagnos | Linearly homomorphic encryption from ddh[END_REF]. This cipher is a variant of the homomorphically additive ElGamal, which circumvents the main drawback of the vanilla additive ElGamal (having to solve a discrete logarithm to perform a decryption) by taking the plaintext in a subgroup where the discrete logarithm problem is less expensive to solve. This variant also allows unbounded additive homomorphic operations.

Castagnos-Laguillaumie cryptosystem sets up as follows:

Setupp1 λ , 1 µ q : let µ be an integer, and B, n, p, s four integers such that s in an λ-bit integer, p is a µ-bit integer, p and s are coprime, n " p ˆs and B is an upper bound for s. Let G be a cyclic group of order n and generator g, F Ă G a group of order p and generator f . Pick x $ Ð Ý t0, . . . , Bp ´1u and compute h " g x . The public key is P K " pB, p, g, h, f q and the secret key is SK " x.

Encrypt P K pmq : for m P Z p , pick r $ Ð Ý t0, . . . , Bp ´1u and compute c 1 " g r , c 2 " f m h r . The ciphered message is c " pc 1 , c 2 q.

Decrypt SK pcq : Compute M " c 2 {c x 1 , which gives M " f m . Use an algorithm Solvepp, g, f, G, F, M q to compute the discrete logarithm f m and recover the message m.

This cryptosystem supports the same homomorphic operations as Naccache-Stern and thus can be used in MP-SW. The interested reader may refer to (Castagnos and Laguillaumie, 2015, Section 3) for details on G and F groups and on the Solve algorithm. In Blaze et al. scheme, proxy keys are a quotient of players' secret keys. While it is possible to adapt Castagnos-Laguillaumie scheme to fit this specification, it does require to restrain the choice of secret keys to invertible elements, thus modifying the security of the scheme. Instead, we propose to create a proxy key from a difference of players' secret keys: given two players, A with secret key sk A and B with secret key sk B , the key enabling recipher from A to B, Π AÑB is sk B ´sk A .

This allows to use an unmodified version of Castagnos-Laguillaumie: with the same notations as above, a ciphertext using A's key would be pc 1 , c 2 q " pg r A , f m A g rx A A q. Then, reciphering this cipher for B requires to perform:

c 2 Ð c 2 ˆcΠ AÑB 1 " f m A g rx A A ĝrpx B ´xA q A " f m A g rx B A .
As this multiparty use of Castagnos-Laguillaumie would require to remember which player first ciphered an element in order to know which subgroup and generator to use for discrete logarithm computation, we propose that all players share the same subgroup and generator, respectively denoted as F and f .

4.5.1

Description of the new protocol

In the original Blaze et al. proxy scheme, proxy entities were trusted third parties. This setting is not desirable here, as it would mean extra communications in order to send and recover data from the proxy, and as we chose to not rely on trusted entities anyway. The data repartition we have in Strassen-Winograd, alongside the regularity of the algorithm allows us to predict the list of players for which a given player will need to perform copy operations for throughout the protocol. This means we can ensure that there will always be a player able to take the role of a proxy without compromising the security, and we thus propose that players play the role of proxies instead of invoking trusted third parties. We then need a new protocol which allows players to craft their proxy keys in a secure way: players cannot learn any information on the secret keys of the others' secret keys. We consider three players Alice, Bob and Charlie, where Charlie needs to learn the proxy key Π AÑB , Bob first ciphers his private key with Charlie's public key and sends the result to Alice. Using homomorphic properties of Castagnos-Laguillaumie cryptosystem, she computes a ciphered sk B ´sk A and sends it to Charlie, who then deciphers it and only learns the proxy key. ProxyKeyGen gives a formal description of this proxy key generation. Protocol 4.9: ProxyKeyGen Input: Three parties, further denoted as Alice, Bob and Charlie. They both know their own private key and the public keys of all the parties involved. Output: Charlie learns the proxy key allowing to transform a cipher for Alice into a cipher for Bob. Goal: Perform the difference between Bob's secret key and Alice's secret key.

1 Proof. Players Alice and Bob only see ciphered elements so they do not learn anything from the execution. As the output of the protocol is a difference of values which are unknown to Charlie, the player receiving them, it is computationally indistinguishable from a simulation in which inputs are ciphered random values.

According to the definition of the location and key sequences and the schedule of MP-SW, a given player P Lris will always own elements ciphered with the key of P Kris , hence always having to recipher elements from this player to another. The "destination" player changes at each recursive level, meaning that for an instance of MP-SW with k recursive levels, our player P Lris will have to get k different proxy keys. More specifically, at a given recursive level r, where input matrices have size s " n{p2 r´1 q, P Lris has to relocate the elements they own for P Lr1`pi´1`s{2 mod sqs , meaning they have to recipher it for P Kr1`pi´1`s{2 mod sqs . This allows to predict which proxy keys will be needed throughout the whole protocol, and to generate them during the setup phase.

From this information, the setup phase is now modified and the new setup is proposed in SW-Setup-Proxy. Protocol 4.10: SW-Setup-Proxy Input: Two N ˆN matrices A and B over M, where N " b2 , such that party P i knows the i-th row of A and the i-th row B for all i P t1..N u. A location and a key sequence L P t1..N u N and K P t1..N u N such that pL, K, L, Kq form an -recursive data layout, following Definition 4.1.2. All parties know a security parameter λ, an integer µ and a group F with generator f . Output: For all i P t1..N u, party P Lris learns vectors ta i,˚uKris and tb i,˚uKris , learns the public key of every other party and the required proxy keys. Goal: Generate key pairs for each party, cipher and distribute input matrices according to their respective location and key sequences.

1. Key generation: for all i P t1..N u, each party P i locally executes CastganosLaguillaumieSetup(1 λ , 1 µ ) to generate a pair of keys (pk i , sk i ). The group generator for the group in which the message will be mapped to has to be f . 2. Broadcast keys: for all i P t1..N u, party P i broadcasts its public key pk i . 3. Proxy keys generation: for all i P t1..N u, for all j P t1.. u, run ProxyKey-Gen (P Kris , P Kr1`pi´1`N {2 j mod N {2 j`1 qs , P Lris ). 4. Cipher inputs: for all i P t1..N u, for all j P rns, party P i locally performs CastagnosLaguillaumieEncrypt(pk Kris , a ij ) and stores the result as a new vector ta i,˚uKris . It does the exact same operation with b i,˚t o get tb i,˚uKris . 5. Distribute rows: a) Rows of A: for all i P t1..N u, party P i sends ta i,˚uKris to party P Lris . b) Rows of B: for all i P t1..N u, party P i sends tb i,˚uKris to party P Lris .

The call to MP-Copy is simply replaced by a call to the proxy re-encryption function, and the reciphered value is forwarded to the appropriate player, as shown in MP-Copy-Proxy. This new copy protocol, MP-Copy-Proxy is a simple application of the secure

4.5.3

Comparisons between fully and semi homomorphic solutions

In the introduction of this chapter, we justified setting aside fully homomorphic cryptography based on the sheer cost of their arithmetic operations. However, the protocols we developed need to perform a large amount of additional cryptographic operations, which would not be required with fully homomorphic tools. Hence, we need to verify that this argument still holds. One bottleneck of fully homomorphic cryptography is the multiplicative depth of the algorithm: if it is too high, costly bootstrapping operations have to be performed in order to ensure proper decryption. As matrix multiplication algorithms have a multiplicative depth of 1, they seem to be quite favourable algorithms for such cryptographic solutions, which further calls for a refined analysis on the cost of fully homomorphic cryptography in our setting. For Strassen-Winograd, ciphered elements are only used in product operations when computing dot products in the base case step, and there are no accumulations, as the result of multiplications performed for dot products are not reused for other multiplications. Thus, there is no need to perform bootstrapping operations with fully homomorphic cryptosystems with Strassen-Winograd algorithm.

Thus, we propose to estimate the total runtime of a run of Strassen-Winograd for SEAL and HElib. We model this run in a slightly different setting than the one considered in MP-SW. We will indeed assume there exists a trusted third party, to which players will send their ciphered inputs, and from which players will receive their output. In this model, the protocol only consists in running Strassen-Winograd algorithm homomorphically, which amounts for the exact same amount of arithmetic operations as the textbook version, and the initial and final encryptions and decryptions. This will allow us to evaluate the practical cost of the fully homomorphic libraries under consideration.

Our estimations are based on an input matrix size of N " 224, with a threshold of 56, as given in Section 4.3.3. This means two recursive levels will be performed before the base case. Table 4.4 gives an estimation of the execution time per operation, and of the total execution for MP-SW (proxyless vanilla version and the improved proxy-based version) and for HElib and SEAL. We computed the amount of times each operation has to be performed to complete an execution of Strassen-Winograd on both models and used the timings per operations that were given in Table 4.1.

In order to get an estimation of the runtime of the proxy variant of MP-SW, we had to get timings for elementary cryptographic and arithmetic operations in Castagnos-Laguillaumie. We chose to base these timings on Paillier cryptosystem, as Castagnos-Laguillaumie behaves the same, mostly using exponentiations modulo n 2 , where n is the public modulus obtained from the key generation phase of the cryptosystem. Table 4.3 presents a comparison between the modular operations used to perform an encryption, a decryption, an homomorphic addition and a multiplications in both cryptosystems. We chose to display only the most expensive operation: Paillier, for instance, also requires to perform a multiplication modulo n in the encryption step, but its cost is negligible compared to the cost of exponentiations modulo n 2 . The ratio column shows the factor to apply to the timings measured for Paillier in Table 4.1 to

Conclusion

We have presented in this chapter a novel secure multiparty matrix multiplication where each player owns one row of the different matrices. For this we use Strassen-Winograd algorithm and reduce for the first time the total communication volume from OpN 3 q to OpN log 2 p7q q. The improvement in communication cost over state of the art algorithms takes effect for dimensions as small as 96, verified in practice, or 72 with the proxy-based variant.

In this matrix multiplication protocol, it was necessary to protect both multiplicands, as Strassen-Winograd algorithm requires to perform pre-additions between elements of one input matrix at a time. This new constraint required to have a secure routine to move data and change its encryption key: this was initially done with encryption/decryption and random masking sequences, which was later improved with proxy re-encryption techniques.

The version of Strassen-Winograd we presented here is secure against semi-honest adversaries. However, as many of its building blocks have a stronger security level anyway, it would be interesting to see if it is possible to increase the security of the whole MP-SW protocol and how it would impact its performance.

Even if this chapter is a about improving the communication cost while preserving security, several arithmetic cost improvements could be envisioned. A possibility would be to replace the Naccache-Stern by a faster cryptosystem. The difficulty is to be able to combine the masking schemes with the homomorphic encryption.

This chapter proposed a new protocol for matrix multiplication. Matrix multiplication is a tool used in many applications and computations, as linear system solving, Ax " b. Developing an efficient multiparty protocol for this problem with the same data layout (each player knows one row of A, one coefficient of b and learns one coefficient of x) has interesting real world applications: multiparty polynomial interpolation, for instance, where each player knows one interpolation point. We explored one idea for this application, based on building a protocol with entropic security for the LU decomposition of matrix. In this protocol, players would build a shared U matrix and keep their row of L secret, thus protecting their input values. This protocol would then straightforwardly allow for system solving, as it would just be a run of the LU protocol on matrix A augmented with b. However, with this idea, players input are in the worst case only protected by one coefficient -which is especially dangerous for polynomial interpolation as the input matrix is Vandermonde, meaning that leaking information about one coefficient leaks information about the entire row. It would then be worth exploring other directions, as for instance designing a protocol for secure triangular system solving which could be used to securely compute the LU decomposition.

Conclusion

In this thesis, we focused on two aspects of outsourced computation in exact linear algebra: output verification, and data confidentiality. We proposed new protocols to verify rank-related invariants: the matrix rank, the row and column rank profiles and the rank profile matrix. This lead us to design a verification protocol for the generic rank profile-ness of a matrix, which we then used to develop new protocols for problem based on triangular decompositions: the determinant and the signature. We then designed verification protocols for the classical properties of polynomial matrices, either specific to modules or carrying to vector spaces. Our protocols for modules, are, to the best of our knowledge, the first verification protocols for matrix properties on such algebraic structures. Finally, we proposed a new multi-party protocol for matrix multiplication based on Strassen-Winograd algorithm, improving the state of the art for the important communication volume cost of such protocols. It is also, as far as we are aware of, the first multi-party algorithm with a recursive structure.

These results are either maiden contributions (verification protocols for modules, multi-party protocols with a recursive structure) or crucial improvements (rank-related protocols) to the field of algorithm-based outsourced computation for exact linear algebra. Short-term perspectives and improvements to our results have been given in the conclusions to the different chapters. The two major ones are the design of a Smith form verification protocol for polynomial matrices and a secure multi-party protocol for the LU decomposition. They also allow us to envision new significant, longer-term perspectives that we propose in what follows.

Verification protocols for numerical linear algebra. The verification protocols we proposed in this thesis are based on verification checks in which the output of the check only depends on the Prover's honesty: if a check is false, then the Prover cheated. This restrictive definition of the Verifier's checks makes it harder to design protocols for numerical linear algebra: defining equality checks in this field is a complex task because of the rounding errors in computations, which might cause a check to fail with an honest Prover. To design such protocols, we could focus on new definitions of completeness, based for instance on stability analysis.

Error correction. In this thesis, we focused on verifying outsourced computations: the goal was to design protocols able to detect whether a given result was correct. An extension to this work would be to also fix the errors in a wrong result in order to recover the actual output to the outsourced problem. While coding theory seems to be the perfect candidate for this task, the redundancy in encoding is not efficient communication-wise, and error-correcting codes are designed to deal with uniform distribution of errors, which does not fit our model. It is possible to design such protocols, by for instance using the redundancy in algebraic relations between the public input and the output. There have been advances on designing error-correction protocols for outsourced computations in exact linear algebra in the past few years, with for instance Roche (2018) on matrix multiplication (and inverse) or Dumas et al. (2019b) for LU decomposition of generic rank profile matrices. Some difficult problems remain: a straightforward improvement to these works would be to find an error-correction protocol for the LU decomposition with pivoting, leading to the correction of the LUP or the PLUQ decomposition. Designing such protocols for the properties we focused on in this thesis, as the rank profile matrix computation would be a natural extension to our work.

A slightly different focus could be to incorporate Monte-Carlo probabilistic algorithms for the Prover side of our verification protocols. These algorithms can silently fail, meaning they can return a wrong result without notice. Our verification protocols already are Monte-Carlo for the Verifier: a dishonest Prover can sometimes not be detected (this is the probabilistic soundness), but an honest Prover will never be rejected (perfect completeness). Because of the nature of our verification checks, which assume that failures are due to the Prover, we naturally excluded such algorithms when designing our protocols. Being able to fix the errors that might come from the use of Monte-Carlo algorithms would allow us to actually use these algorithms, leading to protocols with faster computation time for the Prover. As the verification certificate from (Dumas et al., 2016, Section 4) allows the use of Monte-Carlo algorithms for the Prover, their approach should also be investigated.

Verify the negation of a statement. Our verification protocols frequently prove affirmative statements, for instance that there exists a triangular matrix such T such that AT " B or that a given vector is in the row space of a polynomial matrix. Designing protocols that are able to verify negative statements would be a major improvement to the family of algorithm-based verification protocols. These are often quite harder to prove than the affirmative ones, as they are more generic: the Prover can no longer provide a simple single answer (such as the constraint projection of the triangular matrix) to the Verifier. A very ambitious question would be to investigate how to get a verification protocol for a the negation of a statement from the protocol for the affirmative statement. A starting point could be to develop several negative statements verification protocols on specific problems, -such as the ones from this thesis -to investigate how they relate to their affirmative statements counterparts and whether these relations have similarities. Farkas certificate of inconsistency [START_REF] Farkas | Theorie der einfachen ungleichungen[END_REF]) could be a useful tool for the verification of such negative statements.

Existence of fundamental building blocks for verification protocols. The verification protocols we proposed in this thesis heavily rely on a few sub-protocols: the step-by-step data exchange of TriangularEquivalence is a central tool for the protocols in Chapter 2 while RowSpaceMembership is heavily used by the protocols from Chapter 3. These two sub-protocols can be seen as building block for verification protocols: central elements into which problems could be reduced. Matrix multiplication (with Freivalds' check) and linear system solve verification also appear to be such building blocks, as they are heavily used, not only by some of our protocols but also by many of the others that were given in Chapter 1. We then wonder the scope of these four building blocks: which verification protocols could be reduced to one of them, and amongst the protocols that we cannot reduce to our building blocks, could we find new building blocks to cover such protocols ? We would need to develop more algorithm-based verification protocols in exact linear algebra, in order to look for these building blocks. These fundamental building blocks are also extremely useful for the practicality of verification protocols: they would allow us to take one step further towards real-world applications, with the development of a library for outsourced computation verification containing highly efficient implementation of these fundamental protocols.

New data layout for MP-SW. The multiparty protocol version of Strassen-Winograd algorithm we proposed in Chapter 4 requires a very specific data layout in which players knows one full row of both input matrices. This layout is very well suited to the problem, as its high regularity allowed us to take full advantage of the algorithm's structure. A data layout often used in multi-party computation setting is the additive sharing of the input (Cramer et al., 2015, Chapter 9) [START_REF] Dagdelen | A multi-party protocol for privacy-preserving cooperative linear systems of equations[END_REF]: each party knows one share of the input and the full input can be obtained by adding all the shares owned by the parties. Designing a multi-party version of Strassen-Winograd for this layout would allow us to open our work to a wider array of practical applications. However, this would require some heavy work on the foundations of our protocol: with this layout, it is no longer possible to perform local homomorphic operations during the recursive steps, and our other subroutines would need to be adapted as well. Our main result was to obtain the same communication volume complexity as the textbook Strassen-Winograd's algorithm computational complexity (Opn 2.8 q). However, reaching the same cost with the additive setting seems much more difficult, as performing arithmetic operations would require to communicate data between more than two players, thus increasing the overall communication volume.

  protocols for outsourced computation . . . . . . . . . . . . . 1.1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 Interactive proof systems and verification protocols . . . . . . . . 1.1.3 Evaluation of the efficiency of a verification protocol . . . . . . . 1.1.4 From interactive to non interactive protocols and public verifiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.5 Paradigms for verification protocols . . . . . . . . . . . . . . . . . 1.1.6 Linear algebra intermediate approach . . . . . . . . . . . . . . . 1.1.7 Overview of existing state of the art algorithm-based verification protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Multi-party computation protocols . . . . . . . . . . . . . . . . . . . . . 1.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Evaluation of the efficiency of an MPC protocol . . . . . . . . . . 1.2.4 Paradigms for MPC protocols . . . . . . . . . . . . . . . . . . . . 1.2.5 Algorithm-based approaches . . . . . . . . . . . . . . . . . . . . .

3 .

 3 Protocol LDUP is a complete and probabilistically sound interactive protocol. It requires 6n communications and has Verifier cost µpAq `12n `opnq. The Protocol 2.5: Protocol LDUP Public: A P F nˆn , non singular, P P F nˆn , D P F nˆn Certifies: That D and P come from an LDUP decomposition of A

  InvertibleRankProfileMatrix Public: A P F mˆn , invertible, P P F nˆn , D P F nˆn Certifies: P is the rank profile matrix of A Prover Verifier 1. A " LDU P , with public P and D 2. P ? P S n , D ? P D n pFq 3.

  Figure 2.1: (Verifiable) signature computation on an Intel i7-6700U@3.4GHz.

Protocol 3 . 3 :

 33 RankLowerBoundPublic: A P Frxs mˆn , ρ P N Certifies: rankpAq ě ρProver Verifier1. Find index sets I, J such that #I " ρ, #J " ρ, and A I,J is nonsingular I

Protocol 3 .

 3 8: MatMulPublic: A P Frxs mˆn , B P Frxs nˆ , C P Frxs mˆ Certifies: Let d A " maxp1, degpAqq and similarly for d B , d C .Protocol 3.8

Corollary 3 . 3 .

 33 11. If #S ě 2mnd A , then Protocol 3.11 requires only Opn `md A `dv q communication and has Verifier cost Opmnd A `nd v q.

Protocol 3 . 4 .

 34 14: RowBasisPublic: A P Frxs mˆn , B P Frxs ˆn Certifies: B is a row basis of A Let r " maxpr A , r B q and d " maxpd A , d B q. Then, Protocol 3.14 is a probabilistically sound interactive protocol, and is complete assuming #S ě 2 maxpmd A , d B q.It requiresOppm logpmq ` logp qqd `nq Ă r Opmd ` d `nqcommunication and has Verifier costOppm logpmq ` logp qqndq Ă r Opmnd ` ndq.

  HermiteForm Public: A P Frxs mˆn , B P Frxs ˆn Certifies: B is the Hermite form of A Prover Verifier 1.

Protocol 3 . 20 :

 320 KernelBasisPublic: A P Frxs mˆn , B P Frxs ˆm Certifies: B is a left kernel basis of A Protocol 3.20 is a probabilistically sound interactive protocol and is complete assuming #S ě maxppm ´ qd A `1, 2md B q in its subprotocols. It requires Opmd B logpmqq communication and has Verifier cost Op md B logpmq `mnd A q.

Figure 4 . 1 :

 41 Figure 4.1: Recursive splitting of the location and key sequences of the input and output operands in Strassen-Winograd algorithm.

  Definition 4.1.2. It consists in n 2 scalar products in which, products of elements a i,k of A by elements b k,j of B are performed using MP-Copy : Multiparty copy the homomorphic multiplication between a ciphertext and a plaintext: ta i,k u b k,j

Theorem 4 . 3 . 1 .

 431 Assuming an -data layout, Protocol MP-Mat-Copy is secure against one semi-honest adversary. Protocol 4.6: MP-Mat-Copy

Lemma 4 . 3 . 2 .

 432 The total communication cost of a recursive level of MP-SW following the schedule defined MP-SW, Step 2 is 18 `n 2 ˘2 communications. Protocol 4.7: MP-SW

Figure 4 . 4 :

 44 Figure 4.4: Protocol for Strassen-Winograd algorithm. Each column represents one of the four sub-group of players where the submatrices A U , A L , B U , B L are stored.

Figure 4 . 5 :

 45 Figure 4.5: Comparing communication volume for multiparty matrix multiplications

Theorem 4 .

 4 5.1.ProxyKeyGen is secure against one semi-honest adversary.

  A P F mˆn , B P F nˆ , C P F mˆ

		Protocol 1.2: Freivalds
	Public: Certifies: C	? " AB
		Prover	Verifier
	1.	v

$ Ð Ý S ˆ1 ApBvq ? " Cv Lemma 1.1.3. Protocol 1.2 is a perfectly complete and probabilistically sound non interactive protocol. It has Verifier cost µpAq `µpBq `µpCq. The probability that the Verifier incorrectly accepts is at most 1{#S.

  3.

	1.1.7
	Protocol 1.3: KNS11
	Public: Input to the algorithm A
	Certifies: The output of A
	Prover	Verifier
	1. Run the algorithm
	Inter. matrix products ÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÑ
	2.	Run the algorithm, but
		replace each matrix
		product by a call to
		Freivalds' check

  Table 1.1: State of the art verification protocols for several linear algebra properties

	DET			RANK
	(DKTV16) & CHARPOLY	(F79) & PLUQ	(E15)	(DK14)	(KNS11) over (CKL13)		Algorithm
	2 No OpnµpAqq	0 Yes Opn ω q	2 Yes Opmnr ω´2 q	2 No OpnpµpAq `nqq or Opmnr ω´2 q	0 No r Opr ω `µpAqq	Determ. Time	Rounds Prover
	Opnq	Opn 2 q	Opn `rq	Opm `nq	r Opr 2 `m `nq		Communication
	µpAq `Opnq n 2	Opn 2 q `µpAq 2	OpµpAq `nq 2	2µpAq `r Opm `nq Ωpmintm, nu logpmnqq	r Opr 2 `µpAqq 2	Verifier Time	Probabilistic Min. #S

or Opn ω q

Chapter 2 Elimination-based verification protocols for triangular equivalence and rank profiles Contents

	2.1 Non interactive and quadratic communication verification protocols . . .
	2.1.1 Column rank profile verification protocol . . . . . . . . . . . . . .
	2.1.2 Non interactive Rank Profile Matrix verification protocol . . . . .
	2.2 An interactive verification protocol for the rank profile matrix . . . . . .
	2.2.1 Triangular one sided equivalence . . . . . . . . . . . . . . . . . .
	2.2.2 Generic rank profile-ness . . . . . . . . . . . . . . . . . . . . . . .
	2.2.3 LDUP decomposition . . . . . . . . . . . . . . . . . . . . . . . . .
	2.2.4 Column or row rank profile verification protocol . . . . . . . . .
	2.2.5 Rank profile matrix verification protocol . . . . . . . . . . . . . .
	2.3 Constant rounds verification protocols . . . . . . . . . . . . . . . . . . .
	2.3.1 Representative Laurent polynomial of a matrix . . . . . . . . . .
	2.3.2 Constant rounds triangular equivalence verification protocol . . .
	2.3.3 Constant round verification protocols for the row and column
	rank profiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	2.4 Some additional verification protocol . . . . . . . . . . . . . . . . . . . .
	2.4.1 Linear communication verification protocols for the determinant
	2.4.2 Verification protocol for the signature of an integer matrix . . . .

  as A is regular, there is only one solution y

	Protocol 2.11: ConstantRoundTriangularEquivalence
	Public: A, B, P F mˆn , A is regular, m ě n, there exists a lower triangular matrix
	L s.t. AL " B
	Certifies: L indeed exists
	Prover	Verifier
	1. Find L lower triangular
	s.t. AL " B
	2.
	to Ay " Bx, and y " Lx. Therefore	" 1 λ . . . λ n´1 ‰	¨y "	"	1 λ . . . λ n´1 ‰	¨

  Trian-gularEquivalence, within the column rank profile ColumnRankProfile, in order to get the constant-round ConstantRoundColumnRankProfile for column rank profile. It remains Prover efficient, linear in communication volume and Verifier time. A P F mˆn , J a set of r column indices of A Certifies: J is the column rank profile of A

	Protocol 2.12: ConstantRoundColumnRankProfile
	Public: Prover	Verifier
	Corollary 2.3.2. ConstantRoundColumnRankProfile is a complete and probabilistically
	sound interactive protocol. It requires m `n `4r `1 communications and has Verifier
	cost 2µpAq `n `9r.

Table 2 .2: Contributions Chapter 3 Verification protocols with sub-linear communication for polynomial matrix operations Contents 3

 2 .1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Some probability bounds. . . . . . . . . . . . . . . . . . . . . . . 3.2 Linear algebra operations . . . . . . . . . . . . . . . . . . . . . . . . . . Row space membership . . . . . . . . . . . . . . . . . . . . . . . . . . . Row spaces and normal forms . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Row space subset and row basis . . . . . . . . . . . . . . . . . . . 3.4.2 Normal forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 3.5 Saturation and kernel bases . . . . . . . . . . . . . . . . . . . . . . . . . 103 3.5.1 Saturation and saturated matrices . . . . . . . . . . . . . . . . . 103 3.5.2 Kernel bases and unimodular completability . . . . . . . . . . . . 107

					´1
	Probabilistic #S	Verifier Time	Oprpm `nqq `µpAq ě 2	2µpAq `Opm `nq ě 2	2µpAq `Opm `nq ě 2n	Oprpm `nqq `µpAq ě 2	4µpAq `Opm `nq Ωpnq	µpAq `Opnq Ωpnq
	Communication		Oprpm `nqq	Opm `nq	Opm `nq	Oprpm `nqq	Opm `nq	Opnq
			q	q	q	q	q
	Algorithm Rounds Prover	Determ. Time	§ 2.1.1 0 Yes Opmnr ω´2	§ 2.2.4 Opnq Yes Opmnr ω´2	§ 2.3.3 3 Yes Opmnr ω´2	§ 2.1.2 0 Yes Opmnr ω´2	§ 2.2.5 Opnq Yes Opmnr ω´2	§ 2.4.1 & PLUQ Opnq Yes Opn ω q
				CRP/RRP		RPM	DET

3.2.1 Singularity and nonsingularity . . . . . . . . . . . . . . . . . . . 3.2.2 Matrix Rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.4 Protocols based on matrix multiplication . . . . . . . . . . . . . . 3.3 3.3.1 Full row rank case . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Arbitrary rank case . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4

  Frxs mˆn , v P Frxs 1ˆn , ρ P N Certifies: v P RowSp Frxs pAq and rankpAq " ρ Compute sub-Toeplitz C 1 , . . . , C t P F ρˆm and polynomials f 1 , . . . , f t P Frxs s.t. @i, rankpC i Aq " ρ, and @i, f i v P RowSp Frxs pC i Aq, and gcdpf 1 , . . . , f t q " 1 C 1 , . . . , C t , f 1 , . . . , f t Such a factorization always exists: if B P Frxs rˆn is any row basis of A, then there is a unimodular matrix rU | V s P Frxs mˆm such that rU | V sr B | 0s " U B " A; and then we have U B " AP where B " BP . It is easily verified that B has full row rank and the same Frxs-row space as AP ; that is, B is a row basis of AP .

		Protocol 3.11: RowSpaceMembership
	Public: A P Prover		Verifier
	1.	RankUpperBound(A, ρ)
	2.		Is rankpAq convinced ? ď ρ	that
		ρ	? ď minpm, nq
	3.	t Ð 1m
			ax `1, rlog #F{ρ p2ρ degpAqqs 4.
		Ý ÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝ Ñ
	5.	@i, degpf i q

?

ď ρ degpAq 6.

CoPrime(f 1 , . . . , f t ) 7. for i " 1, . . . , t do FullRankRowSpaceMembership(C i A, f i v)

  The Verifier may incorrectly accept if either λ is such that λA P RowSp Frxs pBq, which happens with probability at most 1{#S by lemma 3.4.1, or the subprotocol RowSpaceMembership has incorrectly accepted. From Theorem 3.3.10, and the union bound, we obtain the claimed probability bound.Repeating this check in both directions proves that two matrices have the same row space. Frxs mˆn , B P Frxs ˆn, ρ P N Certifies: RowSp Frxs pAq " RowSp Frxs pBq and rankpAq " rankpBq " ρ Let r " maxpr A , r B q and d " maxpd A , d B q. Protocol 3.13 is a probabilistically sound interactive protocol, and is complete assuming #S ě 2 maxpmd A , d B q.

	communication and has Verifier cost
		Oppm logpmq ` logp qqndq Ă r Opmnd ` ndq.
		Protocol 3.13: RowSpaceEquality
	Public: A P Prover	Verifier
	1.	RowSpaceSubset(A, B)
	2.	RowSpaceSubset(B, A)
	Theorem 3.4.3. It requires
		Oppm logpmq ` logp qqd `nq Ă r Opmd ` d `nq

  Protocol 3.18 is a probabilistically sound interactive protocol and is complete assuming #S ě maxp d A `1, 2nd B q in its subprotocols. It requires Opnd B logpnqq communication and has Verifier cost Opmnd A ` nd B logpnqq. If B is a saturation basis of A, then there is a Las Vegas randomized algorithm for the Prover with expected cost r O `mn ω´2 `mnd A `n ω´1 d B ˘;

	Theorem 3.5.8.

  trix B P Frxs pn´mqˆn such that Note that if A does not have full row rank, then it is not unimodular completable. Otherwise,Zhou and Labahn (2014, Lemma 2.10) showed that A is unimodular completable if and only if A has unimodular column bases; by lemma 3.5.5, this holds if and only if A is saturated. This readily leads us to Protocol 3.19. Protocol 3.19 is a probabilistically sound interactive protocol and is complete assuming #S ě 2md in its subprotocols. It requires Opnd logpnqq communication and has Verifier cost Opmnd logpnqq. If A is unimodular completable, then there is a Las Vegas randomized algorithm for the Prover with expected cost r Opnm ω´1 dq; otherwise the probability that the Verifier incorrectly accepts is at most p4md `2q{#S.

	" B A Public: A P Frxs mˆn Certifies: A is unimodular completable  Prover 1. 2. Saturated(A) is unimodular. Protocol 3.19: UnimodularCompletable m ? ă n Theorem 3.5.9.	Verifier

4.1 Preliminaries 4.1.1 Strassen-Winograd algorithm C

  " A ˆB by splitting the input matrices in four quadrants of equal dimensions:

	A "	" A 11 A 12 A 21 A 22	‰	and B "	" B 11 B 12 B 21 B 22

  For N " b2 , the following values for the location and key sequences form an -recursive data layout according toDefinition 4.1.2:

	are both
	p ´1q-recursive data layouts
	Lemma 4.1.3.

  Party P L Brks samples uniformly at random a seed s k P N according to the security parameter λ. b) Parties P L Brks and P K Brks run MaskAndDecrypt on vector tb k,˚uK Brks c) For all i P t1..nu Parties P L Aris , P L Brks , P K Brks and P K Aris run PointwiseProducts where Parties P L Aris learn i,k,j " ta i,k b k,j u K A ris for all j P t1..nu.

	1. Computation:
	For all k P t1..nu
	a) Choose a seed:

2. Reduction: for all

i P t1..nu Party P L Aris computes tc i,j u K Aris Ð ś n k"1 i,k,j

Theorem 4.2.1. BaseCase correctly computes the product C " A ˆB in the specified layout. It requires a communication of n 3 `3n 2 `n modular integers.

  2 b 2,2 u A1 ´Figure 4.3: BaseCase protocol execution with 4 players P L A ris is corrupted: the view of P L A ris is: view BaseCase P L A ris

  tA 12 u tA 21 u, tA 22 u tB 11 u, tB 12 u tB 21 u, tB 22 u tS 1

  The only communication are that of the 6 calls to MP-Mat-Copy, each accounting for 3pn{2q 2 communication.Finally, our main security result is that of the following Theorem 4.3.3. Assuming an -data layout, MP-SW is secure against one semi-honest adversary.Proof. First, we prove that MP-SW is secure in the F BaseCase , F Copy , F MP-SW BaseCase , F Copy and F MP-SW N {2 respectively denotes the ideal functionality associated to BaseCase, MP-Mat-Copy, and MP-SW with N {2 players. In this model, calls to MP-Mat-Copy are replaced by ideals calls to F Copy . In the same vein, if N ď T , the MP-SW calls are replaced by F BaseCase , or by FMP-SW

	Theorem 4.3.3. N {2	-hybrid model,
	where F N {2

Table 4 .

 4 2: Computation time (in s) per player of Multiparty Strassen-Winograd MP-SW compared to MP-PDP on an Intel Xeon E7-8860 2.2Ghz.

	Key size		1024			2048
	n	16	32	64	16	32	64
	MP-PDP 0.58 2.68 11.01 4.54 18.05 69.80
	MP-SW 2.87 6.19 13.27 23.63 49.22 196.24

Proxy key generation: Alice

  , sk B ) and stores the result in tsk B u sk C . 2. Communication: Bob sends tsk B u sk C to Alice. , -sk A ) and stores the result in tsk A u sk C . 4. performs tsk B u sk C ˆt´sk A u sk C . 5. Communication: Alice sends tsk B ´sk A u sk C to Charlie. 6. Decipher: Charlie performs CastagnosLaguillaumieDecrypt(sk C , tsk B śk A u sk C ) and learns sk B ´sk A .

	. Cipher	Bob's	secret	key:	Bob	performs
	CastagnosLaguillaumieEncrypt(pk C 3. Cipher Alice's secret	key:	Alice	performs
	CastagnosLaguillaumieEncrypt(pk C

https://www.mersenne.org/

https://www.nsf.gov/awardsearch/showAward?AWD_ID=1646999

We hope that the reader will forgive us for overloading the capital letter S: a bold S always refers to this sub-permutation matrix, while a sans-serif S refers to a subset of the field F used to select random elements.

https://github.com/rdragos/awesome-mpc

The best value known to date, due to[START_REF] François | Powers of tensors and fast matrix multiplication[END_REF], of approximately 2.3728639. However, only a few sub-cubic time algorithms are competitive in practice and used in software[START_REF] Dumas | Dense linear algebra over word-size prime fields: The FFLAS and FFPACK packages[END_REF][START_REF] Boyer | Matrix multiplication over word-size modular rings using approximate formulas[END_REF][START_REF] Kaporin | A practical algorithm for faster matrix multiplication[END_REF] (see also(Karstadt and Schwartz) and references therein), among which Strassen's algorithm and its variants stand out as a very effective one in practice.

https://github.com/bristolcrypto/SPDZ-2

Algorithm 2: Honest Prover for RowSpaceMembership

Input: A P Frxs mˆn with rank r, v P RowSp Frxs pAq, finite S Ď F Output: C 1 , . . . , C t , f 1 , . . . , f t satisfying the conditions of Step 4 from Protocol 3.11 1 t Ð 1 `rlog #S{r p2r degpAqqs 2 repeat 3 T 1 Ð random m ˆm Toeplitz matrix with entries from S 4 until rankpT 1 Aq " r 5 S P t0, 1u rˆm Ð selection of r linearly independent rows from T 1 A 6 w 1 Ð solution to w 1 ST 1 A " v, using algorithm 1 7 repeat 8 i Ð 2 9 while i ď t do 10 T i Ð random m ˆm Toeplitz matrix with entries from S 11 w i Ð solution to w i ST i A " v, using algorithm 1 12 if w i is not LOW_RANK then i Ð i `1 13 until gcdpdenompw 1 q, . . . , denompw t qq " 1 14 return ST 1 , . . . , ST t and denompw 1 q, . . . , denompw t q Lemma 3.3.9. If v P RowSp Frxs pAq and #S ě 2r where r " rankpAq, then algorithm 2 is a correct Las Vegas randomized algorithm with expected cost bound r Opmnr ω´2 d A rω´1 d v q.

Proof. Computing the rank and the row rank profile (giving r independent rows) on lines 4 and 5 can be done deterministically in the stated cost bound via the column rank profile algorithm from (Zhou, 2012, Section 11), just as was used in algorithm 1.

Each matrix product T i A can be explicitly computed in r Opmnd A q operations using Opnd A q Toeplitz-vector products, each done in r Opmq operations by relying on fast polynomial multiplication (Bini and Pan, 1994, Problem 5.1).

If the algorithm returns, correctness is clear from the correctness of algorithm 1. What remains is to prove the expected number of iterations of each nested loop. From lemma 3.3.8, for each random Toeplitz matrix T i , the probability that ST i A is nonsingular is at least 1 ´r{#S ě 1{2. Therefore the expected number of iterations of the first loop is at most 2, and the expected number of iterations of the nested while loop until i reaches t is at most 2t.

Write f i " denompw i q. To find the expected number of iterations of the outer loop on lines 7 to 13, we need the probability that gcdpf 1 , . . . , f t q " 1 given that each ST i A has full row rank r.

If gcdpf 1 , . . . , f t q ‰ 1, then there is some irreducible polynomial p which divides every denominator f 1 , . . . , f t . Because the T i 's are chosen independently of each other, the events "p divides f i " are pairwise independent; thus, according to lemma 3.3.8, the probability that any given irreducible polynomial p is such a common factor is at most pr{#Sq t´1 .

Chapter 3: Verification protocols for polynomial matrix operations

The degree of f 1 is at most rd A since ST i A is r ˆn with degree d A ; this also gives an upper bound on the number of distinct irreducible factors p of f 1 . Taking the union bound we see that the probability of any factor being shared by all denominators is at most r t d A p#Sq t´1 , which is at most 1 2 from the definition of t. Therefore the expected number of iterations of the outer loop is Op1q.

The stated cost bound follows from lemma 3.3.2. It does not involve t because we can see that t P Oplogprd A qq, which is subsumed by the soft-oh notation.

For the sake of simplicity in presentation, and because they do not affect the asymptotic cost bound, we have omitted a few optimizations to the Prover's algorithm that would be useful in practice, namely:

• The Prover can reduce to the full column rank case by computing a column rank profile of A once at the beginning (using Zhou (2012, Chapter 11)), and then removing corresponding non-pivot columns from A and v. This does not change the correctness, but means that each matrix ST i A is square.

• When each ST i A is square, computing w i can be done in a simpler way than by calling algorithm 1, as follows: check that ST i A is nonsingular to confirm the rank, and then use a fast linear system solver to obtain w i .

• The solution vectors w i may be re-used in the subprotocols FullRankRowSpace-Membership confirming that each f i v P RowSp Frxs pST i Aq.

We conclude the section by proving RowSpaceMembership is complete, sound, and efficient. As above, write d A " maxp1, degpAqq and d v " maxp1, degpvqq, and let r " rankpAq. Theorem 3.3.10. Assuming #S ě 2 minpm, nqd A , then Protocol 3.11 is a complete and probabilistically sound interactive protocol which requires Opn `md A t `dv tq communication and has Verifier cost Opmnd A t `nd v tq. If v P RowSp Frxs pAq, there is a Las Vegas randomized algorithm for the Prover with expected cost r Opmnr ω´2 d A `rω´1 d v q. Otherwise, the probability that the Verifier incorrectly accepts is at most p3rd A `dv `1q{#S.

Proof. For the communication, note that sending each C i has communication cost Opmq from lemma 3.3.7. Furthermore, the Verifier does not actually compute the products C i A, but rather uses these as a black box for matrix-vector products in the two subprotocols. For any scalar α P F, the complexity of computing C i Apαq times any vector of scalars on the left or right-hand side is Opmnd A q.

Along with the degree conditions on each f i and theorems 3.2.3, 3.2.4 and 3.3.3 and lemma 3.3.5, this proves the communication and Verifier cost claims.

The Prover's cost comes from lemma 3.3.9, which dominates the cost for the Prover in any of the subprotocols. Fact 3.5.4. Let K P Frxs nˆ . For any left kernel basis B P Frxs rˆn of K, we have ColSp Frxs pBq " Frxs rˆ1 . Lemma 3.5.5. Let A P Frxs mˆn have full row rank. Then, A is saturated if and only if ColSp Frxs pAq " Frxs mˆ1 .

Proof. If A is saturated, it is a basis of its own saturation since it has full row rank. Then writing K for a right kernel basis of A, by lemma 3.5.3, A is a left kernel basis of K. Then fact 3.5.4 gives ColSp Frxs pAq " Frxs mˆ1 .

Conversely, assume ColSp Frxs pAq " Frxs mˆ1 . Since the row space of A is a submodule of its saturation, we have A " U B where B P Frxs mˆn is a saturation basis of A and U P Frxs mˆm is nonsingular. By assumption, we have AV " I m for some V P Frxs nˆm , hence U pBV q " I m . Because these are all polynomial matrices, this means that U is unimodular, and A " U B implies that A is saturated.

We are now ready to state Protocol 3.17 for the certification that a matrix is saturated, assuming it has either full row rank or full column rank. The latter restriction is satisfied in all the applications we have in mind, including the two we present below (section 3.5.2): unimodular completability and kernel basis certification. We note that, if one accepts a communication cost similar to the size of the public matrix A, then removing this assumption is easily done by making use of a row basis of A. if m ď n: // full row rank RowSpaceSubset(I m , A ) else:

// full column rank RowSpaceSubset(I n , A) Theorem 3.5.6. Let d " maxp1, degpAqq, µ " maxpm, nq, and ν " minpm, nq. Protocol 3.17 is a probabilistically sound interactive protocol and is complete assuming #S ě 2µd in its subprotocol. It requires Opµd log µq communication and has Verifier cost Opmnd log µq. Assuming that A has full rank and is saturated, there is a Las Vegas randomized algorithm for the Prover with expected cost r Opµν ω´1 dq, and otherwise the probability that the Verifier incorrectly accepts is at most p4νd `2q{#S.

Proof. This directly follows from lemmas 3.5.2 and 3.5.5 and theorem 3.4.2. Remark that in both cases m ď n and m ą n, the protocol RowSpaceSubset is applied with public matrices I ν and a µ ˆν matrix of rank at most ν and degree at most d. and we show that our proposition compares favourably to the former is this model.

The article associated with this chapter is (Dumas et al., 2019a).

Outline

We start by presenting Strassen-Winograd algorithm and the competitor YTP-SS protocols in in Section 4.1. There, we also define the dedicated data layout and the cryptographic tools we will use. Next, in Section 4.2, we first describe our building block protocols, with their security analysis. Second, we present in this Section a new cubic-time matrix multiplication algorithm on ciphered entries to be used as a base case. Section 4.3 describes the complete novel sub-cubic MPC Strassen-Winograd algorithm and details its theoretical communication cost. In Section 4.4, we propose practical comparisons between our C++ and competitor implementations. Finally, in Section 4.5, we give an improved variant of our protocol using proxy re-encryption techniques and compare estimated runtimes of our protocols and fully-homomorphic cryptography-based ones. Finally, Strassen-Winograd algorithm involves numerous additions and subtractions on parts of the A and B matrices that are held by different players. Security concerns require then that these entries should be encrypted from the start, contrarily to (Dumas et al., 2017a). As a consequence, the classical matrix multiplication can no longer be used as stated in the latter reference, even for the base case of the recursive algorithm. We therefore propose an alternative base case. Its arithmetic cost is higher, but it involves an equivalent amount of communication. We shall show that this choice combined with our multiparty recursive Strassen-Winograd algorithm compares favourably to existing implementations in communication cost for matrices of dimensions larger than N " 96.

As Strassen-Winograd algorithm trades multiplications for additions, and as homomorphic additions are cheaper than multiplications, this algorithm is a very good candidate for a multiparty protocol using homomorphic techniques.

Hypotheses. In this chapter, we will only consider the case of semi-honest (also called honest-but-curious) adversaries. As a reminder, such adversaries, represented as probabilistic polynomial time machines, try to gather as many information as possible during the execution of the protocol, and can locally run any computation based on this information in order to deduce some private input. However, they strictly follow protocol specifications. We also consider that communications are performed over secure channels: this means transferred data is resistant to eavesdropping and that only the recipient will learn anything from communicated data.

Protocol 4.1: SW-Setup

Input: Two N ˆN matrices A and B over M, where N " b2 , such that party P i knows the i-th row of A and the i-th row B for all i P t1..N u. A location and a key sequence L P t1..N u N and K P t1..N u N such that pL, K, L, Kq form an -recursive data layout, following Definition 4.1.2. All parties know a security parameter λ. Output: For all i P t1..N u, party P Lris learns vectors ta i,˚uKris and tb i,˚uKris and learns the public key of every other party. Goal: Generate key pairs for each party, cipher and distribute input matrices according to their respective location and key sequences.

1. Key generation: for all i P t1..N u, each party P i locally executes NaccacheSternSetup(1 λ ) to generate a pair of keys (pk i , sk i ). 2. Broadcast keys: for all i P t1..N u, party P i broadcasts its public key pk i . Proof. We start by proving that both subprotocols MaskAndDecrypt (M &D) and Point-wiseProducts (P W P ) are secure against one semi-honest adversary.

Security of MaskAndDecrypt

MaskAndDecrypt is a 2-party protocol such that: output M &D pptb 1 u P 2 , s 1 q, ´q " p´, u 1 q, with b 1 " b k,˚, s 1 " s k , and u 1 " tu k,j u jPt1..nu . The proof is then divided in two parts: one for each corruption case. We labeled P 1 the player providing the seeds as input.

P 1 is corrupted: the view of P 1 is: view M &D P 1

" pt 1 , β 1 q. From the inputs of P 1 , the simulator is able to perfectly simulate the view of P 1 .

P 2 is corrupted: the view of P 2 is: view M &D P 2 " pβ 1 q. From the output u 1 of P 2 , the simulator S 2 ciphers each of its elements with the key of P 2 . From the IND-CPA security, the simulated view is computationally indistinguishable from the real one.

Security of PointwiseProducts

PointwiseProducts is a 4-party protocol. However, the 4 th player does not have any input nor output: only its public key is used. In the same vein, P 2 only sends s 2 and does not interact otherwise. Its view is empty, so that its simulator is trivial. Therefore, the proof is only divided in two parts. The output of the protocol is:

P 1 is corrupted: the view of P 1 is: view P W P P 1 " ps 2 , t 1 , δ 1 q. The simulator S 1 picks s 1 2 $ Ð Ý N and computes t 1 1 as in the protocol. Then, from the output and the input ta 1 u P 4 , it computes δ 1 " ˚ta 1 u t 1 1 P 4 component wise. Since the δ values are ciphered with the key of P 4 , and that s 1 is a random value, both views are indistinguishable. P 3 is corrupted: we have view P W P P 3 " pta 1 u P 4 , δ 1 q. S 3 : a 1 1 $ Ð Ý M, then the value is ciphered with the public key of P 4 to obtain ta 1 1 u P 4 . Next, it computes δ 1 1 as in protocol using the simulated value ta 1 1 u P 4 . This simulation is computationally indistinguishable from the real view thanks to the IND-CPA security of the cryptosystem.

We denote by F M &D (respectively F P W P ) the ideal functionalities associated to MaskAndDecrypt (resp. PointwiseProducts). We will now prove that if players shares a 0data-layout, BaseCase is secure against one semi-honest adversary in the pF M &D , F P W P qhybrid model.

Security of BaseCase

BaseCase is am N -party protocol, where the view depends on which group the player belongs. Since players share a 0-data-layout, there are four distinct possibilities: tL A , K A , L B , K B u. The cases where P K A ris or P L B ris is corrupted are trivial, since their respective view are empty in the pF M &D , F P W P q-hybrid model.

Protocol 4.8: SW-Finalise

Input: An N ˆN matrix tCu K C distributed and ciphered according to the location and key sequences pL C , K C q P pt1..N u N q 2 among parties P 1 , . . . , P N , following Definition 4.1.1. Output: Each party P K Cris learns the plaintext of the i-th row of C.

1. Exchange rows: For all i P t1..N u, party P L Cris send row i of C to party P K Cris . 2. Decipher vector: For all i P t1..N u, for all j P t1..N u, party P K Cris runs NaccacheSternDecrypt(sk K Cris , ptc i,j u K Cris q) and stores the output values in a vector c K Cris P M N .

4.3.3

Cost and security analysis

From Lemma 4.3.2 and Theorem 4.2.1, the recurrence relation for communication complexity of MP-SW writes:

The threshold at which the recursive algorithm should switch to the base case algorithm is set by finding at which dimension b does the base case algorithm start to perform worse than one recursive level. In terms of communication cost, this means the following equation: 7pp b 2 q 3 `3p b 2 q 2 `b 2 q `18p b 2 q 2 " b 3 `3b 2 `b which comes from injecting the base case cost of Theorem 4.2.1 into the recurrence formula. It gives a threshold of b " 56. Theorem 4.3.4. For N " b2 parties pP i q iPt1..N u and two matrices A, B P M N ˆN , such that party P i knows the i-th row of A and the i-th row B for all i P t1..N u, the execution in sequence of algorithms (SW-Setup; MP-SW; SW-Finalise), using the -recursive data layout of Equation (4.1.1), correctly computes C " A ˆB P M with Op7 b 3 q communications in Op q rounds and is secure against one semi-honest adversary. When b is constant, then " Oplog 2 pN qq, and the communication bound is OpN log 2 p7q q.

Proof. Correctness of MP-SW is given by Theorem 4.2.1 for the basecase and that of Strassen-Winograd algorithm (Section 4.1.1). Then SW-Setup is just the set up of the keys and initial encipherings, while SW-Finalise is the associated decipherings. Then, the communication bound stems from Theorem 4.2.1 and Equation (4.3.1), with 3N 2 communications for SW-Setup and SW-Finalise. The non-recursive parts of each recursive level of MP-SW require a constant number of rounds, and so does the execution of BaseCase, leading to a total of Op q rounds. For the security. again SW-Setup is just the communication of public keys and self-ciphered values, while SW-Finalise is also the communication of ciphered values to their legitimate locations. The other steps in MP-SW remain unchanged.

4.5.2

Communication cost analysis

We now perform the same analysis as the one from Section 4. We then compare the cost of proxy-based MP-SW to MP-PDP, with C MP-PDP pnq " n 3 ǹpn ´1q. The new initialisation step SW-Setup-Proxy costs C init " 2n 2 `2n , with the number of recursive levels, and the finalisation step SW-Finalise costs C final " n 2 . The crossover point where this variant improves over MP-PDP in communication cost is obtained by solving the equation: Cpnq `3n 2 `2n ď n 3 `npn ´1q which yields n ą 71, with one recursive call. This means that for any instance of dimension larger than 71, the proposed MP-SW algorithm has a better communication cost than MP-PDP, which also makes it better than the proxyless MP-SW. A complete run of Strassen-Winograd requires to perform N 2 encryptions, N decryptions for the input/output data, 7 3 ˆp N 4 q 3 `15 ˆp N 2 q 2 `7 ˆ15 ˆp N 4 q 2 additions and 7 2 ˆpN 4 q 3 multiplications (with 2 recursive levels, using the formulae from Section 4.3.3. MP-SW requires even more operations: 7 2 ˆp N 4 q 2 encryptions and decryptions from the base case (for the masking operations) and 6 ˆpN 2 q 2 `6 ˆ7 ˆp N 4 q 2 extra calls to MP-Copy (with 3 encryptions, 1 decryption and 2 additions per call). The proxy variant of MP-SW modifies this operation count once again: the cost of copy is reduced to one application of ProxyRecipher per call, which is equivalent to performing two modular exponentiations. Performing Decryptions and Additions is no longer needed, but there is an extra (though negligible) cost in the call to SW-Setup-Proxy, with four calls per player as our example runs over two recursive levels.

Table 4.1 shows that decryption is by far the most expensive operation for Naccache-Stern. In MP-SW, the amount of decryptions is equivalent to the amount of multiplications, OpN 2.8 q, which is not the case for fully homomorphic encryption (where it is OpN 2 q). Table 4.4 shows that our solution remains cheaper: MP-SW would take roughly 7 hours to perform over messages of 64-bit at λ " 130 against 88 hours for HElib. At 20-bit, MP-SW would roughly take 2 hours against the 190 hours of SEAL. Our proxy variant of MP-SW runs roughly 3 times slower than the vanilla version for 20-bit messages, because of the field size required for Castagnos-Laguillaumie. However, runtimes are equivalent with 64-bits messages, and given the rapid growth of Naccache-Stern operation cost, especially the discrete logarithms required for deciphering elements, the proxy variant should perform better than the vanilla one on larger message size.

While considering these timings, it is important to remember that we compare elementary arithmetic operations on both sides. An interesting extension on this estimation would be to consider linear algebra optimizations (vector and matrix products) for semi-and fully-homomorphic solutions.

Finally, in term of communication, it is worth noting that fully homomorphic ciphertexts are much more heavy than Naccache-Stern's: at λ " 112, roughly 264kb for SEAL, 360kb for HElib against only 5.14kb for Naccache-Stern. For matrices of order 224, sending and recovering the matrices to the trusted third party would then cost 3 ˆ224 2 ˆ264 " 5.1GB for SEAL and 6.9GB for HElib against the 2.4GB of MP-SW.