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

Полный текст

Введение Клеточные автоматы (КлА) как вычислительные структуры известны уже более 70 лет [1]. Теория КлА является установившейся научной дисциплиной с многочисленными приложениями в очень многих областях науки. КлА играют важную роль в качестве моделей пространственно-распределенных динамических систем, поскольку изначально обладают рядом фундаментальных свойств, присущих физическому миру: параллелизмом, однородностью, локальностью взаимодействия. Другие свойства, такие как обратимость и законы сохранения, могут быть обеспечены надлежащим выбором локальных функций связи. КлА успешно применяются при моделировании физических и химических процессов, сложных систем в биохимии и генетике, в компьютерных технологиях и информатике, экономике и социологии. Применяются они и в криптографии. Так, в последнее время клеточные автоматы (в особенности обратимые) активно применяются в качестве криптографических примитивов для построения высокопроизводительных криптографических алгоритмов [2]. Вообще вопросы обратимости КлА исследованы достаточно подробно, но, как это ни парадоксально, исследования в основном касались КлА на бесконечных решетках. В криптографии же, как и в большинстве приложений, используются КлА на решетках конечного размера. Вопросы обратимости для таких КлА в принципе всегда разрешимы, и основная задача состоит в нахождении приемлемых критериев для проверки обратимости, построении алгоритмов для реализации обратного преобразования и оценки сложности этих алгоритмов. И здесь результатов существенно меньше. В настоящей работе устанавливается связь обратимости однородных одномерных бинарных клеточных автоматов с автоматами без потери информации и запретами для конечных автоматов. Эта связь позволяет решать вопрос обратимости КлА с бóльшей эффективностью. Полученные результаты легко переносятся на КлА с небинарным множеством состояний ячеек памяти, а также на КлА с решеткой размерности больше 1. 1. Конкретный тип автоматов, рассматриваемых в данной работе Объектом изучения в настоящей работе является однородный одномерный бинарный клеточный автомат. Однородный одномерный (1D) бинарный клеточный автомат (КлА) длины L с локальной функцией связи ƒ определяется следующим образом. Пусть имеется линейно упорядоченный (1D) массив из L двоичных ячеек памяти (клеток). Время для клеточного автомата изменяется дискретными шагами (тактами). Пусть - булева величина, являющаяся заполнением i-й ячейки памяти в момент времени t. Внутренним состоянием (или конфигурацией) КлА в момент времени t называется заполнение всего массива ячеек: (). Число различных конфигураций 1D бинарного КлА длины L равно 2L. Изменение заполнений ячеек происходит синхронно и одновременно при увеличении номера такта в соответствии с правилами перехода, определяющими новое заполнение каждой ячейки памяти как функцию от текущих заполнений соседних ячеек, т. е. ячеек, входящих в ее окрестность. В рассматриваемом ниже примере окрестностью i-й ячейки будем называть ячейки с номерами . Тогда заполнение i-й ячейки в момент времени t определяется формулой . 2. Задача нахождения прообраза заданной конфигурации одномерного клеточного автомата Пусть - конфигурация 1D КлА в момент времени t, а - конфигурация КлА в следующий момент времени (рис. 1). y1 y2 y3 … yL-1 yL Рис. 1. Две последовательные конфигурации КлА Figure 1. Two sequential CA configurations Поскольку решетка нашего клеточного автомата имеет конечные размеры, возникает так называемая «проблема краевых клеток» - как задавать значения аргументов локальной функции связи для ячеек, у которых отсутствует часть соседей. Для этого вводятся граничные условия: • Чаще всего в соответствии со свойством однородности для разрешения проблемы краевых клеток противоположные края решетки клеточного автомата отождествляются - это так называемая периодическая граница (PB - periodic boundary). • Другой тип граничных условий - нулевая граница (NB - null boundary): значения для отсутствующих соседей полагаются равными нулю. • Еще один тип граничных условий - отражающая граница (RB - reflective boundary). Таким образом, для вычисления следующей конфигурации КлА помимо текущего заполнения L ячеек требуется знать значения в виртуальных ячейках (в нашем случае это и - см. рис. 2). x0 x1 x2 x3 … xL-1 xL xL+1 y1 y2 y3 … yL-1 yL Рис. 2. Виртуальные ячейки, используемые для вычисления следующей конфигурации Figure 2. Virtual cells used to compute next configuration Набор назовем виртуальным прообразом конфигурации . На рис. 3 приведена схема вычисления следующей конфигурации 1D КлА: Рис. 3. Схема вычисления следующей конфигурации Figure 3. Calculation of next configuration Следующую конфигурацию для данного КлА можно вычислить с помощью конструкции (рис. 4), называемой нелинейным фильтром с входной памятью (НФВП) [3] или кодирующим устройством с конечной памятью и без обратной связи [4; 5]. Рис. 4. Нелинейный фильтр с входной памятью, реализующий вычисления, приведенные на рис. 3 Figure 4. Binary filter with input memory that implements the calculations shown in Fig. 3 Задавая в качестве начального состояния (начального заполнения регистра) и подавая на вход последовательность , на выходе мы получим последовательность , т. е. конфигурацию нашего КлА в следующий момент времени. Тогда нахождение прообраза для конфигурации КлА эквивалентно нахождению прообраза для выходной последовательности НФВП , т. е. нахождению такого начального состояния и входной последовательности , чтобы на выходе НФВП мы получили последовательность . Последовательность , образованную начальным заполнением регистра НФВП и входной последовательностью, назовем виртуальным прообразом последовательности . При этом наличие граничных условий налагает ограничения на значения и (значения в виртуальных ячейках). В случае нулевой границы (NB) это . Задачи нахождения прообраза выходной последовательности конечного автомата достаточно хорошо изучены в таких разделах теории конечных автоматов, как «Конечные автоматы без потери информации (БПИ)» и «Запреты конечных автоматов». 3. Автоматы без запретов и автоматы без потери информации Для дальнейшего изложения нам понадобятся понятия автомата с запретами, автомата без запретов, автомата с потерей информации и автомата без потери информации. Приведем основные определения и результаты, связанные с этими понятиями. Читатель, для которого эти понятия известны, может пропустить настоящий раздел. Рассмотрим конечный автомат , где X и Y - входной и, соответственно, выходной алфавиты, Q - множество внутренних состояний автомата, f и g - функции выхода и, соответственно, перехода в следующее состояние. Автомат A называется автоматом без запретов (БЗ), если для любой последовательности , найдутся такое внутр еннее состояние и последовательность , что автомат А, находясь в начальном состоянии и получив на вход последовательность , даст на выходе последовательность . Если же для некоторой последовательности такие и не существуют, то автомат А называется автоматом с запретами, соответствующая последовательность называется запретом автомата А, а Т - длиной этого запрета. Незаменимым инструментом для исследований запретов является так называемый граф запретов. Формального описания графа запретов в опубликованной литературе, насколько это известно автору, не существует, в то же время эта конструкция (возможно под другими названиями) на протяжении нескольких последних десятилетий использовалась для анализа свойств конечных автоматов. В этой связи приведем в достаточной для понимания подробности эту конструкцию, которая, по сути, является «графом преемников по выходу» (схожая, но в некотором смысле «избыточная» конструкция приведена в [6]). Граф запретов G автомата A определяется следующим образом. Вершинами графа являются - подмножества множества внутренних состояний автомата, включая, возможно, вершину . Построение графа начинается с вершины - начальной вершины графа запретов. Ее образует множество возможных начальных состояний автомата. При отсутствии каких-либо ограничений совпадает с множеством Q всех внутренних состояний автомата. Далее алгоритм построения графа запретов таков. Выбирается необработанная вершина . Выбирается символ выходного алфавита: . Для каждого состояния определяются его преемники по выходу y (y-преемники) - это состояния, в которые можно за один такт перейти из состояния q с выходом y. Объединение преемников по выходу y для всех состояний образует подмножество . Заметим, что может совпадать с или быть пустым множеством: . Если вершина, соответствующая подмножеству , была получена ранее, то в графе добавляется дуга, помеченная символом y, которая ведет из в . Если вершины, соответствующей подмножеству , в графе нет, то такая вершина добавляется в граф вместе с дугой, помеченной символом y, которая ведет из в . После этого процедура повторяется для следующего символа выходного алфавита. Для вершины все дуги с пометками ведут в нее же, т. е. являются петлями. После обработки всех вершин (а эта процедура конечна, поскольку число вершин не превосходит числа всех подмножеств конечного множества Q) получаем связный ориентированный граф G с одной выделенной вершиной, называемой начальной. Вершинами графа являются подмножества (как правило - не все) множества внутренних состояний автомата. Из каждой вершины выходит дуг, помеченных символами . Дуга, помеченная символом , соединяет вершину с вершиной, образованной y-преемниками всех состояний, входящих в . По построению любая вершина построенного графа достижима из начальной вершины . Тогда, если из начальной вершины в вершину ведет путь длины T, пометки которого образуют последовательность то - это множество возможных состояний, в которые может перейти наш автомат, начавший работу в одном из состояний из множества и выработавший при этом выходную последовательность . Если конечная вершина, соответствующая пути , является пустой ( ), это означает, что выходная последовательность не может быть выработана нашим автоматом с множеством начальных состояний из . Если при этом , то последовательность является запретом нашего автомата. Таким образом, запретами (или запретными комбинациями) автомата A являются все последовательности знаков выходного алфавита, соответствующие путям в графе G, ведущим из начальной вершины в вершину . В свою очередь, если для любого , любой последовательности , в графе запретов G существует путь длины T, помеченный знаками последовательности , начинающийся в и заканчивающийся в вершине , автомат A является автоматом без запретов. Иными словами, отсутствие запретов у автомата A означает, что граф запретов G не содержит вершину . Сложность построения графа запретов можно оценить как , Q - множество внутренних состояний автомата A. В статье [5] вводится понятие запрета булевой функции: если НФВП с функцией выхода f является автоматом без запретов, то функция f называется функцией без запретов, в противном случае f называется функцией с запретами, а последовательность, являющаяся запретной для НФВП, называется запретом функции f. В работах [5; 7] была показано, что для НФВП, рассматриваемого как конечный автомат, отсутствие запретов эквивалентно свойству отсутствия потери информации. Конечный автомат A называется автоматом без потери информации - БПИ (information lossless), если знание начального состояния, выходной последовательности и конечного состояния достаточно для однозначного определения входной последовательности [8]. Конечный автомат, который не является автоматом без потери информации, называется автоматом с потерей информации - ПИ (lossy). Для проверки, является ли данный автомат автоматом без потери информации, имеется эффективный алгоритм, сложность которого оценивается как [9]. 4. Обратимость одномерных клеточных автоматов конечного размера Возвращаясь к одномерным клеточным автоматам, рассмотрим 1D КлА длины L с произвольной окрестностью. В общем случае окрестностью i-й ячейки 1D КлА будем называть ячейки с номерами i+j, где . Назовем размером окрестности вели- . Тогда заполнение i-й ячейки в момент времени t определяется формулой и всех t. Клеточный автомат называется обратимым, если для каждой конфигурации КлА существует только одна предшествующая конфигурация. В силу конечности числа конфигураций у рассматриваемых КлА для доказательства обратимости достаточно показать, что для каждой конфигурации существует хотя бы одна предшествующая конфигурация. Обратимость 1D КлА длины L с локальной функцией связи f может быть проверена непосредственным вычислением конфигурации, в которую переходит автомат, находящийся в конфигурации . Проделав эти вычисления для всех 2 L конфигураций КлА, мы можем легко определить обратимость КлА, проверив, что в списке конфигураций, полученных в результате таких вычислений, нет совпадающих конфигураций. Сложность такого алгоритма оценивается как , требуемая память - как . В то же время, если использовать подход, описанный в начале данной работы, нахождение прообраза для состояния КлА эквивалентно нахождению прообраза выходной последовательности для НФВП, приведенного на рис. 5, т. е. нахождению такого начального состояния и входной последовательности , чтобы на выходе НФВП получилась последовательность . При этом нулевая граница (NB) накладывает дополнительные условия: . Рис. 5. Нелинейный фильтр с входной памятью для 1D КлА с окрестностью общего вида Figure 5. Binary filter with input memory for 1D CA with an arbitrary type of neighborhood Таким образом, обратимость 1D КлА длины L с локальной функцией f связи эквивалентна тому, что НФВП с регистром длины R (R - размер окрестности КлА) и функцией выхода f порождает все возможные выходные последовательности длины L. Для проверки этого свойства построим ограниченный граф запретов . Строится он по тем же правилам, что и обычный граф запретов G, но в качестве - начальной вершины графа запретов - берется множество состояний НФВП, удовлетворяющих граничным условиям . Обратимость 1D КлА длины L эквивалентна тому, что в ограниченном графе запретов любой путь длины L, начинающийся в вершине , должен заканчиваться в вершине, содержащей хотя бы одно состояние НФВП, удовлетворяющее граничным условиям . Заметим, что граф , как и граф G, зависит только от f - локальной функции связи; сложность его построения зависит от числа внутренних состояний НФВП, равного 2R, где R - размер окрестности 1D КлА, и не зависит от L - длины 1D КлА. Таким образом, исследование 1D КлА с локальной функцией связи f можно проводить независимо от размера КлА. Для этого исследуется ограниченный граф запретов . • Если каждая вершина, принадлежащая графу , содержит хотя бы одно состояние НФВП, удовлетворяющее граничным условиям , то все 1D КлА с локальной функцией связи f являются обратимыми, независимо от длины КлА. • Если граф содержит вершину V, не содержащую ни одного состояния НФВП, удовлетворяющего граничным условиям , и имеется путь длины L из в V, то 1D КлА длины L с локальной функцией связи f необратим. Заметим, что если ограниченный граф запретов содержит вершину - длина кратчайшего пути из в , то все 1D КлА длины с локальной функцией связи f не являются обратимыми. Для потребуется провести исследование, аналогичное описанному выше. Заметим также, что если НФВП с функцией выхода f является автоматом с запретом G, его граф запретов содержит вершину . Из построения ограниченного графа запретов следует, что граф также содержит вершину , причем длина кратчайшего пути из в в графе не превосходит длину кратчайшего пути из в в графе . Однако в силу того, что для НФВП, рассматриваемого как конечный автомат, наличие запретов эквивалентно наличию потери информации, проверить факт наличия запрета легче с помощью эффективного алгоритма проверки автомата на наличие потери информации. Сложность этой проверки можно оценить как . В заключение следует отметить, что все приведенные выше рассуждения можно перенести на 1D КлА с небинарным заполнением клеток. 5. Применение к двумерным клеточным автоматам Рассмотренный выше подход можно применить для исследования двумерных клеточных автоматов (2D КлА), если свести их к одномерным. Рассмотрим 2D КлА размера , заполнение каждой ячейки которого является булевой величиной (бинарный 2D КлА) - рис. 6. Рис. 6. Двумерный клеточный автомат (2D КлА) Figure 6. Two-dimensional cellular automaton (2D CA) Клетки, лежащие в одном столбце, можно считать одной ячейкой, содержимое которой принимает 2k значений и является элементом или (рис. 7). Теперь бинарный 2D КлА размера можно рассматривать как 1D КлА размера L над алфавитом мощности 2k (рис. 8). Рис. 7. Клеточный автомат с объединенными ячейками памяти Figure 7. Cellular automaton with combined memory cells L Рис. 8. 1D КлА, соответствующий исходному 2D КлА Figure 8. 1D CA corresponding to the original 2D CA Заметим, что в двумерном случае окрестность ячейки можно выбирать различным образом. На рис. 9 приведены наиболее часто используемые двумерные окрестности радиуса r = 1. а б в г Рис. 9. Некоторые типы окрестности радиуса r = 1 для ячейки двумерного КлА: a - полная окрестность (окрестность Мура); б - квазиполная окрестность Мура; в - окрестность фон Неймана; г - неполная окрестность фон Неймана Figure 9. Some types of radius r = 1 neighborhood for cell of 2D CA: a - complete neighborhood (Moore neighborhood); б - quasi-complete Moore neighborhood; в - von Neumann neighborhood; г - incomplete von Neumann neighborhood Тогда для применения описанного выше подхода надо предварительно решить следующую задачу: по окрестности и локальной функцией связи f для 2D КлА построить окрестность и локальную функцию связи f1 для соответствующего 1D КлА. Выводы В работе показано, что 1D КлА с локальной функцией связи f можно сопоставить НФВП с регистром длины R (где R - размер окрестности КлА) и функцией выхода, совпадающей с локальной функцией связи 1D КлА. Определение обратимости 1D КлА связано с нахождением прообраза (а по сути с обратимостью) НФВП. При этом от L (размера 1D КлА) НФВП не зависит. Полученные результаты позволяют снизить сложность решения массовых задач переборного типа, связанных с вопросами обратимости КлА. Все полученные результаты можно перенести на КлА с небинарным заполнением ячеек и на КлА размерности, большей 1.

Об авторах

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

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

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

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

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

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