On the security of REDOG

Tanja Lange; Alex Pellegrini; Alberto Ravagnani

Paper 2023/1205

On the security of REDOG

Tanja Lange, Eindhoven University of Technology

Alex Pellegrini

, Eindhoven University of Technology

Alberto Ravagnani

, Eindhoven University of Technology

Abstract

We analyze REDOG, a public-key encryption system submitted to the Korean competition on post-quantum cryptography. REDOG is based on rank-metric codes. We prove its incorrectness and attack its implementation, providing an efficient message recovery attack. Furthermore, we show that the security of REDOG is much lower than claimed. We then proceed to mitigate these issues and provide two approaches to fix the decryption issue, one of which also leads to better security.

Note: Update: full version with corrected results and typos

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: post-quantum cryptography code-based- cryptography rank-metric codes
Contact author(s): tanja @ hyperelliptic org
alex pellegrini @ live com
a ravagnani @ tue nl
History: 2023-11-15: last of 2 revisions; 2023-08-08: received; See all versions
Short URL: https://ia.cr/2023/1205
License: CC0

BibTeX

@misc{cryptoeprint:2023/1205,
      author = {Tanja Lange and Alex Pellegrini and Alberto Ravagnani},
      title = {On the security of REDOG},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1205},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1205}},
      url = {https://eprint.iacr.org/2023/1205}
}