準同型暗号

Last updated Nov 2, 2022 Edit Source

レベルn準同型 = 加法準同型 + n回の乗算準同型

• 乗算回数に制約がある完全準同型
• レベルnはn次方程式を計算できる
• レベル2準同型なら乗算が1度だけ可能

乗法準同型 $$ \begin{aligned} \mathcal{E}(m_1)\times\mathcal{E}(m_2) &= m_1^em_2^e & \bmod n \\ &= (m_1m_2)^e & \bmod n \\ &= \mathcal{E}(m_1m_2) \end{aligned} $$

乗法準同型 $$ \begin{aligned} \mathcal{E}(m_1)\times\mathcal{E}(m_2) &= (g^{r_1},m_1h^{r_1})(g^{r_2},m_2h^{r_2}) \\ &= (g^{r_1+r_2},m_1m_2h^{r_1+r_2}) \\ &= \mathcal{E}(m_1m_2) \end{aligned} $$

加法準同型 $$ \begin{aligned} \mathcal{E}(m_1)\times\mathcal{E}(m_2) &= (g^{m_1}r_1^n)(g^{m_2}r_2^n) & \bmod n^2 \\ &= g^{m_1+m_2}(r_1r_2)^n & \bmod n^2 \\ &= \mathcal{E}(m_1+m_2) \end{aligned} $$

加法準同型

レベル2準同型暗号 位数 $p$ の楕円曲線 $E$, と生成元 $P\in E$ 秘密鍵 $s\in\mathbb{F}_p$ と公開鍵 $sP$ 平文 $m$ に対して乱数 $r$ をとり $c=(mP+rsP, rP)$ $c = (S, T)$ に対して $S-sT = (mP+rsP)-s(rP)=mP$ としDLPを解いて $m$ を得る

加法準同型性 $$ \begin{aligned} \mathcal{E}(m_1)+\mathcal{E}(m_2) &= (m_1P+r_1sP,r_1P)+(m_2P+r_2sP,r_2P) \\ &= ((m_1+m_2)P, (r_1+r_2)sP, (r_1+r_2)P) \\ &= \mathcal{E}(m_1+m_2) \end{aligned} $$ 乗法準同型性 $\mathcal{E}(m_1)\times\mathcal{E}(m_2) := (e(S_1, S_2), e(S_1, T_2), e(T_1, S_2), e(T_1, T_2))$ $$ \begin{aligned} \mathcal{D}(c_1,c_2,c_3,c_4) &= \frac{c_1c_4^{s_1s_2}}{c_2^{s_2}c_3^{s_1}} = \frac{e(S_1,s_2)e(s_1T_1,s_2T_2)}{e(S_1,s_2T_2)e(s_1T_1,S_2)} \\ &=e(S_1-s_1T_1,S_2-s_2T_2) \\ &=e(mP_1,m’P_2)=e(P_1,P_2)^{mm’} \end{aligned} $$

ペアリングベースの効率的なレベル2準同型暗号（SCIS2018） (slideshare.net)

完全準同型 ex. Gentry, 格子ベース

完全準同型

完全準同型