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

Logic Journal of IGPL

A modification proposal for the reconciliation mechanism of the key exchange algorithm NewHope

Víctor Gayoso Martínez, Luis Hernández Encinas, A Martín Muñoz

Published Feb 16, 2022• 6 citations
Publisher

Abstract

Abstract The latest advances in quantum computing forced the National Institute of Standards and Technology (NIST) to launch an initiative for selecting quantum-resistant cryptographic algorithms. One of the best-known proposals is NewHope, an algorithm that was initially designed as a key exchange algorithm. In its original design, NewHope presented a reconciliation mechanism that is complex and represents an entry barrier for potential implementers. This contribution presents equivalent schemes in one, two and three dimensions, which allow anyone to make the transition to the 4D NewHope algorithm easier to undertake. In addition to that, the effect of modifying some of the parameters associated to NewHope’s reconciliation mechanism is studied, which has allowed us to propose different sets of parameters that could increase the security of NewHope implementations.

DOI
10.1093/jigpal/jzac011

Related papers

Tight Bound on NewHope Failure Probability

Thomas Plantard, Arnaud Sipasseuth, Willy Susilo +1 more

NewHopeKey Encapsulation Mechanism (KEM) has been presented at USENIX 2016 by Alkimet al.and was one of the lattice-based candidates to the post-quantum standardization initiated by the NIST. However, despite the relative simplicity of the protocol, the bound on the decapsulation failure probability resulting from the original analysis is not tight. In this work we refine this analysis to get a tight upper-bound on this probability which happens to be much lower than what was originally evaluated. As a consequence, we propose a set of alternative parameters, increasing the security and the compactness of the scheme. However using a smaller modulus prevent the use of a full NTT algorithm to perform multiplications of elements in dimension 512 or 1024. Nonetheless, similarly to previous works, we combine different multiplication algorithms and show that our new parameters are competitive on a constant time vectorized implementation. Our most compact parameters bring a speed-up of$17\%$(resp.$11\%$) in performance but allow to gain more than$19\%$over the bandwidth requirements and to increase the security of$10\%$(resp.$7\%$) in dimension 512 (resp. 1024).

IEEE Transactions on Emerging Topics in Computing•Jan 5, 2022•5 citations

Quantum resistant cryptography: Survey of NIST third round candidates and real world implementation

Aarushi Dua, Anubhav Gupta, Bhawana Pujasani Hettiarachchi

The emergence of quantum computing poses a significant threat to classical encryption techniques, rendering them vulnerable to powerful algorithms proposed to be used in quantum computers. In response to this, the National Institute of Standards and Technology (NIST) initiated a standardization process to streamline quantum resistant cryptographic algorithms. This work surveys the three algorithms selected to move onto the 4th round and one selected for standardization by the National Institute of Standards and Technology (NIST). In addition to this, our work also discusses some real-life implementations of quantum-resistant algorithms like the PQXDH algorithm and an approach implemented by Microsoft, as a step towards a quantum-resistant future.

AIP conference proceedings•Jan 1, 2025•0 citations

Analysis of BCNS and Newhope Key-exchange Protocols

Seyedamirhossein Hesamian

Lattice-based cryptographic primitives are believed to offer resilience against attacks by quantum computers. Following increasing interest from both companies and government agencies in building quantum computers, a number of works have proposed instantiations of practical post-quantum key-exchange protocols based on hard problems in lattices, mainly based on the Ring Learning With Errors (R-LWE) problem.\nIn this work we present an analysis of Ring-LWE based key-exchange mechanisms and compare two implementations of Ring-LWE based key-exchange protocol: BCNS and NewHope. This is important as NewHope protocol implementation outperforms state-of-the art elliptic curve based Diffie-Hellman key-exchange X25519, thus showing that using quantum safe key-exchange is not only a viable option but also a faster one. Specifically, this thesis compares different reconciliation methods, parameter choices, noise sampling algorithms and performance.

•Jan 1, 2017•1 citation

Comparison analysis of Ding's RLWE-based key exchange protocol and NewHope variants

Xinwei Gao

In this paper, we present a comparison study on three RLWE key exchange protocols: one from Ding et al. in 2012 (DING12) and two from Alkim et al. in 2016 (NewHope and NewHope-Simple). We compare and analyze protocol construction, notion of designing and realizing key exchange, signal computation, error reconciliation and cost of these three protocols. We show that NewHope and NewHope-Simple share very similar notion as DING12 in the sense that NewHope series also send small additional bits with small size (i.e. signal) to assist error reconciliation, where this idea was first practically proposed in DING12. We believe that DING12 is the first work that presented complete LWE & RLWE-based key exchange constructions. The idea of sending additional information in order to realize error reconciliation and key exchange in NewHope and NewHope-Simple remain the same as DING12, despite concrete approaches to compute signal and reconcile error are not the same.

Advances in Mathematics of Communications•Jan 1, 2019•3 citations

Best-Fit Dual Signatures for PQ Transition

Kunal Meher, Divya Midhunchakkaravarthy

Post Quantum Cryptography (sometimes referred to as a quantum-proof, quantum-safe or quantum-resistant) refers to cryptographic algorithms (usually public-key algorithms) that are thought to be secure against an attack by a quantum computer. PQC is all about preparing for the era of quantum computing by updating existing mathematical-based algorithms and standards. The cryptographic community is working on post-quantum cryptography in order to provide alternatives using hard mathematical problems that cannot be broken by quantum computers. A hybrid scheme is recommended to ease the transition into the post-quantum era. A hybrid scheme is a combination of a traditional and a post-quantum scheme. The resulting scheme is at least as secure as one of the schemes used. In hybrid key establishment, two independent key exchanges are performed one with a traditional scheme like ECDHE and one with a post-quantum scheme like NewHope [1]. In this paper, we propose possible best-fit hybrid digital signatures.

Biennial International Conference on Nascent Technologies in Engineering (ICNTE)•Jan 15, 2021•1 citation

A Survey of Post-Quantum Cryptography: Start of a New Race

Duc-Thuan Dam, Thai-Ha Tran, Van‐Phuc Hoang +2 more

Information security is a fundamental and urgent issue in the digital transformation era. Cryptographic techniques and digital signatures have been applied to protect and authenticate relevant information. However, with the advent of quantum computers and quantum algorithms, classical cryptographic techniques have been in danger of collapsing because quantum computers can solve complex problems in polynomial time. Stemming from that risk, researchers worldwide have stepped up research on post-quantum algorithms to resist attack by quantum computers. In this review paper, we survey studies in recent years on post-quantum cryptography (PQC) and provide statistics on the number and content of publications, including a literature overview, detailed explanations of the most common methods so far, current implementation status, implementation comparisons, and discussion on future work. These studies focused on essential public cryptography techniques and digital signature schemes, and the US National Institute of Standards and Technology (NIST) launched a competition to select the best candidate for the expected standard. Recent studies have practically implemented the public key encryption/key encapsulation mechanism (PKE/KEM) and digital signature schemes on different hardware platforms and applied various optimization measures based on other criteria. Along with the increasing number of scientific publications, the recent trend of PQC research is increasingly evident and is the general trend in the cryptography industry. The movement opens up a promising avenue for researchers in public key cryptography and digital signatures, especially on algorithms selected by NIST.

Cryptography•Aug 14, 2023•228 citations
Abstract The latest advances in quantum computing forced the National Institute of Standards and Technology (NIST) to launch an initiative for selecting quantum-resistant cryptographic algorithms. One of the best-known proposals is NewHope, an algorithm that was initially designed as a key exchange algorithm. In its original design, NewHope presented a reconciliation mechanism that is complex and represents an entry barrier for potential implementers. This contribution presents equivalent schemes in one, two and three dimensions, which allow anyone to make the transition to the 4D NewHope algorithm easier to undertake. In addition to that, the effect of modifying some of the parameters associated to NewHope’s reconciliation mechanism is studied, which has allowed us to propose different sets of parameters that could increase the security of NewHope implementations.
NewHopeKey Encapsulation Mechanism (KEM) has been presented at USENIX 2016 by Alkimet al.and was one of the lattice-based candidates to the post-quantum standardization initiated by the NIST. However, despite the relative simplicity of the protocol, the bound on the decapsulation failure probability resulting from the original analysis is not tight. In this work we refine this analysis to get a tight upper-bound on this probability which happens to be much lower than what was originally evaluated. As a consequence, we propose a set of alternative parameters, increasing the security and the compactness of the scheme. However using a smaller modulus prevent the use of a full NTT algorithm to perform multiplications of elements in dimension 512 or 1024. Nonetheless, similarly to previous works, we combine different multiplication algorithms and show that our new parameters are competitive on a constant time vectorized implementation. Our most compact parameters bring a speed-up of17%17\%17%(resp.11%11\%11%) in performance but allow to gain more than19%19\%19%over the bandwidth requirements and to increase the security of10%10\%10%(resp.7%7\%7%) in dimension 512 (resp. 1024).
The emergence of quantum computing poses a significant threat to classical encryption techniques, rendering them vulnerable to powerful algorithms proposed to be used in quantum computers. In response to this, the National Institute of Standards and Technology (NIST) initiated a standardization process to streamline quantum resistant cryptographic algorithms. This work surveys the three algorithms selected to move onto the 4th round and one selected for standardization by the National Institute of Standards and Technology (NIST). In addition to this, our work also discusses some real-life implementations of quantum-resistant algorithms like the PQXDH algorithm and an approach implemented by Microsoft, as a step towards a quantum-resistant future.
Lattice-based cryptographic primitives are believed to offer resilience against attacks by quantum computers. Following increasing interest from both companies and government agencies in building quantum computers, a number of works have proposed instantiations of practical post-quantum key-exchange protocols based on hard problems in lattices, mainly based on the Ring Learning With Errors (R-LWE) problem.\nIn this work we present an analysis of Ring-LWE based key-exchange mechanisms and compare two implementations of Ring-LWE based key-exchange protocol: BCNS and NewHope. This is important as NewHope protocol implementation outperforms state-of-the art elliptic curve based Diffie-Hellman key-exchange X25519, thus showing that using quantum safe key-exchange is not only a viable option but also a faster one. Specifically, this thesis compares different reconciliation methods, parameter choices, noise sampling algorithms and performance.
In this paper, we present a comparison study on three RLWE key exchange protocols: one from Ding et al. in 2012 (DING12) and two from Alkim et al. in 2016 (NewHope and NewHope-Simple). We compare and analyze protocol construction, notion of designing and realizing key exchange, signal computation, error reconciliation and cost of these three protocols. We show that NewHope and NewHope-Simple share very similar notion as DING12 in the sense that NewHope series also send small additional bits with small size (i.e. signal) to assist error reconciliation, where this idea was first practically proposed in DING12. We believe that DING12 is the first work that presented complete LWE & RLWE-based key exchange constructions. The idea of sending additional information in order to realize error reconciliation and key exchange in NewHope and NewHope-Simple remain the same as DING12, despite concrete approaches to compute signal and reconcile error are not the same.
Post Quantum Cryptography (sometimes referred to as a quantum-proof, quantum-safe or quantum-resistant) refers to cryptographic algorithms (usually public-key algorithms) that are thought to be secure against an attack by a quantum computer. PQC is all about preparing for the era of quantum computing by updating existing mathematical-based algorithms and standards. The cryptographic community is working on post-quantum cryptography in order to provide alternatives using hard mathematical problems that cannot be broken by quantum computers. A hybrid scheme is recommended to ease the transition into the post-quantum era. A hybrid scheme is a combination of a traditional and a post-quantum scheme. The resulting scheme is at least as secure as one of the schemes used. In hybrid key establishment, two independent key exchanges are performed one with a traditional scheme like ECDHE and one with a post-quantum scheme like NewHope [1]. In this paper, we propose possible best-fit hybrid digital signatures.
Information security is a fundamental and urgent issue in the digital transformation era. Cryptographic techniques and digital signatures have been applied to protect and authenticate relevant information. However, with the advent of quantum computers and quantum algorithms, classical cryptographic techniques have been in danger of collapsing because quantum computers can solve complex problems in polynomial time. Stemming from that risk, researchers worldwide have stepped up research on post-quantum algorithms to resist attack by quantum computers. In this review paper, we survey studies in recent years on post-quantum cryptography (PQC) and provide statistics on the number and content of publications, including a literature overview, detailed explanations of the most common methods so far, current implementation status, implementation comparisons, and discussion on future work. These studies focused on essential public cryptography techniques and digital signature schemes, and the US National Institute of Standards and Technology (NIST) launched a competition to select the best candidate for the expected standard. Recent studies have practically implemented the public key encryption/key encapsulation mechanism (PKE/KEM) and digital signature schemes on different hardware platforms and applied various optimization measures based on other criteria. Along with the increasing number of scientific publications, the recent trend of PQC research is increasingly evident and is the general trend in the cryptography industry. The movement opens up a promising avenue for researchers in public key cryptography and digital signatures, especially on algorithms selected by NIST.