A finite semifield is a division algebra over a finite field where multiplication is not necessarily associative. We consider here the complexity of the multiplication in small semifields and finite field extensions. For this operation, the number of required base field multiplications is the tensor rank, or the multiplicative complexity. The other base field operations are additions and scalings by constants, which together we refer to as the additive complexity. When used recursively, the tensor rank determines the exponent while the other operations determine the constant of the associated asymptotic complexity bounds. For small extensions, both measures are of similar importance.

This paper deals with simultaneously fast and in-place algorithms for formulae where the result has to be linearly accumulated: some output variables are also input variables, linked by a linear dependency. Fundamental examples include the in-place accumulated multiplication of polynomials or matrices, <?TeX $C\operatorname{\,{+}=\,}{AB}$?> Math 1 . The difficulty is to combine in-place computations with fast algorithms: those usually come at the expense of (potentially large) extra temporary space, but with accumulation the output variables are not even available to store intermediate values. We first propose a novel automatic design of fast and in-place accumulating algorithms for any bilinear formulae (and thus for polynomial and matrix multiplication) and then extend it to any linear accumulation of a collection of functions. For this, we relax the in-place model to any algorithm allowed to modify its inputs, provided that those are restored to their initial state afterwards. This allows us, in fine, to derive unprecedented in-place accumulating algorithms for fast polynomial multiplications and for Strassen-like matrix multiplications.

We consider the simultaneously fast and in-place computation of the Euclidean polynomial modular remainder <?TeX $R(X)\equiv {A(X)}\mod {B(X)}$?> Math 1 with A and B of respective degrees n and m ≤ n. Fast algorithms for this usually come at the expense of a linear amount of extra temporary space. In particular, they require to first compute and store the whole quotient Q(X) such that A = BQ + R.

We propose a non-commutative algorithm for multiplying 2x2 matrices using 7 coefficient products. This algorithm reaches simultaneously a better accuracy in practice compared to previously known such fast algorithms, and a time complexity bound with the best currently known leading term (obtained via alternate basis sparsification). To build this algorithm, we consider matrix and tensor norms bounds governing the stability and accuracy of numerical matrix multiplication. First, we reduce those bounds by minimizing a growth factor along the unique orbit of Strassen's 2x2-matrix multiplication tensor decomposition. Second, we develop heuristics for minimizing the number of operations required to realize a given bilinear formula, while further improving its accuracy. Third, we perform an alternate basis sparsification that improves on the time complexity constant and mostly preserves the overall accuracy.

Proofs of Retrievability are protocols which allow a Client to store data remotely and to efficiently ensure, via audits, that the entirety of that data is still intact. Dynamic Proofs of Retrievability (DPoR) also support efficient retrieval and update of any small portion of the data. We propose a novel protocol for arbitrary outsourced data storage that achieves both low remote storage size and audit complexity. A key ingredient, that can be also of intrinsic interest, reduces to efficiently evaluating a secret polynomial at given public points, when the (encrypted) polynomial is stored on an untrusted Server. The Server performs the evaluations and also returns associated certificates. A Client can check that the evaluations are correct using the certificates and some pre-computed keys, more efficiently than re-evaluating the polynomial. Our protocols support two important features: the polynomial itself can be encrypted on the Server, and it can be dynamically updated by changing individual coefficients cheaply without redoing the entire setup. Our methods rely on linearly homomorphic encryption and pairings, and our implementation shows good performance for polynomial evaluations with millions of coefficients, and efficient DPoR with terabytes of data. For instance, for a 1TB database, compared to the state of art, we can reduce the Client storage by 5000x, communication size by 20x, and client-side audit time by 2x, at the cost of one order of magnitude increase in server-side audit time.

In 1968, Liu described the problem of securing documents in a shared secret project. In an example, at least six out of eleven participating scientists need to be present to open the lock securing the secret documents. Shamir proposed a mathematical solution to this physical problem in 1979, by designing an efficient k-out-of- n secret sharing scheme based on Lagrange’s interpolation. Liu and Shamir also claimed that the minimal solution using physical locks is clearly impractical and exponential in the number of participants. In this paper we relax some implicit assumptions in their claim and propose an optimal physical solution to the problem of Liu that uses physical padlocks, but the number of padlocks is not greater than the number of participants. Then, we show that no device can do better for k-out-of- n threshold padlock systems as soon as [Formula: see text], which holds true in particular for Liu’s example. More generally, we derive bounds required to implement any threshold system and prove a lower bound of [Formula: see text] padlocks for any threshold larger than 2. For instance we propose an optimal scheme reaching that bound for 2-out-of- n threshold systems and requiring less than [Formula: see text] padlocks. We also discuss more complex access structures, a wrapping technique, and other sublinear realizations like an algorithm to generate 3-out-of- n systems with [Formula: see text] padlocks. Finally we give an algorithm building k-out-of- n threshold padlock systems with only [Formula: see text] padlocks. Apart from the physical world, our results also show that it is possible to implement secret sharing over small fields.

We present a non-commutative algorithm for the multiplication of a 2 × 2-block-matrix by its transpose using 5 block products (3 recursive calls and 2 general products) over C or any field of prime characteristic. We use geometric considerations on the space of bilinear forms describing 2 × 2 matrix products to obtain this algorithm and we show how to reduce the number of involved additions. The resulting algorithm for arbitrary dimensions is a reduction of multiplication of a matrix by its transpose to general matrix product, improving by a constant factor previously known reductions. Finally we propose schedules with low memory footprint that support a fast and memory efficient practical implementation over a prime field. To conclude, we show how to use our result in L · D · LT factorization.

Proof of Retrievability (PoR) and Provable Data Possession (PDP) schemes have been proposed to ensure the integrity of stored data on untrusted servers. A successful PoR audit ensures, with high probability, that every piece of stored data is recoverable by the server. Most PoR schemes proposed have focused on bandwidth and computation cost, but in some deployment scenarios the size of remote storage can be the most expensive factor. We propose a simple PoR scheme which is a variant on some existing PDP work. Compared to existing audit routines, the server computation cost and bandwidth are higher, but the server storage cost is minimal. Our preliminary work indicates that deploying this scheme may be less costly in commercial cloud settings, depending on the cost structure and frequency of audits.

We present new algorithms to detect and correct errors in the lower-upper factorization of a matrix, or the triangular linear system solution, over an arbitrary field. Our main algorithms do not require any additional information or encoding other than the original inputs and the erroneous output. Their running time is softly linear in the dimension times the number of errors when there are few errors, smoothly growing to the cost of fast matrix multiplication as the number of errors increases. We also present applications to general linear system solving.

We present a novel recursive algorithm for reducing a symmetric matrix to a triangular factorization which reveals the rank profile matrix. That is, the algorithm computes a factorization P TA P = L D L T where P is a permutation matrix, L is lower triangular with a unit diagonal and D is symmetric block diagonal with 1 x 1 and 2 x 2 antidiagonal blocks. This algorithm requires O(n2rømega-2) arithmetic operations, with n the dimension of the matrix, r its rank and ømega an admissible exponent for matrix multiplication. Furthermore, experimental results demonstrate that our algorithm has very good performance: its computational speed matches that of its numerical counterpart and is twice as fast as the unsymmetric exact Gaussian factorization. By adapting the pivoting strategy developed in the unsymmetric case, we show how to recover the rank profile matrix from the permutation matrix and the support of the block-diagonal matrix. We also note that there is an obstruction in characteristic 2 for revealing the rank profile matrix, which requires to relax the shape of the block diagonal by allowing the 2-dimensional blocks to have a non-zero bottom-right coefficient. This relaxed decomposition can then be transformed into a standard PLDLTP T decomposition at a negligible cost.

We present an interactive probabilistic proof protocol that certifies in (log N)O(1) arithmetic and Boolean operations for the verifier the determinant, for example, of an N x N matrix over a field whose entries a(i,j) are given by a single (log NO(1)-depth arithmetic circuit, which contains (log NO(1) field constants and which is polynomial time uniform, for example, which has size (log NO(1). The prover can produce the interactive certificate within a (log NO(1) factor of the cost of computing the determinant. Our protocol is a version of the proofs for muggles protocol by Goldwasser, Kalai and Rothblum [STOC 2008, J. ACM 2015]. An application is the following: suppose in a system of k homogeneous polynomials of total degree ≤ d in the k variables y1,...,yk the coefficient of the term y1e1 ... ykek in the i-th polynomial is the (hypergeometric) value ((i+e1 + ... + ek)!)/((i!)(e1!)...(ek!)), where e! is the factorial of e. Then we have a probabilistic protocol that certifies (projective) solvability or inconsistency of such a system in (k log(d))O(1) bit complexity for the verifier, that is, in polynomial time in the number of variables k and the logarithm of the total degree, log(d).

In this paper, we give novel certificates for triangular equivalence and rank profiles. These certificates enable to verify the row or column rank profiles or the whole rank profile matrix faster than recomputing them, with a negligible overall overhead. We first provide quadratic time and space non-interactive certificates saving the logarithmic factors of previously known ones. Then we propose interactive certificates for the same problems whose Monte Carlo verification complexity requires a small constant number of matrix-vector multiplications, a linear space, and a linear number of extra field operations. As an application we also give an interactive protocol, certifying the determinant of dense matrices, faster than the best previously known one.

International audience

Computational problem certificates are additional data structures for each output, which can be used by a---possibly randomized---verification algorithm that proves the correctness of each output. In this paper, we give an algorithm that computes a certificate for the minimal polynomial of sparse or structured matrices over an abstract field, of sufficiently large cardinality, whose Monte Carlo verification complexity requires a single matrix-vector multiplication and a linear number of extra field operations. We also propose a novel preconditioner that ensures irreducibility of the characteristic polynomial of the generically preconditioned matrix. This preconditioner takes linear time to be applied and uses only two random entries. We then combine these two techniques to give algorithms that compute certificates for the determinant, and thus for the characteristic polynomial, whose Monte Carlo verification complexity is therefore also linear.

International audience

Bini-Capovani-Lotti-Romani approximate formula (or border rank) for matrix multiplication achieves a better complexity than Strassen’s matrix multiplication formula. In this article, we show a novel way to use the approximate formula in the special case where the ring is Z / p Z . In addition, we show an implementation à la FFLAS--FFPACK, where p is a word-size modulo, that improves on state-of-the-art Z / p Z matrix multiplication implementations.

The row (resp. column) rank profile of a matrix describes the stair case shape of its row (resp. column) echelon form. In an ISSAC'13 paper, we proposed a recursive Gaussian elimination that can compute simultaneously the row and column rank profiles of a matrix, as well as those of all of its leading sub-matrices, in the same time as state of the art Gaussian elimination algorithms. Here we first study the conditions making a Gaussian elimination algorithm reveal this information. We propose the definition of a new matrix invariant, the rank profile matrix, summarizing all information on the row and column rank profiles of all the leading sub-matrices. We also explore the conditions for a Gaussian elimination algorithm to compute all or part of this invariant, through the corresponding PLUQ decomposition. As a consequence, we show that the classical iterative CUP decomposition algorithm can actually be adapted to compute the rank profile matrix. Used, in a Crout variant, as a base-case to our ISSAC'13 implementation, it delivers a significant improvement in efficiency. Second, the row (resp. column) echelon form of a matrix are usually computed via different dedicated triangular decompositions. We show here that, from some PLUQ decompositions, it is possible to recover the row and column echelon forms of a matrix and of any of its leading sub-matrices thanks to an elementary post-processing algorithm.

Auctions have a long history, having been recorded as early as 500 B.C. [Auction Theory, Academic Press, San Diego, USA, 2002]. Nowadays, electronic auctions have been a great success and are increasingly used in various applications, including high performance computing [Concurrency and Computatio n: Practice and Experience 14(13–15) (2002), 1507–1542]. Many cryptographic protocols have been proposed to address the various security requirements of these electronic transactions, in particular to ensure privacy. Brandt [International Journal of Information Security 5 (2006), 201–216] developed a protocol that computes the winner using homomorphic operations on a distributed ElGamal encryption of the bids. He claimed that it ensures full privacy of the bidders, i.e. no information apart from the winner and the winning price is leaked. We first show that this protocol – when using malleable interactive zero-knowledge proofs – is vulnerable to attacks by dishonest bidders. Such bidders can manipulate the publicly available data in a way that allows the seller to deduce all participants’ bids. We provide an efficient parallelized implementation of the protocol and the attack to show its practicality. Additionally we discuss some issues with verifiability as well as attacks on non-repudiation, fairness and the privacy of individual bidders exploiting authentication problems.

Certificates to a linear algebra computation are additional data structures for each output, which can be used by a---possibly randomized---verification algorithm that proves the correctness of each output. The certificates are essentially optimal if the time (and space) complexity of verification is essentially linear in the input size N, meaning N times a factor No(1), i.e., a factor Nη(N) with limN → ∞ η(N) = 0.

We study algorithms for the fast computation of modular inverses. Newton–Raphson iteration over$p$-adic numbers gives a recurrence relation computing modular inverse modulo${p^m}$, that is logarithmic in$m$. We solve the recurrence to obtain an explicit formula for the inverse. Then, we study different implementation variants of this iteration and show that our explicit formula is interesting for small exponent values but slower or large exponent, say of more than 700 bits. Overall, we thus propose a hybrid combination of our explicit formula and the best asymptotic variants. This hybrid combination yields then a constant factor improvement, also for large exponents.

Gaussian elimination with full pivoting generates a PLUQ matrix decomposition. Depending on the strategy used in the search for pivots, the permutation matrices can reveal some information about the row or the column rank profiles of the matrix. We propose a new pivoting strategy that makes it possible to recover at the same time both row and column rank profiles of the input matrix and of any of its leading sub-matrices. We propose a rank-sensitive and quad-recursive algorithm that computes the latter PLUQ triangular decomposition of an m x n matrix of rank r in O(mnrω-2) field operations, with ω the exponent of matrix multiplication. Compared to the LEU decomposition by Malashonock, sharing a similar recursive structure, its time complexity is rank sensitive and has a lower leading constant. Over a word size finite field, this algorithm also improves the practical efficiency of previously known implementations.

In this short note we study the semantics of two basic computational effects, exceptions and states, from a new point of view. In the handling of exceptions we dissociate the control from the elementary operation that recovers from the exception. In this way it becomes apparent that there is a duality, in the categorical sense, between exceptions and states.

International audience

We present algorithms and heuristics to compute the characteristic polynomial of a matrix given its minimal polynomial. The matrix is represented as a black-box, i.e., by a function to compute its matrix-vector product. The methods apply to matrices either over the integers or over a large enough finite field. Experiments show that these methods perform efficiently in practice. Combined in an adaptive strategy, these algorithms reach significant speedups in practice for some integer matrices arising in an application from graph theory.

We present an algorithm to perform a simultaneous modular reduction of several residues. This enables to compress polynomials into integers and perform several modular operations with machine integer arithmetic. The idea is to convert the X-adic representation of modular polynomials, with X an indeterminate, to a q-adic representation where q is an integer larger than the field characteristic. With some control on the different involved sizes it is then possible to perform some of the q-adic arithmetic directly with machine integers or floating points. Depending also on the number of performed numerical operations one can then convert back to the q-adic or X-adic representation and eventually mod out high residues. In this note we present a new version of both conversions: more tabulations and a way to reduce the number of divisions involved in the process are presented. The polynomial multiplication is then applied to arithmetic and linear algebra in small finite field extensions.

In the past two decades, some major efforts have been made to reduce exact (e.g. integer, rational, polynomial) linear algebra problems to matrix multiplication in order to provide algorithms with optimal asymptotic complexity. To provide efficient implementations of such algorithms one need to be careful with the underlying arithmetic. It is well known that modular techniques such as the Chinese remainder algorithm or the p -adic lifting allow very good practical performance, especially when word size arithmetic is used. Therefore, finite field arithmetic becomes an important core for efficient exact linear algebra libraries. In this article, we study high performance implementations of basic linear algebra routines over word size prime fields: especially matrix multiplication; our goal being to provide an exact alternate to the numerical BLAS library. We show that this is made possible by a careful combination of numerical computations and asymptotically faster algorithms. Our kernel has several symbolic linear algebra applications enabled by diverse matrix multiplication reductions: symbolic triangularization, system solving, determinant, and matrix inverse implementations are thus studied.

We deal with the computation of the characteristic polynomial of dense matrices over word size finite fields and over the integers. We first present two algorithms for finite fields: one is based on Krylov iterates and Gaussian elimination. We compare it to an improvement of the second algorithm of Keller-Gehrig. Then we show that a generalization of Keller-Gehrig's third algorithm could improve both complexity and computational time. We use these results as a basis for the computation of the characteristic polynomial of integer matrices. We first use early termination and Chinese remaindering for dense matrices. Then a probabilistic approach, based on integer minimal polynomial and Hensel factorization, is particularly well suited to sparse and/or structured matrices.

We consider a general linear dynamical system and want to control its behavior. The goal is to reach a given target by minimizing a cost function. We provide a new generic algorithm with together exact, symbolic and numerical modules. In particular new efficient methods computing a block Kalman canonical exact decomposition and the optimal solutions are presented. We also propose a new numerical algorithm under-approximating the controllable domain in view of its analytical resolution in the context of singular sub-arcs.

The FFLAS project has established that exact matrix multiplication over finite fields can be performed at the speed of the highly optimized numerical BLAS routines. Since many algorithms have been reduced to use matrix multiplication in order to be able to prove an optimal theoretical complexity, this paper shows that those optimal complexity algorithms, such as LSP factorization, rank determinant and inverse computation can also be the most efficient.

In this paper we study different implementations of finite field arithmetic, essential foundation of computer algebra. We focus on Galois fields of word size cardinality at most, with any characteristic. Classical representations as machine integers, floating point numbers, polynomials and Zech logarithms are compared. Furthermore, very efficient implementations of finite field dot products, matrix-vector products and matrix-matrix products (namely the symbolic equivalent of level 1, 2 and 3 BLAS) are presented. Our implementations have many symbolic linear algebra applications: symbolic triangularization, system solving, exact determinant computation, matrix normal form are such examples.

A new block algorithm for triangularization of regular or singular matrices with dimension m × n is proposed. Taking benefit of fast block multiplication algorithms, it achieves the best known sequential complexity Ο(mw-1n) for any sizes and any rank. Moreover, the block strategy enables to improve locality with respect to previous algorithms as exhibited by practical performances.

We present a new algorithm to compute the Integer Smith normal form of large sparse matrices. We reduce the computation of the Smith form to independent, and therefore parallel, computations modulo powers of word-size primes. Consequently, the algorithm does not suffer from coefficient growth. We have implemented several variants of this algorithm (Elimination and/or Black-Box techniques) since practical performance depends strongly on the memory available. Our method has proven useful in algebraic topology for the computation of the homology of some large simplicial complexes.