In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case NP search problem of finding a solution to a system of (underdetermined) constant degree multivariate equations over the finite field \(\mathbb{F}_2\) drawn from a specified distribution. In particular, for any \(d \ge 2\), we design a distribution of degree up to \(d\) polynomials \(\{p_i(x_1,\ldots,x_n)\}_{i\in[m]}\) for \(m \lt n\) over \(\mathbb{F}_2\) for which we show that there is an expected polynomial-time quantum algorithm that provably simultaneously solves \(\{p_i(x_1,\ldots,x_n) = y_i\}_{i\in[m]}\) for a random vector \((y_1,\ldots,y_m)\). On the other hand, while solutions exist with high probability, we conjecture that for constant \(d \gt 2\), it is classically hard to find one based on a thorough review of existing classical cryptanalysis. Our work thus posits that degree three functions are enough to instantiate the random oracle to obtain non-relativized quantum advantage.

In this paper, we revisit the Rank Quasi-Cyclic (RQC) (Melchor et al., IEEE IT, 2018) encryption scheme by proposing three possible variations for its design. Our first improvement relies on the introduction of Augmented Gabidulin codes, a new family of decodable codes exploiting the concept of support erasure for the rank metric. Following the work of Melchor et al. (PQCrypto, 2022), our second improvement uses multiple syndromes to increase the weight of the error to be decoded. As pioneered in Melchor et al. (NIST PQC, 2020), our third variation considers non-homogeneous error weights in order to decrease the parameters. These improvements can be combined together to design schemes offering various trade-offs in term of security and size. Our Multi-UR-AG (multiple syndromes, unstructured, augmented Gabidulin) scheme achieves a size of 11kB (public key + ciphertext) for 128 bits of security while featuring a conservative design as it relies on pure random instances without any ideal structure. Besides, our NH- Multi-RQC-AG (non-homogeneous error, multiple syndromes, ideal structure, augmented Gabidulin) achieves a size of 2.7 kB for 128 bits of security, namely a 50 % improvement with respect to classical RQC. Our second and third variations respectively rely on the security of the$\textsf {RSL} $and$\textsf {NHRSD} $problems (or$\textsf {NHRSL} $when considered together). In this paper, we also provide new security analysis and attacks for these problems. While these results are important for our new schemes, they are of independent interest as well. Our security analysis for the$\textsf {RSL} $problem provides an improvement on the recent algebraic attacks for some instances. In addition, we show that the$\textsf {RSL} $problem can be solved in polynomial time when$N \geq (k+1) r\frac {m}{m-r}$, this improves the best known combinatorial attack (Gaborit et al., Crypto, 2017). We also propose the first combinatorial attack against the$\textsf {NHRSD} $problem along with a precise complexity analysis of the algebraic attack described Melchor et al. (NIST PQC, 2020). At last, we combine these analysis to provide an attack against the$\textsf {NHRSL} $problem.

International audience