Search results for Linear Algebra

Jules Maire, Damien VergnaudPublished 20240409 Show abstract PDF
We present new secure multiparty computation protocols for linear algebra over a finite field, which improve the stateoftheart in terms of security. We look at the case of unconditional security with perfect correctness, i.e., informationtheoretic security without errors. We notably propose an expected constantround protocol for solving systems of m linear equations in n variables over Fq with expected complexity O(k n^2.5 + k m) (where complexity is measured in terms of the number of secure multiplications required) with k > m(m+n)+1. The previous proposals were not errorfree: known protocols can indeed fail and thus reveal information with probability Omega(poly(m)/q). Our protocols are simple and rely on existing computeralgebra techniques, notably the PreparataSarwate algorithm, a simple but poorly known “babystep giantstep” method for computing the characteristic polynomial of a matrix, and techniques due to Mulmuley for errorfree linear algebra in positive characteristic.

Subhadeep Banik, Andrea Caforio, Serge VaudenayPublished 20240409 Show abstract PDF
The LowMC family of block ciphers was proposed by Albrecht et al. in Eurocrypt 2015, specifically targeting adoption in FHE and MPC applications due to its low multiplicative complexity. The construction operates a 3bit quadratic Sbox as the sole nonlinear transformation in the algorithm. In contrast, both the linear layer and round key generation are achieved through multiplications of full rank matrices over GF(2). The cipher is instantiable using a diverse set of default configurations, some of which have partial nonlinear layers i.e., in which the Sboxes are not applied over the entire internal state of the cipher.
The significance of cryptanalysing LowMC was elevated by its inclusion into the NIST PQC digital signature scheme PICNIC in which a successful key recovery using a single plaintext/ciphertext pair is akin to retrieving the secret signing key. The current stateoftheart attack in this setting is due to Dinur at Eurocrypt 2021, in which a novel way of enumerating roots of a Boolean system of equation is morphed into a keyrecovery procedure that undercuts an ordinary exhaustive search in terms of time complexity for the variants of the cipher up to five rounds.
In this work, we demonstrate that this technique can efficiently be enriched with a specific linearization strategy that reduces the algebraic degree of the nonlinear layer as put forward by Banik et al. at IACR ToSC 2020(4). This amalgamation yields new attacks on certain instances of LowMC up to seven rounds.

Décio Luiz Gazzoni Filho, Guilherme Brandão, Julio LópezPublished 20240409 Show abstract PDF
Efficient polynomial multiplication routines are critical to the performance of latticebased postquantum cryptography (PQC). As PQC standards only recently started to emerge, CPUs still lack specialized instructions to accelerate such routines. Meanwhile, deep learning has grown immeasurably in importance. Its workloads call for teraflopslevel of processing power for linear algebra operations, mainly matrix multiplication. Computer architects have responded by introducing ISA extensions, coprocessors and specialpurpose cores to accelerate such operations. In particular, Apple ships an undocumented matrixmultiplication coprocessor, AMX, in hundreds of millions of mobile phones, tablets and personal computers. Our work repurposes AMX to implement polynomial multiplication and applies it to the NTRU cryptosystem, setting new speed records on the Apple M1 and M3 systemsonchip (SoCs): polynomial multiplication, key generation, encapsulation and decapsulation are sped up by $1.54$–$3.07\times$, $1.08$–$1.33\times$, $1.11$–$1.50\times$ and $1.20$–$1.98\times$, respectively, over the previous stateoftheart.