Attack on LAC Key Exchange in Misuse Situation

Aurelien Greuet; Simon Montoya; Guenael Renault

Paper 2020/063

Attack on LAC Key Exchange in Misuse Situation

Aurelien Greuet, Simon Montoya, and Guenael Renault

Abstract

LAC is a Ring Learning With Error based cryptosystem that has been proposed to the NIST call for post-quantum standardization and passed the first round of the submission process. The particularity of LAC is to use an error-correction code ensuring a high security level with small key sizes and small ciphertext sizes. LAC team proposes a CPA secure cryptosystem, LAC.CPA, and a CCA secure one, LAC.CCA, obtained by applying the Fujisaki-Okamoto transformation on LAC.CPA. In this paper, we study the security of LAC Key Exchange (KE) mechanism, using LAC.CPA, in a misuse context: when the same secret key is reused for several key exchanges and an active adversary has access to a mismatch oracle. This oracle indicates information on the possible mismatch at the end of the KE protocol. In this context, we show that an attacker needs at most $8$ queries to the oracle to retrieve one coefficient of a static secret key. This result has been experimentally confirmed using the reference and optimized implementations of LAC. Since our attack can break the CPA version in a misuse context, the Authenticated KE protocol, based on the CCA version, is not impacted. However, this research provides a tight estimation of LAC resilience against this type of attacks.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: lattice based cryptography post-quantum cryptography active attack key reuse
Contact author(s): aurelien greuet @ idemia com
simon montoya @ idemia com
guenael renault @ lix polytechnique fr
History: 2020-01-21: received
Short URL: https://ia.cr/2020/063
License: CC BY

BibTeX

@misc{cryptoeprint:2020/063,
      author = {Aurelien Greuet and Simon Montoya and Guenael Renault},
      title = {Attack on LAC Key Exchange in Misuse Situation},
      howpublished = {Cryptology ePrint Archive, Paper 2020/063},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/063}},
      url = {https://eprint.iacr.org/2020/063}
}