公開鍵暗号

$\mathsf A$ は相異なる $m_0,m_1$ を選び、受け取った $c$ と自分で計算した $c_0:=\mathsf{Enc}(\mathit{pk},m_0)$ を比べ、$c=c_0$ なら $0$、そうでなければ $1$ を出力する。実験 $0$ では $c=c_0$ なので $p_0=0$ である。実験 $1$ では $c=\mathsf{Enc}(\mathit{pk},m_1)$ で、正しさから $\mathsf{Dec}(\mathit{sk},c)=m_1\ne m_0=\mathsf{Dec}(\mathit{sk},c_0)$ なので $c\ne c_0$、よって $p_1=1$ である。$\square$

$\mathsf B$ は三つ組 $(X,Y,Z)\in G^3$ を受け取り、次を行う。$X$ を公開鍵として $\mathsf A$ に渡し、$\mathsf A$ が選んだ $m_0,m_1$ を受け取る。$b\in\{0,1\}$ を一様に選び、$(Y,\ Zm_b)$ を暗号文として $\mathsf A$ に渡す。$\mathsf A$ の出力 $\hat b$ が $b$ に等しければ $1$、そうでなければ $0$ を出力する。
段 1（本物の三つ組）。$(X,Y,Z)=(g^x,g^y,g^{xy})$ なら、$X$ は $\alpha=x$ の公開鍵と同じ分布をもち、$(Y,Zm_b)=(g^y,X^ym_b)$ は $\beta=y$ による $m_b$ の暗号文そのものである。よって $\mathsf A$ から見た状況は実験 $b$ と同じで、
$$ \Pr[\mathsf B(\mathcal D)=1]=\Pr[\hat b=b]=\tfrac12(1-p_0)+\tfrac12p_1=\tfrac12+\tfrac12(p_1-p_0) $$
である。
段 2（無作為な三つ組）。$(X,Y,Z)=(g^x,g^y,g^z)$ で $z$ がほかのすべてと独立なら、$x,y$、$\mathsf A$ の乱数、$b$ を固定したとき $m_b$ は決まり、$g^z$ は $G$ 上で一様なので $Zm_b=g^zm_b$ も $G$ 上で一様である。よって $\mathsf A$ が受け取るもの $(X,Y,Zm_b)$ の分布は $b$ によらず、$\hat b$ は $b$ と独立である。したがって $\Pr[\mathsf B(\mathcal R)=1]=\Pr[\hat b=b]=\frac12$ である。
段 1 と段 2 の差をとると $\operatorname{Adv}^{\mathrm{DDH}}(\mathsf B)=\frac12\lvert p_1-p_0\rvert=\frac12\operatorname{Adv}^{\mathrm{SS}}(\mathsf A)$ である。$\square$

1. 公開鍵 $u=g^\alpha$ と暗号文の $v=g^\beta$ から $g^{\alpha\beta}=u^\beta$ が求まり、$m=e\,(u^\beta)^{-1}$ である。
2. $(X,Y)=(g^x,g^y)$ を受け取ったら、$e\in G$ を一様に選んで $m':=\mathsf A(X,Y,e)$ を計算し、$e\,m'^{-1}$ を出力する。本物の暗号化では $m$ が一様で $\alpha,\beta$ と独立なので、$e=u^\beta m$ は $(u,v)$ を固定しても $G$ 上で一様であり、$(u,v,e)$ の分布は「$\alpha,\beta$ と独立に一様な $e$」と同じである。よってこの手順の入力 $(X,Y,e)$ は本物の $(u,v,e)$ と同じ分布をもち、確率 $\varepsilon$ で $m'$ は $e=X^ym'$ を満たす平文 $m'=e\,(g^{xy})^{-1}$ に等しい。このとき出力は $e\,m'^{-1}=g^{xy}$ である。$\square$

Fermatの小定理 により $s^2\equiv c^{(p+1)/2}\equiv r^{p+1}=r^{p-1}r^2\equiv r^2\equiv c\pmod p$ である。一般に奇素数 $p$ と $p\nmid r$ について、$x^2\equiv r^2$ なら $(x-r)(x+r)\equiv0$ で、$p$ は素数なので $x\equiv\pm r$ であり、$p$ が奇数なので $r\not\equiv-r$ である。よって法 $p$ の平方根はちょうど 2 つである。法 $n$ では、$x^2\equiv c\pmod n$ は $x^2\equiv c$ が法 $p$ と法 $q$ の両方で成り立つことと同値で、それぞれ 2 つの解の組合せ 4 通りが、中国剰余定理 によりちょうど 4 つの剰余類に対応する。$\square$

手順：$r\in\mathbb Z_n^\times$ を一様に選び、$c:=r^2\bmod n$ として $s:=\mathsf A(n,c)$ を得る。$s^2\equiv c$ かつ $s\not\equiv\pm r\pmod n$ なら $\gcd(s-r,n)$ を出力する。
段 1（出力は素因数）。$s^2\equiv r^2$ なので $n\mid(s-r)(s+r)$ である。$p\mid s-r$ でなければ $p\mid s+r$ である。$p$ と $q$ がどちらも $s-r$ を割れば $n\mid s-r$、どちらも $s+r$ を割れば $n\mid s+r$ となり、$s\not\equiv\pm r$ に反する。よって $p,q$ の一方だけが $s-r$ を割り、$\gcd(s-r,n)$ は $p$ か $q$ である。
段 2（成功の確率）。$c$ を固定すると、prop-pke-sqrt により $r^2\equiv c$ となる $r\in\mathbb Z_n^\times$ はちょうど 4 つで、$r$ を一様に選んだので、$c$ を与えたときの $r$ の条件付き分布はこの 4 つの上の一様分布である。$\mathsf A$ の出力 $s$ は $c$ と $\mathsf A$ の乱数だけで決まり、$r$ が 4 つのどれであるかとは独立である。$s$ が正しい平方根のとき、$r\in\{s,-s\}$ となる条件付き確率は $\frac24=\frac12$ である（$s\not\equiv-s$ は $n$ が奇数で $s\in\mathbb Z_n^\times$ だから）。よって成功の確率は $\varepsilon\cdot\frac12$ 以上である。$\square$