Прикладная теория кодирования и автоматов

О невозможности «компактного» задания хеш-функций автоматами

К. Д. Царегородцев


Аннотация: В 2024 г. на олимпиаде NSUCRYPTO была предложена задача представления постквантового алгоритма подписи с помощью «компактного» автомата Мили. Большинство постквантовых схем подписи хешируют сообщение перед его непосредственной подписью (парадигма Hash-and-Sign). В работе показано, что любая хеш-функция, удовлетворяющая разумным требованиям к её безопасности, не может быть представлена автоматом Мили, если к нему дополнительно предъявляются требования «компактности» представления. Таким образом, схемы, основанные на парадигме Hash-and-Sign, скорее всего, не могут быть реализованы с помощью относительно простых и «компактных» моделей вычислений.

Ключевые слова: хеш-функция, автомат Мили, ДКА.

УДК: 519.7

DOI: 10.17223/2226308X/18/50