Boneh_Durfee Attack

Boneh_Durfee Attack

在这里我们仅关注一般情况，即 ，可以证明的是，在 时，我们可以在多项式时间内分解 ；下面首先给出一个算法满足 ​

这里我们有 令 ，那么 即 为方程 的一组解

最终我们将原问题转化为求解如下问题

HG98

设 为一个最多含 项单项的多项式， 对于一些正整数 有 ；若 ，那么

证明

一般地我们记多项式

根据 Cauchy不等式 我们有 同时 即 又因为 所以

引理1

设 为格的 LLL 规约基，那么

格的构造

我们取

为什么用 的 和 来构造格 ，而使用 形式的混合位移

原因是 中使用的单项式上的所有 的混合位移都已经包含在格中了。也就是说，任何多项式 都可以是表示为 和 的整数线性组合。为了理解这一点，观察对于任意 ，我们有

给定 ，，对于每个 我们使用

边界推导

根据 引理1，HG98，我们只需要满足 忽略小项有 这里

对于行列式的计算我们分别计算两种唯一多项式的贡献 同理

代入得到 故只需满足 这里整理为以 为主元的多项式（其为一个二次多项式），有 这里取 为其对称轴(，这样可以使左侧尽可能小)，得到 即 因此实际情况中，对于足够大的 (可以保证 足够小)，可以取 ，并不断尝试 检验 即可；

这样我们就得到了一个二元多项式 ；

在构造的格中，前一小部分的向量任然是相对短的，故很大概率上有 ；我们只需要找到其中的两个线性无关的多项式 ，通过结式将其化为 ，从而进一步解出

代码见 boneh_durfee.py

另外值得一提的是，如果我们只选取 ，得到结果如下 此时我们得到了 wiener 方法的界限