如何線上性密碼分析中找到最優路徑

我正在閱讀和實施本教程，作者非常清楚地解釋了所有內容，我唯一缺少的是他如何決定使用哪條路徑（第 12 頁）。我知道人們應該更喜歡活動 S-Box 數量最少的路徑並最大化路徑的偏差（事實上，在嘗試將線性密碼分析應用於對稱加密算法時，找到最佳路徑似乎是最重要的一步） .

在我看來，這像是某種動態規劃問題，但我想知道是否有通用算法來解決尋找最佳路徑（或至少是一系列候選路徑）的問題。

人們使用松井的“最佳路徑搜尋算法”，這確實是一種動態規劃方法。資源成本難以預測，因此在實踐中採用了分支定界變化。

可以在Matsui 在 Asicrypt 2018 上關於線性密碼分析的回顧性演講的幻燈片 14-17 中找到骨架輪廓。

更正式的描述和一些變體可以在 Ji、Zhang 和 Ding 的 2019 年論文“改進 Matsui 的最佳差分/線性軌蹟的搜尋算法及其在 DES、DESL 和 GIFT 中的應用”中找到

引用自：https://crypto.stackexchange.com/questions/98816