Paper 2018/1172

The impact of error dependencies on Ring/Mod-LWE/LWR based schemes

Jan-Pieter D'Anvers, Frederik Vercauteren, and Ingrid Verbauwhede

Abstract

Current estimation techniques for the probability of decryption failures in Ring/Mod-LWE/LWR based schemes assume independence of the failures in individual bits of the transmitted message to calculate the full failure rate of the scheme. In this paper we disprove this assumption both theoretically and practically for schemes based on Ring/Mod-Learning with Errors/Rounding. We provide a method to estimate the decryption failure probability, taking into account the bit failure dependency. We show that the independence assumption is suitable for schemes without error correction, but that it might lead to underestimating the failure probability of algorithms using error correcting codes. In the worst case, for LAC-128, the failure rate is $2^{48}$ times bigger than estimated under the assumption of independence. This higher-than-expected failure rate could lead to more efficient cryptanalysis of the scheme through decryption failure attacks.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. PQCrypto 2019
Keywords
Lattice cryptographyRing-LWEError Correcting CodesDecryption Failures
Contact author(s)
janpieter danvers @ esat kuleuven be
History
2019-02-20: last of 2 revisions
2018-12-03: received
See all versions
Short URL
https://ia.cr/2018/1172
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1172,
      author = {Jan-Pieter D'Anvers and Frederik Vercauteren and Ingrid Verbauwhede},
      title = {The impact of error dependencies on Ring/Mod-{LWE}/{LWR} based schemes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/1172},
      year = {2018},
      url = {https://eprint.iacr.org/2018/1172}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.