Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Бент-функція (від англ. bent — вигнутий, нахилений) — булева функція з парним числом змінних, для якої відстань Геммінга від множини афінних булевих функцій з тим самим числом змінних найбільша. Бент-функції в цьому сенсі мають найбільший ступінь нелінійності серед усіх функцій з даним числом змінних і завдяки цьому широко застосовуються в криптографії для створення шифрів, максимально стійких до методів лінійного та диференціального криптоаналізу.
Близьким за змістом є термін «максимально нелінійна функція», кількість змінних таких функцій не обмежується парними числами. Максимально нелінійна функція з парною кількістю змінних є бент-функцією.
Визначення
Відстань Геммінга для двох булевих функцій n змінних — кількість відмінностей у значеннях цих функцій на повній множині 2n наборів змінних.
Афінна (лінійна) булева функція — булева функція, поліном Жегалкіна якої не має нелінійних членів, тобто членів, що є кон'юнкцією декількох змінних.
Ступінь нелінійності булевої функції deg(f) — число змінних у найдовшому доданку її полінома Жегалкіна.
Нелінійність булевої функції N(f) — відстань Геммінга від даної функції до множини всіх афінних функцій.
Історія
Бент-функції запровадив у 1960-х роках Оскар Ротгауз (1927—2003), який тоді (від 1960 до 1966 року) працював у [en] (IDA), де займався криптографічними дослідженнями. Його перша робота з бент-функцій відноситься до , проте вона була засекречена й у відкритій пресі з'явилася тільки 1976 року.
У 1960-х роках В. А. Єлісєєв та О. П. Степченков досліджували бент-функції в СРСР, проте їхні роботи досі засекречено. Відомо, що вони називали бент-функції «мінімальними функціями» і запропонували побудову Макфарланда ще 1962 року.
Властивості
Нелінійність бент-функцій із кількістю змінних n (n — парне) визначається співвідношенням:
![image]()
.
Для максимально нелінійних функцій з непарним числом змінних точного виразу нелінійності невідомо.
Приклади бент-функцій
Нижче наведено приклади бент-функцій чотирьох, шести та восьми змінних.
Монографія
У книзі наведено докладний огляд результатів у галузі бент-функцій. Розглянуто історію відкриття бент-функцій, описано їх застосування в криптографії та дискретній математиці. Досліджуються основні властивості та еквівалентні подання бент-функцій, класифікації бент-функцій від малої кількості змінних, комбінаторні та алгебричні побудови бент-функцій, зв'язок бент-функцій з іншими криптографічними властивостями. Вивчаються відстані між бент-функціями та група автоморфізмів бент-функцій. Розглянуто верхні та нижні оцінки числа бент-функцій та гіпотези про його асимптотичне значення. Наведено докладний систематичний огляд 25 різних узагальнень бент-функцій, розглянуто відкриті питання в цій галузі. Книга 2015 року містить понад 125 теорем про бент-функції та суттєво розширює книгу, опубліковану 2011 року.
Примітки
- N. Tokareva. Bent functions: results and applications to cryptography : ( )[англ.] // Acad. Press. Elsevier, 2015. 220 pages. : журнал.
- Токарева Н. Н. Нелинейные булевы функции: бент-функции и их обобщения [ 2012-07-14 у Wayback Machine.] // Издательство LAP LAMBERT Academic Publishing (Saarbrucken, Germany), 2011. . 180 с.
- Rothaus O. On bent functions // IDA CRD W.P. No. 169. 1966.
- O. S. Rothaus. On "Bent" Functions : ( )[англ.] // : журнал. — 1976. — Vol. 20, № 3 (May). — С. 300—305. — ISSN 0097-3165. — DOI:10.1016/0097-3165(76)90024-8.
- Молдовян А. А. Криптография. Скоростные шифры // БХВ-Петербург, 2002. , . 496 c.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Bent funkciya vid angl bent vignutij nahilenij buleva funkciya z parnim chislom zminnih dlya yakoyi vidstan Gemminga vid mnozhini afinnih bulevih funkcij z tim samim chislom zminnih najbilsha Bent funkciyi v comu sensi mayut najbilshij stupin nelinijnosti sered usih funkcij z danim chislom zminnih i zavdyaki comu shiroko zastosovuyutsya v kriptografiyi dlya stvorennya shifriv maksimalno stijkih do metodiv linijnogo ta diferencialnogo kriptoanalizu Dvijkovi bent funkciyi z vidstannyu Gemminga sho dorivnyuye 1 i nelinijnistyu 22 1 222 1 2 1 1 displaystyle 2 2 1 2 frac 2 2 1 2 1 1 Nelinijnist bent funkciyi x1x2 x3x4 displaystyle x 1 x 2 x 3 x 4 dorivnyuye 24 1 242 1 8 2 6 displaystyle 2 4 1 2 frac 4 2 1 8 2 6 Blizkim za zmistom ye termin maksimalno nelinijna funkciya kilkist zminnih takih funkcij ne obmezhuyetsya parnimi chislami Maksimalno nelinijna funkciya z parnoyu kilkistyu zminnih ye bent funkciyeyu ViznachennyaVidstan Gemminga dlya dvoh bulevih funkcij n zminnih kilkist vidminnostej u znachennyah cih funkcij na povnij mnozhini 2n naboriv zminnih Afinna linijna buleva funkciya buleva funkciya polinom Zhegalkina yakoyi ne maye nelinijnih chleniv tobto chleniv sho ye kon yunkciyeyu dekilkoh zminnih Stupin nelinijnosti bulevoyi funkciyi deg f chislo zminnih u najdovshomu dodanku yiyi polinoma Zhegalkina Nelinijnist bulevoyi funkciyi N f vidstan Gemminga vid danoyi funkciyi do mnozhini vsih afinnih funkcij IstoriyaBent funkciyi zaprovadiv u 1960 h rokah Oskar Rotgauz 1927 2003 yakij todi vid 1960 do 1966 roku pracyuvav u en IDA de zajmavsya kriptografichnimi doslidzhennyami Jogo persha robota z bent funkcij vidnositsya do prote vona bula zasekrechena j u vidkritij presi z yavilasya tilki 1976 roku U 1960 h rokah V A Yelisyeyev ta O P Stepchenkov doslidzhuvali bent funkciyi v SRSR prote yihni roboti dosi zasekrecheno Vidomo sho voni nazivali bent funkciyi minimalnimi funkciyami i zaproponuvali pobudovu Makfarlanda she 1962 roku VlastivostiNelinijnist bent funkcij iz kilkistyu zminnih n n parne viznachayetsya spivvidnoshennyam N f 2n 1 2n2 1 displaystyle N f 2 n 1 2 frac n 2 1 Dlya maksimalno nelinijnih funkcij z neparnim chislom zminnih tochnogo virazu nelinijnosti nevidomo Prikladi bent funkcijNizhche navedeno prikladi bent funkcij chotiroh shesti ta vosmi zminnih n 4 f1 X x1x3 x2x4 N f1 6 displaystyle n 4 f 1 X x 1 x 3 oplus x 2 x 4 N f 1 6 n 6 f2 X x1x2x3 x1x4 x2x5 x3x6 N f2 28 displaystyle n 6 f 2 X x 1 x 2 x 3 oplus x 1 x 4 oplus x 2 x 5 oplus x 3 x 6 N f 2 28 n 8 f3 X x1x2x3 x2x4x5 x1x2 x1x4 x2x6 x3x5 x4x5 x7x8 N f3 120 displaystyle n 8 f 3 X x 1 x 2 x 3 oplus x 2 x 4 x 5 oplus x 1 x 2 oplus x 1 x 4 oplus x 2 x 6 oplus x 3 x 5 oplus x 4 x 5 oplus x 7 x 8 N f 3 120 n 8 f4 X x1x2x3 x2x4x5 x3x4x6 x1x4 x2x6 x3x4 x3x5 x3x6 x4x5 x4x6 x7x8 N f4 120 displaystyle n 8 f 4 X x 1 x 2 x 3 oplus x 2 x 4 x 5 oplus x 3 x 4 x 6 oplus x 1 x 4 oplus x 2 x 6 oplus x 3 x 4 oplus x 3 x 5 oplus x 3 x 6 oplus x 4 x 5 oplus x 4 x 6 oplus x 7 x 8 N f 4 120 MonografiyaU knizi navedeno dokladnij oglyad rezultativ u galuzi bent funkcij Rozglyanuto istoriyu vidkrittya bent funkcij opisano yih zastosuvannya v kriptografiyi ta diskretnij matematici Doslidzhuyutsya osnovni vlastivosti ta ekvivalentni podannya bent funkcij klasifikaciyi bent funkcij vid maloyi kilkosti zminnih kombinatorni ta algebrichni pobudovi bent funkcij zv yazok bent funkcij z inshimi kriptografichnimi vlastivostyami Vivchayutsya vidstani mizh bent funkciyami ta grupa avtomorfizmiv bent funkcij Rozglyanuto verhni ta nizhni ocinki chisla bent funkcij ta gipotezi pro jogo asimptotichne znachennya Navedeno dokladnij sistematichnij oglyad 25 riznih uzagalnen bent funkcij rozglyanuto vidkriti pitannya v cij galuzi Kniga 2015 roku mistit ponad 125 teorem pro bent funkciyi ta suttyevo rozshiryuye knigu opublikovanu 2011 roku PrimitkiN Tokareva Bent functions results and applications to cryptography angl Acad Press Elsevier 2015 220 pages zhurnal Tokareva N N Nelinejnye bulevy funkcii bent funkcii i ih obobsheniya 2012 07 14 u Wayback Machine Izdatelstvo LAP LAMBERT Academic Publishing Saarbrucken Germany 2011 ISBN 978 3 8433 0904 2 180 s Rothaus O On bent functions IDA CRD W P No 169 1966 O S Rothaus On Bent Functions angl zhurnal 1976 Vol 20 3 May S 300 305 ISSN 0097 3165 DOI 10 1016 0097 3165 76 90024 8 Moldovyan A A Kriptografiya Skorostnye shifry BHV Peterburg 2002 ISBN 594157214X ISBN 9785941572144 496 c