Practical algebraic attack on DAGS

DOI10.1007/978-3-030-25922-8_5MaRDI QIDQ6199260zbMATH OpenFDO

Authors Magali Bardet, Manon Bertin, Alain Couvreur, Ayoub Otmani

Publication date 23 February 2024

Published in Code-Based Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.03635

zbMATH Keywords

algebraic cryptanalysisdyadic alternant codeMcEliece cryptosystemquantum safe cryptography

Mathematics Subject Classification ID

Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60) Theory of error-correcting codes and error-detecting codes (94B99)

Abstract: DAGS scheme is a key encapsulation mechanism (KEM) based on quasi-dyadic alternant codes that was submitted to NIST standardization process for a quantum resistant public key algorithm. Recently an algebraic attack was devised by Barelli and Couvreur (Asiacrypt 2018) that efficiently recovers the private key. It shows that DAGS can be totally cryptanalysed by solving a system of bilinear polynomial equations. However, some sets of DAGS parameters were not broken in practice. In this paper we improve the algebraic attack by showing that the original approach was not optimal in terms of the ratio of the number of equations to the number of variables. Contrary to the common belief that reducing at any cost the number of variables in a polynomial system is always beneficial, we actually observed that, provided that the ratio is increased and up to a threshold, the solving can be heavily improved by adding variables to the polynomial system. This enables us to recover the private keys in a few seconds. Furthermore, our experimentations also show that the maximum degree reached during the computation of the Gr"obner basis is an important parameter that explains the efficiency of the attack. Finally, the authors of DAGS updated the parameters to take into account the algebraic cryptanalysis of Barelli and Couvreur. In the present article, we propose a hybrid approach that performs an exhaustive search on some variables and computes a Gr"obner basis on the polynomial system involving the remaining variables. We then show that the updated set of parameters corresponding to 128-bit security can be broken with 2^83 operations.

Recommendations

• An efficient structural attack on NIST submission DAGS
• DAGS: reloaded revisiting dyadic key encapsulation
• DAGS: key encapsulation using dyadic GS codes
• Structural cryptanalysis of McEliece schemes with compact keys
• Algebraic cryptanalysis of McEliece variants with compact keys

Cited in

(5)

• Improvement of algebraic attacks for solving superdetermined MinRank instances
• Software implementation of a code-based key encapsulation mechanism from binary QD generalized Srivastava codes
• DAGS: reloaded revisiting dyadic key encapsulation
• Hadamard square of series connected linear codes
• Hadamard square of linear codes and the generalized minimal distance of Reed-Muller code of order 2

This page was built for publication: Practical algebraic attack on DAGS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199260)