Криптаналитическая обратимость с конечной задержкой конечных автоматов | Прикладная дискретная математика. 2019. № 46. DOI: 10.17223/20710410/46/3

В работе продолжаются исследования концепции криптаналитической обратимости с конечной задержкой, введенной автором для конечных автоматов. Приводится алгоритмический тест для автомата A, который может быть криптаналитически обратимым с конечной задержкой, то есть иметь функцию восстановления f, которая позволяет вычислить префикс длины m во входной последовательности автомата A с использованием его выходной последовательности длины m + τ и некоторой дополнительной информации об A, определяющей тип его обратимости и известной криптаналитикам. Тест выясняет, имеет ли автомат А функцию восстановления f или нет, и если имеет, находит некоторые или, может быть, все такие функции. Алгоритм выполняет поиск с возвратом для преобразования бинарного отношения к функции путём сокращения области её определения до множества, соответствующего рассматриваемому типу обратимости.