Average- and worst-case complexity
Average Case Hardness（平均困难度）
平均情况下的困难度：随机选择参数，解决该问题的困难度。
密码学中要求的困难：随机选择一个key，没有敌手能在多项式时间内以不可忽略的概率破解该问题，即平均困难度
例如：
- 大整数分解问题，我们要求的并非是最难分解的N难以分解，而是按照我们的方式选择出来的N大部分都难以分解；
- 对于Ajtai的OWF问题，如果我们随机的抽取 \(\mathbf{A}\) 矩阵, 并且给予它来构造OWF。只要保证大部分时候 \(\Lambda(\mathbf{A})\)中的SVP是困难的, 那么我们得到的 \(f_{\mathrm{A}}\) 就是单向 (OWF) 并且collision resistant的。
对于大整数分解问题，如果我们随机挑选N，我们知道 \[ \operatorname{Pr}\left[\mathbf{N}=2 \cdot \frac{\mathbf{N}}{2}\right]=\frac{1}{2} \] 对于这个问题，我们挑选 \(\mathbf{N}=p \cdot q\), 并且选取 \(p, q\) 为随机的质数, 那么在这个新的 \(\mathbf{N}\) 的分布下, 我们相信factoring是困难的。
对于Ajtai的OWF问题，只要 \(\Lambda^{\perp}(\mathbf{A})\) 的SVP问题困难, 我们的SIS构造的OWF就是安全的。那么如果我们均匀的随机生成矩阵 \(\mathbf{A}\), 这个矩阵构成的格 \(\Lambda, \Lambda^{\perp}\) 中的SVP问题到底难不难呢? 这个问题很难回答
我们可以尝试看能否把平均困难度归约成最坏情况困难度
Worst Case Hardness（最坏情况困难度）
首先, 我们先随机的生成一个 \(\Lambda\) 中的格点 \(\mathbf{v}_i\) 。然后我们从随机噪音分布中生成一个噪音向量 \(\mathbf{r}_i\), 并且根据我们模糊化的结果, \(\|\mathbf{r}\| \leq \sqrt{n} \cdot \lambda_n\) 。 \[ \mathbf{a}_i=\mathbf{v}_i+\mathbf{r}_i \] 此时的\(\mathbf{a}_i\)可以看作是平均分布的。 \[ \mathbf{A}=\left[\mathbf{a}_1, \ldots, \mathbf{a}_m\right] \in \mathbb{R}_q^{n \times m} \]
因为我们是拼接了 \(m\) 个类似的随机向量得到矩阵 \(\mathbf{A}\) 的, 所以这个矩阵也可以被看作是随机分布的。
得到了 \(\mathbf{A}\) 之后, 我们使用这个矩阵来构造一个Ajtai OWF的实例 \(f_{\mathbf{A}}\) 。这个时候, 因为从 \(\mathbf{A}\) 根本看不出来我们原本的Lattice是什么结构的, 对于一个adversary来说, 这个 \(f_{\mathbf{A}}\) 就是一个平均情况的, 可能是任何Lattice形成的一个Ajtai OWF实例。这个时候, 就算我们一开始使用的是空间中 “最难的”一个Lattice生成的随机向量, 因为adversary并不知道这一回事, 所以他只会觉得他在求解一个平均难度的问题。
如果adversary可以成功的破解这个 \(f_{\mathrm{A}}\) 实例的话, 那么就代表我们找到了一个短向量 \(\mathbf{z} \in\{-1,0,1\}^m\) 并且满足: \[ \sum\left(\mathbf{v}_i+\mathbf{r}_i\right) \mathbf{z}_i=\sum \mathbf{a}_i \mathbf{z}_i=0 \]
我们把这个等式变换一下, 就可以得到如下的形式: \[ \sum \mathbf{v}_i \mathbf{z}_i=-\sum \mathbf{r}_i \mathbf{z}_i \]
观察可以发现, 等式的左侧我们可以得到一个格点, 而右侧我们可以得到一个相对来说较短的向量（并不是格点）。因为 \(\mathbf{r}\) 向量长度的上限和 \(\mathbf{z}\) 向量是个短向量的原因, 我们可以约束右侧的向量: \[ \left\|\sum \mathbf{r}_i \mathbf{z}_i\right\| \approx \sqrt{m} \cdot \max \left\|\mathbf{r}_i\right\| \approx n \cdot \lambda_n \]
虽然右侧的向量并不在格点上, 但是我们发现这个向量相对来说还是比较短的。因为左侧的在 \(\Lambda\)格中的向量的值等于右侧的向量的值, 这就代表说左侧的格点向量也是很短的。这样一来, 我们就等于间接的解决了 \(\Lambda\) 中的短向量了。