FrodoKEM
Općenito
FrodoKEM je Microsoftova obitelj mehanizama za generiranje i razmjenu ključeva. U središtu mehanizma nalazi se FrodoPKE, shema kriptiranja javnim ključem temeljena na dobro poznatom LWE problemu. Za razliku od Kybera, koji se temelji na modularnom LWE, FrodoKEM se temelji na LWE problemu nad nekonstrukturiranim rešetkama. Takav nedostatak algebarske strukture rezultira jednostavnošću algoritama što smanjuje potencijalnu ranjivost cijelog mehanizma. Još jedna posljedica jednostavnosti je iznimno efikasna skalabilnost, gdje je za povećanje sigurnosne razine potrebno promijeniti samo nekoliko parametara. FrodoKEM algoritmi su također i IND-CCA2 sigurni.
Svojstva
Nedostatak algebarske strukture rešetke znači da algoritmi ne mogu koristiti brzu Fourierovu transformaciju za generiranje glavne matrice. Zbog toga njena generacija postaje glavni čimbenik u evaluaciji performansi algoritama. Matrica se generira pomoću kriptografskih primitivnih funkcija na dva moguća načina: AES i SHAKE.
Na procesorima koji imaju sklopovsku potporu za brže izvođenje kriptografskih operacija, AES inačica je značajno brža. No, na procesorima bez sklopovske potpore, SHAKE je u pravilu brži. U svakom slučaju, vrijeme izvođenja algoritama je dovoljno brzo da ostane kompetentno sa ostalim algoritmima.
Sigurnost
FrodoKEM nudi tri varijante za tri razine sigurnosti, to su redom: FrodoKEM-640, FrodoKEM-976 i FrodoKEM-1344 koji odgovaraju razinama sigurnosti AES-128, AES-192 odnosno AES-256. Kao i za Kyber, jedine moguće slabe točke algoritma leže u rješavanju temeljnog LWE problema, te u eksploataciji kriptografskih primitiva.
Prednosti i mane
Najveća prednost FrodoKEM-a leži u njegovoj jednostavnosti; čini ga naročito skalabilnim te eliminira potencijalne ranjivosti koje proizlaze iz algebarske strukture. No, bitno je istaknuti da nedostatak strukture rezultira nešto duljim vremenom izvođenja te većom veličinom ključeva. Tablica ispod uspoređuje veličine ključeva Kybera i FrodoKEM-a (u byteovima).
| Shema | secret key | public key | ciphertext |
|---|---|---|---|
| Kyber512 | 1632 | 800 | 768 |
| FrodoKEM-640 | 19888 | 9616 | 9720 |
| Kyber768 | 2400 | 1184 | 1088 |
| FrodoKEM-976 | 31296 | 15632 | 15744 |
| Kyber1024 | 3168 | 1568 | 1568 |
| FrodoKEM-1344 | 43088 | 21520 | 21632 |
Imajući to na umu, FrodoKEM tim tvrdi da su ključevi i dalje dovoljno mali da ne utječu osjetno na propusnost u uobičajenoj komunikaciji.