Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

An upper bound on the decryption failure rate of static-key NewHope.

John M. Schanck

Published Jan 1, 2020• 1 citation
OpenAlex

Related papers

Breakdown Resilience of Key Exchange Protocols: NewHope, TLS 1.3, and Hybrids

Jacqueline Brendel, Marc Fischlin, Felix Günther

Lecture notes in computer science•Jan 1, 2019•16 citations

Lower and Upper Bounds for Deniable Public-Key Encryption

Rikke Bendlin, Jesper Buus Nielsen, Peter Sebastian Nordholt +1 more

Lecture notes in computer science•Jan 1, 2011•33 citations

Analysis of Error Dependencies on Newhope

Minki Song, Seunghwan Lee, Dong‐Joon Shin +3 more

Among many submissions to NIST post-quantum cryptography (PQC) project, NewHope is a promising key encapsulation mechanism (KEM) based on the Ring-Learning with errors (Ring-LWE) problem. Since NewHope is an indistinguishability (IND)-chosen ciphertext attack secure KEM by applying the Fujisaki-Okamoto transform to an IND-chosen plaintext attack secure public-key encryption, accurate calculation of decryption failure rate (DFR) is required to guarantee resilience against attacks that exploit decryption failures. However, the current upper bound (UB) on DFR of NewHope is rather loose because the compression noise, the effect of encoding/decoding of NewHope, and the approximation effect of centered binomial distribution are not fully considered. Furthermore, since NewHope is a Ring-LWE based cryptography, there is a problem of error dependency among error coefficients, which makes accurate DFR calculation difficult. In this paper, we derive much tighter UB on DFR than the current UB by using constraint relaxation and union bound. Especially, the above-mentioned factors are all considered in the derivation of new UB and the centered binomial distribution is not approximated. Since the error dependency is also considered, the new UB is much closer to the real DFR than the current UB. Furthermore, the new UB is parameterized by using Chernoff-Cramer bound to facilitate the calculation of new UB for the parameters of NewHope. Since the new UB is much lower than the DFR requirement of PQC, this DFR margin can be used to improve NewHope. As a result, the security level and bandwidth efficiency of NewHope are improved by 7.2 % and 5.9 %, respectively.

arXiv:1910.00432•IEEE Access•Jan 1, 2020•8 citations

public-Key Encryption Resilient to Randomness Leakage.

圭介 田中, Keisuke Tanaka, 均 並木 +3 more

•Jan 1, 2010•0 citations

CRYSTALS-Kyber With Lattice Quantizer

Shuiyin Liu, Amin Sakzad

Module Learning with Errors (M-LWE) based key reconciliation mechanisms (KRM) can be viewed as quantizing an M-LWE sample according to a lattice codebook. This paper describes a generic M-LWE-based KRM framework, valid for any dimensional lattices and any modulus$q$without a dither. Our main result is an explicit upper bound on the decryption failure rate (DFR) of M-LWE-based KRM. This bound allows us to construct optimal lattice quantizers to reduce the DFR and communication cost simultaneously. Moreover, we present a KRM scheme using the same security parameters$(q, k, \eta_{1}, \eta_{2})$as in Kyber. Compared with Kyber, the communication cost is reduced by up to 36.47% and the DFR is reduced by a factor of up to 299. The security arguments remain the same as Kyber.

arXiv:2401.15534•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•8 citations

Deterministic Public-Key Encryption Revisited.

Adam O’Neill

•Jan 1, 2010•13 citations
Among many submissions to NIST post-quantum cryptography (PQC) project, NewHope is a promising key encapsulation mechanism (KEM) based on the Ring-Learning with errors (Ring-LWE) problem. Since NewHope is an indistinguishability (IND)-chosen ciphertext attack secure KEM by applying the Fujisaki-Okamoto transform to an IND-chosen plaintext attack secure public-key encryption, accurate calculation of decryption failure rate (DFR) is required to guarantee resilience against attacks that exploit decryption failures. However, the current upper bound (UB) on DFR of NewHope is rather loose because the compression noise, the effect of encoding/decoding of NewHope, and the approximation effect of centered binomial distribution are not fully considered. Furthermore, since NewHope is a Ring-LWE based cryptography, there is a problem of error dependency among error coefficients, which makes accurate DFR calculation difficult. In this paper, we derive much tighter UB on DFR than the current UB by using constraint relaxation and union bound. Especially, the above-mentioned factors are all considered in the derivation of new UB and the centered binomial distribution is not approximated. Since the error dependency is also considered, the new UB is much closer to the real DFR than the current UB. Furthermore, the new UB is parameterized by using Chernoff-Cramer bound to facilitate the calculation of new UB for the parameters of NewHope. Since the new UB is much lower than the DFR requirement of PQC, this DFR margin can be used to improve NewHope. As a result, the security level and bandwidth efficiency of NewHope are improved by 7.2 % and 5.9 %, respectively.
Module Learning with Errors (M-LWE) based key reconciliation mechanisms (KRM) can be viewed as quantizing an M-LWE sample according to a lattice codebook. This paper describes a generic M-LWE-based KRM framework, valid for any dimensional lattices and any modulusqqqwithout a dither. Our main result is an explicit upper bound on the decryption failure rate (DFR) of M-LWE-based KRM. This bound allows us to construct optimal lattice quantizers to reduce the DFR and communication cost simultaneously. Moreover, we present a KRM scheme using the same security parameters(q,k,η1,η2)(q, k, \eta_{1}, \eta_{2})(q,k,η1​,η2​)as in Kyber. Compared with Kyber, the communication cost is reduced by up to 36.47% and the DFR is reduced by a factor of up to 299. The security arguments remain the same as Kyber.