Paper 2024/835
Provable security against decryption failure attacks from LWE
, Technical University of Denmark, Technical University of DenmarkAbstract
In a recent work, Hövelmanns, Hülsing and Majenz introduced a new security proof for the Fujisaki-Okamoto transform in the quantum-accessible random oracle model (QROM) used in post-quantum key encapsulation mechanisms. While having a smaller security loss due to decryption failures present in many constructions, it requires two new security properties of the underlying public-key encryption scheme (PKE). In this work, we show that one of the properties, Find Failing Plaintexts - Non Generic (FFP-NG) security, is achievable using a relatively efficient LWE-based PKE that does not have perfect correctness. In particular, we show that LWE reduces to breaking FFP-NG security of the PVW scheme, when all LWE errors are discrete Gaussian distributed. The reduction has an arbitrarily small constant multiplicative loss in LWE error size. For the proof, we make use of techniques by Genise, Micciancio, Peikert and Walter to analyze marginal and conditional distributions of sums of discrete Gaussians.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- LWEFFP-NGdiscrete gaussians
- Contact author(s)
-
chmaj @ dtu dk
fasi @ dtu dk - History
- 2024-05-31: approved
- 2024-05-28: received
- See all versions
- Short URL
- https://ia.cr/2024/835
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/835,
author = {Christian Majenz and Fabrizio Sisinni},
title = {Provable security against decryption failure attacks from {LWE}},
howpublished = {Cryptology ePrint Archive, Paper 2024/835},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/835}},
url = {https://eprint.iacr.org/2024/835}
}
