Developments in Blockchain Security & Privacy

The 9 Flavors of Lattice-Based Cryptography

With quantum computing gradually emerging as a security threat, cryptographers are scrambling to develop quantum-resistant cryptography.

Without such safeguards, financial institutions and eCommerce sites will become vulnerable to intrusion. 

Consequently, the National Institute for Standards and Technology (NIST) has initiated “a competition to develop encryption tools that can protect against quantum computers.” 

The most promising of these cryptographic schemes are based on lattice-based cryptography. 

Briefly stated, lattice-based cryptography refers to hidden data inside complex algebraic structures called lattices. 

It arguably offers the best safeguard against Schor’s algorithm, a technique amenable to quantum-computing that would break current cryptographic solutions (by solving prime number factoring problems).  

Since lattice problems are exceedingly difficult to solve, they’re immensely useful to cryptography. In part, this is due to their incorporation of learning with error (LWE) problems. 

“(LWE’s) main claim to fame is being as hard as worst-case lattice problems, hence rendering all cryptographic constructions based on it secure under the assumption that worst-case lattice problems are hard” (Regev). 

Learning with Errors (In Brief)

LWE is a fundamental element of post-quantum cryptography, as it can be used to produce a shared encryption key. 

If two parties seek to do so, they would first create a private key (s, a secret value) and small random numbers (e, error values). 

They would then create a public key (A, based on a random number matrix). Together, these values would be used to calculate B. 

So B = A x s + e

Both parties would then exchange their value of B. They would then calculate new values with the B values they have received and their own secret values.  

This would enable both parties to generate the same shared key.

NIST Selections

NIST has selected 9 lattice-based cryptography schemes as offering the most protection in a post-quantum world. They’re listed below.

1. Three Bears

The Three Bears algorithm is based on module learning with errors (LWE).

Here, LWE is limited to  Mersenne numbers (prime numbers that are one less than a power of two, Mn = 2n − 1 for some integer n).

Many other post-quantum algorithms rely on a polynomial ring (a set of polynomials in one or more variables with coefficients from a ring). 

Although Three Bears is faster than Google’s New Hope algorithm, it’s far slower when operating on 32-bit platforms.

In part, this is due to ThreeBear’s reliance on multi-precision arithmetic and slow, 64-bit SHAKE-256 (SHA-256 with variable length hash function). 

2. New Hope

Google’s New Hope is a key exchange method based on ring learning with errors (RLWE). 

RWLE adds and multiplies coefficients of polynomials within a finite field (Fq), with all coefficients being less than q). It also offers 256-bit level security. 

Here, two individuals who generate and pass each other messages can proceed to process these messages and in so doing, receive the same shared key. 

In 2015, a technical report about New Hope refers to its many cryptographic advances. The abstract reads,

…we propose new parameters and a better-suited error distribution, analyze the scheme’s hardness against attacks by quantum computers in a conservative way, introduce a new and more efficient error-reconciliation mechanism, and propose a defense against backdoors and all-for-the-price-of-one attacks. By these measures and for the same lattice dimension, we more than double the security parameter, halve the communication overhead, and speed up computation by more than a factor of 8 in a portable C implementation and by more than a factor of 20 in an optimized implementation targeting current Intel CPUs.” 

A New Hope key generator allows readers to see how it produces key matches.

3. Saber

Designed with “simplicity, efficiency, and flexibility” in mind, Saber relies on strengths found in learning with rounding problem (LWR). 

LWR is a variant of LWE, replacing random errors with deterministic rounding. In so doing, it  “halves the amount of randomness required compared to LWE-based schemes and (thus) reduces bandwidth”.  

SABER goes further than LRW, however, ensuring that, “all integer moduli are powers of 2, thus avoiding modular reduction and rejection sampling entirely”

4. NTRU Prime

Proposed 22 years ago, NTRUEncrypt was the first practical lattice-based encryption system. Being open-source, it’s commonly used in many applications already.

NTRU stands for Nth Degree Truncated Polynomial Ring Units. It functions by posing  “algebraic problems with polynomial rings whose solutions can be thought of as vectors in a lattice” (Zahid). 

Since it’s based on finding the shortest vector problem in a lattice, it’s generally considered unbreakable by quantum computers. 

However, “several ideal-lattice-based cryptosystems have been broken by recent attacks that exploit special structures of the (polynomial) rings used in those cryptosystems. (ntruprime.cr.yp.to).” 

As a result, NTRU Prime was designed to use rings without these structures. 

5. NTRU-HRSS-KEM

Unlike NTRUPrime, NTRU-HRSS-KEM avoids using a NAEP padding mechanism. The latter is used to ensure security in the presence of decryption failures.  

However, NTRU-HRSS parameters ensure that decryption failure is impossible,

NTRU-HRSS-KEM offers several advantages over NTRUPrime. For instance, it does not rely on fixed weight distributions to achieve proof of correctness. Likewise, it does not require a prime modulus (as it relies on the power of 2). Finally, its private keys are always invertible. 

In terms of disadvantages, NTRU-HRSS-KEM does not protect against cyclotomic ring attacks (as NTRUPrime does). And unlike NTRUPrime, it’s fully reliant on probabilistic (rather than deterministic) encryption. Furthermore, it cannot compress ciphertexts (so no LWR-like rounding is available).

6. Round5

Round5 is a Ring Learning with Rounding (RLWR)- based IND-CPA secure public-key encryption scheme. 

It performs encryption and decryption tasks via multiplication and employs “secret-key polynomials that have a factor (x − 1). This technique reduces the probability of failure and keeps the decryption error extremely low” (Baan et al). The latter allows the effective application of error correction through XEf (a constant error correction code) to further reduce the failure rate and shrink parameters, improving both security and performance.”  (Hülsing et al).

Round5 combines the “dense parameter space offered by the prime-order cyclotomic polynomial (n+1 a prime), with the low decryption failure rates typical of the power-of-two polynomial (n a power of two), such as in NewHope and Kyber” (Hülsing et al).

7. FrodoKEM

FrodoKEM  is a “family of key-encapsulation mechanisms that are designed to be conservative yet practical post-quantum constructions whose security derives from cautious parameterizations of the well-studied learning with errors problem” (LWE), 

Unlike Ring-Learning With Errors (or R-LWE), FrodoKEM does not use the algebraic ring structure central to these schemes.

8. Crystals

The “Cryptographic Suite for Algebraic Lattices” (CRYSTALS) incorporates Kyber, an IND-CCA2-secure key-encapsulation mechanism (KEM) and Dilithium, a strongly EUF-CMA-secure digital signature algorithm.

Both algorithms are designed to withstand attacks by quantum computers.

From the CRYSTALS website

“Module lattices can be thought of as lattices that lie between the ones used in the definitions of the LWE problem, and those used for the Ring-LWE problem. If the ring underlying the module has a sufficiently high degree (like 256), then these lattices inherit all the efficiency of the ones used in the Ring-LWE problem, and additionally have the following advantages in cryptographic algorithms:

(However), the lattices used in Kyber and Dilithium have less algebraic structure than those used for Ring-LWE and are closer to the unstructured lattices used in LWE.  It is therefore conceivable that if algebraic attacks against Ring-LWE appear (there are none that we are aware of at this point), then they may be less effective against schemes like Kyber and Dilithium.

9. LAC

LAC relies on four quantum-safe algorithms derived from lattice-based cryptography.  

LAC.CPA, the first algorithm, is the primary cryptosystem and the one which the remaining three schemes are based on, It’s primarily used to create keys for the public key encryption scheme.

LAC.CCA, the second algorithm, is used as a secure key encapsulation mechanism (KEM). It’s created by applying the Fujisaki-Okamoto transformation to the public-key encryption scheme (as is commonly done in other schemes as well). 

LAC.KE, the third algorithm, is the “passively secure unauthenticated key exchange protocol, based off of LAC.CPA” (Shaw).

The fourth algorithm is “the authenticated key exchange protocol based on the public key encryption scheme (LAC.CPA), and the secure key encapsulation mechanism (LAC.CCA)” (Shaw).


Add Your Comment

* Indicates Required Field

Your email address will not be published.

*