On the security of REDOG

[Alex Pellegrini]

Dear All,

We thought we'd let you know that we uploaded the full version of our analysis
of REDOG on eprint: https://eprint.iacr.org/2023/1205.

The paper contains new estimates, based on the most recent approaches to the
rank decoding problem. In particular, [BBB+23] showed that some estimates from
[BBC+20] were too optimistic for the attacker. This results in much higher
security estimates for the same parameters for the fixed scheme, both for the
fix by the authors and by us.

A conference version of the paper will appear in the proceedings of ICISC 2023.

Best regards,
Alex with Alberto and Tanja

References:

BBB + 23. Magali Bardet, Pierre Briaud, Maxime Bros, Philippe Gaborit, and
Jean-Pierre Tillich. Revisiting algebraic attacks on minrank and on the rank
decoding problem. Designs, Codes and Cryptography, pages 1–37, 07 2023.

BBC + 20. Magali Bardet, Maxime Bros, Daniel Cabarcas, Philippe Gaborit, Ray A.
Perlner, Daniel Smith-Tone, Jean-Pierre Tillich, and Javier A. Verbel.
Improvements of algebraic attacks for solving the rank decoding and MinRank
problems. ASIACRYPT 2020.