以下の記事で紹介した論文に登場したCamenish-Shoup暗号について紹介する記事です。

Camenish-Shoup暗号

検証可能な暗号化と復号が行える暗号方式であり、Crammer-Shoup暗号とPailier暗号を合わせたような形をしている。Crammer-Shoup暗号は検証可能な復号機能を持っており、適応的選択暗号文攻撃（IND-CCA2）である方式だが、暗号化は検証可能ではなかった。Camenish-Shoup暗号では暗号機能とは独立したΣプロトコルを用いることで暗号化の正当性を証明する。また、加法準同型性を持つ。

方式

鍵生成

ソフィージェルマン素数とは $2p'+1$ も素数であるような $p'$ のこと。このとき、 $2p'+1$ は安全素数という。

2つのソフィージェルマン素数 $p',q'$ をランダムに選ぶ。ここで $p'\neq q'$ である。
$p:=(2p'+1),q:=(2q'+1),n:=p\cdot q,n':=p'\cdot q'$ を計算する。
$x _ 1,x _ 2,x _ 3 \in _ R [n ^ 2 / 4$ ]、 $g'\in _ R \mathbb{Z} ^ * _{n ^ 2}$ をランダムに選ぶ。
$g=(g') ^ {2n},y _ 1=g ^ {x _ 1},y _ 2=g ^ {x _ 2},y _ 3=g ^ {x _ 3}$ を計算する。
ハッシュ関数 $\mathcal{H _ {hk}(\cdot)}$ の鍵 $hk$ を生成する。
$pk=(hk,n,g,y _ 1,y _ 2,y _ 3)$ , $sk=(hk,n,g,x _ 1,x _ 2,x _ 3)$ とする。
$h=(1+n\ mod\ n ^ 2)\in \mathbb{Z} ^ * _{n ^ 2}$ とする。

暗号化

$m\in[n$ ]とそのラベル $L\in \{0,1\}^*$ を公開鍵で暗号化し、 $(u,e,v)$ とする。この時、乱数 $r\in _ R [n ^ 2 / 4$ ]を生成して使用する。

$u:=g ^ r,e:=y ^ r _ 1 \cdot h ^ m, v:=abs((y _ 2 \cdot y _ 3 ^ {H _ {hk}(u,e,L)}) ^ r)$

復号

まず、 $abs(v)=v$ と $v ^ 2 := u^{2(x _ 2+H _ {hk}(u,e,L)\cdot x _ 3)}$ を計算する。これが成立してなければrejectする。
$t=2 ^ {-1} mod\ n$ と $\hat{m} := (e/u ^ {x _ 1}) ^ {2t}$ を計算する。 $\hat{m}:=h ^ m,m\in [n$ ]でなければrejectする。通過したら、 $m$ を得る。

性質

IND-CCA2安全性

DCR仮定とハッシュ関数 $\mathcal{H} _ {hk}(\cdot)$ の衝突困難性のもと、Camenish-Shoup暗号は適応的選択暗号文攻撃に対して安全である。

加法準同型

暗号文 $C=(u,e,v)$ は同じ公開鍵で暗号化された $C'=(u',e',v')$ と掛け算を行うと

$(u\cdot u',e \cdot e',v \cdot v')=(g ^ {r+r'} ,y _ 1 ^ {r+r'} \cdot h ^ {m+m'},(y _ 2 \cdot y _ 3 ^ {H _ hk (u,e,L)})^ {r+r'})$

これは $m+m'$ の暗号文なので、加法準同型性を持つ。

検証可能な暗号化

検証可能とは、復号や暗号化の時に暗号状態で不正かどうかチェックして計算を中止できる機能のこと。Crammer-Shoup暗号は検証可能な復号機能が暗号方式に組み込まれていた。

Camenish−Shoup暗号では検証可能な復号機能に加え暗号方式とは別にΣプロトコルを行い、暗号化が正しいことも証明する。このプロトコルはPがVに対して、暗号文が確かに公開鍵とラベルによって暗号化されていることを証明する。このプロトコルはstrong RSA仮定のもと、verifiable encryptionである。