Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Четыре 2-арные булевы функции с весом Хэмминга 1 изогнуты; т.е. их нелинейность равна 1 (что и показывает эта диаграмма) .
Следующая формула показывает, что двумерная функция искривляется, когда ее нелинейность равна 1:
Логическая функция изогнута; т.е. его нелинейность равна 6 (что и показывает эта диаграмма) .
Следующая формула показывает, что 4-мерная функция искривляется, когда ее нелинейность равна 6:

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

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

Преобразование Уолша [ править ]

Бент-функции определяются в терминах преобразования Уолша . Преобразование Уолша булевой функции - это функция, заданная формулой

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

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

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

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

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

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

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

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

Ротхаус доказал, что бент-функции существуют только для четных n , а для бент-функции f - для всех a ∈ Zп
2. [3] Фактически , где g также изогнута. В этом случае, поэтому f и g считаются двойственными функциями. [5]

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

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

Конструкции [ править ]

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

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

Приложения [ править ]

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

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

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

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

Обобщения [ править ]

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

Наиболее распространенным классом обобщенных бент-функций является тип mod m , такой что

имеет постоянное абсолютное значение m n / 2 . Совершенные нелинейные функции , такие, что для всех ненулевых a , f ( x + a ) - f ( a ) принимает каждое значение m n - 1 раз, обобщенно изогнуты. Если т является простой , верно и обратное. В большинстве случаев рассматриваются только простые числа m . Для нечетного простого числа m существуют обобщенные бент-функции для любого положительного n , четного и нечетного. Они обладают многими из тех же хороших криптографических свойств, что и двоичные бент-функции.[16] [17]

Полубент-функции - это нечетный аналог бент-функций. Полу-согнуты функция с п нечетно, таким образом, что принимает только значения 0 и т ( п + 1) / 2 . Также они обладают хорошими криптографическими характеристиками, причем некоторые из них сбалансированы, одинаково часто принимая все возможные значения. [18]

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

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

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

Ссылки [ править ]

  1. ^ OS Rothaus (май 1976). «О« гнутых »функциях». Журнал комбинаторной теории, Серия А . 20 (3): 300–305. DOI : 10.1016 / 0097-3165 (76) 90024-8 . ISSN  0097-3165 .
  2. ^ a b c Н. Токарева (2015). Бент-функции: результаты и приложения к криптографии . Академическая пресса. ISBN 9780128023181.
  3. ^ a b c C. Qu; Дж. Себери ; Т. Ся (29 декабря 2001 г.). «Булевы функции в криптографии» . Проверено 14 сентября 2009 года . Cite journal requires |journal= (help)
  4. ^ а б в г В. Мейер; О. Стаффельбах (апрель 1989 г.). Критерии нелинейности криптографических функций . Еврокрипт '89. С. 549–562.
  5. ^ а б К. Карлет; LE Danielsen; MG Parker; П. Соле (19 мая 2008 г.). Самодвойственные бент-функции (PDF) . Четвертый международный семинар по булевым функциям: криптография и приложения (BFCA '08) . Проверено 21 сентября 2009 года .
  6. ^ Т. Ся; Дж. Себери; Я. Пиепшик ; К. Чарнз (июнь 2004 г.). «Однородные бент-функции степени n от 2n переменных не существуют при n> 3» . Дискретная прикладная математика . 142 (1–3): 127–132. DOI : 10.1016 / j.dam.2004.02.006 . ISSN 0166-218X . Проверено 21 сентября 2009 года . 
  7. ^ А. Канто ; П. Шарпен; Г. Кюрегян (январь 2008 г.). «Новый класс мономиальных бент-функций» (PDF) . Конечные поля и их приложения . 14 (1): 221–241. DOI : 10.1016 / j.ffa.2007.02.004 . ISSN 1071-5797 . Архивировано из оригинального (PDF) 21 июля 2011 года . Проверено 21 сентября 2009 года .  
  8. ^ Дж. Олсен; Р. Шольц; Л. Велч (ноябрь 1982 г.). «Последовательности бент-функций» . IEEE Transactions по теории информации . ИТ-28 (6): 858–864. DOI : 10,1109 / tit.1982.1056589 . ISSN 0018-9448 . Архивировано из оригинального 22 июля 2011 года . Проверено 24 сентября 2009 года . 
  9. ^ R. Forré (август 1988). Строгий лавинный критерий: спектральные свойства булевых функций и расширенное определение . CRYPTO '88. С. 450–468.
  10. ^ а б К. Адамс ; С. Таварес (январь 1990 г.). «Использование изогнутых последовательностей для достижения строгого лавинного критерия более высокого порядка в дизайне S-box». Технический отчет TR 90-013. Королевский университет . CiteSeerX 10.1.1.41.8374 .  Cite journal requires |journal= (help)
  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. DOI : 10,1023 / A: 1008229029587 . ISSN 0925-1022 . Архивировано из оригинального 26 октября 2008 года . Проверено 20 сентября 2009 года . 
  14. ^ Y. Zheng ; Я. Пиепшик; Дж. Себери (декабрь 1992 г.). HAVAL - односторонний алгоритм хеширования с переменной длиной вывода . AUSCRYPT '92. С. 83–104 . Проверено 20 июня 2015 года .
  15. ^ М. Ад; Т. Йоханссон; А. Максимов; В. Мейер. «Предложение поточного шифра: Grain-128» (PDF) . Проверено 24 сентября 2009 года . Cite journal requires |journal= (help)
  16. ↑ К. Ниберг (май 1990 г.). Построения бент-функций и разностных множеств . Eurocrypt '90. С. 151–160.
  17. ↑ Шаши Кант Панди; Б.К. Дасс (сентябрь 2017 г.). «О спектре Уолша криптографической булевой функции». Оборонный научный журнал . 67 (5): 536–541. DOI : 10,14429 / dsj.67.10638 . ISSN 0011-748X . 
  18. ^ К. Кху; Г. Гонг; Д. Стинсон (февраль 2006 г.). «Новая характеризация полубентых и бент-функций на конечных полях» ( PostScript ) . Конструкции, коды и криптография . 38 (2): 279–295. CiteSeerX 10.1.1.10.6303 . DOI : 10.1007 / s10623-005-6345-х . ISSN 0925-1022 . Проверено 24 сентября 2009 года .   
  19. ^ Y. Zheng; 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 . Cite journal requires |journal= (help)
  • Колборн, Чарльз Дж .; Диниц, Джеффри Х. (2006). Справочник комбинаторных конструкций (2-е изд.). CRC Press . С.  337–339 . ISBN 978-1-58488-506-1.
  • Cusick, TW; Станица, П. (2009). Криптографические логические функции и приложения . Академическая пресса. ISBN 9780123748904.