HQC is a quantum-resistant cryptographic key encapsulation mechanism, recently selected by NIST as a future standard. Polynomial multiplication is one of the most critical operations in HQC. Due to side-channel security concerns, the previously-used sparse-dense method was recently replaced by classical dense-dense multiplication implemented using Karatsuba’s algorithm. This change has made polynomial multiplication the primary performance bottleneck, accounting for approximately 95% of the total execution time. This paper presents an alternative polynomial multiplication technique for HQC: the Frobenius Additive Fast Fourier Transform (FAFFT), which provides significant algorithmic-level performance improvements. We also present ANDROMEDA, the first state-of-the-art hardware implementation of FAFFT, and evaluate its performance impact by integrating our solution in a resourceconstrained RISC-V-based System-on-Chip scenario. Experimental results show that our solution improves HQC performance by approximately $9.64 \times$ and $19.22 \times$ across its security levels, making HQC more practical for real-world deployment.

While CVE have become a de facto standard for publishing advisories on vulnerabilities, the state of current CVE databases is lackluster. Yet, CVE advisories are insufficient to bridge the gap with the vulnerability artifacts in the impacted program. Therefore, the community is lacking a public real-world vulnerabilities dataset providing such association. In this paper, we present a method restoring this missing link by analyzing the vulnerabilities from the AOSP, an aggregate of more than 1,800 projects. It is the perfect target for building a representative dataset of vulnerabilities, as it covers the full spectrum that may be encountered in a modern system where a variety of low-level and higher-level components interact. More specifically, our main contribution is a dataset of more than 1,900 vulnerabilities, associating generic metadata (e.g. vulnerability type, impact level) with their respective patches at the commit granularity (e.g. fix commit-id, affected files, source code language). Finally, we also augment this dataset by providing precompiled binaries for a subset of the vulnerabilities. These binaries open various data usage, both for binary only analysis and at the interface between source and binary. In addition of providing a common baseline benchmark, our dataset release supports the community for data-driven software security research.

The NIST selection process for standardizing Post-Quantum Cryptography Mechanisms is currently running. Many papers already studied their theoretical security, but the resistance in deployed device has not been much investigated so far. In particular, fault attack is a serious threat for algorithms implemented in embedded devices. One particularly powerful technique is to use safe-error attacks. Such attacks exploit the fact that a specific fault may or may not lead to a faulty output depending on a secret value. In this paper, we investigate the resistance of various Post-Quantum candidates algorithms against such attacks.

The usual algorithm to solve polynomial systems using Gröbner bases consists of two steps: first computing the DRL Gröbner basis using the F5 algorithm then computing the LEX Gröbner basis using a change of ordering algorithm. When the Bézout bound is reached, the bottleneck of the total solving process is the change of ordering step. For 20 years, thanks to the FGLM algorithm the complexity of change of ordering is known to be cubic in the number of solutions of the system to solve.

In this article, we present new results about the computation of a general shape of a triangular basis generating the splitting ideal of an irreducible polynomial given with the permutation representation of its Galois group G. We provide some theoretical results and a new general algorithm based on the study of the non redundant bases of permutation groups. These new results deeply increase the efficiency of the computation of the splitting field of a polynomial.

Let f be a univariate monic integral polynomial of degree n and let (α1, ..., αn) be an n-tuple of its roots in an algebraic closure Q of Q. Obtaining an algebraic representation of the splitting field Q(α1, ..., αn) of f is a question of first importance in effective Galois theory. For instance, it allows us to manipulate symbolically the roots of f. In this paper, we propose a new method based on multi-modular strategy. Actually, we provide algorithms for this task which return a triangular set encoding the splitting ideal of f. We examine the ability/practicality of the method by experiments on a real computer and study its complexity.

International audience