公钥加密中的密钥隐私与可证明安全的公平盲签名

### 公钥加密中的密钥隐私与可证明安全的公平盲签名 #### 公钥加密中的密钥隐私 在公钥加密领域，密钥隐私是一个重要的研究方向。对于RSA - RAEP加密方案，存在一个关于敌手优势的不等式： \[Adv_{ik - cca}^{\Pi,A}(k) \leq 32q_{hash} \cdot ((1 - \epsilon_1) \cdot (1 - \epsilon_2) \cdot (1 - \epsilon_3))^{-1} \cdot Adv_{\theta - pow - fnc}^{RSA,M_A}(k) + q_{gen} \cdot (1 - \epsilon_3)^{-1} \cdot 2^{-k + 2}\] 其中： \[\epsilon_1 = 4 \cdot (\frac{3}{4})^{\frac{k}{2}-1}\] \[\epsilon_2 = \frac{1}{2^{\frac{k}{2}-3}-1}\] \[\epsilon_3 = \frac{2q_{gen} + q_{dec} + 2q_{gen}q_{dec}}{2^{k_0}} + \frac{2q_{dec}}{2^{k_1}} + \frac{2q_{hash}}{2^{k - k_0}}\] 并且，算法\(M_A\)的运行时间是算法\(A\)的运行时间加上\(q_{gen} \cdot q_{hash} \cdot O(k^3)\)。 对于典型的参数\(k_0(k)\)、\(k_1(k)\)以及允许的查询次数\(q_{gen}\)、\(q_{hash}\)和\(q_{dec}\)，\(\epsilon_1\)、\(\epsilon_2\)和\(\epsilon_3\)的值非常小。这意味着，如果存在一个敌手能够在IK - CCA意义上成功破解RSA - RAEP，那么就存在一个针对RSA陷门置换族的部分求逆敌手，其优势和运行时间相当。 当\(\theta > 0.5\)时，RSA的\(\theta\) - 部分单向性已被证明等价于RSA的单向性。在RSA - RAEP（以及RSA - OAEP）中通常就是这种情况。基于此，在假设RSA是单向的前提下，我们能够证明RSA - RAEP在IK - CCA意义上的安全性。 #### 匿名陷门置换加密 由于标准RSA族不是匿名的，我们需要寻找匿名的族。下面介绍两种基于RSA的匿名族构造： - **构造1**：定义一个族\(F = (K, S, E)\)。密钥生成算法与标准RSA族相同。设\((N, e)\)为公共密钥，\(k\)为相应的安全参数。定义域\(Dom_F(N, e)\)和值域\(Rng_F(N, e)\)都为\(\{0, 1\}^k\)。对于任意\(x \in \{0, 1\}^k\)，定义加密函数为： \[E_{N,e}(x) = \begin{cases} x^e \bmod N & \text{如果 } x \in \mathbb{Z}_N^* \\ x & \text{否则} \end{cases} \] 这是\(\{0, 1\}^k\)上的一个置换。采样算法\(S\)在输入\(N\)和\(e\)时，简单地返回一个随机的\(k\)位字符串。这个族是陷门的，并且是完全匿名的，但不是单向的，只是弱单向的。即对于每个多项式时间敌手\(B\)，存在一个多项式\(\beta(\cdot)\)，使得对于所有足够大的\(k\)，有\(Adv_{1 - pow - fnc}^{F,B}(k) \leq 1 - \frac{1}{\beta(k)}\)。因此，可以应用将弱单向函数转换为强单向函数的标准变换。 - **构造2**：通过Yao的叉积构造从构造1的族\(F\)得到一个新的族\(F = (K, S, E)\)。密钥生成算法不变，对于任意密钥\(N\)和\(e\)，定义域\(Dom_F(N, e)\)和值域\(Rng_F(N, e)\)都为\(\{0, 1\}^{k^2}\)。将定义域中的一个点解析为\(k\)位字符串的序列，加密函数定义为\(E_{N,e}(x_1, \ldots, x_k) = (E_{N,e}(x_1), \ldots, E_{N,e}(x_k))\)。采样算法很明显，并且这个族