BIKE

Općenito o algoritmu

BIKE je još jedna kodna shema bazirana na kvazi cikličkim polinomima koja nudi tri verzije (BIKE-1, BIKE-2 te BIKE-3). Nastao je 2017. godine kao produkt rada sedamnaestero doktoranada iz Francuske, Sjedinjenih Država, Izraela i Njemačke pri čemu je dio autora sudjelovalo i u dizajniranju i HQC algoritma.

Parametri

Veličina bloka je r za kodne riječi duljine n = 2 * r, a Hammingova težina w = sqrt(n) te vrijedi da je w paran, a w/2 neparan. Težinu unesenog vektora pogreške označavamo sa t, a duljinu dijeljene tajne sa l. M = {0, 1}^l je prostor mogućih poruka, a K = {0, 1}^l je prostor mogućih ključeva.

Dekoder je, dakle, zasnovan na principu QC-MDPC (kvazi ciklički srednje gusti kôd provjere pariteta) i ispravljanju namjerno unesenih pogrešaka sa zadovoljavajuće visokom vjerojatnošću. Javni je ključ sastavljen od h₁h₀^-1 te se on šalje sugovorniku u komunikaciji. On zatim koristi njega da stvori poruku kao (e₀ + e₁ h₁h₀^-1, h₁h₀^-1) te se oslanjamo na činjenicu da je vrlo težak problem razlučiti kriptat od slučajnog vektora ((e₀, e₁), h₁h₀^-1). Privatni ključ za dekriptiranje je sastavljen kao konkatenacija dvaju ciklučkih matrica polinoma H₀ i H₁.

Sigurnost

Razlikuje se od prethodno obrađenog HQC i McEliece algoritama po svojstvu da nije IND-CCA2 siguran, već IND-CCA1 siguran. To je i za očekivati s obzirom na to da je skup važećih matrica za njegovo generiranje zapravo nadskup od McEliece algoritma te su zahtjevi na sigurnost time i slabiji. Znači da nije otporan na postepenu dedukciju ključa iz modela u kojem napadač može slati proizvoljan broj kriptiranih poruka. To za posljedicu ima potrebu da se pronalazi novi ključ iz prostora ključeva za svaku sjednicu komunikacije odnosno poruku.

Prednosti i nedostaci

Prethodno navedene tri verzije BIKE-a idejno odgovaraju NIST-ovim razinama sigurnosti: 1, 3 i 5 (ekvivalent AES-128, AES-192, AES-256 razinama sigurnosti). Parametri za petu razinu sigurnosti odabrani su naknadno na NIST-ov zahtjev na kraju drugog kruga selekcije. Ono što BIKE stvarno čini posebnim od ostalih kandidata jest trud uložen u optimizaciju njegovog izvođenja kako bi se nadomjestila nužnost jednokratnih ključeva. Jan Richter-Brockmann i Tim Güneysu su autori VHDL hardverske implementacije BIKE-a visokih performansi čiji je kod dostupan na Githubu.

Veličine BIKE ključeva, iako velike u usporedbi sa tradicionalnim metodama kriptiranja, nisu znatno veće od prosječnog RSA 4096-bitnog ključa. Konkretne veličine elemenata u sustavu možemo vidjeti u tablici ispod izražene u bitovima:

Element	Size	Razina 1	Razina 2	Razina 3
Privatni ključ	l+ w * ⌈log2(r)⌉	2,244	3,346	4,640
Javni ključ	r	12,323	24,659	40,973
Kriptat	r + l	12,579	24,915	41,229

Reference

• https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions
• https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/submissions/BIKE-Round3.zip
• https://bikesuite.org/
• https://bikesuite.org/files/v4.1/BIKE_Spec.2020.10.22.1.pdf
• https://github.com/Chair-for-Security-Engineering/BIKE