Criptografie multivariată

Criptografiei cu variabile multiple este un set de tehnică chei criptografice publice bazată pe utilizarea polinoamelor multivariate cu coeficienți într - un câmp finit . Aceasta este una dintre direcțiile de cercetare luate în considerare pentru dezvoltarea criptografiei post-cuantice . În esență, securitatea construcțiilor care rezultă din această direcție de cercetare provine din faptul că rezoluția sistemelor de ecuații polinomiale este, în general, o problemă dificilă pentru NP .

Istorie

Prima schemă de criptare a acestei familii a fost descrisă de Tsutomu Matsumoto și Hideki Imai în 1988. Deși a fost rapid criptanalizat , a inspirat multe variante, inclusiv HFE , datorită lui Jacques Patarin . În timp ce HFE, așa cum a fost descris inițial, este considerat astăzi defect, variante precum UOV, HFE v- sau Rainbow sunt încă viabile. La fel, schema de semnături Sflash, oferită la competiția NESSIE , este acum complet ruptă.

Toate aceste criptosisteme au în comun faptul că cheia publică este alcătuită dintr-un set de polinoame multivariate, în general polinoame pătratice din motive de eficiență algoritmică și dimensiunea cheilor.

Principiu general

Fixăm un câmp finit , cheia publică este dată de un set: ${\ displaystyle \ mathbb {F}}$

${\ displaystyle G (x_ {1}, \ dotsc, x_ {n}) = \ left (G_ {1} (x_ {1}, \ dotsc, x_ {n}), \ dotsc, G_ {m} (x_ {1}, \ dotsc, x_ {n}) \ right)}$

unde fiecare . Un mesaj clar corespunde unei secvențe , iar criptarea constă pur și simplu în evaluarea fiecărui polinom al cheii publice în acest moment: ${\ displaystyle G_ {i} \ in \ mathbb {F} [x_ {1}, \ dotsc, x_ {n}]}$ ${\ displaystyle M = (m_ {1}, \ dotsc, m_ {n}) \ in \ mathbb {F} ^ {n}}$

${\ displaystyle C = G (M) = \ left (G_ {1} (M), \ dotsc, G_ {m} (M) \ right).}$

Vedem aici apărând unul dintre interesele acestei familii de tehnici criptografice: evaluarea polinomială este foarte eficientă din punct de vedere al calculului (și chiar, într-o anumită măsură, paralelizabilă), ceea ce permite o criptare relativ foarte rapidă. Până în prezent descrierea de mai sus se aplică tuturor metodelor de criptare multivariată.

Pentru a decripta, este necesar să aveți ca cheie secretă un mijloc de inversare , notat în general . Acest mijloc este specific criptării multivariate luate în considerare și de multe ori, prin studierea modului în care și inversul său sunt alese, a fost descoperit un atac: într-adevăr, este adesea o operație ușor reversibilă „mascată” de două transformări, destul de analogă. la abordarea utilizată pentru cifrele bazate pe cod, cum ar fi criptosistemul McEliece , pentru a ascunde codul. $G$ $G ^ {{- 1}}$ $G$

Pentru un set general de polinoame (adică nu prezintă o anumită structură exploatabilă de atacator), problema inversiunii se dovedește a fi NP-dificilă . Presupunând că P ≠ NP se presupune că nici măcar un computer cuantic nu poate rezolva această problemă eficient. Deoarece polinoamele utilizate în criptografia multivariată nu sunt în întregime aleatorii, ci sunt alese cu o structură ascunsă, argumentul de securitate este totuși doar euristic. $G$

Calculând inversul în loc de , obținem o schemă de semnături în loc de o schemă de criptare, unde de data aceasta verificarea publică a semnăturii este deosebit de eficientă. Una dintre atracțiile criptografiei multivariate pentru generarea semnăturilor este dimensiunea redusă a acestora în comparație cu alte abordări. ${\ displaystyle G ^ {- 1} (M)}$ ${\ displaystyle G (M)}$

Exemplu

Pentru a ilustra operația pe un exemplu simplu (preluat din criptosistemul Imai-Matsumoto), ne plasăm în corp , care are 4 elemente , pe care le vom nota respectiv . Să presupunem cheia publică dată de ${\ displaystyle \ mathbb {F} = \ mathbb {F} _ {2 ^ {2}} = \ mathbb {F} _ {2} [X] / (X ^ {2} + X + 1)}$ ${\ displaystyle 0,1, \ alpha, 1 + \ alpha}$ ${\ displaystyle 0,1,2,3}$

${\ displaystyle {\ begin {align} G_ {1} & = 1 + x_ {2} + 2x_ {0} x_ {2} + 3x_ {1} ^ {2} + 3x_ {1} x_ {2} + x_ {2} ^ {2} \\ G_ {2} & = 1 + 3x_ {0} + 2x_ {1} + x_ {2} + x_ {0} ^ {2} + x_ {0} x_ {1} + 3x_ {0} x_ {2} + x_ {1} ^ {2} \\ G_ {3} & = 3x_ {2} + x_ {0} ^ {2} + 3x_ {1} ^ {2} + x_ { 1} x_ {2} + 3x_ {2} ^ {2} \\\ end {align}}}$

și mesajul , apoi primim criptat ${\ displaystyle M = (1,2,3)}$

${\ displaystyle C = G (M) = (0,0,1)}$

Primitive bazate pe criptografie multivariată

Scheme de criptare:

Ecuații de câmp ascuns (HFE) și variantele sale HFE + , HFE - , HFE v , HFE f și HFE v- .
Ulei și oțet dezechilibrat (UOV)

Scheme de semnături:

Sflash
Cuarţ

Referințe

(în) Tsutomu Matsumoto și Hideki Imai , " Public Quadratic Polynomial-tuples for Efficient Signature-Verification and Message-Encryption " , Advances in Cryptology - EUROCRYPT '88 , Springer, Berlin, Heidelberg, citiți Notes in Computer Science,25 mai 1988, p. 419–453 ( ISBN 3540459618 , DOI 10.1007 / 3-540-45961-8_39 , citit online , accesat la 28 februarie 2018 )
(în) Jacques Patarin , " Cryptanalysis of the Matsumoto and Imai Public Scheme of Eurocrypt'88 " , Advances in Cryptology - CRYPTO '95 , Springer, Berlin, Heidelberg, citit Note in Computer Science,27 august 1995, p. 248–261 ( ISBN 3540447504 , DOI 10.1007 / 3-540-44750-4_20 , citit online , accesat la 28 februarie 2018 )
(în) Jacques Patarin , „ Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms ” , Advances in Cryptology - EUROCRYPT '96 , Springer, Berlin, Heidelberg, citește Note in Computer Science, În plus, trebuie să știți mai multe despre asta.12 mai 1996, p. 33–48 ( ISBN 3540683399 , DOI 10.1007 / 3-540-68339-9_4 , citit online , accesat la 28 februarie 2018 )
(ro) Jean-Charles Faugère și Antoine Joux , " Criptanaliza algebrică a ecuațiilor de câmp ascuns (HFE) Cryptosystems Using Gröbner Bases " , Advances in Cryptology - CRYPTO 2003 , Springer, Berlin, Heidelberg, citit Note in Computer Science,17 august 2003, p. 44–60 ( ISBN 9783540406747 , DOI 10.1007 / 978-3-540-45146-4_3 , citit online , accesat la 28 februarie 2018 )
(în) Louis Granboulan Antoine Joux și Jacques Stern , „ Inverting HFE Is Quasipolynomial ” , Advances in Cryptology - CRYPTO 2006 , Springer, Berlin, Heidelberg, citit Note in Computer Science,20 august 2006, p. 345–356 ( DOI 10.1007 / 11818175_20 , citit online , accesat la 28 februarie 2018 )
(în) Aviad Kipnis și Adi Shamir , " Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization " , Advances in Cryptology - CRYPTO '99 , Springer, Berlin, Heidelberg, citit Note in Computer Science,15 august 1999, p. 19–30 ( ISBN 3540484051 , DOI 10.1007 / 3-540-48405-1_2 , citit online , accesat la 28 februarie 2018 )
(în) Luk Bettale , Jean-Charles Faugère și Ludovic Perret , " Criptanaliza HFE, HFE și multi-variante pentru caracteristicile impare și pare " , Modele, coduri și criptografie , vol. 69, n o 1,1 st octombrie 2013, p. 1–52 ( ISSN 0925-1022 și 1573-7586 , DOI 10.1007 / s10623-012-9617-2 , citit online , accesat la 28 februarie 2018 )
(în) Jeremy Vates și Daniel Smith-Tone , " Key Recovery Attack for All Parameters of HFE- " , Post-Quantum Cryptography , Springer, Ham, Reading Notes in Computer Science,26 iunie 2017, p. 272–288 ( ISBN 9783319598789 , DOI 10.1007 / 978-3-319-59879-6_16 , citit online , accesat la 28 februarie 2018 )
(în) Nicolas T. Courtois , „ Securitatea ecuațiilor de câmp ascuns (HFE) ” , Subiecte în criptologie - CT-RSA 2001 , Springer, Berlin, Heidelberg, citit Note în informatică,8 aprilie 2001, p. 266–281 ( ISBN 3540453539 , DOI 10.1007 / 3-540-45353-9_20 , citit online , accesat la 28 februarie 2018 )
(în) Aviad Kipnis , Jacques Patarin și Louis Goubin , „ Scheme de semnături de ulei și oțet dezechilibrate ” , Progrese în criptologie - EUROCRYPT '99 , Springer, Berlin, Heidelberg, citiți Note în informatică,2 mai 1999, p. 206–222 ( ISBN 354048910X , DOI 10.1007 / 3-540-48910-x_15 , citit online , accesat la 28 februarie 2018 )
(în) Ryann Cartor Ryan Gipson , Daniel Smith-Tone și Jeremy Vates , „ Despre securitatea diferențialei HFEv-Signature Primitive ” , Criptografie post-cuantică , Springer, Ham, Reading Notes in Computer Science,24 februarie 2016, p. 162–181 ( ISBN 9783319293592 , DOI 10.1007 / 978-3-319-29360-8_11 , citit online , accesat la 28 februarie 2018 )
(în) Albrecht Petzoldt , Ming-Shing Chen , Bo-Yin Yang și Chengdong Tao , „ Principii de proiectare pentru scheme de semnături multivariate bazate pe HFEv ” , Progrese în criptologie - ASIACRYPT 2015 , Springer, Berlin, Heidelberg, citiți Note în informatică ,29 noiembrie 2015, p. 311–334 ( ISBN 9783662487969 , DOI 10.1007 / 978-3-662-48797-6_14 , citit online , accesat la 28 februarie 2018 )
(în) Jintai Ding și Dieter Schmidt , „ Rainbow in New Multivariable Polynomial Signature Scheme ” , Criptografie aplicată și securitate a rețelelor , Springer, Berlin, Heidelberg, citit Note în informatică,7 iunie 2005, p. 164–175 ( DOI 10.1007 / 11496137_12 , citit online , accesat la 28 februarie 2018 )
(în) Koichi Sakumoto , Taizo Shirai și Harunaga Hiwatari , „ este demonstrabil și securitatea schemelor de semnătură HFE UOV contre-Attached Message Attack ” , criptografie post-cuantică , Springer, Berlin, Heidelberg, citiți Note în informatică,29 noiembrie 2011, p. 68–82 ( ISBN 9783642254048 , DOI 10.1007 / 978-3-642-25405-5_5 , citit online , accesat la 28 februarie 2018 )
(în) Nicolas T. Courtois , Magnus Daum și Patrick Felke , „ Despre securitatea HFE, HFEv- și cuarț ” , Criptografie cu cheie publică - PKC 2003 , Springer, Berlin, Heidelberg, citit Note în informatică,6 ianuarie 2003, p. 337–350 ( ISBN 3540362886 , DOI 10.1007 / 3-540-36288-6_25 , citit online , accesat la 28 februarie 2018 )
(în) J. Ding și A. Petzoldt , „ Starea actuală a criptografiei multivariate ” , IEEE Security Privacy , vol. 15, n o 4,2017, p. 28-36 ( ISSN 1540-7993 , DOI 10.1109 / msp.2017.3151328 , citit online , accesat la 28 februarie 2018 )
(în) Mehdi-Laurent Akkar , Nicolas T. Courtois , Romain Duteuil și Louis Goubin , " A Fast and Secure Implementation of Sflash " , Public Key Cryptography - PKC 2003 , Springer, Berlin, Heidelberg, citit Note in Computer Science,6 ianuarie 2003, p. 267-278 ( ISBN 3540362886 , DOI 10.1007 / 3-540-36288-6_20 , citit on - line , accesat 28 februarie 2018 )
(în) Vivien Dubois , Pierre-Alain Fouque , Adi Shamir și Jacques Stern , " Criptanaliza practică a SFLASH " , Progrese în criptologie - CRYPTO 2007 , Springer, Berlin, Heidelberg, citit Note în informatică,19 august 2007, p. 1-12 ( ISBN 9783540741428 , DOI 10.1007 / 978-3-540-74143-5_1 , citit online , accesat la 28 februarie 2018 )
(în) Charles Bouillaguet , Pierre-Alain Fouque și Gilles Macario-Rat , " Practical Key-Recovery for All Possible Parameters of SFLASH " , Advances in Cryptology - ASIACRYPT 2011 , Springer, Berlin, Heidelberg, citit Note in Computer Science,4 decembrie 2011, p. 667–685 ( ISBN 9783642253843 , DOI 10.1007 / 978-3-642-25385-0_36 , citit online , accesat la 28 februarie 2018 )
(în) Jacques Patarin , Nicolas Courtois și Louis Goubin , " QUARTZ, 128-Bit Long Digital Signatures " , Subiecte în criptologie - CT-RSA 2001 , Springer, Berlin, Heidelberg, citit Note în informatică,8 aprilie 2001, p. 282–297 ( ISBN 3540453539 , DOI 10.1007 / 3-540-45353-9_21 , citit online , accesat la 28 februarie 2018 )