CRYSTALS–Kyber

Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim
Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, Damien Stehlé
authors@pq-crystals.org
https://pq-crystals.org/kyber
August 23, 2019

Reminder: the big picture
Kyber.CPAPKE: LPR encryption or “Noisy ElGamal”
s, e ← χ
sk = s, pk = t = As + er, e1 , e2 ← χu ← AT r + e1v ← tT r + e2 + Enc(m)c = (u, v )m = Dec(v − sT u)

1

Reminder: the big picture
Kyber.CPAPKE: LPR encryption or “Noisy ElGamal”
s, e ← χ
sk = s, pk = t = As + er, e1 , e2 ← χu ← AT r + e1v ← tT r + e2 + Enc(m)c = (u, v )m = Dec(v − sT u)
Kyber.CCAKEM: CCA-secure KEM via tweaked FO transform• Use implicit rejection• Hash public key into seed and shared key• Hash ciphertext into shared key• Use Keccak-based functions for all hashes and XOF1

Reminder: Kyber in Round 1• Use MLWE instead of LWE or RLWE2Reminder: Kyber in Round 1• Use MLWE instead of LWE or RLWE
• Use R = Zq [X ]/(X 256 + 1) with q = 7681

2

Reminder: Kyber in Round 1• Use MLWE instead of LWE or RLWE
• Use R = Zq [X ]/(X 256 + 1) with q = 7681
• Use centered binomial noise2Reminder: Kyber in Round 1• Use MLWE instead of LWE or RLWE
• Use R = Zq [X ]/(X 256 + 1) with q = 7681
• Use centered binomial noise• Generate A via XOF(ρ) (“NewHope style”)

2Reminder: Kyber in Round 1• Use MLWE instead of LWE or RLWE
• Use R = Zq [X ]/(X 256 + 1) with q = 7681
• Use centered binomial noise• Generate A via XOF(ρ) (“NewHope style”)• Compress ciphertexts (round off least-significant bits)2

Reminder: Kyber in Round 1• Use MLWE instead of LWE or RLWE
• Use R = Zq [X ]/(X 256 + 1) with q = 7681
• Use centered binomial noise• Generate A via XOF(ρ) (“NewHope style”)• Compress ciphertexts (round off least-significant bits)• Compress public keys

2NIST comments“We note that a potential issue is that the security proof does notdirectly apply to Kyber itself, but rather to a modified version of thescheme which does not compress the public key.”—NIST IR 8240

3

Main changes in round 2

1. Remove the public-key compression• Proof now applies to Kyber itself• However, bandwidth requirement increases

4Main changes in round 2

1. Remove the public-key compression• Proof now applies to Kyber itself• However, bandwidth requirement increases

2. Reduce parameter q to 3329
• Bandwidth requirement decreases

3. Update ciphertext-compression parameters

4Main changes in round 2
Kyber sizes, round 1 vs. round 2
Kyber512 (k = 2, level 1)round 1, sizes in bytes
pk:
ct:

736
800

round 2, sizes in bytes
pk:
800
ct:
736

1088
1152

round 2, sizes in bytes
pk:
1184
ct:
1088

1440
1504

round 2, sizes in bytes
pk:
1568
ct:
1568

Kyber768 (k = 3, level 3)
round 1, sizes in bytes
pk:
ct:
Kyber1024 (k = 4, level 5)round 1, sizes in bytes
pk:
ct:

4

Main changes in round 2

1. Remove the public-key compression• Proof now applies to Kyber itself• However, bandwidth requirement increases

2. Reduce parameter q to 3329
• Bandwidth requirement decreases

3. Update ciphertext-compression parameters
4. Update the specification of the NTT (inspired by NTTRU)• Even faster polynomial multiplication

4

Main changes in round 2

1. Remove the public-key compression• Proof now applies to Kyber itself• However, bandwidth requirement increases

2. Reduce parameter q to 3329
• Bandwidth requirement decreases

3. Update ciphertext-compression parameters
4. Update the specification of the NTT (inspired by NTTRU)• Even faster polynomial multiplication

5. Reduce noise parameter to η = 2• Faster noise sampling4

Main changes in round 2

1. Remove the public-key compression• Proof now applies to Kyber itself• However, bandwidth requirement increases

2. Reduce parameter q to 3329
• Bandwidth requirement decreases

3. Update ciphertext-compression parameters
4. Update the specification of the NTT (inspired by NTTRU)• Even faster polynomial multiplication

5. Reduce noise parameter to η = 2• Faster noise sampling

6. Represent public key in NTT domain• Save several NTT computations

4

Kyber is fast
Kyber512 (k = 2, level 1)
Sizes (in Bytes)
sk:
pk:
ct:

1632
800
736

Haswell Cycles (AVX2)
gen:
29100
enc:
46196
dec:
39410

2400
1184
1088

Haswell Cycles (AVX2)
gen:
57340
enc:
78692
dec:
68620

3168
1568
1568

Haswell Cycles (AVX2)
gen:
81244
enc:
109584dec:
97280

Kyber768 (k = 3, level 3)
Sizes (in Bytes)
sk:
pk:
ct:
Kyber1024 (k = 4, level 5)Sizes (in Bytes)
sk:
pk:
ct:

5

Kyber is fast and small
Kyber512 (k = 2, level 1)
Stack usage (in Bytes)
gen:
enc:
dec:

2952
2552
2560

Cortex-M4 Cycles
gen:513992
enc:
652470dec:
620946

3848
3128
3072

Cortex-M4 Cycles
gen:976205enc:
1146021dec:
1094314

4360
3584
3592

Cortex-M4 Cycles
gen:1574351
enc:
1779192dec:
1708692

Kyber768 (k = 3, level 3)
Stack usage (in Bytes)
gen:
enc:
dec:
Kyber1024 (k = 4, level 5)
Stack usage (in Bytes)
gen:
enc:
dec:

6

What are we benchmarking, really?
• More than 50% of the cycles are spent in Keccak• Many conservative choices in FO transform• Use SHAKE-128 to as XOF• Generally, Keccak is not very fast in software7What are we benchmarking, really?
• More than 50% of the cycles are spent in Keccak• Many conservative choices in FO transform• Use SHAKE-128 to as XOF• Generally, Keccak is not very fast in software• Long-term solution: hardware-accelerated Keccak

7What are we benchmarking, really?
• More than 50% of the cycles are spent in Keccak• Many conservative choices in FO transform• Use SHAKE-128 to as XOF• Generally, Keccak is not very fast in software• Long-term solution: hardware-accelerated Keccak• Short-term problem:• Benchmarks of lattice-based KEMs are really benchmarks ofsymmetric crypto• Risk to make wrong decision about lattice design from“symmetrically tainted” benchmarks

7What are we benchmarking, really?
• More than 50% of the cycles are spent in Keccak• Many conservative choices in FO transform• Use SHAKE-128 to as XOF• Generally, Keccak is not very fast in software• Long-term solution: hardware-accelerated Keccak• Short-term problem:• Benchmarks of lattice-based KEMs are really benchmarks ofsymmetric crypto• Risk to make wrong decision about lattice design from“symmetrically tainted” benchmarks• Maybe just a small problem, because lattice-based KEMs are all fastenough7

What are we benchmarking, really?
• More than 50% of the cycles are spent in Keccak• Many conservative choices in FO transform• Use SHAKE-128 to as XOF• Generally, Keccak is not very fast in software• Long-term solution: hardware-accelerated Keccak• Short-term problem:• Benchmarks of lattice-based KEMs are really benchmarks ofsymmetric crypto• Risk to make wrong decision about lattice design from“symmetrically tainted” benchmarks• Maybe just a small problem, because lattice-based KEMs are all fastenough• Better to decide based on• size/bandwidth• RAM/ROM footprint and gate count in HW• simplicity• how conservative designs are• cost of SCA protection

7

Kyber-90s

https://www.bbc.co.uk/bbcthree/article/91603cc1- f159- 4c89- 9462- 443a078945ca

90s crypto (AES, SHA-2) is accelerated in HW!
8

Kyber-90s performance (Haswell cycles)
Kyber512 (k = 2, level 1)
Kyber cycles
gen:
29100
enc:
46196
dec:
39410

Kyber-90s cycles
gen:
15792
enc:
26612
dec:
22248

Kyber768 (k = 3, level 3)
Kyber cycles
gen:
57340
enc:
78692
dec:
68620

Kyber-90s cycles
gen:
25632
enc:
39976
dec:
33744

Kyber1024 (k = 4, level 5)
Kyber cycles
gen:
81244
enc: 109584
dec:
97280

Kyber-90s cycles
gen:
38164
enc:
57280
dec:
50360
9

Kyber online

https://pq-crystals.org/kyber

10