Funcția îndoită

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 8 martie 2020; verificările necesită 2 modificări .

Funcția Bent (din engleză  bent  - „curved, inclined” [1] , [2] ) este o funcție booleană cu un număr par de variabile , pentru care distanța Hamming față de mulțimea de funcții booleene afine funcționează cu același număr de variabile este maxim. Funcțiile îndoite în acest sens au gradul maxim de neliniaritate între toate funcțiile cu un număr dat de variabile și datorită acestui fapt sunt utilizate pe scară largă în criptografie pentru a crea cifruri care sunt maxim rezistente la metodele de criptoanaliza liniară și diferențială [ 1] .

În literatura în limba rusă, este folosit termenul „funcție maxim neliniară ”, care are un sens apropiat; numărul de variabile ale unor astfel de funcții nu este limitat la numere pare. O funcție maxim neliniară cu un număr par de variabile este o funcție îndoită [1] .

Definiții

Distanța Hamming pentru două funcții booleene de n variabile este numărul de diferențe ale valorilor acestor funcții pe setul complet de 2 n seturi de variabile.

O funcție booleană afină (liniară)  este o funcție booleană al cărei polinom Zhegalkin nu are membri neliniari, adică membri care sunt o conjuncție de mai multe variabile.

Gradul de neliniaritate al funcției booleene deg ( f )  este numărul de variabile pe termenul cel mai lung al polinomului său Zhegalkin.

Neliniaritatea funcției booleene N ( f )  este distanța Hamming de la funcția dată la mulțimea tuturor funcțiilor afine.

Istorie

Funcțiile îndoite au fost introduse în anii 1960 de Oskar Rothaus (1927–2003), care la acea vreme (din 1960 până în 1966) lucra la Institutul de Analiză a Apărării (IDA), unde era angajat în cercetare criptografică. Prima sa lucrare despre funcțiile îndoite datează din 1966 [3] , dar a fost clasificată și a apărut în presa deschisă abia în 1976 [4] .

În anii 1960, V.A. Eliseev și O.P. Stepchenkov s-au angajat în studiul funcțiilor îndoite în URSS, dar munca lor este încă clasificată [1] . Se știe că au numit funcțiile îndoite „funcții minime” și au propus construcția lui McFarland încă din 1962.

Proprietăți

Neliniaritatea funcțiilor îndoite cu numărul de variabile n ( n  este par) este definită de relația [1] , [2] :

.

Pentru funcțiile maxim neliniare cu un număr impar de variabile, expresia exactă a neliniarității este necunoscută [1] .

Exemple de funcții îndoite

Mai jos sunt exemple de funcții îndoite ale patru, șase și opt variabile [5] .

Monografie

Cartea [1] oferă un studiu detaliat al rezultatelor în domeniul funcțiilor îndoite. Este luată în considerare istoria descoperirii funcțiilor îndoite, sunt descrise aplicațiile lor în criptografie și matematică discretă . Sunt investigate principalele proprietăți și reprezentări echivalente ale funcțiilor îndoite, clasificări ale funcțiilor îndoite într-un număr mic de variabile, construcții combinatorii și algebrice ale funcțiilor îndoite, conexiunea funcțiilor îndoite cu alte proprietăți criptografice. Se studiază distanțele dintre funcțiile îndoite și grupul de automorfisme ale funcțiilor îndoite. Sunt luate în considerare limitele superioare și inferioare pentru numărul de funcții îndoite și ipotezele despre valoarea sa asimptotică. Este oferită o revizuire sistematică detaliată a 25 de generalizări diferite ale funcțiilor îndoite și sunt luate în considerare întrebările deschise în acest domeniu. Cartea din 2015 [1] conține mai mult de 125 de teoreme ale funcției îndoite și extinde semnificativ cartea [2] publicată în 2011.

Note

  1. ↑ 1 2 3 4 5 6 7 8 N. Tokareva. Funcții îndoite: rezultate și aplicații la criptografie  (engleză)  // Acad. Presa. Elsevier, 2015. 220 pagini. : jurnal.
  2. ↑ 1 2 3 Tokareva N. N. Nonlinear Boolean functions: bent functions and their generalizations Arhivat 14 iulie 2012 la Wayback Machine // Editura Academică LAP LAMBERT (Saarbrucken, Germania), 2011. ISBN 978-3-8433- 0904-2 . 180 s.
  3. ↑ Rothaus O. Pe funcții îndoite // IDA CRD WP Nr. 169. 1966.
  4. ↑ OS Rothaus. Despre funcțiile „Bent”  (engleză)  // Journal of Combinatorial Theory, Seria A  : jurnal. - 1976. - Mai ( vol. 20 , nr. 3 ). - P. 300-305 . — ISSN 0097-3165 . - doi : 10.1016/0097-3165(76)90024-8 .
  5. ↑ Moldovan A.A. Criptografie. Speed ​​​​ciphers // BHV-Petersburg, 2002. ISBN 594157214X , ISBN 9785941572144 . 496 c.