Classic McEliece is one of the most promising public key encryption schemes in the NIST PQC Round 4. Thus, there are many researches on cryptanalysis of this cryptosystem. In particular, Hemmert et al. (PQCrypto 2022) proposed a backdoor mechanism for (Classic) McEliece and proved that it is possible to embed a backdoor into this cryptosystem in a single-user setting where a single backdoor holder can embed a backdoor into a cryptosystem. In addition, they also presented how to prevent this backdoor mechanism. In this paper, we prove that this backdoor mechanism for (Classic) McEliece is valid in a multi-user setting where multiple users are allowed to use the backdoor mechanism against (Classic) McEliece. This indicates that backdoor holders can embed a backdoor into Classic McEliece in a more practical security model. Furthermore, we also give a slight variant of (Classic) McEliece so that we can prevent the backdoor mechanism in the multi-user setting.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Analysis of Backdoored (Classic) McEliece in a Multi-user Setting

  • Dai Miura,
  • Hyungrok Jo,
  • Shingo Sato,
  • Junji Shikata

摘要

Classic McEliece is one of the most promising public key encryption schemes in the NIST PQC Round 4. Thus, there are many researches on cryptanalysis of this cryptosystem. In particular, Hemmert et al. (PQCrypto 2022) proposed a backdoor mechanism for (Classic) McEliece and proved that it is possible to embed a backdoor into this cryptosystem in a single-user setting where a single backdoor holder can embed a backdoor into a cryptosystem. In addition, they also presented how to prevent this backdoor mechanism. In this paper, we prove that this backdoor mechanism for (Classic) McEliece is valid in a multi-user setting where multiple users are allowed to use the backdoor mechanism against (Classic) McEliece. This indicates that backdoor holders can embed a backdoor into Classic McEliece in a more practical security model. Furthermore, we also give a slight variant of (Classic) McEliece so that we can prevent the backdoor mechanism in the multi-user setting.