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
April 12, 2018

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

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• Enforce “honest” encapsulation• Generate all randomnes in encryption via PRG, encrypt seed
• Recover seed during decapsulation• Reencrypt and compare ciphertexts
1

Kyber.CPAPKE – design decisions I• Use MLWE instead of LWE or RLWE• Performance similar to RLWE
• Very easy to scale security and performance• Remove some of the cyclic structure of RLWE

• Use R = Zq [X ]/(X 256 + 1) with q = 7681
• Fast, simple, in-place negacyclic NTT for multiplication• Most widely studied and best understood structure2

Kyber.CPAPKE – design decisions I• Use MLWE instead of LWE or RLWE
• Performance similar to RLWE
• Very easy to scale security and performance• Remove some of the cyclic structure of RLWE

• Use R = Zq [X ]/(X 256 + 1) with q = 7681
• Fast, simple, in-place negacyclic NTT for multiplication• Most widely studied and best understood structure• Use centered binomial noise• Efficient to sample without timing leakage

2

Kyber.CPAPKE – design decisions I• Use MLWE instead of LWE or RLWE
• Performance similar to RLWE
• Very easy to scale security and performance• Remove some of the cyclic structure of RLWE

• Use R = Zq [X ]/(X 256 + 1) with q = 7681
• Fast, simple, in-place negacyclic NTT for multiplication• Most widely studied and best understood structure• Use centered binomial noise• Efficient to sample without timing leakage• Generate A via XOF(ρ) (“NewHope style”)• Avoid “nothing-up-my-sleeves” discussions• Avoid all-for-the-price-of-one attacks• Sample A in NTT domain: save k 2 NTTs

2

Kyber.CPAPKE – design decisions II• Compress ciphertexts (round off least-significant bits)• Reduce bandwidth requirements• Introduce extra “LWR” noise

3

Kyber.CPAPKE – design decisions II• Compress ciphertexts (round off least-significant bits)• Reduce bandwidth requirements• Introduce extra “LWR” noise• Compress public keys
• Reduce bandwidth requirements• Adds MLWR-style assumption instead of pure reduction from MLWE
(thanks to D’Anvers for pointing this out)
• No actual attacks or security problems• Could fix proof by re-randomizing after decompression

3

Kyber.CPAPKE – design decisions II• Compress ciphertexts (round off least-significant bits)• Reduce bandwidth requirements• Introduce extra “LWR” noise• Compress public keys
• Reduce bandwidth requirements• Adds MLWR-style assumption instead of pure reduction from MLWE
(thanks to D’Anvers for pointing this out)
• No actual attacks or security problems• Could fix proof by re-randomizing after decompression• Allow decapsulation failures• Failure probability < 2−140• Avoiding failures would cost security (or performance)3

FO transform – tweaks• Hash public key into seed and shared key• Multitarget protection against precomputation attacks• Obtain contributory KEM

4

FO transform – tweaks• Hash public key into seed and shared key• Multitarget protection against precomputation attacks• Obtain contributory KEM• Hash ciphertext into shared key• Shared key depends on full KEM transcript• More robust when building, e.g., AKE from Kyber

4

FO transform – tweaks• Hash public key into seed and shared key• Multitarget protection against precomputation attacks• Obtain contributory KEM• Hash ciphertext into shared key• Shared key depends on full KEM transcript• More robust when building, e.g., AKE from Kyber• Use Keccak-based functions for all hashes and XOF

4Parameter sets and performance
Kyber512 (k = 2, level 1)
Sizes (in Bytes)
sk:
pk:
ct:

1632
736
800

Haswell Cycles (AVX2)
gen:
55 160enc:
75 680dec:
74 428

2400
1088
1152

Haswell Cycles (AVX2)
gen:
85 472enc:
112 660dec:
108 904

3168
1440
1504

Haswell Cycles (AVX2)
gen:
121 056enc:
157 964dec:
154 952

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

5

Kyber online

https://pq-crystals.org/kyber

6