Функция изгиба
Специальный тип булевой функции
Четыре 2-арные булевы функции с весом Хэмминга 1 являются изогнутыми, т. е. их нелинейность равна 1 (эти матрицы Адамара показывают расстояние Хэмминга до каждой из восьми линейных и аффинных функций) .
Следующая формула показывает, что 2-арная функция искривляется, когда ее нелинейность равна 1:
2 2 − 1 − 2 2 2 − 1 = 2 − 1 = 1 {\displaystyle 2^{2-1}-2^{{\frac {2}{2}}-1}=2-1=1}
Булева функция является изогнутой, т.е. ее нелинейность равна 6 (что и показывают эти матрицы Адамара) . х 1 х 2 ⊕ х 3 х 4 {\displaystyle x_{1}x_{2}\oplus x_{3}x_{4}}
Следующая формула показывает, что 4-арная функция изгибается, когда ее нелинейность равна 6:
2 4 − 1 − 2 4 2 − 1 = 8 − 2 = 6 {\displaystyle 2^{4-1}-2^{{\frac {4}{2}}-1}=8-2=6}

В математической области комбинаторики бент -функция — это булева функция , которая максимально нелинейна; она максимально отличается от множества всех линейных и аффинных функций при измерении с помощью расстояния Хэмминга между таблицами истинности . Конкретно, это означает, что максимальная корреляция между выходом функции и линейной функцией минимальна. Кроме того, производные бент-функции являются сбалансированными булевыми функциями, поэтому при любом изменении входных переменных существует 50-процентная вероятность того, что выходное значение изменится.

Максимальная нелинейность означает, что аппроксимация изогнутой функции аффинной (линейной) функцией является сложной, полезное свойство в защите от линейного криптоанализа . Кроме того, обнаружение изменения в выходных данных функции не дает никакой информации о том, какое изменение произошло во входных данных, что делает функцию невосприимчивой к дифференциальному криптоанализу .

Бент-функции были определены и названы в 1960-х годах Оскаром Ротхаусом в исследовании, опубликованном только в 1976 году. [1] Они были широко изучены для их приложений в криптографии , но также применялись к расширенному спектру , теории кодирования и комбинаторному проектированию . Определение может быть расширено несколькими способами, что приводит к различным классам обобщенных бент-функций, которые разделяют многие из полезных свойств оригинала.

Известно, что в СССР в 1962 году В. А. Елисеев и О. П. Степченков изучали бент-функции, названные ими минимальными функциями . [2] Однако их результаты до сих пор не рассекречены.

Бент-функции также известны как идеально нелинейные ( PN ) булевы функции. Некоторые функции, которые максимально приближены к идеальной нелинейности (например, для функций нечетного числа бит или векторных функций), известны как почти идеально нелинейные ( APN ). [3]

преобразование Уолша

Бент-функции определяются в терминах преобразования Уолша . Преобразование Уолша булевой функции — это функция, заданная формулой ф : З 2 н → З 2 {\displaystyle f:\mathbb {Z} _{2}^{n}\to \mathbb {Z} _{2}} ф ^ : З 2 н → З {\displaystyle {\hat {f}}:\mathbb {Z} _{2}^{n}\to \mathbb {Z} }

ф ^ ( а ) = ∑ х ∈ З 2 н ( − 1 ) ф ( х ) + а ⋅ х , {\displaystyle {\hat {f}}(a)=\sum _{\scriptstyle {x\in \mathbb {Z} _{2}^{n}}}(-1)^{f(x)+a\cdot x},}

где a · x = a 1 x 1 + a 2 x 2 + … + a n x n (mod 2) — скалярное произведение в Zн
2[4] В качестве альтернативы, пусть S 0 ( a ) = { x ∈ Zн
2 : f ( x ) = a · x } и S 1 ( a ) = { x ∈ Zн
2 : f ( x ) ≠ a · x } . Тогда | S 0 ( a ) | + | S 1 ( a ) | = 2 n и, следовательно,

ф ^ ( а ) = | С 0 ( а ) | − | С 1 ( а ) | = 2 | С 0 ( а ) | − 2 н . {\displaystyle {\hat {f}}(a)=\left|S_{0}(a)\right|-\left|S_{1}(a)\right|=2\left|S_{0}(a)\right|-2^{n}.}

Для любой булевой функции f и a ∈ Zн
2, преобразование лежит в диапазоне

− 2 н ≤ ф ^ ( а ) ≤ 2 н . {\displaystyle -2^{n}\leq {\hat {f}}(a)\leq 2^{n}.}

Более того, линейная функция f 0 ( x ) = a · x и аффинная функция f 1 ( x ) = a · x + 1 соответствуют двум крайним случаям, поскольку

ф ^ 0 ( а ) = 2 н ,   ф ^ 1 ( а ) = − 2 н . {\displaystyle {\hat {f}}_{0}(a)=2^{n},~{\hat {f}}_{1}(a)=-2^{n}.}

Таким образом, для каждого a ∈ Zн
2Значение характеризует, где функция f ( x ) лежит в диапазоне от f 0 ( x ) до f 1 ( x ). ф ^ ( а ) {\displaystyle {\hat {f}}(a)}

Определение и свойства

Ротхаус определил бент-функцию как булеву функцию, преобразование Уолша которой имеет постоянное абсолютное значение . Бент-функции в некотором смысле равноудалены от всех аффинных функций, поэтому их одинаково трудно аппроксимировать любой аффинной функцией. ф : З 2 н → З 2 {\displaystyle f:\mathbb {Z} _{2}^{n}\to \mathbb {Z} _{2}}

Простейшими примерами бент-функций, записанных в алгебраической нормальной форме , являются F ( x 1 , x 2 ) = x 1 x 2 и G ( x 1 , x 2 , x 3 , x 4 ) = x 1 x 2 ⊕ x 3 x 4 . Эта закономерность продолжается: x 1 x 2 ⊕ x 3 x 4 ⊕ … ⊕ x n −1 x n является бент-функцией для каждого четного n , но существует большое разнообразие других бент-функций по мере увеличения n . [5] Последовательность значений (−1) f ( x ) , где x ∈ Z З 2 н → З 2 {\displaystyle \mathbb {Z} _{2}^{n}\to \mathbb {Z} _{2}} н
2взятая в лексикографическом порядке , называется изогнутой последовательностью ; изогнутые функции и изогнутые последовательности имеют эквивалентные свойства. В этой ±1 форме преобразование Уолша легко вычисляется как

ф ^ ( а ) = Вт ( 2 н ) ( − 1 ) ф ( а ) , {\displaystyle {\hat {f}}(a)=W\left(2^{n}\right)(-1)^{f(a)},}

где W (2 n ) — естественно упорядоченная матрица Уолша , а последовательность рассматривается как вектор-столбец . [6]

Ротхаус доказал, что бент-функции существуют только для четных n , и что для бент-функции f для всех a ∈ Z | ф ^ ( а ) | = 2 н / 2 {\displaystyle \left|{\hat {f}}(a)\right|=2^{n/2}} н
2. [4] Фактически, , где g также изогнута. В этом случае , поэтому f и g считаются дуальными функциями. [6] ф ^ ( а ) = 2 н / 2 ( − 1 ) г ( а ) {\displaystyle {\hat {f}}(a)=2^{n/2}(-1)^{g(a)}} г ^ ( а ) = 2 н / 2 ( − 1 ) ф ( а ) {\displaystyle {\hat {g}}(a)=2^{n/2}(-1)^{f(a)}}

Каждая бент-функция имеет вес Хэмминга (число раз , когда она принимает значение 1) 2 n −1 ± 2 n /2−1 , и фактически согласуется с любой аффинной функцией в одном из этих двух количеств точек. Таким образом, нелинейность f ( минимальное число раз, когда она равна любой аффинной функции) равна 2 n −1 − 2 n /2−1 , максимально возможному. И наоборот, любая булева функция с нелинейностью 2 n −1 − 2 n /2−1 является бент- функцией . [4] Степень f в алгебраической нормальной форме (называемая нелинейным порядком f ) не превышает ⁠н/2⁠ (для n > 2 ). [5]

Хотя бент-функции исчезающе редки среди булевых функций многих переменных, они бывают разных видов. Были проведены подробные исследования специальных классов бент-функций, таких как однородные [7] или те , которые возникают из монома над конечным полем , [8], но до сих пор бент-функции не поддаются всем попыткам полного перечисления или классификации.

Конструкции

Существует несколько типов конструкций для изогнутых функций. [2]

  • Комбинаторные конструкции: итеративные конструкции, конструкция Майораны–Макфарланда, частичные спреды, бент-функции Диллона и Доббертина, бент-функции Минтерма, бент-итеративные функции
  • Алгебраические конструкции: мономиальные бент-функции с показателями Голда, Диллона, Касами, Канто–Леандера и Канто–Шарпена–Кюрегяна; бент-функции Нихо и т. д.

Приложения

Еще в 1982 году было обнаружено, что последовательности максимальной длины, основанные на изогнутых функциях, обладают свойствами взаимной корреляции и автокорреляции, конкурирующими со свойствами кодов Голда и кодов Касами , используемых в CDMA . [9] Эти последовательности имеют несколько применений в методах расширенного спектра .

Свойства изогнутых функций, естественно, представляют интерес для современной цифровой криптографии , которая стремится скрыть связи между входом и выходом. К 1988 году Форре понял, что преобразование Уолша функции может быть использовано для того, чтобы показать, что она удовлетворяет строгому критерию лавины (SAC) и обобщениям более высокого порядка, и рекомендовал этот инструмент для выбора кандидатов на хорошие S-блоки, достигающие почти идеальной диффузии . [10] Действительно, функции, удовлетворяющие SAC до максимально возможного порядка, всегда изогнуты. [11] Более того, изогнутые функции максимально далеки от того, что называется линейными структурами , ненулевыми векторами a такими, что f ( x + a ) + f ( x ) является константой. На языке дифференциального криптоанализа (введенного после открытия этого свойства) производная бент-функции f в каждой ненулевой точке a (то есть f a ( x ) = f ( x + a ) + f ( x )) является сбалансированной булевой функцией, принимающей каждое значение ровно половину времени. Это свойство называется идеальной нелинейностью . [5]

Учитывая такие хорошие свойства диффузии, очевидно, идеальную устойчивость к дифференциальному криптоанализу и устойчивость по определению к линейному криптоанализу , бент-функции могут на первый взгляд показаться идеальным выбором для защищенных криптографических функций, таких как S-boxes. Их фатальным недостатком является то, что они не сбалансированы. В частности, обратимый S-box не может быть построен непосредственно из бент-функций, а потоковый шифр, использующий функцию объединения бент-функций, уязвим для корреляционной атаки . Вместо этого можно начать с бент-функции и случайным образом дополнять соответствующие значения до тех пор, пока результат не будет сбалансирован. Модифицированная функция по-прежнему имеет высокую нелинейность, и поскольку такие функции встречаются очень редко, процесс должен быть намного быстрее, чем поиск методом грубой силы. [5] Но функции, полученные таким образом, могут потерять другие желаемые свойства, даже не удовлетворяя SAC, поэтому необходимо тщательное тестирование. [11] Ряд криптографов работали над методами генерации сбалансированных функций, которые сохраняют как можно больше хороших криптографических качеств бент-функций. [12] [13] [14]

Некоторые из этих теоретических исследований были включены в реальные криптографические алгоритмы. Процедура проектирования CAST , использованная Карлайлом Адамсом и Стаффордом Таваресом для построения S-boxes для блочных шифров CAST-128 и CAST-256 , использует бент-функции. [14] Криптографическая хэш-функция HAVAL использует булевы функции, построенные из представителей всех четырех классов эквивалентности бент-функций на шести переменных. [15] Потоковый шифр Grain использует NLFSR , нелинейный полином обратной связи которого по своей конструкции является суммой бент-функции и линейной функции. [16]

Обобщения

В монографии Токаревой 2015 года описано более 25 различных обобщений бент-функций. [2] Существуют алгебраические обобщения ( q -значные бент-функции, p -арные бент-функции, бент-функции над конечным полем, обобщенные булевы бент-функции Шмидта, бент-функции из конечной абелевой группы в множество комплексных чисел на единичной окружности, бент-функции из конечной абелевой группы в конечную абелеву группу, неабелевы бент-функции, векторные G-бент-функции, многомерные бент-функции на конечной абелевой группе), комбинаторные обобщения (симметричные бент-функции, однородные бент-функции, вращательно-симметричные бент-функции, нормальные бент-функции, самодуальные и антисамодуальные бент-функции, частично определенные бент-функции, платообразные функции, Z-бент-функции и квантовые бент-функции) и криптографические обобщения (полубент-функции, сбалансированные бент-функции, частично бент-функции, гипербент-функции, бент-функции высшего порядка, k -бент-функции).

Наиболее распространенным классом обобщенных бент-функций является тип mod m , такой что ф : З м н → З м {\displaystyle f:\mathbb {Z} _{m}^{n}\to \mathbb {Z} _{m}}

ф ^ ( а ) = ∑ х ∈ З м н е 2 π я м ( ф ( х ) − а ⋅ х ) {\displaystyle {\hat {f}}(a)=\sum _{x\in \mathbb {Z} _{m}^{n}}e^{{\frac {2\pi i}{m}}(f(x)-a\cdot x)}}

имеет постоянное абсолютное значение m n /2 . Совершенные нелинейные функции , такие, что для всех ненулевых a , f ( x + a ) − f ( a ) принимает каждое значение m n −1 раз, являются обобщенными бент-функциями. Если m является простым числом , то обратное верно. В большинстве случаев рассматриваются только простые m . Для нечетных простых m существуют обобщенные бент-функции для каждого положительного n , четного и нечетного. Они обладают многими из тех же хороших криптографических свойств, что и бинарные бент-функции. [17] [18] ф : З м н → З м {\displaystyle f:\mathbb {Z} _{m}^{n}\to \mathbb {Z} _{m}}

Полу-бент-функции являются нечетным аналогом бент-функций. Полу-бент-функция имеет нечетное n , то есть принимает только значения 0 и m ( n +1)/2 . Они также имеют хорошие криптографические характеристики, и некоторые из них сбалансированы, принимая все возможные значения одинаково часто. [19] ф : З м н → З м {\displaystyle f:\mathbb {Z} _{m}^{n}\to \mathbb {Z} _{m}} | ф ^ | {\displaystyle \left|{\hat {f}}\right|}

Частично изогнутые функции образуют большой класс, определяемый условием на преобразование Уолша и автокорреляционные функции. Все аффинные и изогнутые функции являются частично изогнутыми. Это, в свою очередь, является собственным подклассом платообразных функций . [20]

Идея гипер-бент-функций заключается в максимизации минимального расстояния до всех булевых функций, получаемых из биективных мономов на конечном поле GF(2 n ), а не только до аффинных функций. Для этих функций это расстояние постоянно, что может сделать их устойчивыми к интерполяционной атаке .

Другие связанные названия были даны криптографически важным классам функций , таким как почти изогнутые функции и кривые функции . Хотя они сами по себе не являются изогнутыми функциями (они даже не являются булевыми функциями), они тесно связаны с изогнутыми функциями и обладают хорошими свойствами нелинейности. ф : З 2 н → З 2 н {\displaystyle f:\mathbb {Z} _{2}^{n}\to \mathbb {Z} _{2}^{n}}

Смотрите также

Ссылки

  1. ^ OS Rothaus (май 1976). «О «изогнутых» функциях». Журнал комбинаторной теории, серия A. 20 ( 3): 300–305. doi : 10.1016/0097-3165(76)90024-8 . ISSN  0097-3165.
  2. ^ abc Н. Токарева (2015). Изогнутые функции: результаты и приложения к криптографии . Academic Press. ISBN 9780128023181.
  3. ^ Блондо; Нюберг (2015-03-01). «Совершенные нелинейные функции и криптография». Конечные поля и их приложения . 32 : 120–147. doi : 10.1016/j.ffa.2014.10.007 . ISSN  1071-5797.
  4. ^ abc C. Qu; J. Seberry ; T. Xia (29 декабря 2001 г.). "Булевы функции в криптографии" . Получено 14 сентября 2009 г.
  5. ^ abcd W. Meier; O. Staffelbach (апрель 1989). Критерии нелинейности криптографических функций . Eurocrypt '89. С. 549–562.
  6. ^ ab C. Carlet; LE Danielsen; MG Parker; P. Solé (19 мая 2008 г.). Self Dual Bent Functions (PDF) . Четвертый международный семинар по булевым функциям: криптография и приложения (BFCA '08) . Получено 21 сентября 2009 г. .
  7. ^ T. Xia; J. Seberry; J. Pieprzyk ; C. Charnes (июнь 2004 г.). «Однородные бент-функции степени n от 2n переменных не существуют для n > 3». Discrete Applied Mathematics . 142 (1–3): 127–132. doi : 10.1016/j.dam.2004.02.006 . ISSN  0166-218X . Получено 21 сентября 2009 г. .
  8. ^ A. Canteaut ; P. Charpin; G. Kyureghyan (январь 2008). "A new class of monomial bent functions" (PDF) . Finite Fields and Their Applications . 14 (1): 221–241. doi :10.1016/j.ffa.2007.02.004. ISSN  1071-5797. Архивировано из оригинала (PDF) 21 июля 2011 г. . Получено 21 сентября 2009 г. .
  9. ^ J. Olsen; R. Scholtz; L. Welch (ноябрь 1982 г.). "Bent-Function Sequences". IEEE Transactions on Information Theory . IT-28 (6): 858–864. doi :10.1109/tit.1982.1056589. ISSN  0018-9448. Архивировано из оригинала 22 июля 2011 г. Получено 24 сентября 2009 г.
  10. ^ Р. Форре (август 1988 г.). Строгий лавинный критерий: спектральные свойства булевых функций и расширенное определение . CRYPTO '88. стр. 450–468.
  11. ^ ab C. Adams ; S. Tavares (январь 1990). Использование изогнутых последовательностей для достижения строгого критерия лавины высшего порядка в S-box Design . Технический отчет TR 90-013. Университет Квинс . CiteSeerX 10.1.1.41.8374 . 
  12. ^ К. Нюберг (апрель 1991 г.). Совершенные нелинейные S-блоки . Eurocrypt '91. С. 378–386.
  13. ^ J. Seberry; X. Zhang (декабрь 1992 г.). Высоконелинейные сбалансированные булевы функции 0–1, удовлетворяющие строгому лавинному критерию . AUSCRYPT '92. стр. 143–155. CiteSeerX 10.1.1.57.4992 . 
  14. ^ ab C. Adams (ноябрь 1997 г.). «Построение симметричных шифров с использованием процедуры проектирования CAST». Designs, Codes and Cryptography . 12 (3): 283–316. doi :10.1023/A:1008229029587. ISSN  0925-1022. S2CID  14365543. Архивировано из оригинала 26 октября 2008 г. Получено 20 сентября 2009 г.
  15. ^ Y. Zheng ; J. Pieprzyk ; J. Seberry (декабрь 1992 г.). HAVAL – односторонний алгоритм хеширования с переменной длиной выходных данных. AUSCRYPT '92. стр. 83–104 . Получено 20 июня 2015 г. .
  16. ^ Хелл, Мартин; Йоханссон, Томас; Максимов, Александр; Мейер, Вилли (2006). "Предложение о потоковом шифре: Grain-128" (PDF) . Труды Международного симпозиума IEEE 2006 года по теории информации, ISIT 2006, The Westin Seattle, Сиэтл, Вашингтон, США, 9–14 июля 2006 года . IEEE. стр. 1614–1618. doi :10.1109/ISIT.2006.261549.
  17. ^ К. Нюберг (май 1990 г.). Конструкции бент-функций и разностных множеств . Eurocrypt '90. С. 151–160.
  18. ^ Шаши Кант Пандей; БК Дасс (сентябрь 2017 г.). «О спектре Уолша криптографической булевой функции». Defence Science Journal . 67 (5): 536–541. doi :10.14429/dsj.67.10638. ISSN  0011-748X.
  19. ^ K. Khoo; G. Gong; D. Stinson (февраль 2006 г.). "Новая характеристика полуизогнутых и изогнутых функций на конечных полях" ( PostScript ) . Designs, Codes and Cryptography . 38 (2): 279–295. CiteSeerX 10.1.1.10.6303 . doi :10.1007/s10623-005-6345-x. ISSN  0925-1022. S2CID  10572850. Получено 24 сентября 2009 г. 
  20. ^ Y. Zheng; X. Zhang (ноябрь 1999). Plateaued Functions. Вторая международная конференция по безопасности информации и связи (ICICS '99). стр. 284–300 . Получено 24 сентября 2009 г.

Дальнейшее чтение

  • C. Carlet (май 1993 г.). Два новых класса изогнутых функций . Eurocrypt '93. С. 77–101.
  • J. Seberry; X. Zhang (март 1994). «Построение изогнутых функций из двух известных изогнутых функций». Australasian Journal of Combinatorics . 9 : 21–35. CiteSeerX  10.1.1.55.531 . ISSN  1034-4942.
  • Колборн, Чарльз Дж .; Диниц, Джеффри Х. (2006). Справочник комбинаторных конструкций (2-е изд.). CRC Press . стр. 337–339. ISBN 978-1-58488-506-1.
  • Cusick, TW; Stanica, P. (2009). Криптографические булевы функции и приложения . Academic Press. ISBN 9780123748904.
Взято с "https://en.wikipedia.org/w/index.php?title=Bent_function&oldid=1214725026"