一種改進的刻畫S 盒的球方法*

王永興，馮秀濤，徐圣源

1.中國科學院 數學機械化重點實驗室，北京100190

2.中國科學院大學，北京100049

1 引言

混合整數線性規劃(mixed integer linear programming，MILP) 是一種尋找某個線性目標函數最大值或最小值的基礎方法，其中，目標函數的變量受到一些線性約束(即這些變量滿足某個不等式組).MILP 被廣泛應用于運籌學、圖論和計算幾何等領域[1].一個MILP 問題可以有如下描述: 給定一個矩陣Rm×n，一個向量Rm以及n個實數c1，c2，···，cn，尋找一個滿足Ax ≤b的Zn，使得目標函數達到最大或最小，這里m和n是兩個正整數，R 和Z 分別是實數集和整數集，Rm×n、Rm和Zn分別代表R 上m×n階矩陣集合、R 上m維向量空間以及Z 上n維向量空間.

在密碼學領域，MILP 被成功應用到密碼分析中.在2009 年，Borghoff首次將二元域上求解稀疏二次方程組的問題轉化為一個組合優化問題，并且提出了對一些Trivium 簡化版本的數值攻擊[2].在2011年，Albrecht 和Cid 通過冷啟動攻擊得到了帶噪聲的非線性代數方程組，提出了一種整數規劃方法求解該方程組[3].在2012 年，Walter 等人展示了如何使用MILP 優化對分組密碼EPCBC 進行代數密碼分析的猜測策略[4].最近又出現了一種基于MILP 求解推理系統最小化問題的新方法，該方法可用于搜索猜測確定分析的最優路徑[5].

對于分組密碼的差分密碼分析[6]和線性密碼分析[7]，構造MILP 模型是一種搜索高概率差分跡和線性跡的有效方法.Mouha 等人提出了一種基于MILP 的方法來搜索最小活躍S 盒個數，可以用來證明分組密碼抵抗差分分析和線性分析的安全界[8].文獻[9] 給出了基于整數規劃的一般算法……