数理解析研究所講究録1093 巻 1999 年 162-167

162

Unpredictability of Pseudorandom Number Generators
on Public Key Cryptosystems with Random Inputs
小柴健史 (Takeshi Koshiba)

通信放送機構/横浜リサーチセンター

1

はじめに

現在のセキュリティ技術において乱数はごく自然なものとして利用されている. とくに, 暗号系や署名系の中には乱数は不可欠な部品となっているものもある. 公開鍵暗号系では, 例えば, EIGamal 暗号 [8] は暗号化のときにランダム入力を利用している. 乱数を用いる場合, 暗号などの安全性を測るのに乱数生成法をも含めた安全性をも考慮するのは当然である. ElGamal 自身, 同じ数を (短期間で) 生成するような乱数生成法を好ましくないとしている. しかしながら, 多くの研究者は暗号の安全性を証明するのに際して乱数は理想的であるという仮定を置いている. 暗号系が計算機上で動作する限りにおいては乱数生成法もアルゴリズ
ム的であり, 暗号系の安全性の評価は乱数生成法をも合わせてなされるべきであろう.
擬似乱数の性質と暗号の安全性は密接な関係にはがあるが, 本稿において, 乱数の予測困難性と暗号の安全比の関係を明らかにする. 線形合同法については, $[10, 4]$ の結果からその暗号学安全性が疑問視されている. が, それは共通暗号鍵などのスケジューリングやストリーム暗号に対してである. -方, 公開鍵暗号系
に対する結果としては, [1] において DSS 署名が線形合同法との組合せで安全でないことが示されている.
著者の知る限りにおいて, その他の場合については証明がされてはいない.
さて現在, 乱数と呼ばれているものをおおまかに分類すると,

1. モンテカルロシミュレーションなどに利用するもの,
2. 共通鍵暗号などの鍵生成などに利用する統計的にランダムとされているもの,

3. (–方向関数などを利用して) 乱数の種の計算問題を計算量的に困難であると評価したもの,のようになる. 1 の例としては線形合同法がある. 線形合同法の利点としては最大周期を得るための性質などがよく分かっていることが挙げられる. 例えばろ上の乱数が欲しい場合, 線形合同法を用いると同 $-$ の数が出てくるまでの期間を最大周期にすることが可能である. この性質は EIGamal 暗号には大変好ましいものである. 2 の例はいろいろあるが, 理論的な保証を与えないので本稿では考察の対象外とする. 3 の例
としては Shamir の手法 [16], あるいはなどの乱数ビット生成器がある。 ただし, ランダムな数ではなくランダムなビットの生成器では効率面で問題がある. 同様に,も効率面で問題がある. また, 線形合同法のときのような最大周期性に
Yao の意味での擬似乱数生成器 [関しては保証を与えることが難しい. 本稿では, ランダムな入力を要求するような公開鍵暗号系にはどのような乱数がよいのかを議論する.
をランダム入力, $m$ を
を秘密鍵,
を公開鍵,
公開鍵暗号系のスキームについて復習してみる. 今
$D$
$E$
平文,
を暗号文とすると, 暗号化関数と復号関数
は以下のように書き下せる.
$\mathrm{B}\mathrm{l}\mathrm{u}\mathrm{m}- \mathrm{M}\mathrm{i}_{\mathrm{C}}\mathrm{a}\mathrm{l}\mathrm{i}[3],$$\mathrm{B}\mathrm{l}\mathrm{u}\mathrm{m}-\mathrm{B}\mathrm{l}\mathrm{u}\mathrm{m}- \mathrm{S}\mathrm{h}\mathrm{u}\mathrm{b}[2],$$\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{l}[13]$$1\eta$$k_{p}$$r$$k_{\theta}$$c$$c=E(k_{\mathrm{p}},m,r)$and$m=D(k_{p}, k_{s},c)$.

これらの式から以下の関係式が成立する.
$m=D(k_{p}, k_{\epsilon},E(k_{p},m,r))$

ここまでは公開鍵暗号系一般について言えることだが, ここで担えるとしよう.

この

$R$

.
,

の関数
のことをランダムトラップドア関数と呼ぶことにする. 書き下すと$k_{\mathit{8}}$の役割を$k_{\mathrm{p}}$$k_{\epsilon},r$$R(k_{\mathrm{p}’ s}k,r)$が$m=D’(k_{p},E(k_{p},m,r), R(kk\epsilon’ r)\mathrm{P}’)$となる. この式が意味するのは, 秘密情報が分かれば (

$D’$

そのものが分からなくてもランダムトラップドア関数 $R$ の値の計算も容易であるという条件の元で) 復号ができることを意味している.
$k_{s}$

今考える状況として の系列は理想的なランダム列ではなく, ある計算法によって生成されているとし
よう. このとき, 公開鍵暗号系において$r$$(m_{1},c_{1}, R(\cdot, \cdot,r_{1})),$$(m_{2}, c_{2}, R(\cdot, \cdot, r_{2}))$, ...,$(m_{i}, c_{i}, R(\cdot, \cdot,r_{i}))$および $c_{i+1}$

163

から $m_{i+1}$ を推測する, つまりを推測することが容易ならば安全とは言えないだろう. なお, $R$の値が予測困難性は必ずしも暗号の安全性を保証しない.
少くとも言えることは, 公開鍵暗号系において, その復号がランダムトラップドア関数 $R$ を用いて効率.
的に計算できるならば,の予測問題は困難である必要がある.
以下では,の系列が $r_{i+1}=f(r_{i})$ のように帰納的関数 で表現できるとする.
がから必ずしも効率的に計算できる必要はないが,そのものは効率よく計算できる必要がある.
本稿では, ランダムトラップドア関数で記述できる公開鍵暗号系において に関して安全であるための条件を与える. また, 適用例として, EIGamal 暗号において, いくつかの乱数生成法に適用し, その生成法に関して安全でなくなってしまうことを示す. 具体的には, 乱数が線形合同法の場合, -方向関数的である離散対数問題を利用した場合など, について乱数生成法が原因となって解読されることを示す. また, EIGamal$R(\cdot, \cdot,r_{i+1})$

$R$

$r$

$f$

$f$

$r_{i}$$\{r_{i}\}$$f$

暗号において $R$ の予測問題を困難にする, つまり, 乱数生成法に関して EIGamal 暗号が安全になるような生成法を提案する.

2

乱数生成

今, 数列
において, 帰納的関数 $f$ (以下, 単に乱数関数と呼ぶ) によって $r_{i+1}=f(r_{i})$ なる関係を満たすものとする. 本稿を通じてこの仮定を置くものとする. $f$ は必ずしも多項式時間計算可能である必要がな$\{r_{i}\}$いが

3$\{r_{i}\}$を効率的に生成する手法は存在するものとする.

公開鍵暗号系とランダムトラップドア関数

暗号の安全性はいくつかの平文 $m$ と暗号文 のペアが分かっているときに未知の暗号文に対応する平文を求めるのが困難か容易かによって測られる. ランダムトラップドア関数 $R$ で表記可能という条件の元では,そのものの値は分からないが $(m, c)$ から $R(r)$ が容易に計算されてしまうという前提に立った安全性を考えた方がよい. (ここで $R(r)$ という表記はおよびの略記であるが, 本稿を通じてを固定して考える).
ランダムトラップドア関数 $R$ で表記可能な公開鍵暗号系として ElGamal 暗号を考えよう. まず ElGamal
暗号 [8] について簡単に説明する.
$x\in Z_{p1}-$ を選択し,鍵生成 : 素数乃 生成元とする. 公開鍵は
で秘密鍵は
$c$

$r$

$R(k_{\mathrm{P}}, ks’ r)$$k_{\epsilon}$$\langle p,g,y)$$y=g^{x}\mathrm{m}\mathrm{o}\mathrm{d} p$$g\in Z_{\mathrm{P}^{*}},$$x$$k_{p}$

である.

暗号化

: まず,

$r\in Z_{p-1}$

を–様ランダムに選択する.

メッセージ $m$ に対して暗号化関数$E((p,g,y\rangle,m,r)=$ ( $g’$ mod $p,$で暗号化する.
復号 受け取った暗号文:$(c_{m}, c_{r})$$y^{r}m$

mod )
$p$

に対して復号関数$D((p,g,y),X, c_{m’ r}C)=c_{m}/(c_{r})^{x}$

mod

$p$

で復号する.
ここで$g,p,g^{x}\mathrm{m}\mathrm{o}\mathrm{d} p$から $x$ を求める問題は離散対数問題と呼ばれ, 現在のところ効率的な計算法は知られていない.

,ElGamal 暗号において $R(\langle_{P,g},y\rangle,X,r)=g^{rx}$ とすると, 復号関数 $D()=c_{m}/R()$ という関係にある
ことが容易に確認できる. よって, ElGamal 暗号はランダムトラップドア関数で表記可能と言える. また,ElGamal 暗号の場合, -組の $(m, c)$ から $R(r)$ が容易に計算できる.
EIGamal 暗号の他にもランダムトラップドア関数で表記可能な暗号は存在する. 楕円曲線を用いた暗号系はいくつかあるが, そのうち楕円 ElGamal 暗号と呼ばれるものや, 従来の枠組では最も強い安全性の概念とされている non-malleability [7] や適応的選択暗号文攻撃 [14] に対する保証がある Cramer-Shoup 暗号 [5]もランダムトラップドア関数で表記可能である. また離散対数問題をベースにしない暗号系では,暗号系 [11] がランダムトラップドア関数で表記可能である.

$\mathrm{M}\mathrm{c}\mathrm{E}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{C}\mathrm{e}$164

Theorem 1 $(E, D)$ を公開鍵暗号系とし, $D$ がランダムトラップドア関数 $R$ で表記可能であるとする. 今,
乱数関数を $f$ とする. このとき $R\circ f\circ R^{-1}$ が効率的に計算可能ならば, 公開鍵暗号系 $(E, D)$ は安全でない.
このことから言えることであるが,$f$が–般に計算が困難だからといって$R\mathrm{o}f\mathrm{o}R^{-}1$の計算が困難とは限らない. 以下の章でいくつかの適用例を見ていくことする.

4

適用例

4.1

線形合同法

の形
一般に広く用いられている乱数生成法として線形合同法がある. 線形合同法はとする. ここでは, 最大周期性の条件など,の数列轟} を生成する. ただし, $m$ は正整数で線形合同法の様々な性質については言及しない. 線形合同法の詳細については $[9, 12]$ などの教科書を参照の$r_{i}=ari-1+b\mathrm{m}\mathrm{o}\mathrm{d} m$$a,$ $b,$ $s_{0}\in Z_{m}$こと.

線形合同法において, 乱数関数 $f$ は$f(r_{i})=ar_{i}+b\mathrm{m}\mathrm{o}\mathrm{d} n$

ここで $R\circ f\circ R^{-}1(s)=sy^{b}a$ なる関係がある.

る.

$g$

では, パラメータが未知の場合ではどうであろうか.

問題

は入力 ( $g,p$ , のに対して

は生成元

$g$

の位数とす

の位数の) 線形合同法であるとする. パラメータ

このことを考えるのに幾つかの準備をする.

で $y=g^{x}$ なる $x$ を計算する問題,$\mathrm{m}\mathrm{o}\mathrm{d} p$

$n$

よって

Corollary 2ElGamal 暗号において乱数生成法が (法がが既知の場合は, 次以降の暗号文の解読が容易である.

$\mathrm{D}\mathrm{L}$と書ける. ただし問題 DLLC は入力 $(g,p,y_{1},y_{2},y3)$ に対して mod で $y_{1}=g’,$
での元での等号である.
計算する問題. ただし, 等号は$P$$y_{2}=g^{ar+b},$つまり離散対数問題. また,$y_{3}=g^{a(b}ar+$) $+b$

なる $(a, b)$ を$\mathrm{m}\mathrm{o}\mathrm{d} p$

ここで, いくつかの定義をする. 関数 $f$ が関数 $f’$ に多項式時間関数悉無対–帰着可能であるとは多項式時間計算可能関数$\leq_{m}^{\mathrm{F}\mathrm{P}}$が存在して, 任意の入力$h_{1},$ $h_{2}$で多項式時間関数勢多対–帰着を表す. また

Proposition 3

DLLC

Proof

$\mathrm{D}\mathrm{L}\equiv_{m}^{\mathrm{F}\mathrm{P}}$$\leq_{m}^{\mathrm{p}\mathrm{p}}\mathrm{D}\llcorner$$x$について, $f(x)=h_{2}(f’(h1(X)))$ が成立するときを言う.

$f\leq_{m}^{\mathrm{p}\mathrm{P}}f’$かつ$f’\leq_{m}^{\mathrm{F}\mathrm{P}}f$のときは$f\equiv_{m}^{\mathrm{F}\mathrm{P}}f’$と表記する.

DLLC.

は明らか.

$\mathrm{D}\mathrm{L}\leq_{m}^{\mathrm{F}\mathrm{P}}$DLLC を示そう. DLLC を解く 7 ルゴリズムを $B(g,p,y_{1},y2,ys)$として, DL を解く 7 ルゴリズム $A(g,p,y)$ を構成すればいい. $A$ の入力 $g,p,y$ に対して $B(g,p,y, y^{3},y^{7})$ をを $A$ の出力とする. このアルゴリズムの正当性を検証しよう. $y=g^{r}$ とす
呼ぶ. その解を $(a, b)$ とする.
$b$と, $ar+b=3r,$ $3ar+b=7r$ が成立する. この連立方程式を解くと $a=2,$ $b=r$ が解であることが容易に分かり, $A$ は DL を解くアルゴリズムとなっている. 口
この Proposition が意味することを考えてみよう. $R\circ f\mathrm{o}R^{-1}(S)=S^{a}y=b(g^{x})^{ar+b}$ なので, 今, 仮にる.

.

の生成元になったとき, 連続する $R(r_{i})$ と $R(r_{i+1})$ から乱数関\Re . (線形合同法) $f$ のパラメータを計算するのは離散対数問題を解くのと同じくらい難しいと言っている. もちろん, パラメータの計算を無くして $R(ri+1)$ の計算は可能かもしれないが, パラメータが未知にする場合は ElGamal 暗号に線形合同法を$g^{x}$

が$Z_{p}^{*}$

用いても急務の対策が必要な危険性はないかもしれない.

4.2

線形合同法で法が異なる場合

先の例において ElGamal 暗号における法を とし, また, 乱数生成法の法を $p-1$ と仮定した. ElGamal 暗
上の–様乱数を要求しているので, $p-1$ を法とする線形合同法を用いることは–つの簡単な実装
号はではある. ここではこの条件を緩和することを考える. 今 $q>p-1$ と仮定し, 乱数関数 が $f(r:)=ari+b$$P$$Z_{\mathrm{p}-1}$$f$$\mathrm{m}\mathrm{o}\mathrm{d} q$と書けるとする.

$Z_{\mathrm{p}-1}$

範囲の乱数が必要であるので,$t_{i}=\lfloor_{S_{1}}\cdot(p-1)/q\rfloor$

165として計算する. この場合一様ではなくなるが, 実際的にはほぼ–様なので問題はないとして利用している.
ここで$\frac{\mathrm{z}}{p-1}t_{i}\leq r_{i}<\frac{\mathrm{Y}}{p-1}(ti+1)$

であり,$r_{i}$

は整数値なので$r_{i}$の候補を$S_{i}$とすると$\frac{q}{p-1}t_{i}+c_{j}$と表現できる. よって,$j=1,$$\ldots,$$|S_{i}|$の値は$t_{i+1}$$\lfloor$の要素数は高々 $q/(p-1)$ である. これらの各要素は$S_{i}$($( \frac{aq}{p-1}t_{i}+aC_{j}+b)$$\mathrm{m}\mathrm{o}\mathrm{d} q$)$\frac{p-1}{q}\rfloor$,$j=1,$$\ldots,$$|S_{i}|$の中の–つである. これを t(のと置く. この値を計算すると$t(j)=ati+\lfloor(acj+b)(p-1)/q\rfloor \mathrm{m}\mathrm{o}\mathrm{d} (p-1)$となる. また$c_{j}$の値を正確に表現すると,$c_{j}=j- \frac{qt_{i}\mathrm{m}\mathrm{o}\mathrm{d} (p-1)}{p-1}$,$j=1,$$\ldots,$$\}S_{i}|$と書ける. これを代入すると,$t(j)=at_{i}+ \lfloor\frac{1}{q}((aj+b)(p-1)-qt_{i}\mathrm{m}\mathrm{o}\mathrm{d} (p-1))\rfloor$と書ける. $p-1<q$ を仮定しているので$t(j)=ati+\mathrm{L}(aj+b)(p-1)/q\rfloor$が言える. よって, すべての

$j$

or

$at_{i}+\lfloor(aj+b)(p-1)/q\rfloor-1$

について

or

$g^{t:+1}=g^{at_{i}+\lfloor(}aj+b)(p-1)/q\rfloor$

をチェックすることにより正しい$j$と補正値 (指数の$0$$g^{at\lfloor}:+(aj+b)(p-1)/q\rfloor-1$

または 1 のこと) を計算できる.

Corolary 4 ElGamal 暗号において乱数生成法が (法が の位数の) 線形合同法であるとする. もし $q/p=$でパラメータが既知の場合は, 次以降の暗号文の解読が容易である.
$q$$O(p_{\mathit{0}\iota}y(n))$

4.3

非線形な乱数関数

線形合同法の数列は線形であったが, ここでは非線形な例を考える.
やにおいてなる生成系を用いて,からあるビットを選ぶことにより擬似ランダムビット生成器を構成している. 非線形な例として $r_{i+1}=g^{r_{*}}$ を考えたいが, 簡単のために多少変形してとする. この$\mathrm{B}\mathrm{l}\mathrm{u}\mathrm{m}-\mathrm{M}\mathrm{i}_{\mathrm{C}\mathrm{a}\mathrm{l}\mathrm{i}}[3]$$s_{i+1}=g\epsilon_{*}$$\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{l}[13]$$s_{i}$$f(r_{i})=(g^{x})^{\mathrm{r}}$.

とき $R\circ f\mathrm{o}R^{-1}(s)=(g^{x})^{\epsilon}$ となる.

Corolary 5 ElGamal 暗号において乱数関数がの解読が容易である.

5$f(r_{i})=(g^{x})^{\prime:}$であるとする. このとき, 次以降の暗号文

乱数生成法の提案

ElGamal 暗号は離散対数問題をベースにした暗号系なので, 離散対数問題をベースにした乱数生成法を考える. また ElGamal 暗号ではの乱数で同じ数が現れるまでの長さが極力大きいことが望まれる. その実現として $p-1$ を法とする線形合同法を直接利用する替りに以下のように間接的に利用することを考える.
$Z_{p-1}$

166

Procedure GEN-RND$s_{i}:=aS_{i}-1+b\mathrm{m}\mathrm{o}\mathrm{d} (p-.

$r_{i}:=(g^{\epsilon}:\mathrm{m}\mathrm{o}\mathrm{d} p)-1$

output$r_{i}$

1)$

;

;

;

GEN-RND で得られる数列

は $Z_{p-1}$ 上の乱数でなるべく周期が大きくなるようパラメータの調整を$\{r_{i}\}$することができる. このときのを, 素数 P とまず,を見たす $(m, x,r)$ が存在するならば,$R\circ f\circ R^{-1}$$\mathrm{E}\mathrm{G}(p,g, \mathrm{Y}, C_{1}, C1)$の次の値の予測問題を考える.

$g,\mathrm{Y},$$C_{1},$$C2\in z*p$を入力として,$\mathrm{Y}=g^{x}$

かつ $C_{1}=g^{r},$ $C_{2}=mg^{xr}$を計算する問題とする. この問題は ElGamal 暗号を直接解をと $g,X,$を入力として, $X=g^{x}$ かつ
くことに対応している.
. を, 素数
問題
[6]
と呼ばれて
を計算する問題とする. この問題は Diffie-Hellman
満たす ( , のが存在するならばを満たす $(x,y)$ がを入力として, $X=g^{x}$ かついる.
を, 素数 と $g,X,$を入力として,を, 素数 と $g,X,$を計算する問題とする.
存在するならば,”$X=g^{x}$ かつを計算する, 存在しなければ, 特別な記号を満たす ( , のが存在するならば,と $g,$ $R,$を入力として, $R=g^{g’}$ かつを出力する問題とする. NXTR $(p,g, R,A, B)$ を, 素数$A=g^{a},$ $B=g^{b}$ を満たす $(r,a, b)$ が存在するならば,を計算する問題とする. この問題は EIGamal
暗号と乱数生成に GEN-RND を用いて, かつ, 内部状態の更新に利用している線形合同法のパラメータが既知の場合の $R\circ f\circ R-1$ の次の値の計算問題に対応している.
$m\in Z_{\mathrm{p}}^{*}$$\mathrm{D}\mathrm{H}(P,g, X,\mathrm{Y})$$\mathrm{Y}=g^{y}$$Y\in Z_{p}^{*}$$P$$g^{xy}$$x$$\mathrm{D}\mathrm{H}\mathrm{E}(p,g,X,\mathrm{Y})$$\mathrm{Y}=g^{y}$$\mathrm{Y}\in z_{p}*$$P$$g^{x^{y}}$$\mathrm{D}\mathrm{H}\mathrm{E}^{\star}(p,g,x, \mathrm{Y})$$\mathrm{Y}=g^{y}$$P$$\mathrm{Y}\in Z_{p}*$$”\perp$$g^{x^{y}}$$x$$A,B\in Z_{\mathrm{p}}^{*}$$P$$g^{g^{\mathrm{c}\prime+b}}$

Theorem 6$\mathrm{E}\mathrm{G}\equiv_{m}^{\mathrm{F}}\mathrm{p}\mathrm{D}\mathrm{H}\leq_{m}^{\mathrm{F}\mathrm{P}}\mathrm{D}\mathrm{H}\mathrm{E}^{\star}$

かっ DHE$\equiv_{m}^{\mathrm{F}\mathrm{P}}$NXTR$\leq_{m}^{\mathrm{p}\mathrm{p}}\mathrm{D}\llcorner$.

を解くアルゴリズムとする. このとき, DH をを示す. $B(p,g,X, Y)$ を解くアルゴリズム $A(p,g,X, Y)$ を構成すればよい. アルゴリズム $A$ は以下のようになる.

Proof

まず

$\mathrm{D}\mathrm{H}\mathrm{E}^{\star}$$\mathrm{D}\mathrm{H}\leq_{m}^{\mathrm{F}\mathrm{P}}\mathrm{D}\mathrm{H}\mathrm{E}^{\star}$

Algorithm $A(p,g, X, \mathrm{Y})$ to solve DH$z_{1}:=B(p,g^{2}, X, g)4$ ;;outputand hallt;
if
outputand halt;if$B(p,g^{2},x\mathrm{Y}g,\mathit{9}^{4})/B(p,g^{2},
Yg,g^{4})z1X$
and halt;
outputif$B(p,g^{2},X\mathrm{Y}g^{2},g^{4})/B(p,g^{2},Xg,g)4B(p,\mathit{9}^{2},\mathrm{Y}g,g)4X\mathrm{Y}g$ and halt.
outputif$z_{2}:=B(\mathrm{P},\mathit{9}^{2}, \mathrm{Y},g)4$$z_{1}\neq\perp \mathrm{a}\mathrm{n}\mathrm{d}z_{2}\neq\perp \mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}$$B(p,g^{2},X\mathrm{Y},g^{4})/z_{1}z_{2}$$z_{1}=\perp \mathrm{a}\mathrm{n}\mathrm{d}z_{2}\neq\perp \mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}$$B(p,g^{2},X\mathrm{Y}g,\mathit{9}^{4})/B(p,g^{2}, xg,g)4z_{2}\mathrm{Y}$$z_{1}\neq\perp \mathrm{a}\mathrm{n}\mathrm{d}z_{2}=\perp \mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}$$z_{1}=\perp \mathrm{a}\mathrm{n}\mathrm{d}z_{2}=\perp \mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}$が偶素数のときは$P$$g^{(x+y)^{2}}/2$とき$\#\mathrm{h}g^{2}$のとき$g^{2}$$z_{1}$

も$z_{2}$

もなので, アルゴリズム$\perp$$A$とはならない. このとき $z_{1}=g^{x^{2}/2}$ かつ $z_{2}=g^{v^{2}/2},$ $B(p,g^{2},X\mathrm{Y},g^{4})=$は$g^{xy}$を出力するので,$A$は DH を正しく解いている. ,$P$ が奇素数のの生成元でないかもしれない. ここで部分群 $G=$ { : is even in $Z_{p-1}$ } を考える. こ
は $G$ の生成元にはなる. アルゴリズム $A$ がアルゴリズム $B$ を呼ぶときに, アルゴリズム $A$ はは$g^{i}$$Z_{P}^{*}$$i$

3 つめの引数が $G$ に属するように調整を加えている. 場合分けは 4 通りになるが, $z_{1}=\perp$ かつの場合だけを考えよう. 他の場合も同様な議論ができる. ここで, $B(p,g^{2},X\mathrm{Y}g,\mathit{9}^{4})=g^{((x+1)y)/2}+2$ かつ$B(p,g^{2}, x\mathit{9},g)4=g^{(x+1})2/2$ が成立していることは容易に確かめられる. いずれの場合にしろ, アルゴリズ
ム
はを出力するので, DH を解いていることになる.
次に DHENXTR を示そう. $C(p,g,R, A, B)$ を NXTR を解くアルゴリズムとしよう. DHE を解く
アルゴリズム $B(p,g,X,Y)$ を構成しさえすればよい. アルゴリズム $B$ は, まず $C(p,g,X, \mathrm{Y}, 1)$ を呼び, 答をそのまま $B$ の出力とする. ここで, $x=g^{z}$ を仮定しよう. こえとしてを得る. アルゴリズム $B$ はであり, 7 ルゴリズム $B$ は DHE を解いている.
のとき
DHE を示そう. $B(p,g, X, Y)$ を DHE を解くアルゴリズムとする. NXTR を解くア
最後にルゴリズム $C(p,g,R, A, B)$ を構成すればよい. アルゴリズム $C$ はアルゴリズム $B(p,g,R, A)$ を呼び, 答えを解き, 答えとしとしてDHE であるからアルゴリズム $C$ はを得る. さらに,およびが成立することは容易に確認でて $w’$ を得ることができる.
$z_{2}\neq\perp$$A$$g^{xy}$$\leq_{m}^{\mathrm{F}\mathrm{P}}$

$w$

$w$

$W=gff^{z_{\mathrm{V}}}=g^{(g^{z}})^{y}=g^{x^{y}}$

NXTR.

$w$

$\leq_{m}\mathrm{F}\mathrm{P}$$\mathrm{D}\mathrm{H}\leq_{m}^{\mathrm{F}\mathrm{P}}$$w=g^{(_{\mathit{9}^{r}})^{\Phi}}=g^{g^{pa}}$$\mathrm{D}\mathrm{H}(p,g,w,g)B$$w’=g^{\mathit{9}^{ra}ff^{b}}=g^{\mathit{9}^{fa}}+b$

167

きる.

のことからアルゴリズム $C$ は NXTR を解いている.
NXTR
DL については明らかである. [15] で,DH が証明されているので, これで証明は完$–$$\leq_{m}^{\mathrm{F}\mathrm{P}}$$\mathrm{E}\mathrm{G}\equiv_{m}^{\mathrm{F}\mathrm{P}}$

了する.

口

この定理から, EIGamal 暗号において GEN-RND を乱数生成法 (線形合同法のパラメータが既知でもよい) 利用すれば, 乱数部分を切っ掛けにして解かれることはないと思われる.

References[1] M. Bellare, S. Goldwasser, and D. Micciancio. Pseudo-random number generation within cryptographic algorithms: The DSS case. In Lecture Notes in Computer Science (CRYPTO’97), Vol. 1294,
pp. 277-291. Springer-Verlag, 1997.

[2] L. Blum, M. Blum, and M. Shub. A simple unpredictable pseudo-random number generator. SIAM
Joumal on Computing, $15(2):364-383$ , 1986.
[3] M. Blum and S. Micali. How to generate cryptographically strong sequences of
SIAM $Jo$ ufnal on Computing, $13(4):850-864$ , 1984.

$\mathrm{p}\mathrm{s}\mathrm{e}\mathrm{u}\mathrm{d}_{0}$ndom bits.

[4] J. Boyar. Inferring sequences produced by pseudo-random number generators. Joumal of the Association for Computing Machinery, $36(1):129-141$ , 1989.
[5] R. Cramer and V. Shoup. A practical public key cryptosystem provably secure against adaptive
chosen ciphertext attack. In Lecture Notes in Computer Science (CRYPTO’98), Vol. 1462, pp. 13-25.

Springer-Verlag, 1998.

[6] W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information
Theory,, 1976.
$\mathrm{I}\mathrm{T}-22(6):644-654$[7] D. Dolev, C. Dwork, and M. Naor. Non-malleable cryptography. In Proceedings of the$ACM$ Symposium on Theofy
of Computing, pp. 542-552. ACM Press, 1991.
[8] T. ElGamal. A public key cryptosystem and a signature scheme

Ransactions on Information Theory,[9] D. E. Knuth. The Art of
3rd edition, 1998.

$\mathrm{I}\mathrm{T}-31(4):469-472$$\mathrm{b}\mathrm{a}s$$\mathit{2}\mathit{3}rd$

Annualed on discrete logarithms. IEEE

, 1985.

puter Programing, Vol. 2. Seminumerical Algorithms. Addison-Wesley,$Co^{\backslash }\dot{m}$$..s$[10] H. Krawczyk. How to predict congruential generators. Journal of Algorithms, $13(4):527-545$ , 1992.

[11] R. J.
. A public-key cryptosystem based on algebraic coding theory. The Deep Space Network
Progress Report 42-44, pp. 114-116, Jet Propulsion Laboratory, 1978.
$\mathrm{M}\mathrm{c}\mathrm{E}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{c}\mathrm{e}$[12] H. Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods, Vol. 63 of CBMS-NSF
Regional Conferencein Applied Mathematics. SIAM, 1992.
$Se\dot{\mathcal{H}}es$[13] S. Patel and G. S. Sundaram. An efficient discrete
pseudo random generator. In Lecture Notes in
Computer Science (CRYPTO’98), Vol. 1462, pp. 304-317. Springer-Verlag, 1998.
$\log$[14] C. Rackoff and D. R. Simon. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext
attack. In Lecture Notes in Computer Science (CRYPTO’91), Vol. 576, pp. 433-444. SPringer-Verlag,

1992.
[15] K. Sakurai and H. Shizuya. A structural comparison of the computational difficulty of breaking discrete
cryptosystems. Joumal of Crgptology, $11(1):29-43$ , 1998.
$\log$[16] A. Shamir. On the generation of cryptographically strong pseudorandom sequences. $ACM\pi_{ansac}-$tions on Computer Systems,, 1983.
$1(1):38\triangleleft 4$[17] A. C. Yao. Theory and applications of trapdoor functions. In Proceedings of theAnnual IEEE
Symposium on Foundations of Computer Science, pp. 80-91. IEEE Computer Society Press, 1982.
$\mathit{2}\mathit{3}rd$