Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Guo, Qian LU ; Johansson, Thomas LU orcid and Nilsson, Alexander LU orcid (2019)
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Working paper/Preprint
publication status
published
subject
project
Side channels on software implementations of post-quantum cryptographic algorithms
language
English
LU publication?
yes
id
a448fb8c-873a-4080-9fa9-687015fc93f7
alternative location
https://eprint.iacr.org/2019/043
date added to LUP
2023-03-29 09:53:50
date last changed
2023-09-23 02:52:51
@misc{a448fb8c-873a-4080-9fa9-687015fc93f7,
  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<br/>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<br/>NIST Post-Quantum Proposal, ss-ntru-pke, that is attacked with complexity below the claimed security level.}},
  author       = {{Guo, Qian and Johansson, Thomas and Nilsson, Alexander}},
  language     = {{eng}},
  month        = {{01}},
  note         = {{Preprint}},
  title        = {{A Generic Attack on Lattice-based Schemes using Decryption Errors with Application to ss-ntru-pke}},
  url          = {{https://eprint.iacr.org/2019/043}},
  year         = {{2019}},
}