Paper 2019/043

A Generic Attack on Lattice-based Schemes using Decryption Errors with Application to ss-ntru-pke

Qian Guo, Thomas Johansson, and Alexander Nilsson

Abstract

Hard learning problems are central topics in recent cryptographic research. Many cryptographic primitives relate their security to difficult problems in lattices, such as the shortest vector problem. Such schemes include the possibility of decryption errors with some very small probability. In this paper we propose and discuss a generic attack for secret key recovery based on generating decryption errors. In a standard PKC setting, the model first consists of a precomputation phase where special messages and their corresponding error vectors are generated. Secondly, the messages are submitted for decryption and some decryption errors are observed. Finally, a phase with a statistical analysis of the messages/errors causing the decryption errors reveals the secret key. The idea is that conditioned on certain secret keys, the decryption error probability is significantly higher than the average case used in the error probability estimation. The attack is demonstrated in detail on one NIST Post-Quantum Proposal, ss-ntru-pke, that is attacked with complexity below the claimed security level.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Lattice-based cryptographyNIST post-quantum standardizationdecryption errorLWENTRUReaction attack.
Contact author(s)
qian guo @ uib no
History
2019-01-18: received
Short URL
https://ia.cr/2019/043
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/043,
      author = {Qian Guo and Thomas Johansson and Alexander Nilsson},
      title = {A Generic Attack on Lattice-based Schemes using Decryption Errors with Application to ss-ntru-pke},
      howpublished = {Cryptology ePrint Archive, Paper 2019/043},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/043}},
      url = {https://eprint.iacr.org/2019/043}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.