ThreeBears Cryptosystem: Why NIST Rejected Integer Lattices

In August 2024, NIST picked CRYSTALS-Kyber (now called ML-KEM) as the official encryption standard for protecting data against future quantum computers. The competition lasted years. ThreeBears, designed by Mike Hamburg at Rambus, offered a different approach to the same problem but lost because security experts worried it hadn't been tested enough and discovered real vulnerabilities that could leak secret keys.

Modern encryption relies on hard math problems that even supercomputers can't solve quickly. Today's encryption uses problems like factoring huge numbers - it would take centuries to crack. But quantum computers, once they exist at scale, will solve these problems in hours. That's why NIST ran a competition to find new math problems that resist quantum attacks.

ThreeBears tried solving this problem using something called Integer Module Learning with Errors (I-MLWE). Think of it like building security from a different type of math problem than everyone else used. Most competitors built their encryption on polynomial rings - a specific type of mathematical structure that cryptographers have studied for decades. ThreeBears used direct integer operations instead, which made the code simpler but created a security foundation nobody had studied much.

The algorithm came in three versions named after the fairy tale: BabyBear provided 153 bits of quantum security, MamaBear offered 238 bits, and PapaBear reached 318 bits. These numbers represent how hard the system is to break. BabyBear requires roughly 2^153 quantum operations to crack - that's a number with 46 digits. PapaBear needs 2^318 operations, which has 96 digits. Each version adjusted the math to hit these security targets while keeping file sizes and speed reasonable.

Hamburg admitted from the start that I-MLWE represented completely new territory. He stated directly that he lacked confidence in BabyBear's security because cryptographers hadn't studied this type of problem enough. When you change from polynomial math to integer math, the entire attack landscape changes. Security proofs that work for polynomial problems don't automatically transfer to integer problems. The ways errors accumulate during encryption change. The difficulty of the attacks changes. Everything needs fresh analysis.

NIST eliminated ThreeBears after Round 2 ended in July 2020. The agency picked seven finalists and eight alternates for Round 3 but excluded Hamburg's proposal. The standardization report said I-MLWE was too new and hadn't received enough security analysis compared to the polynomial approach underlying competitors like CRYSTALS-Kyber, NTRU, and SABER. These competing schemes benefited from decades of research - thick stacks of academic papers analyzing every possible attack.

In 2021, researchers Vacek and Václavek published an attack that breaks ThreeBears when attackers can test whether specific encrypted messages decrypt correctly under a targeted secret key. This "key mismatch attack" recovers complete secret keys with 100% success using roughly 2,000 attempts on average. The attack exploits how errors behave in the integer lattice structure during decryption. Similar attacks hit other Round 2 candidates including Frodo and Round5, but the discovery reinforced worries about ThreeBears' security compared to more studied schemes.

The choice between I-MLWE and polynomial Module-LWE boils down to a tradeoff Hamburg made consciously. Module-LWE sits between two extremes: plain LWE (which uses simple unstructured vectors) and Ring-LWE (which exploits structured polynomial rings). Research proves polynomial Module-LWE is at least as hard as Ring-LWE under specific conditions. ThreeBears abandoned these proven hardness relationships for simpler arithmetic that hadn't been studied thoroughly.

Hamburg designed ThreeBears to use less bandwidth than competing schemes at the same security levels. This matters for IoT devices like smart sensors or embedded systems where network transmission costs more than computation speed. The integer arithmetic avoids Number Theoretic Transform operations that schemes like Kyber need for efficient polynomial multiplication - Kyber spends roughly 30% of execution time on these calculations. ThreeBears traded proven security for cleaner code.

NIST's final choice of CRYSTALS-Kyber shows the agency values proven security over new ideas, especially when defending against quantum computers that don't exist yet. Kyber bases security on polynomial Module-LWE, which benefits from extensive research into Ring-LWE and the broader Module-LWE framework. The standardization process picked schemes with well-understood security properties and established mathematical proofs over algorithms offering simpler code built on untested assumptions.

The elimination shows how cautious cryptographers get when standardizing algorithms meant to protect data for decades. ThreeBears offered real advantages in bandwidth and implementation simplicity while introducing a hardness assumption that lacked the scrutiny applied to polynomial lattice problems over thirty years. NIST chose proven security foundations over simpler implementations, accepting more complex code in exchange for confidence that standardized algorithms will actually resist quantum attacks when those computers arrive.

The key mismatch vulnerability that affected ThreeBears demonstrates why NIST prefers thoroughly-tested constructions. Attackers with access to key validation functions extracted secret keys from ThreeBears, Frodo, and Round5 by exploiting how these schemes handle decryption errors. These schemes leaked information through their error-handling code. NIST's selection of Kyber avoided these specific vulnerabilities and picked a scheme that survived more aggressive security testing.

Hamburg's design represents a legitimate alternative that prioritizes different engineering choices than what NIST standardized. Integer Module-LWE might prove just as secure as polynomial Module-LWE after receiving equivalent analysis, but the standardization timeline required NIST to decide before that analysis happened. The agency chose schemes with established security arguments over algorithms offering potential advantages built on unproven foundations, accepting that conservative choices might exclude viable alternatives in favor of lower-risk options.

ThreeBears remains available as open-source code for researchers exploring integer lattice approaches to post-quantum encryption. The elimination demonstrates that cryptographic novelty creates standardization risk regardless of performance benefits. NIST prioritized security maturity over implementation simplicity when selecting algorithms meant to protect against quantum computers that don't exist yet but will eventually break everything we use today.