As CPU performance cannot keep up with the dramatic growth of the past few decades, CPU architects turn to domain-specific architectures to accelerate certain tasks. A recent trend is the introduction of matrix-multiplication accelerators to CPUs by manufacturers such as IBM, Intel and ARM, some of them yet to launch commercially. Apple’s systems-on-chip (SoCs) for its mobile phones, tablets and personal computers include a proprietary, undocumented CPU-coupled matrix multiplication coprocessor called AMX. We leverage AMX to accelerate the post-quantum lattice-based cryptosystems Saber and FrodoKEM, and benchmark their performance on Apple M1 and M3 SoCs. We propose a variant of the Toeplitz Matrix-Vector Product algorithm for polynomial multiplication, which sets new speed records for Saber using AMX, improving up to 20% for the main KEM operations, and 152% for matrix-vector multiplication of polynomials, over the current state-of-the-art. We also set new FrodoKEM speed records using AMX, gaining up to 21% for the main KEM operations and 124% for matrix multiplication (with further improvements for 4×-batching), over our optimized NEON implementation, also introduced here, which already improves upon the previous state-of-the-art for ARMv8 CPUs.

This paper presents a comprehensive study of the computation of square roots over finite extension fields. We propose two novel algorithms for computing square roots over even field extensions of the form${\BBF_{{q^2}}}$, with$q = {p^n}$,$p$an odd prime and$n \geq 1$. Both algorithms have an associate computational cost roughly equivalent to one exponentiation in${\BBF_{{q^2}}}$. The first algorithm is devoted to the case when$q \equiv 1\, {\rm mod}\, 4$, whereas the second one handles the case when$q \equiv 3\, {\rm mod}\,4$. Numerical comparisons show that the two algorithms presented in this paper are competitive and in some cases more efficient than the square root methods previously known.