一种布尔多项式的高效计算机表示

作者：李昕; 林东岱; 徐琳

来源：Z201212010, 2012, (12): 2568-2574.

• 代数攻击
• 布尔多项式代表
• 布尔方程组求解
• Grnber基
• 空间需求 algebraic attack
• Boolean polynomial representation
• Boolean equations solving
• Grnbner bases
• space requirement

布尔方程组求解技术对于密码分析具有重要的现实意义.然而,在众多求解算法的实际计算过程中,难以抑制的空间需求增长与计算机系统有限的存储能力之间的矛盾,正是当前制约布尔方程组求解技术取得更大成果的最主要瓶颈.针对基于消项的求解算法,分析了该矛盾的产生根源,提出了解决途径,进而设计了一种全新的布尔多项式计算机表示,称之为BanYan.BanYan适用于基于首项约化的求解算法,如F4,F5,XL等算法.通过记录中间结果的生成信息而非其本身,避免算法实现陷入项数规模高速膨胀带来的巨大存储负担.与BDD和系数矩阵等基于项的传统布尔多项式表示相比,平均情况以及最坏情况下,使用BanYan表示法所需要的空间约...

• 单位
  中国矿业大学; 中国矿业大学（北京）; 中国科学院大学; 信息安全国家重点实验室; 中国科学院软件研究所