Criptografia multivariată

Criptografia multivariată este termenul generic pentru primitivele criptografice asimetrice bazate pe polinoame multivariate pe un câmp finit F. În anumite cazuri, aceste polinoame ar putea fi definite atât pe un câmp fundamental, cât și pe un câmp de extensie. Dacă polinoamele au gradul doi, vorbim despre ecuații de gradul doi multivariate. Rezolvarea sistemelor de ecuații polinomiale multivariate s-a dovedit a fi NP-completă.[1] Aceste scheme sunt adesea considerate a fi candidați buni pentru criptografia post-cuantică. Criptografia multivariată a fost foarte productivă în ceea ce privește proiectarea și criptanaliza. Per total, situația este acum mai stabilă, iar cele mai puternice scheme au rezistat testului timpului. Se admite în general că criptografia multivariată s-a dovedit a fi mai eficientă ca abordare pentru construirea schemelor de semnătură, în principal pentru că schemele multivariate oferă cea mai scurtă semnătură dintre algoritmii post-cuantici.

Istoric

Tsutomu Matsumoto și Hideki Imai (1988) au prezentat așa-numita lor schemă C* la conferința Eurocrypt. Deși C* a fost descifrat de Jacques Patarin (1995), principiul general al lui Matsumoto și Imai a inspirat o generație de propuneri îmbunătățite. În lucrări ulterioare, „Criptosistemele Monomiale Ascunse” au fost dezvoltate de Jacques Patarin. Acestea se bazează pe un câmp fundamental și un câmp de extensie. „Ecuațiile câmpului ascuns” (HFE), dezvoltate de Patarin în 1996, rămân o schemă multivariată populară astăzi [P96]. Securitatea HFE a fost investigată temeinic, începând cu un atac direct de bază Gröbner [FJ03, GJS06], atacuri de recuperare a cheilor (Kipnis & Shamir 1999) [BFP13] și multe altele. Versiunea simplă a HFE este considerată a fi practic descifrată, în sensul că parametrii siguri duc la o schemă impracticabilă. Cu toate acestea, unele variante simple ale HFE, cum ar fi varianta minus și varianta oțet, permit consolidarea HFE de bază împotriva tuturor atacurilor cunoscute.

Pe lângă HFE, Patarin a dezvoltat și alte scheme. În 1997 a prezentat „Balanced Oil & Vinegar” (Ulei și oțet echilibrate), iar în 1999 „Unbalanced Oil and Vinegar” (Ulei și oțet neechilibrate), în cooperare cu Aviad Kipnis și Louis Goubin (Kipnis, Patarin & Goubin 1999).

Construcție

Echipamentele de gradul doi multivariate implică o cheie publică și una privată. Cheia privată constă din două transformări afine, S și T, și o aplicație de gradul doi ușor de inversat P′ : F^m → Fⁿ. Notăm matricea n × n a endomorfismelor afine S : Fⁿ → Fⁿ cu M_S și vectorul de deplasare cu v_S ∈ Fⁿ și similar pentru T : F^m → F^m. Cu alte cuvinte,

• S(x) = M_Sx + v_S și
• T(y) = M_Ty + v_T.

Tripla (S⁻¹, P^′−1, T⁻¹) este cheia privată, cunoscută și sub numele de trapă. Cheia publică este compoziția P = S ∘ P′ ∘ T care, prin presupunere, este greu de inversat fără cunoașterea trapei.

Semnătura

Semnăturile sunt generate folosind cheia privată și sunt verificate folosind cheia publică după cum urmează. Mesajul este hashat într-un vector în y ∈ Fⁿ prin intermediul unei funcții hash cunoscute. Semnătura este

x = P⁻¹(y) = T⁻¹(P′⁻¹(S⁻¹(y)).

Destinatarul documentului semnat trebuie să dețină cheia publică P. El calculează hash-ul y și verifică dacă semnătura x îndeplinește P(x) = y.

Aplicații

• Ulei și oțet dezechilibrate
• Ecuații de câmp ascuns
• SFLASH de NESSIE
• Rainbow
• TTS
• QUARTZ
• QUAD (cifru)
• Patru scheme de semnătură criptografică multivariată (GeMMS, LUOV, Rainbow și MQDSS) și-au croit drum în a doua rundă a competiției post-cuantice NIST: consultați diapozitivul 12 al raportului.[2]

Referințe

1. Garey, Michael R. (1979). Computers and intractability : a guide to the theory of NP-completeness. Johnson, David S., 1945-. San Francisco: W.H. Freeman. ISBN 0-7167-1044-7. OCLC 4195125.
2. Moody, Dustin (22 August 2019). „The 2nd Round of the NIST PQC Standardization Process„. NIST. Retrieved 11 October 2020.

(Include texte traduse și adaptate din Wikipedia de Nicolae Sfetcu)