HQC
Općenito
HQC (Hamming Quasi-Cyclic) je algoritam šifriranja javnim ključem dizajniran da pruži sigurnost od napada klasičnih i kvantnih računala. HQC je jedan od zamjenskih kandidata za pobjednike trećeg kruga kandidata NIST-ov natječaja za izbor novih asimetričnih algoritama za uspostavu tajnog ključa otpornih na napade kvantnim računalom.
Tim koji je razvio HQC čine članovi: Carlos Aguilar Melchor, Nicolas Aragon, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jurjen Bos, Jean-Christophe Deneuville, Arnaud Dion, Philippe Gaborit, Jérôme Lacan, Edoardo Persichetti, Jean-Marc Robert, Pascal Véron i Gilles Zémor.
HQC započinje s verzijom PKE koja se kasnije razvija u KEM-DEM koji postiže IND-CCA2 razinu sigurnosti.
Glavne prednosti HQC-a u odnosu na postojeće kriptosustave koji se temelje na kodu su njegovo smanjenje IND-CPA na jednostavniji teoretski problem kodiranja, uspješan protiv napada koji cilja oporavak skrivene strukture koda, mala veličina javnog ključa, točna procjena stope neuspjeha u dekripciji i djelotvorne implementacije temeljene na klasičnim algoritmima dekodiranja.
Ograničenje HQC algoritma (barem za verziju PKE) je niska kripcijska stopa. Moguće je šifrirati 256 bitova otvorenog teksta prema zahtjevu NIST-a, ali povećavajući tu stopu također se povećavaju parametri.
HQC nudi tri razine sigurnosti: HQC-128, HQC-192, HQC-256.
Parametri
Postoji nekoliko skupova parametara koji ciljaju različite razine sigurnosti s DFR-om povezanim s tim razinama sigurnosti. Predloženi skupovi parametara pokrivaju sigurnosne kategorije 1, 3 i 5 (za 128, 192 i 256 bitova sigurnosti). Za svaki skup parametara, parametri su odabrani tako da minimalni radni faktor najpoznatijeg napada premaši sigurnosni parametar. Smatra se w = O √n .
U tablici veličina parametara, n1 označava duljinu Reed-Salomonovog koda, n2 duljinu Reed-Mullerovog koda tako da duljina spojenog koda C iznosi n1n2 (ambijentalni prostor ima duljinu n, a najmanji primitivni prosti broj veći od n1n2 je potreban kako bi se izbjegli algebarski napadi). w je težina n-dimenzionalnih vektora x, y, wr težina r1 i r2 te je prema tome we = w (e) za ovaj kriptosustav. pfail je vjerojatnost pogreške prilikom šifriranja i dekripcije javnim ključem.
Veličina parametara
| instanca | n1 | n2 | n | w | wr = we | razina sigurnosti | pfail |
|---|---|---|---|---|---|---|---|
| hqc-128 | 46 | 384 | 17.669 | 66 | 75 | 128 | < 2-128 |
| hqc-192 | 56 | 640 | 35.851 | 100 | 114 | 192 | < 2-192 |
| hqc-256 | 90 | 640 | 57.637 | 131 | 149 | 256 | < 2-256 |
| instanca | veličina pk (bit) | veličina sk (bit) | veličina ct (bit) | veličina ss (bit) |
|---|---|---|---|---|
| hqc-128 | 2.249 | 40 | 4.481 | 64 |
| hqc-192 | 4.522 | 40 | 9.026 | 64 |
| hqc-256 | 7.245 | 40 | 14.469 | 64 |
Očekivana razina sigurnosti
Praktična složenost problema SD-a za Hammingovu metriku široko je proučavana više od 50 godina. Najučinkovitiji napadi temelje se na dekodiranju skupa informacija, a prvo je tehniku uveo Prange 1962., kasnije je poboljšao Stern, zatim Dumer. Nedavni radovi sugeriraju složenost reda 2cw (1 + negl (1)), za neku konstantu c. Posebni dio koji se fokusira na režim w = negl (n) potvrđuje ovu formulu, uz jaku ovisnost između c i brzine k/n koda koji se koristi.
Kvazi-ciklički kodovi imaju posebnu strukturu koja može potencijalno otvaraju vrata za specifične strukturne napade. Prvi generički napad je DOOM napad koji zbog cikličnosti podrazumijeva dobitak od O (√n) (kada je dobitak u O (n) za MDPC kodove jer se kod generira na osnovi vektora male težine). Također je moguće razmotriti napade na oblik polinoma koji generira cikličku strukturu. Takvi napadi posebno su učinkoviti kada je polinom xn - 1 ima mnogo faktora niskog stupnja. Ti napadi postaju nedjelotvorni čim xn – 1 ima samo dva nesvodljiva faktora oblika (x - 1) i xn -1 + xn -2 + ... + x + 1, što je slučaj kada je n prost i q generira multiplikativnu skupinu (Z /nZ). Takvi su brojevi poznati do vrlo velikih vrijednosti.
HQC ima različite skupove parametara koji pružaju 128 (kategorija 1), 192 (kategorija 3) i 256 (kategorija 5) bitova klasične (tj. pretkvantne) sigurnosti. Kvantna sigurnost dobiva se dijeljenjem sigurnosnih bitova za dva (uzimajući drugi korijen složenosti). Kada je w = O (√n), najpoznatiji napadi imaju složenost u 2-t ln (1 - R) (1 + o (1)) gdje t = O (w), a R je stopa koda. U ovom algoritmu je t = 2w i R = 1/2 za redukciju na problem 2-DQCSD, a t = 3wr i R = 1/3 za 3-DQCSD problem. Uzimajući u obzir DOOM napad, kao i činjenicu da se smatraju uravnoteženim vektorima (x, y) i (r1, e, r2) za napad (koji zahtijeva samo vrlo mali faktor jer slučajne riječi imaju dobru vjerojatnost uravnoteženja na svakom bloku), ova složenost se mora podijeliti s približno √n (do faktora polinoma). Varijabla o(1) je log ((nw) 2 / (2n2w)) i log ((nwr) 3 / (3n3wr)) za 2-DQCSD i 3-DQCSD probleme. Dakle, smanjenje sigurnosti čvrsto odgovara generičkim primjerima klasičnih problema 2-DQCSD i 3-DQCSD.