可加同态DD-PKE再探

### 可加同态DD - PKE再探 #### 解密过程正确性 解密过程的正确性体现在以下两个等式： - $\text{Dec}(PP,sk)(\text{Enc}(PP,pk)(m)) = \frac{x(rR + Pm - srQ)}{N}= m$ - $m\text{Dec}(PP,MK)(\text{Enc}(PP,pk)(m)) = \frac{x(M(rR + Pm))}{N}M^{-1} \bmod N = m$ 这里利用了$\text{ord}(Q)$整除$M$的事实，即$MR = sMQ = O$。 同时有以下几点说明： 1. 知道$M$在多项式时间内等同于知道$N$的因子分解。因此，从公共参数$PP$计算主秘密密钥$MK$在计算上是不可行的。 2. 在$E(Z_{N^2})$中离散对数问题（DLP）困难的假设下，从用户的公钥计算其私钥在计算上也是不可行的。 3. 在不知道$N$的因子分解的情况下，要在曲线上找到一个与公开已知点$Q$、$R$和$P_1$的线性组合不同的点$Q'$是计算上不可行的，因为需要求解$Z_{N^2}$中的多项式方程。 4. 主解密算法不需要用户的公钥，因此成功定义了一个UI - DD - PKE方案。 5. 主解密对于给定的密文$c \in C$永远不会失败，总是输出消息$m \in P$。而用户解密不同，如果$\frac{x(B - sA)}{N}$不能整除，则输出$\perp$。后续会证明，当且仅当给定的密文无效时会出现这种情况，用户可以有效检测。 #### 密码系统的性质 1. **可加同态性**：密码系统是可加同态的，即$\text{Dec}(PP,sk)(\text{Enc}(PP,pk)(m_1) + \text{Enc}(PP,pk)(m_2)) = m_1 + m_2$。结合前面提到的第4点，该方案是一个可加同态的UI - DD - PKE方案。 - **证明**：设$m_1, m_2 \in Z_N$是两个明文，分别加密为$(A_1, B_1)$和$(A_2, B_2)$。则$(A, B) := (A_1, B_1)+(A_2, B_2)$是$m := m_1 + m_2$的密文，因为： $\frac{x(B - sA)}{N} = \frac{x(r_1R + Pm_1 + r_2R + Pm_2 - sr_1Q - sr_2Q)}{N}= \frac{x(P(m_1 + m_2))}{N}= \frac{(m_1 + m_2)N}{N}= m_1 + m_2$。 2. **用户检测无效密文**：用户可以检测无效密文。 - **证明**：根据定义，密文$c$的形式为$(A, B) = (rQ, tQ + Pm) \in \langle Q \rangle \times \langle Q, P_1 \rangle$。若$s$表示用户的私钥，密文$c$有效当且仅当$t = rs \bmod \text{ord}(Q)$，这等价于$B - sA = Pm$。 3. **主实体检测无效密文**：如果在$E(Z_{N^2})$中DDH$_{Z_{N^2}}$问题是困难的（即使知道$N$的因子分解），那么主实体在给定用户公钥的情况下，无法判断给定的密文是否是在该公钥下的有效加密。 - **证明**：假设主实体可以检测无效密文，其形式为$(A, B) = (rQ, tQ + Pm) \in \langle Q \rangle \times \langle Q, P_