A Generic Attack on Lattice-based Schemes using Decryption Errors with Application to ss-ntru-pke
(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:
https://lup.lub.lu.se/record/a448fb8c-873a-4080-9fa9-687015fc93f7
- author
- Guo, Qian LU ; Johansson, Thomas LU and Nilsson, Alexander LU
- organization
- publishing date
- 2019-01-18
- 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}}, }