How to backdoor LWE-like cryptosystems

Tobias Hemmert

Paper 2022/1381

How to backdoor LWE-like cryptosystems

Tobias Hemmert, Bundesamt für Sicherheit in der Informationstechnik

Abstract

We present a rather generic backdoor mechanism that can be applied to many LWE-like public-key cryptosystems. Our construction manipulates the key generation algorithm of such schemes in a way that allows a malicious adversary in possession of secret backdoor information to recover generated secret keys from corresponding public keys. To any user of the cryptosystem however, the output of our backdoored key generation is indistinguishable from output of the legitimate key generation algorithm. Our construction relies on elliptic-curve cryptography and draws on existing work on encoding of elliptic curve points as bit strings. Our backdoor mechanism can be applied to public-key cryptosystems where the secret key is generated from a secret seed and the public key includes a public seed of the same length. This holds - though not exclusively - for many cryptosystems based on LWE. In particular, we point out that our construction can be applied to backdoor HQC, FrodoKEM, Kyber and Dilithium. We also suggest a countermeasure that makes our backdoor detectable by users of the cryptosystem. To this end, we modify the key generation such that the public and secret key are pseudorandomly generated from a single seed which is included in the generated secret key. This allows any user of the key generation algorithm to regenerate keys using an independent implementation, making our backdooring attempt detectable.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Backdoor Public-Key Cryptography SETUP Elliptic-Curve Cryptography Post-Quantum Cryptography
Contact author(s): tobias hemmert @ bsi bund de
History: 2022-10-14: approved; 2022-10-12: received; See all versions
Short URL: https://ia.cr/2022/1381
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1381,
      author = {Tobias Hemmert},
      title = {How to backdoor LWE-like cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1381},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1381}},
      url = {https://eprint.iacr.org/2022/1381}
}