有限域同构问题与子集和问题的新攻击及优化策略

### 有限域同构问题与子集和问题的新攻击及优化策略 #### 1. 有限域同构问题的攻击 在有限域同构（FFI）问题的研究中，我们可以通过一些方法对其进行攻击。首先，在Fq的表示中，有|Tr(C∗p−1)| = (q − t)/p。根据相关等式和引理，攻击者A可以按照以下规则破解加密C的语义游戏： - 若|Tr(CC∗p−1)| ≤ 0.11 sβ2n5，则返回C是0的加密； - 否则，返回C是1的加密。 定理中对q的条件保证了攻击者A能以优势δ = 1返回m′ ∈ {0, 1}，且攻击者A能在多项式时间内运行。 对于推荐参数的攻击效果，不同级别的（某种程度上）全同态加密方案的推荐参数，除了第一级（q较小且容忍的噪声非常小）之外，都在我们语义攻击的范围内。 #### 2. 计算性FFI问题的攻击 我们将计算性FFI问题转化为格问题。与之前的攻击相比，此方法避免了额外的组合步骤。具体步骤如下： - **定义q - 元格**：给定FFI样本A1(y), A2(y), ..., Ak(y)（k > n），定义一个k × n阶的生成矩阵T，其ij - 元素由Tr(Ai(y)yj−1)定义。q - 元迹格定义为LT,q = {α ∈ Zk : T C = α mod q 对于某些C ∈ Zn}。 - **迹格的性质**： 1. 维度为k。 2. 体积为qk−n。 3. 包含n个线性无关的向量αi，使得∥αi∥ ≤ β（1 ≤ i ≤ n）。 由于β比(q - 1)/2小很多，这n个向量αi很可能是迹格LT,q中的最短向量。通过重新计算对偶基的对偶，我们可以得到x - 基的y - 基表示，从而恢复隐藏的同构φ。 在实际应用中，找到格中的n个最短向量成本太高。因此，我们采用一种概率方法，从Ci - 基的子集中恢复φ。根据引理，在从所有对偶x - 基集合中均匀随机采样的m > 1个元素的集合中，至少有一对对偶x - 基元素(Ci, Cj)的商能给出φ的概率为Ω(m2/n)。 #### 3. 迹格的格约简实验 我们考虑与(n, q) = (256, 32771)接近的参数进行实验，样本大小k（即格的维度）是影响格约简运行时间的主要参数。我们选择k = 2n。 - 对于较小的n，使用小块大小的BKZ算法方便恢复最短向量。但随着n的增加，大块大小的BKZ算法攻击效果不佳。因此，我们采用预处理格约简步骤，使用较小的块大小来降低格的维度。 - 实验中选择的参数(n, q)能在预处理步骤中找到“有点”短的向量。这些短向量对应的有限域基Ci - 基可作为Fqn中的伪对偶x - 基，即|Tr(Cixj)| ⪅ β。对于任何FFI样本Aj，有|Tr(CiAj)| ⪅ nβ2。 - 为了利用Ci - 基中关于x的额外信息，我们生成一个新的整数迹格LT ⊂ Zk，其维度为n。通过观察上述不等式，这个低维格中的基向量异常小，使得我们可以有效地使用更强的格约简算法来恢复最短向量。 实验结果如下表所示： | n | q | 预处理 | Ci - 基 | 最终状态 | |----|----|----|----|----| | 200