Paper 2021/1426

On Unpadded NTRU Quantum (In)Security

Théodore Conrad-Frenkiel, Rémi Géraud-Stewart, and David Naccache

Abstract

This paper utilizes the techniques used by Regev \cite{DBLP:journals/jacm/Regev09} and Lyubashevsky, Peikert \& Regev in the security reduction of LWE and its algebraic variants \cite{DBLP:conf/eurocrypt/LyubashevskyPR13} to exhibit a quantum reduction from the decryption of NTRU to leaking information about the secret key. Since this reduction requires decryption with the same key one wishes to attack, it renders NTRU vulnerable to the same type of attacks that affect the Rabin--Williams scheme \cite{DBLP:conf/eurocrypt/Bernstein08} -- albeit requiring a quantum decryption query. A common practice thwarting such attacks consists in applying the Fujisaki-Okamoto (FO, \cite{DBLP:conf/pkc/FujisakiO99}) transformation before encrypting. However, not all NTRU protocols enforce this protection. In particular the DPKE version of NTRU \cite{DBLP:conf/eurocrypt/SaitoXY18} is susceptible to such an attack.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
NTRUcryptanalysispost-quantum cryptography
Contact author(s)
david naccache @ ens fr
History
2021-10-24: received
Short URL
https://ia.cr/2021/1426
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1426,
      author = {Théodore Conrad-Frenkiel and Rémi Géraud-Stewart and David Naccache},
      title = {On Unpadded NTRU Quantum (In)Security},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1426},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1426}},
      url = {https://eprint.iacr.org/2021/1426}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.