基於MILP自動化搜索技術

陽光密碼小鎮

也許，花落是為了下一季的花開

MILP問題是運籌學中的一類組合優化問題，旨在線性約束條件下求解目標函數的最值，例如0-1背包問題、集合覆蓋問題和旅行商問題。MILP問題在工業和學術界上取得了極大的關注和研究成果，主要應用在物流、航班調度、網路規劃、晶元設計認證等。下面舉一個小實例：

最近幾年，為了獲取分組密碼中活躍S盒數量的下界，進而評估分組密碼抵抗差分和線性攻擊的能力，很多密碼學者將該問題轉換為MILP問題，取得了非常好的結果。基於MILP自動化搜索技術發展越來越成熟，並顯示出強大的密碼分析能力。基於MILP的搜索技術已經發展成為評估分組密碼抵抗差分和線性攻擊的通用工具。今天我們來看一下如何利用MILP問題來刻畫異或操作。

實際使用的MILP自動化搜索技術比這要複雜的多，要解決S盒如何轉化成MILP問題，比特線性置換、線性層如何轉化等等一系列複雜的問題。這些問題部分已經有較好的回答。比如為了解決MILP搜索技術不可以應用到ARX演算法的問題，付凱等人在FSE2016上，基於MILP搜索技術，提出了針對ARX演算法的差分和線性特徵搜索技術。同時，在2017年歐密會上，日本學者Sasaki等人擴展差分MILP搜索技術，提出了新的自動化搜索不可能差分的工具。可以看出基於MILP自動化搜索技術每天都有新的想法和思路產生。

目前對MILP搜索技術雖然存在大量的研究成果，輕量級分組密碼安全性分析的通用工具，但仍然有許多問題有待進一步研，期待你的加入。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！