Standardizing
Lattice Cryptography… and Beyond
Vadim Lyubashevsky
IBM Research – Zurich

Why Lattice Cryptography• One of the oldest and most (the most?)
efficient quantum-resilient alternatives for“basic primitives”– Public key encryption– Digital signatures• Many “advanced” primitives can be based onthese hardness assumptions

CRYSTALS
Cryptographic Suite for Algebraic Lattices

Joppe Bos Leo Ducas
Eike Kiltz Tancrede Lepoint
Vadim Lyubashevsky John SchanckPeter Schwabe Gregor Seiler Damien Stehle

CRYSTALS: KYBER
CCA KEM (AND ENCRYPTION)

Design Philosophies• CCA only
– The primitives are already very fast; no need to setspeed records• Make adjusting security levels simple – always
operate over the ring Zq[X]/(X256+1) for q=213-29+1– If you care about post-quantum security, you can start
implementing/optimizing/using now– Scheme can be easily adjusted once more exact
cryptanalysis is agreed uponKey Exchange / CCA – Encryption/
Authenticated Key Exchange
CPA-Secure PKE

All “black-box”
transformations
CCA-Secure KEM

CCA-Secure PKE

Key Exchange

Authenticated KeyExchange

PKE Development[HPS ’97]
NTRU Cryptosystemover Z[x]/(xn-1)

Minicrypt with WC/AC
reductions

PKE with WC/AC
reductions[Ajt ’96]
CRH over Z[AD ’97]
Ajtai-Dwork
Cryptosystem[Mic ’02]
One-way functions
over Z[x]/(xn-1)[Reg ’05]
LWE Cryptosystemover Z[LM ‘06]
CRH over arbitraryrings. In particular,
Z[x]/(xn+1)[LPR ‘10]
Ring-LWE
cryptosystemGiving Credit• Hoffstein, Pipher, Silverman– Cryptosystem Using Polynomial Rings ‘97• Ajtai, Dwork– General Lattice Cryptosystem ‘97• Alekhnovich– LPN-Based Cryptosystem ‘03• Regev– LWE Cryptosystem ‘05• Lyubashevsky, Peikert, Regev– Practical (Ring)-LWE Cryptosystem ‘10

Giving Credit• Hoffstein, Pipher, Silverman– Cryptosystem Using Polynomial Rings ‘97• Ajtai, Dwork– General Lattice Cryptosystem ‘97• Alekhnovich– LPN-Based Cryptosystem ‘03• Regev– LWE Cryptosystem ‘05• Lyubashevsky, Peikert, Regev– Practical (Ring)-LWE Cryptosystem ‘10

Hard Apples• Hoffstein, Pipher, Silverman– Cryptosystem Using Polynomial Rings ‘97• Ajtai, Dwork– General Lattice Cryptosystem ‘97• Alekhnovich– LPN-Based Cryptosystem ‘03• Regev– LWE Cryptosystem ’05• Lyubashevsky, Peikert, Regev– Practical (Ring)-LWE Cryptosystem ‘10

Hard Apples• Hoffstein, Pipher, Silverman– Cryptosystem Using Polynomial Rings ‘97• Ajtai, Dwork– General Lattice Cryptosystem ‘97• Alekhnovich– LPN-Based Cryptosystem ‘03• Regev– LWE Cryptosystem ‘05• Lyubashevsky, Peikert, Regev– Practical (Ring)-LWE Cryptosystem ‘10

Hard Apples

The Polynomial Ring Zq[x]/(xd+1)
R = Zq[x]/(xd+1) is a polynomial ring with••

Addition mod q
Polynomial multiplication mod q and xd+1

Each element of R consists of d elements in Zq
In R:
••

small+small = small
small*small = small(Note: If d=1, then R=Z*q)

Rounding Function[q/4]

Round1(w)0[q/2]-[q/4]

Roundk(w) = “ Round w to the nearest [q/2] ”Hard Apples Encryption [LPR ’10]
KeyGen:A  Rn x ns,e  ψnt := As+epk: (A,t)
sk: sHard Apples Encryption [LPR ‘10]
Public Key / Secret KeyGeneration

Hard Apples Encryption [LPR ‘10]
Encrypt(μ):
KeyGen:r’,e’  ψnA  Rn x nfψs,e  ψnu’ := r’A+e’t := As+ev := r’t + f + [q/2]μpk: (A,t)
sk: sciphertext: (u’,v)Hard Apples Encryption [LPR ‘10]
Public Key / Secret Key
Generation

Encryption

Hard Apples Encryption [LPR ‘10]
Encrypt(μ):
Decrypt(u’,v):
KeyGen:w:=v-u’s
r’,e’  ψn
A  Rn x n
μ := Round1(w)fψs,e  ψnu’ := r’A+e’t := As+e[q/2]v := r’t + f + [q/2]μpk: (A,t)
sk: sciphertext: (u’,v)Hard Apples Encryption [LPR ‘10]
Public Key / Secret Key
GenerationDecryption≈Encryption-1

Practical Security
100001000010-1

Best attack is finding the shortest vector in a
lattice of dimension 2nd+1

Relation to LWE and Ring-LWE• In LWE, d=1– Security completely dependent on n

• In Ring-LWE, n=1– Security completely dependent on dMessage Space Size
Encryption

message = 1 element in
R with 0/1 coefficientsd coefficients

Larger d  Larger message
But 256-bit messages are enough  Can set d=256

Hard Apples vs. NTRU
Public key size, ciphertext size, encryption,decryption, all approximately the same
NTRU key generation ≈ 10x slower
Main disadvantage of NTRU: Geometricstructure of the NTRU lattice [KF ‘17]
Breaks NTRU for large q, small ψIs NTRU Broken?
• No. For a small modulus as used in encryption, it’s stillsecure.

• No attack in the past 20 years actually threatened NTRU or
Hard Apples– (Even the recent incorrect quantum algorithm of Eldar and Shor
didn’t break these schemes)• But … advanced schemes (like FHE) where q must be large
will be broken if based on NTRU
• Geometric structure could be exploited further

SIMPLE EFFICIENCY IMPROVEMENTS

Rounding Function
Round1(w)

0

[q/2]

-[q/4]

Round2(w)

[q/2]

0
[q/4]

Roundk(w) = “ Round w to the nearest q/2k ”|w - Roundk(w)| < q/2k+1

Hard Apples Encryption [LPR ‘10]
KeyGen:A  Rn x ns,e  ψnt := As+epk: (A,t)
sk: sEncrypt(μ):
r’,e’  ψnfψ
u’ := r’A+e’v := r’t+f+[q/2]μDecrypt(u’,v):w:=v-u’s
μ := Round1(w)[q/2]ciphertext: (u’,v)w := v-u’s = r’e – e’s + f + [q/2]μEach coefficient of |r’e – e’s + f| should be less than q/4

Hard Apples Encryption [LPR ‘10]
KeyGen:A  Rn x ns,e  ψnt := As+epk: (A,t)
sk: sEncrypt(μ):
r’,e’  ψnfψ
u’ := r’A+e’
v := Roundk(r’t+f+[q/2]μ)Decrypt(u’,v):w:=v-u’s
μ := Round1(w)[q/2]ciphertext: (u’,v)w := v-u’s = r’e – e’s + f + [q/2]μ + εv
Each coefficient of |εv | is at most q/2k+1
Each coefficient of |r’e – e’s + f| should be less than q/4 - q/2k+1

INTERLUDE: COMPARISON WITH
“RECONCILIATION-BASED” KEM(Preview: This is not better than PKE)

Reconciliation
Player 1 gets a random value x mod q
Player 2 gets some value y such that |x-y mod q|<ε
Player 1 and 2 want to secretly agree on 1 bit.
This is not possible without additional communication
Upon receiving x, player 1 sends a “hint” to player 2 such that:
1. x and y can agree on a bit
2. anyone who only sees the hint cannot guess the bit

00 1

[q/2]

Reconciliation
Player 1 gets a random value x mod q
Player 2 gets some value y such that |x-y mod q|<ε
Player 1 and 2 want to secretly agree on 1 bit.
This is not possible without additional communication
Upon receiving x, player 1 sends a “hint” to player 2 such that:
1. x and y can agree on a bit
2. anyone who only sees the hint cannot guess the bit

00 1[q/2]

Reconciliation
Player 1 gets a random value x mod q
Player 2 gets some value y such that |x-y mod q|<ε
Player 1 and 2 want to secretly agree on 1 bit.
This is not possible without additional communication
Upon receiving x, player 1 sends a “hint” to player 2 such that:
1. x and y can agree on a bit
2. anyone who only sees the hint cannot guess the bit

00 1[q/2]

a0a bb a[q/2]

0a bb a[q/2]

If ε < q/8, then Player 2 will know which half x is inAllowing for Larger ε
00 10a bb a[q/2]

aa bb a0

[q/2]

[q/2]

If ε < q/8, then Player 2 will know which half x is in

0bca dd acba[q/2]0bca dd acb[q/2]

If ε < 3q/16, then Player 2 will know which half x is in
k “hint bits”  if ε < q/4 - q/2k+2, then Player 2 will know which half x is inKEM Based on Reconciliation [D ’12, P’14]
KeyGen:A  Rn x ns,e  ψnt := As+epk: (A,t’)sk: s’

Decapsulate(u’,v):Encapsulate():w:=u’sr’,e’  ψn( = r’As + e’s )fψ
λ := Reconc(w,v)
u’ := r’A+e’v := HintBitsk(r’t + f)
=HintBitsk(r’As + r’e + f)
ciphertext: (u’,v)
λ := Round1(v)
00 1

[q/2]

0a bb a[q/2]Comparing Encryption andReconciliation KEM
Public Key Encryption

KEM

To encrypt 256-bit message:
ndlog q + dk + 256 bits

To share 256-bit key:ndlog q + dk bits

In practice, the KEM is about 256 bits ≈ 3% shorter, but …
both the Encryption scheme and KEM are only passively-secure
PassiveSecure KEM(u’, v, λ + μ)

PassiveSecure PKE

256 bits added back!

Fujisaki-Okamoto

CCA-SecureKEMStart with KEM or PKE?
For our application, there is no difference
PKE is just simpler and more direct
Maybe one can go from KEM to something useful and save alittle bit … perhaps with error correction, but I’m not sure
But it’s definitely not as stated in [P ‘14]:naïve“As compared with the previous most efficient ring-LWE cryptosystems andKEMs, the new reconciliation mechanism reduces the ciphertext length bynearly a factor of two, because it replaces one of the ciphertext’s two Rq
elements with an R2 element.”

Interlude: Non-Interactive “DiffieHellman”-like Key Exchange
Common randomness A
Player 1 Public Key: t1 = As1+e1
Player 2 Public Key: t2 = s2A+e2
Joint key: HighBits (s2t1) = HighBits(t2s1)
00 1

[q/2]

00 1

[q/2]

Error happens with probability ≈ |s2e1| / q ≈ |e2s1 | / q
PK sizes of (probably) more than 40 - 50 KBDouble that if s1A is not As1
using Ring-LWE is twice as efficient as using Module-LWE

Varieties of Hard Apples•

Use LWE instead of Ring-LWE / Module-LWE (Frodo)
Pros: No algebraic structure to try and exploit in attacks
Cons: 10x slower, 10x larger public key, 10x larger ciphertext (when trying to minimize sizeof public key + ciphertext)•

Use Ring-LWE (i.e. set n=1) instead of Module-LWE (with flexible n) (New Hope Light)
Pros: A little faster
Cons: Less flexible (if the degree is a power of 2), smaller n could affect practical security•

Use rounding instead of adding random errors (Lizard,NTRU-Prime)
Pros: A little faster
Cons: Unclear if deterministic noise leads to new attacks (a very aggressive version of LWR)

•Use a ring Z[X]/(f(x)) for a different f(x) (NTRU-Prime)
Pros: Algebraic attacks could be less obvious than for f(x)=xd+1
Cons: A little slower, slightly larger “expansion factor” , no algebraic structure that’s usefulfor some advanced applications

FURTHER PKE EFFICIENCY IMPROVEMENTS

Hard Apples Encryption [LPR ‘10]
Encrypt(μ):
KeyGen:r’,e’  ψnA  Rn x nfψs,e  ψnu’ := Roundα(r’A+e’)t := Roundα(As+e)v := Roundk(r’t+f+[q/2]μ)pk: (A,t)sk: sDecrypt(u’,v):w:=v-u’s
μ := Round1(w)[q/2]ciphertext: (u’,v)w := v-u’s = r’e – e’s + f + [q/2]μ + εv + r’εt + εu’s
Set the size for securityLarger ε  smaller pk / ciphertext …
but larger decryption error
Need to manually optimize

Added “Benefit” of Rounding
Encrypt(μ):
KeyGen:r’,e’  ψnA  Rn x nfψs,e  ψnu’ := Roundα(r’A+e’)t := Roundα(As+e)v := Roundk(r’t+f+[q/2]μ)pk: (A,t)sk: sDecrypt(u’,v):w:=v-u’s
μ := Round1(w)[q/2]ciphertext: (u’,v)Introduces more noise – makes lattice reduction harder
But this noise is deterministic – we choose not to rely on it for hardness

Kyber CCA-KEM Stats
Ring Rq[X]/(X256+1), q = 213-29+1

dimension of A
pk sizeciphertext size
quantum security
key gen cycles
enc cycles
dec cycles

medium2x 2
736 bytes
832 bytes
102

recommended
3x 31088 bytes
1184 bytes
161
85K
125K
135K

very high
4x 41440 bytes
1536 bytes
218

CRYSTALS: DILITHIUM
DIGITAL SIGNATURE SCHEME

Design Philosophy• Make it simple to securely implement
everywhere – only uniform sampling• Public key size is also important – want tominimize (sig size + pk size)• Make adjusting security levels simple – alwaysoperate over the ring Zq[X]/(X256+1)

Fiat-Shamir with Aborts [Lyu ‘09]
Public Key / Secret Key
GenerationH( ,μ)Fiat-Shamir with Aborts [Lyu ‘09]
Public Key / Secret Key
Generation

H( ,μ)
Perform Rejection Sampling
1. Remove dependence on
2. Keep coefficients smallFiat-Shamir with Aborts [Lyu ‘09]

As1+s2=t
Sign(μ)Verify(z1, z2, c, μ)y1,y2  D with small coefficientsc := H(Ay1+y2, μ)z1 := y1 + cs1 , z2 := y2 + cs2
RejectionSample(z1, z2, cs1, cs2)

Signature = (z1, z2, c)

Check that z1, z2 have small
coefficients

andc=H(Az1+z2 - ct , μ)

Security Proof
Can simulate signing (by programming H)
because the distribution (z1, z2, c) is
independent of the secret key.

Can extract two signatures such that
Az1+z2 - ct = Az‘+z
1 ‘2 - c't
A(z1 - z‘)
1 + (z2 - z‘)
2 - (c - c’)t = 0
Found a short vector in a latticeObservations
A(z1 - z‘)
1 + (z2 - z‘)
2 - (c - c’)t = 0A(z1 - z‘)
1 - (c - c’)t ≈ 0
Still found a short vector… but now don’t have to output z2 
signature shrunk by about 50% [GLP ‘12, BG ‘14]
A(z1 - z‘)
1 - (c - c’)t ≈ 0

High-Order Bits of tA(z1 - z‘)
1 - (c - c’)(t1 + t0) ≈ 0
A(z1 - z‘)
1 - (c - c’)t1 ≈ 0
Still found a short vector… but now don’t have to have t0 in the publickey  public key shrunk by > 50% [DLLSSS ‘17]

Dilithium Sketch
A:=XOF(ρ), t:=As1+s2
Public key: ρ,t1
Sign(μ)Verify((z, h, c), μ)

Use Az-ct1 and h to gety  D with uniform small coefficientsc := H(HighBits(Ay), μ)w:= HighBits(Az-ct)
z := y + cs1
RejectionSample(z, cs1, cs2)
Check that z has small(Must hold: HighBits(Ay)=HighBits(Az-ct))
coefficients
Create a hint h such that
andc=H(w,μ)
HighBits(Az-ct1) & h  HighBits(Az-ct)
Signature = (z, h, c)Dilithium Sketch
A:=XOF(ρ), t:=As1+s2
Public key: ρ,t1
Sign(μ)Verify((z, h, c), μ)

Use Az-ct1 and h to gety  D with uniform small coefficientsc := H(HighBits(Ay), μ)w:= HighBits(Az-ct)
z := y + cs1
RejectionSample(z, cs1, cs2)
Check that z has small(Must hold: HighBits(Ay)=HighBits(Az-ct))
coefficients
Create a hint h such that
andc=H(w,μ)
HighBits(Az-ct1) & h  HighBits(Az-ct)
Signature = (z, h, c)
100 bytes allows to save over 2000 bytes in the pk

Dilithium Stats
Ring Rq[X]/(X256+1), q = 223 - 213 + 1
dimension of Apk size
sig size
BKZ block sizeclassical security
quantum security
key gen cycles
signature cycles
verification cycles

Medium4x 31184 bytes
2043 bytes
340
100
91
160K
640K
205K

Recommended
5x 41472 bytes
2700 bytes
475
140
125
250K
1000K
300K

Very High6x 51760 bytes
3365 bytes
595
174
158
320K
840K
400K

Comparing to BLISS [DDLL ‘13]
BLISS
dimension of A
pk size
sig size
BKZ block sizeclassical security
quantum security

875 bytes
820 bytes
280
claimed 192, why?

Medium4x 31184 bytes
2043 bytes
340
100
91

Recommended
5x 41472 bytes2700 bytes
475
140
125

Most practical attack using BKZ 2.0 [CN ’11] takes > 2192 time
This was a useful number for comparing with current schemes, e.g. RSA, EC-DSA
Now, we want to be more conservative – (e.g. assume exponential-space sieving is OK)

Higher Security BLISS(back-of-envelope calculations)• Using Z[X]/(X1024+1) instead of Z[X]/(X512+1)– Public Key ≈ 2100 bytes– Signature ≈ 1700 bytes– Security > 160 quantum• Using Z[X]/(f(x)) for with deg(f) ≈ 768– Public Key ≈ 1500 bytes– Signature ≈ 1300 bytes– Security ≈ 128 quantum

BLISS vs. Dilithium=+ BLISS+ Dilithium+ Dilithium+ Dilithium+ Dilithium

Public keys around the same size
Signatures half the size (save≈1.5KB)
No Gaussian (rejection) sampling
Security easily adjusted (same ring)
Based on Module-LWE vs. NTRU
Same framework as ZK proofs

Random Oracle Model vs.
Quantum Random Oracle Model
H is a cryptographic hash function
Theorem statements of the form:“If an adversary, having restricted access to H,
can break a primitive S then the reduction caneither solve some hard problem P or break H.”
H should be chosen such that it can’t bebroken by a quantum algorithm.

Black Box Access to H
• Random Oracle Model – give x, receive H(x)• Quantum Random Oracle – give superposition of(x1,…,xk), receive H(superposition(x1,…,xk))

Main open question: Is there a “natural” schemethat is ROM-secure, but is QROM insecure?

ROM vs. QROM
• Similar to the ROM vs. Standard model debate

For encryption – getting QROM is cheap– add 256 bits
– increases ciphertext by 3%

For signatures – getting QROM is more expensive– use “Katz-Wang” idea [AFLT ‘12], [TESLA] over rings– increases signature size by a factor of 2, public key
by a factor of 15, and around 10 times slower– signature + pk size approaches hash-based signatures

Looking Ahead• For more “advanced cryptography” (e.g.
privacy applications, e-voting, etc.), we needzero-knowledge proofs• Prove knowledge of short s1,s2 such thatAs1+s2=t• Same “Fiat-Shamir with Aborts” technique• Bimodal Gaussians from BLISS don’t help
much (in BLISS, A is picked such that As1+s2=0)

CONCLUSIONS

If You Want Quantum Security Now
For encryption / key exchange:– Use Kyber– Very, very good chance that it’s fine
– If some parameters need adjusting later, it’s very easy

For digital signatures– Not crucial at this point for many applications– If you’re signing something for the long-term future,and 40KB sigs is not a problem, use (stateless) hashbased sigs e.g. SPHINCS– If you need something smaller, could use Dilithium

Research Directions• Cryptanalysis!!!

• Understand whether QROM is relevant inpractical attacks and threatens Fiat-Shamir– If yes, then:• We could consider hash-and-sign signatures. They’re small,but a lot of Gaussian sampling and floating-point arithmetic• Or just do hash-based signatures and that’s it• Zero-knowledge proofs will be quite impractical– If things remain as they are, then:• Create practical advanced primitives – lots of work to dohere!