NewHope: The First Real-World Lattice KEM Pilot

In July 2016, Google began a small experiment. For about three months, a fraction of Chrome Canary users connecting to certain Google servers used a hybrid post-quantum key exchange called CECPQ1 ("Combined Elliptic Curve and Post-Quantum 1"). The post-quantum half was a scheme called NewHope, designed by Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe in 2015. The classical half was X25519. By November 2016, the experiment ended and Chrome reverted to plain X25519.

CECPQ1 was the first real-world deployment of post-quantum cryptography on the public internet. It collected real performance data, exposed real implementation issues, and shaped how subsequent designs (most notably the eventual ML-KEM standard) approached parameter selection. NewHope itself was eventually superseded by Kyber, but the lessons from the CECPQ1 trial echo through every major PQC deployment since.

This article walks through what NewHope was, what Google learned from CECPQ1, and how the lessons fed into the design of FIPS 203.

The Test Drive

Imagine an automaker building a new electric car battery. Lab tests look good, but you do not really know how the battery performs until you put it in real cars driving on real roads in real weather. CECPQ1 was the first real-road test for lattice-based key exchange. The results: it works, it is fast enough, but the bandwidth cost is noticeable, and you should pick the parameters carefully before locking in a standard.

Every major PQC deployment since 2016 has followed the same playbook. Cloudflare's hybrid X25519+Kyber rollout in 2023, Apple's iMessage PQ3 in 2024, the Tor browser's hybrid handshake, all trace their methodology back to what Google learned with CECPQ1.

NewHope's Origin: 2015, Alkim et al.

The original paper, "Post-quantum key exchange - a new hope" by Erdem Alkim (then at Ege University), Léo Ducas (CWI Amsterdam), Thomas Pöppelmann (Infineon), and Peter Schwabe (Radboud University), was presented at USENIX Security 2016. The paper proposed a Ring-LWE based key exchange specifically tuned for performance, with extensive benchmarking on commodity hardware.

NewHope's distinguishing features:

• Ring-LWE with a single polynomial ring (n = 1024, q = 12289).
• Centered binomial distribution for noise sampling, which is faster than the discrete Gaussian sampling that earlier schemes used.
• NTT-friendly modulus (12289 is prime and supports the Number Theoretic Transform).
• Reconciliation mechanism for extracting a shared secret from approximately-equal Ring-LWE samples.
• Public key size: 1,824 bytes. Ciphertext size: 2,048 bytes. Total handshake bandwidth: ~3.9 KB.

Compared to X25519's 32-byte public key and 32-byte ciphertext (64 bytes total), NewHope was 60x larger in handshake bandwidth. That ratio is what drove Google's interest: it was big enough to test "does this still work in real TLS?", and small enough that the answer turned out to be yes.

CECPQ1: The Google Experiment

Adam Langley, then at Google, proposed CECPQ1 in early 2016. The protocol combined NewHope with X25519 in a hybrid handshake: derive a shared secret from each scheme separately, hash them together, and use the result as the TLS premaster secret. This pattern, called classical+PQ hybrid, is now the default approach for production post-quantum migration.

The deployment ran from July to November 2016 on a fraction of Google's TLS endpoints, primarily for Chrome Canary clients. Servers that supported CECPQ1 advertised it; clients that supported it negotiated it. Other connections used plain X25519.

What Google Found

Adam Langley wrote a detailed retrospective post in November 2016. Key findings:

• Performance was acceptable. Median TLS handshake latency increased by about 1 ms on broadband connections.
• Tail latency was a problem. The 95th percentile latency increased noticeably more, suggesting that NewHope's larger handshake exposed fragility in middleboxes and networks with constrained MTUs.
• Some middleboxes broke. About 0.3 to 0.4 percent of connections failed the handshake due to old middleboxes that could not handle the larger TLS records. Google patched their server-side fallback logic and the issue resolved.
• The cryptography itself worked. No security incidents were attributed to the post-quantum half.

After the experiment ended in November 2016, Google rolled CECPQ1 out of production. The reason was not that it failed; rather, NewHope was already known to be a stepping-stone scheme. Google wanted to wait for NIST's competition to settle on a standard before committing to a permanent deployment.

NewHope to Kyber: Why It Got Replaced

NewHope was a 2015 design. By 2017, the same research community had begun work on what would become CRYSTALS-Kyber. Kyber improved on NewHope in several ways:

1. Module-LWE instead of Ring-LWE. Module-LWE is generally considered to have a more conservative security analysis. It avoids some of the algebraic structure that Ring-LWE has, which has historically been a target of attempted attacks.
2. Better parameter scaling. NewHope was effectively a single-size scheme (its 1024 ring fixed performance and security at one point). Kyber offered three security levels (Kyber-512, 768, 1024) covering Categories 1, 3, 5, all with similar code paths.
3. CCA security via implicit rejection. Kyber's KEM construction included a stronger chosen-ciphertext security mechanism than NewHope's original "reconciliation" approach.
4. Tighter compression. Kyber's ciphertexts were about 30 percent smaller than NewHope's at comparable security.

The same research team (Bos, Ducas, Schwabe, and others) co-authored both papers, so the transition was natural. Kyber was submitted to NIST in November 2017 and ultimately won the Round 3 lattice KEM slot in July 2022. NewHope was effectively retired.

CECPQ2: The Update

In June 2019, Google launched CECPQ2, another small experiment combining X25519 with Kyber-512 (called HRSS-SXY in Google's nomenclature). CECPQ2 ran briefly and was then succeeded by full Kyber experiments aligned with NIST's standardisation. Cloudflare ran similar experiments in 2019 and 2020. By 2023, the production rollouts of hybrid X25519+Kyber had begun in earnest, leading up to the FIPS 203 finalisation in August 2024.

What CECPQ1 Taught the Field

The CECPQ1 trial taught lessons that shaped every subsequent PQC deployment:

1. Hybrid is mandatory for migration. Pure post-quantum is too risky during the transition. Combining classical (X25519, P-256) with post-quantum (Kyber, NewHope) means an attack on either side does not break the channel. Every major production deployment since CECPQ1 has used hybrid mode.

2. Middlebox fragility is real. Network equipment built before post-quantum cryptography existed sometimes fails on larger handshakes. Migrations need to plan for fallback paths and monitor breakage rates.

3. Tail latency matters more than median. Average performance is fine; the worst 5 percent of connections is where the user experience pain is felt. Bandwidth-sensitive applications need to budget for the tail.

4. Real deployment surfaces issues that lab benchmarks miss. No amount of microbenchmarking would have surfaced the middlebox compatibility issues. Real internet traffic across diverse network conditions is the only way to find these.

5. Standardisation timing matters. Google chose to retire CECPQ1 before NIST settled on a standard, to avoid being stuck on a deprecated algorithm. This is a model for any organisation considering early PQC adoption: align with the standard, and be willing to roll back.

For more on the modern hybrid approach, see Hybrid Encryption Explained.

NewHope Implementation Details

For historical interest, NewHope's implementation profile:

• Reference implementation: ~1,500 lines of C, no external dependencies.
• AVX2-optimised version: ~3 microseconds for KeyGen on a modern Intel CPU.
• Verification of correctness: NewHope ships with extensive Known Answer Tests (KATs).
• Side-channel considerations: The centered binomial sampling is constant-time in the reference implementation, which was a notable contribution to the field's understanding of how to do constant-time noise sampling.

NewHope is not a current production option. It is studied as an example of pre-NIST-competition PQC design, and many of its implementation patterns (constant-time sampling, NTT-based polynomial multiplication) live on in ML-KEM.

Where NewHope Lives Now

NewHope has reference implementations in liboqs and several academic libraries. It is not on a NIST FIPS track. It is not deployed in production anywhere in 2026. It exists as a historical artifact and as a teaching example of how lattice-based key exchange can be implemented.

For production deployment in 2026, the answer is ML-KEM. NewHope's place in history is as the bridge that proved real-world deployment was feasible.

NewHope in QNSQY's History

QNSQY does not ship NewHope. The product was designed in 2023, after NIST had selected Kyber and the entire industry had moved past NewHope. QNSQY ships ML-KEM (FIPS 203) as the lattice KEM and HQC (NIST Round 4) as the non-lattice diversity option.

The CECPQ1 lessons inform QNSQY's design directly. QNSQY's hybrid envelope (X25519 + ML-KEM, or Ed25519 + ML-DSA) follows the hybrid-is-mandatory principle. The modular design that supports rotating algorithms reflects the standardisation-timing principle. The choice to ship multiple KEM sizes (512, 768, 1024) reflects Kyber's parameter-scaling improvement over NewHope's single-size design.

The Cost of Early Adoption Done Right

CECPQ1's design decision to be hybrid (NewHope + X25519) is what kept Google's deployment safe even after the post-quantum half was superseded. If Google had deployed pure NewHope in 2016, every connection during that experiment would have relied entirely on a scheme that has now been retired. With hybrid, the X25519 half kept the protocol secure even if NewHope had been broken (it was not, but the architecture would have survived if it had).

This pattern is now industry standard. Cloudflare's 2023 hybrid X25519+Kyber rollout used the same architecture. Apple's iMessage PQ3 protocol (March 2024) layered post-quantum keys on top of classical ones. The IETF hybrid TLS draft does the same. The lesson from NewHope: never deploy post-quantum cryptography without a classical fallback. The fallback might end up unnecessary, but the cost of including it is cheap insurance against catastrophic failure modes.

Frequently Asked Questions

Was NewHope ever broken?

No. NewHope at its standardised parameters has not been broken. It was retired because Kyber improved on its design, not because of a security failure.

Why did Google use NewHope instead of waiting for the NIST standard?

NIST's competition started in late 2016 and was expected to take years. Google wanted real deployment data sooner. NewHope was the most polished lattice KEM available in mid-2016, with extensive performance benchmarks and reference implementations. Google's calculation was that running an experiment with NewHope would surface deployment issues that would otherwise stay hidden until the eventual NIST standard rolled out.

How is NewHope different from Kyber?

NewHope uses Ring-LWE with a single polynomial ring (n = 1024). Kyber (now ML-KEM) uses Module-LWE with smaller polynomials (n = 256) stacked into modules of varying size. Kyber's module structure gives more conservative security analysis and better parameter scaling. The cryptographic primitives are similar in spirit but differ in algebraic structure. See NTRU vs ML-KEM and Lattice-Based Cryptography Explained.

Did the CECPQ1 trial cause any security incidents?

No. The cryptographic side held up cleanly. The only deployment issues were middlebox compatibility, which caused some connections to fail to negotiate but did not weaken any successfully negotiated connection. The trial was ended on schedule, not in response to a security event.

Sources

1. Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P. "Post-quantum key exchange - a new hope." USENIX Security 2016. https://eprint.iacr.org/2015/1092
2. Langley, A. "CECPQ1 results." Imperial Violet (Adam Langley's blog), November 28, 2016. https://www.imperialviolet.org/2016/11/28/cecpq1.html
3. NIST. "Module-Lattice-Based Key-Encapsulation Mechanism Standard." FIPS 203, August 13, 2024. https://csrc.nist.gov/pubs/fips/203/final
4. NIST. "Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process." NIST IR 8413, July 2022. https://csrc.nist.gov/pubs/ir/8413/final
5. Bos, J., Costello, C., Naehrig, M., Stebila, D. "Post-quantum key exchange for the TLS protocol from the ring learning with errors problem." IEEE S&P 2015. https://eprint.iacr.org/2014/599
6. Westerbaan, B. "Defending against future threats: Cloudflare goes post-quantum." Cloudflare blog, October 2022. https://blog.cloudflare.com/post-quantum-for-all/

Related Articles

• ML-KEM Explained
• Hybrid Encryption Explained
• NTRU vs ML-KEM: Why Lattice Won the Race
• Lattice-Based Cryptography Explained
• What Is Post-Quantum Cryptography?

Protect Your Data Before Q-Day Arrives

QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats.

Try QNSQY