Булевы функции в криптографии
Зарегистрируйся в два клика и получи неограниченный доступ к материалам,а также
промокод
на новый заказ в Автор24. Это бесплатно.
Введение
Булевы функции нашли широкое применение в криптографии, в частности, в симметричной криптографии. Например, булевы функции используются в потоковых шифрах в качестве нелинейных фильтров. Также они применяются в блочных шифрах в S-боксах. Требование устойчивости схем шифрования к существующим атакам накладывает на различные элементы этих схем определенные условия, которым они должны удовлетворять. В случае с потоковыми шифрами речь обычно идет о том, чтобы булевы функции, используемые в качестве нелинейных фильтров, обладали целым набором криптографических свойств. Среди этих свойств наряду с другими можно выделить алгебраическую иммунность и нелинейность высоких порядков. В последнее время появился ряд работ [1, 2, 4, 6, 8], в которых затрагиваются вопросы взаимосвязи этих двух свойств. Одной из самых интересных является проблема получения нижних оценок нелинейности различных порядков функции через значение ее алгебраической иммунности. Это тем более важно, так как для нахождения значения алгебраической иммунности функции в последнее время предложено несколько алгоритмов, а для подсчета нелинейности высоких порядков эффективных алгоритмов не существует. В данной работе предложен новый подход к получению для булевой функции как можно более сильных нижних оценок ее нелинейности высоких порядков через значение алгебраической иммунности. По сути, проблема сведена к оценке размерности определенных линейных подпространств в пространстве всех булевых функций фиксированного числа переменных. Исследование свойств булевых полиномов является классической задачей дискретной математики и комбинаторного анализа. Булевы полиномы широко применяются, в частности, в криптографии и криптологии. В ряде популярных криптосистем с открытым ключом используются коды Рида-Маллера, а их представление, алгоритмы кодирования и декодирования базируются на булевых полиномах, спектральные свойства определяются количеством нулей полиномов и исследуются с помощью леммы о рандомизации. Полином 𝑔(𝑥)∈𝑃2𝑛[𝑥] называется аннигилятором для 𝑓(𝑥)∈𝑃2𝑛[𝑥], если выполняется условие: 𝑓(𝑥)𝑔(𝑥)≡0 или 𝑔(𝑥)[𝑓(𝑥)+1]≡0.
Анализ научной работы Леонтьева В.К. и Гордеева Э.Н. Об аннигиляторах булевых полиномов
Целью данной работ является поиск минимальной степени аннигилятора для заданного булева полинома от n переменных. В своей работе ученые приводят ряд определений, таких как: определение аннигилятора: Полином gx∈P2nx называется аннигилятором для fx∈P2n...
Открыть главуАнализ работы Баева В.В. о некоторых алгоритмах построения аннигиляторов низкой степени для булевых функций
Важность данной научной работы обусловлена широким применением алгебраического метода при анализе фильтрующих генераторов псевдослучайных последовательностей, который основывается на получении булевых уравнений низкой степени относительно битов начал...
Открыть главуАнализ работы Гордеева Э.Н., Леонтьева В.К., Медведева Н.В. О свойствах булевых полиномов, актуальных для криптосистем
В работе предложен алгоритм, основанный на свойствах матрицы мономов. Так же представлена формула для нахождения числа нулей полинома, приведены формулы для математического ожидания числа нулей для нескольких классов булевых полиномов, позволяющие пу...
Открыть главуАнализ работы Сизоненко А.Б. о параллельной реализации криптографических блоков подстановок и перестановок арифметическими полиномами
Криптографические блоки подстановок и перестановок представлены в виде систем логических функций. Построены арифметико-логические модели блоков подстановок и перестановок. Рассмотрена возможность распараллеливания процесса вычисления функций криптогр...
Анализ работы Аркелова Г.Г. прикладная гомоморфная криптография: примеры
Одна из наиболее интересных и важных задач, стоящих перед современной криптографией, — это проведение вычислений над зашифрованными данными без их предварительной расшифровки. Вопрос о принципиальной возможности таких вычислений долгое время оставалс...
Открыть главуСписок литературы
1. Лобанов М. С. Точное соотношение между нелинейностью и алгебраической иммунностью // Дискрет. математика. — 2006. — Т. 18, вып. 3. — С. 152–159. 2. Лобанов М. С. Оценка нелинейности высоких порядков булевой функции через значение ее алгебраической иммунности // Материалы VI молодежной научной школы по дискретной математике и ее приложениям (Москва, апрель 2007). Часть 2. — М.: Ин-т прикладной математики РАН, 2007. — С. 11–16. 3. Canteaut A. Open problems related to algebraic attacks on stream ciphers // International workshop on coding and cryptography (WCC 2005) (Bergen, March 2005). — Berlin: Springer, 2006. — P. 1–11. (Lect. Notes in Comp. Sci.; Vol. 3969). 4. Carlet C. On the higher order nonlinearities of algebraic immune functions // CRYPTO 2006. — Berlin, Heidelberg: Springer, 2006. — P. 584–601. (Lect. Notes in Comp. Sci.; Vol. 4117). 5. Courtois N., MeierW. Algebraic attacks on stream ciphers with linear feedback // Advances in cryptology, EUROCRYPT 2003. — Berlin, Heidelberg: Springer Verl., 2003. — P. 345–359. — (Lect. Notes in Comp. Sci.; Vol. 2656). 6. Dalai D. K., Gupta K. C., Maitra S. Results on algebraic immunity for cryptographically significant boolean functions // Indocrypt 2004 (Chennai, India, December 20–22, 2004). — Berlin, Heidelberg: Springer Verl., 2004. — P. 92–106. (Lect. Notes in Comp. Sci.; Vol. 3348). 7. MeierW., Pasalic E., Carlet C. Algebraic attacks and decomposition of Boolean functions // In Advances in Cryptology, EUROCRYPT 2004. — Berlin, Heidelberg: Springer Verl., 2004. — P. 474–491. (Lect. Notes in Comp. Sci.; Vol. 3027). 8. Mesnager S. Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity // Cryptology ePrint archive(http://eprint.iacr.org/), Report 2007/117. 9. McWilliams F. J., Sloane N. J. A. The theory of error correcring codes. — New York: North-Holland, 1977. — 760 p. х. 10. Агибалов Г. П. Избранные теоремы начального курса крипто- графии. Томск: Изд-во НТЛ, 2005. 11. Бабаш А. В., Шанкин Г. П. Криптография. М.: СОЛОН-Р, 2002. 12. Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2004. 13. Сачков В. Н. Введение в комбинаторные методы дискретной математики. М: МНЦМО, 2004. 14. Токарева Н. Н. Нелинейные булевы функции: бент-функции и их обобщения. Saarbr¨ucken: LAP LAMBERT Academic Publishing, 2011. 15. Токарева Н. Н. Симметричная криптография. Краткий курс. Новосибирск: Изд-во НГУ, 2012.
