Как найти оптимальный след в линейном криптоанализе

Я читаю и реализую это руководство, автор объясняет все довольно ясно, единственное, чего мне не хватает, так это того, как он решает, какую тропу использовать (стр. 12). Я понимаю, что следует отдавать предпочтение трейлам с наименьшим количеством активных S-блоков и максимизировать смещение трейла (на самом деле поиск оптимального трейла кажется самым важным шагом при попытке применить линейный криптоанализ к алгоритму симметричного шифрования) .

Мне кажется, что это какая-то проблема динамического программирования, но мне интересно, существует ли общий алгоритм для решения проблемы поиска оптимального следа (или, по крайней мере, ряда возможных следов).

Метод Мацуи является классическим, но в настоящее время наблюдается тенденция к поиску на основе MILP/SAT/SMT. Корректность следа и его связи с вероятностью перехода кодируется в систему, а затем оптимизируется для минимизации общей вероятности (для SAT/SMT можно использовать бинарный поиск, для MILP оптимизация нативная).

Некоторые примеры (большая часть исследований посвящена дифференциальным атакам, но обычно они переводятся в линейные атаки):

• Ускорение поиска дифференциальных и линейных характеристик методом SAT
• Основанные на MILP алгоритмы автоматического поиска дифференциальных и линейных следов для спека
• Улучшение основанного на MILP алгоритма оценки безопасности против дифференциального/линейного криптоанализа с использованием подхода «разделяй и властвуй»
• Пересмотр дифференциальных атак с использованием связанных ключей AES с программированием ограничений