Обратимость одномерных клеточных автоматов

Обложка

Цитировать

Полный текст

Аннотация

В последнее время обратимые клеточные автоматы все чаще применяются для построения высокопроизводительных криптографических алгоритмов. Устанавливается связь обратимости однородных одномерных бинарных клеточных автоматов конечного размера со свойствами конструкции, называемой нелинейный фильтр с входной памятью и такими свойствами конечных автоматов, как наличие запретов и потеря информации. В работе показано, что нахождение прообраза для произвольной конфигурации одномерного клеточного автомата длины L с локальной функцией связи f связано с нахождением прообраза (а по сути с обратимостью) нелинейного фильтра с входной памятью с регистром длины R (где R - размер окрестности соответствующего одномерного клеточного автомата) и функцией выхода, совпадающей с локальной функцией связи клеточного автомата. При этом нелинейный фильтр с входной памятью, соответствующий клеточному автомату, не зависит от числа ячеек памяти клеточного автомата. Полученные результаты позволяют снизить сложность решения массовых задач переборного типа, связанных с вопросами обратимости клеточных автоматов. Все полученные результаты можно перенести на клеточные автоматы с небинарным заполнением ячеек и на клеточные автоматы размерности большей 1.

Об авторах

Алексей Евгеньевич Жуков

Московский государственный технический университет имени Н.Э. Баумана (национальный исследовательский университет); Ассоциация «РусКрипто»

Автор, ответственный за переписку.
Email: aez_iu8@rambler.ru
ORCID iD: 0000-0002-1663-7773

доцент кафедры информационной безопасности МГТУ им. Н.Э. Баумана, директор ассоциации «РусКрипто», кандидат физико-математических наук

Российская Федерация, 105005, Москва, 2-я Бауманская ул., д. 5, стр. 1; Российская Федерация, 111123, Москва, ул. Плеханова, д. 4А

Список литературы

  1. Zhukov A. Cellular automata in cryptography. Part 1. Voprosy kiberbezopasnosti [Cybersecurity issues]. 2017;3(21):70—76. (In Russ.) https://doi.org/10.21581/2311-3456-2017-3-70-76
  2. Zhukov A. Cellular automata in cryptography. Part 2. Voprosy kiberbezopasnosti [Cybersecurity issues]. 2017;4(22):47—66. (In Russ.) https://doi.org/10.21681/2311-3456-2017-4-47-66
  3. Lai X, Massey JL. Some connections between scramblers and invertible automata. In: Proc. 1988 Beijing Int. Workshop on Info. Theory, Beijing. China, July 4-7;1988:DI-5.1 — DI-5.5.
  4. Preparata FP. Convolutional transformations of binary sequences: Boolean functions and their resynchronizing properties. IEEE Trans. Electron. Comput. 1966;15(6):898—909.
  5. Sumarokov SN. Zaprety dvoichnyh funkcij i obratimost’ dlya odnogo klassa kodiruyushchih ustrojstv [Prohibitions of binary functions and reversibility for one class of coding devices]. Obozrenie prikladnoj i promyshlennoj matematiki, ser. diskretn. matem. [Obozrenie prikladnoy i promyshlennoy matematiki]. 1994;1(1):33—55.
  6. Babash AV. Zaprety avtomatov i dvoichnyh funkcij [Prohibitions of automata and binary functions]. Trudy po diskretnoj matematike [Proceedings of Discrete] Mathematics. 2006;9:7—20. (In Russ.)
  7. Olson RR. On the invertibility of finite state machines. Ph.D. diss. Notre Dame, Indiana, USA: Department of Electrical Engineering, University of Notre Dame; 1970.
  8. Huffman DA. Canonical forms for information loss less finite state logical machines. IRE Trans. Circuit Theory. 1959;6(spec. suppl.):41—59.
  9. Kohavi Z, Niraj K. Jha. Switching and Finite Automata Theory. Cambridge, UK: Cambridge University Press; 2009. https://doi.org/10.1017/CBO9780511816239

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».