Бент-функция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где a · x = a ₁ x ₁ + a ₂ x ₂ + … + a _n x _n (mod 2) — скалярное произведение в Z ^н
₂ . Альтернативно, пусть S ₀ ( a ) = { x ∈ Z ^н
₂ : ж ( Икс ) знак равно а · Икс } и S ₁ ( а ) знак равно { Икс ∈ Z ^н
₂ : ж ( Икс ) ≠ а · Икс } . Тогда | S ₀ ( а ) | + | S ₁ ( а ) | = 2 ^н и поэтому

${\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^{n}\leq {\hat {f}}(a)\leq 2^{n}.$

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

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

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

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

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

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

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

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

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

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

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

Конструкции

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

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

Приложения

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

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

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

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

Обобщения

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

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

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

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

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

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

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

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

См. также

• Корреляционный иммунитет

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

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