Бент функция - Bent function - Wikipedia

Четыре 2-арные булевы функции с Вес Хэмминга 1 гнутся; т.е. их нелинейность равна 1 (что показано на этой диаграмме).

Следующая формула показывает, что двумерная функция искривляется, когда ее нелинейность равна 1:

${\displaystyle 2^{2-1}-2^{{\frac {2}{2}}-1}=2-1=1}$

Булева функция ${\displaystyle x_{1}x_{2}\oplus x_{3}x_{4}}$ согнут; т.е. его нелинейность равна 6 (что показано на этой диаграмме).

Следующая формула показывает, что 4-арная функция искривляется, когда ее нелинейность равна 6:

${\displaystyle 2^{4-1}-2^{{\frac {4}{2}}-1}=8-2=6}$

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

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

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

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

${\displaystyle {\hat {f}}(a)=\sum _{\scriptstyle {x\in \mathbb {Z} _{2}^{n}}}(-1)^{f(x)+a\cdot x}}$

куда а · Икс = а₁Икс₁ + а₂Икс₂ + … + а_пИкс_п (мод 2) это скалярное произведение в Z^п
₂.^[3] В качестве альтернативы пусть S₀(а) = { Икс ∈ Z^п
₂ : ж(Икс) = а · Икс } и S₁(а) = { Икс ∈ Z^п
₂ : ж(Икс) ≠ а · Икс }. потом |S₀(а)| + |S₁(а)| = 2^п и поэтому

${\displaystyle {\hat {f}}(a)=\left|S_{0}(a)\right|-\left|S_{1}(a)\right|=2\left|S_{0}(a)\right|-2^{n}.}$

Для любой логической функции ж и а ∈ Z^п
₂ преобразование лежит в диапазоне

${\displaystyle -2^{n}\leq {\hat {f}}(a)\leq 2^{n}.}$

Кроме того, линейная функция ж₀(Икс) = а · Икс и аффинная функция ж₁(Икс) = а · Икс + 1 соответствуют двум крайним случаям, поскольку

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

Таким образом, для каждого а ∈ Z^п
₂ значение ${\displaystyle {\hat {f}}(a)}$ характеризует, где функция ж(Икс) лежит в диапазоне от ж₀(Икс) к ж₁(Икс).

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

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

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

${\displaystyle {\hat {f}}(a)=W\left(2^{n}\right)(-1)^{f(a)},}$

куда W(2^п) является естественно-упорядоченным Матрица Уолша и последовательность рассматривается как вектор столбца.^[5]

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

Каждая бент-функция имеет Вес Хэмминга (сколько раз он принимает значение 1) 2^п−1 ± 2^{​п⁄₂−1}, и фактически согласуется с любой аффинной функцией в одном из этих двух чисел точек. Итак нелинейность из ж (минимальное количество раз, когда она равна любой аффинной функции) 2^п−1 − 2^{​п⁄₂−1}, максимально возможное. И наоборот, любая булева функция с нелинейностью 2^п−1 − 2^{​п⁄₂−1} согнут.^[3] В степень из ж в алгебраической нормальной форме (называемой нелинейный порядок из ж) не более^п⁄₂ (за п > 2).^[4]

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

Конструкции

Существует несколько типов конструкций для бент-функций.^[2]

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

Приложения

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

Свойства бент-функций естественно вызывают интерес в современных цифровых технологиях. криптография, который пытается скрыть отношения между вводом и выводом. К 1988 году Форре понял, что преобразование Уолша функции можно использовать, чтобы показать, что она удовлетворяет строгий лавинный критерий (SAC) и обобщения более высокого порядка и рекомендовал этот инструмент для отбора кандидатов на S-боксы достижение почти идеального распространение.^[9] В самом деле, функции, удовлетворяющие САК в максимально возможном порядке, всегда изогнуты.^[10] Кроме того, изогнутые функции максимально далеки от того, что называется линейные конструкции, ненулевые векторы a такие, что ж(Икс + а) + ж(Икс) является константой. На языке дифференциальный криптоанализ (введено после того, как это свойство было обнаружено) производная изогнутой функции ж в каждой ненулевой точке а (то есть, ж_а(Икс) = ж(Икс + а) + ж(Икс)) это сбалансированный Логическая функция, принимающая каждое значение ровно в половине случаев. Это свойство называется совершенная нелинейность.^[4]

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

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

Обобщения

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

Самый распространенный класс обобщенные бент-функции это мод м тип, ${\displaystyle f:\mathbb {Z} _{m}^{n}\to \mathbb {Z} _{m}}$ такой, что

${\displaystyle {\hat {f}}(a)=\sum _{x\in \mathbb {Z} _{m}^{n}}e^{{\frac {2\pi i}{m}}(f(x)-a\cdot x)}}$

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

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

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

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

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

Рекомендации

1. О. С. Ротхаус (май 1976 г.). «О« гнутых »функциях». Журнал комбинаторной теории, серия А. 20 (3): 300–305. Дои:10.1016/0097-3165(76)90024-8. ISSN  0097-3165.
2. Н. Токарева (2015). Бент-функции: результаты и приложения к криптографии. Академическая пресса. ISBN  9780128023181.
3. C. Qu; Дж. Себери; Т. Ся (29 декабря 2001 г.). «Логические функции в криптографии». Получено 14 сентября 2009.
4. В. Мейер; О. Стаффельбах (апрель 1989 г.). Критерии нелинейности криптографических функций. Еврокрипт '89. С. 549–562.
5. К. Карлет; L.E. Даниэльсен; М.Г. Паркер; П. Соле (19 мая 2008 г.). Самостоятельные двойные изогнутые функции (PDF). Четвертый международный семинар по булевым функциям: криптография и приложения (BFCA '08). Получено 21 сентября 2009.
6. Т. Ся; Дж. Себери; Я. Пиепшик; К. Чарнз (июнь 2004 г.). «Однородные бент-функции степени n от 2n переменных не существуют при n> 3». Дискретная прикладная математика. 142 (1–3): 127–132. Дои:10.1016 / j.dam.2004.02.006. ISSN  0166-218X. Получено 21 сентября 2009.
7. А. Канто; П. Шарпен; Г. Кюрегян (январь 2008 г.). «Новый класс мономиальных бент-функций» (PDF). Конечные поля и их приложения. 14 (1): 221–241. Дои:10.1016 / j.ffa.2007.02.004. ISSN  1071-5797. Архивировано из оригинал (PDF) 21 июля 2011 г.. Получено 21 сентября 2009.
8. Дж. Олсен; Р. Шольц; Л. Велч (ноябрь 1982 г.). «Последовательности бент-функций». IEEE Transactions по теории информации. ИТ-28 (6): 858–864. Дои:10.1109 / tit.1982.1056589. ISSN  0018-9448. Архивировано из оригинал 22 июля 2011 г.. Получено 24 сентября 2009.
9. Р. Форре (август 1988 г.). Строгий лавинный критерий: спектральные свойства булевых функций и расширенное определение. КРИПТО '88. С. 450–468.
10. К. Адамс; С. Таварес (Январь 1990 г.). «Использование изогнутых последовательностей для достижения строгого лавинного критерия высшего порядка в дизайне S-box». Технический отчет TR 90-013. Королевский университет. CiteSeerX  10.1.1.41.8374.
11. К. Нюберг (Апрель 1991 г.). Совершенные нелинейные S-блоки. Еврокрипт '91. С. 378–386.
12. Дж. Себери; X. Чжан (декабрь 1992 г.). Сильно нелинейные сбалансированные булевы функции 0–1, удовлетворяющие строгому критерию лавинности. AUSCRYPT 92 год. С. 143–155. CiteSeerX  10.1.1.57.4992.
13. К. Адамс (ноябрь 1997 г.). «Построение симметричных шифров с использованием процедуры проектирования CAST». Конструкции, коды и криптография. 12 (3): 283–316. Дои:10.1023 / А: 1008229029587. ISSN  0925-1022. Архивировано из оригинал 26 октября 2008 г.. Получено 20 сентября 2009.
14. Ю. Чжэн; Я. Пиепшик; Дж. Себери (декабрь 1992 г.). HAVAL - односторонний алгоритм хеширования с переменной длиной вывода. AUSCRYPT '92. стр. 83–104. Получено 20 июн 2015.
15. М. Ад; Т. Йоханссон; А. Максимов; В. Мейер. "Предложение поточного шифра: Grain-128" (PDF). Получено 24 сентября 2009.
16. К. Ниберг (май 1990 г.). Построения бент-функций и разностных множеств. Eurocrypt '90. С. 151–160.
17. Шаши Кант Пандей; Б.К. Дасс (сентябрь 2017 г.). «О спектре Уолша криптографической булевой функции». Оборонный научный журнал. 67 (5): 536–541. Дои:10.14429 / dsj.67.10638. ISSN  0011-748X.
18. К. Ху; Г. Гонг; Д. Стинсон (Февраль 2006 г.). «Новая характеризация полубент-функций и бент-функций на конечных полях» (PostScript ). Конструкции, коды и криптография. 38 (2): 279–295. CiteSeerX  10.1.1.10.6303. Дои:10.1007 / s10623-005-6345-х. ISSN  0925-1022. Получено 24 сентября 2009.
19. Ю. Чжэн; X. Чжан (ноябрь 1999 г.). Плато функции. Вторая международная конференция по информационной и коммуникационной безопасности (ICICS '99). стр. 284–300. Получено 24 сентября 2009.

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

• К. Карлет (май 1993 г.). Два новых класса бент-функций. Еврокрипт '93. С. 77–101.
• Дж. Себери; X. Чжан (март 1994). «Построения бент-функций по двум известным бент-функциям». Австралазийский журнал комбинаторики. 9: 21–35. CiteSeerX  10.1.1.55.531. ISSN  1034-4942.
• Т. Нейман (май 2006 г.). «Бент-функции». CiteSeerX  10.1.1.85.8731.
• Колборн, Чарльз Дж.; Диниц, Джеффри Х. (2006). Справочник по комбинаторным схемам (2-е изд.). CRC Press. стр.337–339. ISBN  978-1-58488-506-1.
• Cusick, T.W .; Станица, П. (2009). Криптографические логические функции и приложения. Академическая пресса. ISBN  9780123748904.