数理解析研究所講究録1093 巻 1999 年 156-161

156

分散 RSA 暗号における鍵生成と復号アルゴリズム

Key Generation and Decryption Algorithm in Distributed RSA Cryptosystem
宮崎真悟

櫻井幸

Shingo Miyazaki

Kouichi Sakurai

九州大学大学院システム情報科学研究科情報工学専攻〒 812-8581 福岡市東区箱崎 6-10-1{shingo. akurai} Qcsce. kyushu-u.
$\mathrm{s}$$\mathrm{a}\mathrm{c}$

.jp

:

型で秘密
Boneh と Franklin ?は, 複数の機関で RSA における鍵生成を行い, 秘密鍵を型共有する方式 (D. Boneh and M. Franklin, CRYPTO ’97 (1997)) を示した. $(2,2)$ 型から概要$(\mathrm{t},\mathrm{t})$$(2,\mathrm{n})$へ変換する効率的な手法については同論文にて記されているが,そこで本稿では,されていない.

Boneh-Franklin 法を$(\mathrm{t},\mathrm{n})$$(\mathrm{t},\mathrm{t})$型から$(\mathrm{t},\mathrm{n})$型への変換は示

型に拡張する手法について考察する.

また, ユークリッドのアルゴリズムを用いた RSA 暗号における分散復号アルゴリズムを示す.
キーワード:1閾値法,

RSA, 秘密分散, 分散復号

はじめに

しかし,

RSA 暗号系に閾値法の概念を導入し, 秘密鍵を$(t, n)$ 型で秘密分散させる方式 [FGMY97, ?] が提案されている. 中でも Frankel ら [FGMY971 は, 秘密
鍵そのものを算出することなく任意$t$野の機関で復号や署名を行える方式を示している. これは, 合成
数 $N$ の異なる素因数知るディーラーが, 素因数を知らなくても任意 個で復号や署名が行えるような秘
$t$

密鍵

$d$

を作成することが特徴である.

方, ディーラーの存在しない環境で, 複数の機関で鍵生成を行う方式が Boneh と Franklin [BF,97]
によって示された.

鍵$d$

この鍵生成を実行すると, 秘密に対して $(n, n)$ 型の秘密分散が同時に行われることが特徴である. また保持する部分鍵を用いた全ての機関からの部分出力を合成することで, 秘密鍵$d$を算出せずに暗号文を復号することができる.

を実現させることが本稿の目的である. Frankel .

. Yunga

Boneh-Franklin
値法の概念を導入した方式 [FMY98] を提案している. 彼らの方式では, Boneh-Franklin 法に基づき$\mathrm{M}\mathrm{a}\mathrm{c}\mathrm{K}\mathrm{e}\mathrm{n}\mathrm{z}\mathrm{i}\mathrm{e}$$\uparrow \mathrm{g}$

,

を部分鍵

$d_{i}$$P_{i}$のディーラーとみなす. それぞれの機関は全ての乃からの$d_{j}$

に対する共有情報を合成することで, 最終的に秘密鍵う. これにより, 総数

$n$

$d$

に対する秘密分散を行個のうち任意 個の機関に$t$

よる RSA 秘密鍵 $d$ の鍵回復が可能である.

そのものを算出せRSA 公開鍵の素因数を誰も知らないため, 巾部分での逆元を計算できないことが原因である. つまりはLagrange の補間係数を計算できず, 合成すれば平文を復元できるような部分出力を求めることが不可能となっている.

そこで本稿では$n$個のうち任意 個による鍵回$t$復に加え, 分散復号を可能とするような手法を検討する. そのアプローチとして, 以下二つを考える.
–

つは秘密分散において,$d$に関する $(t, t)$ 型の秘密分散を複数行い, 組み合わせに応じた部分鍵を用いる方法である. これは文献 [BF97] で記されていた $(2, 2)$ 型から $(2, n)$ 型の秘密分散を構築する手法を $-$ 般化する試みである.

$(3, 3)$ 型から $(3, 3^{2})$型を構成する手法は, Blackburnいる.

$\cdot$Burmester .

. Wild [BBDW96] によって提案されてしかし, 同方法では $t=3$ における $n>3^{2}$ の場合と $t\geq 4$ である場合には適用することができな$\#arrow\sim \text{関}$得られる $(n, n)$ 型の秘密分散において, 各機関$d$

ずに暗号文を復元することができない. これは,$\mathrm{D}\mathrm{e}\mathrm{S}\mathrm{m}\mathrm{e}\mathrm{d}\mathrm{t}$この方法に閾値法の概念を導入して, 同じ機能

この方式では秘密鍵

い.

もう $-$ つは文献 [FMY98] の手法で$\mathrm{f}t,$

$n$

) 型の

秘密分散を行うが, 公開鍵の選出を工夫し復号時にユークリッドアルゴリズムを応用する方法である.
前者については, 機関の組み合わせによっては t

個でも復号を行うことができないという問題がある.

ただし, 予め暗号文への入力を表として保管できるため, 補間係数の計算を有する Lagrange 法よりも処理効率が良いという特徴がある. 後者については, 公開指数の選び方に制約がつくが,

どんな組

157

み合わせでも確実に復号処理が行えるという特徴を散することを考える. ここで,持つ.

る.
$d_{1,1}$

2$[0, n]$Boneh-Franklin 法 [BF97]に基づく $(t, n)$ 型の鍵生成・共有方式を提案している.

彼らの方式では, まず $(n, n)$ 型の鍵生成を行

い,

秘密鍵

れから,
て,

$d$

に対する和の多項式を生成する.

各機関乃が部分鍵$d_{j}$-Poly の変換を行い, 結果, 秘密鍵の機関は秘密鍵$d$

そのディーラーとなっ$\mathrm{s}_{\mathrm{u}\mathrm{m}-}\mathrm{t}\mathrm{o}$$(t, n)$ 型の秘密共有を行う.

$\lceil \mathrm{l}\circ \mathrm{g}n\rceil$

まず, ユーザは $d=d_{0,0}+d_{0,1}$

...

$=$

$=$

これにより, 任意の

$d$

の

$t$

個

を算出することができる.

とし,

$z$

を満たす $(2, 2)$ 型の$d_{r,0}+d_{r,1}$

$z$

$\in$

の 2 進表示 $z(2)=\beta_{r}\beta_{\gamma-}1\cdots\beta 0$ とする. ユーザは報:とす$d_{1,0}+$$=$

秘密分散多項式を独立に $r+1$ 個作成する.

分散復号における問題点
文献 [FMY98] では,

$r=$

$z$

番目の機関に,$\mathrm{f}^{d_{r,\beta_{\gamma}},d_{\gamma-1,\beta}\ldots,d}r-1$$0,\beta 0$)$r+1$ 個の部分情} を送る.

機関の番号を唯 $-$ に設定することで, 任意の二つ
の機関

$i,$

$j(i\neq j)$ はその異なるビッ

秘密分散から4$d$

トでの $(2, 2)$ 型を復元することができる.

型閾値法への拡張$(\mathrm{t},\mathrm{n})$$H$

しかし, 秘密鍵$d$$d$そのものを算出せずに, 秘密鍵

4.1を用いた署名や復号を行う場合において, 同方式

では問題が生じる. 今, 公開鍵 $(e, N)$ で暗号化された暗号文 $C=M^{e}$ (mod $N$ ) がある. この暗号文 $C$
を任意の

$t$

個の機関 1 で復号する場合, 各機関

以下のような Lagrange の補間係数$\lambda_{j,\Lambda}$$P_{j}$

は必要がある.
$\prod$$\frac{l}{l-j}$の手法を用いて,$n$個の機関で RSA 暗号の秘密鍵. 公開鍵 $(e, N)$ を分散生成する. 各機関

部分情報$d_{j}$

を保持し,$d_{j}$

が行うことで, 秘密鍵$j$

は $d$ ののディーラーとなってこの操作を全ての機関に対する $(t, n)$ 型の秘密共有を実現する.

ところが, どの機関も合成数 $N$ の素因数を知らないを法とした $l-j$ の乗法逆元を計算することができない.

$d$$(\mathrm{m}\mathrm{o}\mathrm{d} \phi(N))$$l\in\Lambda\backslash \{j\}$$\phi(N)$に拡張する手法を示す. ここでは, まず文献 [BF97]$(t, n)$ 型の秘密分散を行う.

$\lambda_{j,\Lambda}=$ので,

3 節で示した Boneh-Franklin 法を $-$ 般的 $(t, n)$ 型

$d$

を計算する

型秘密分散

$(\mathrm{t},\mathrm{n})$つまり,Lagrange の補間係数を計算できないため, 以下のような分散復号を行うことできない.

以下に具体的プロトコルを示す.

Step 1: まず つの機関は [BF97] 方式を用いて,を生成す
RSA 公開鍵 $(e, N)$ と秘密鍵
$n$

$d$

ここで今,

る.

$n$

個の機関は $N$ の異なる二つ素因数と秘密鍵$d$

を $(n, n)$ 型で秘密共有している. 生成される秘密鍵$d$は$\prod_{j\epsilon\Lambda}C^{S_{j}}.\lambda \mathrm{j},\Lambda=^{c}d=M(\mathrm{m}\mathrm{o}\mathrm{d} N)$.

$d=d_{1}+d_{2}+\cdots d_{n}$そこで, 本稿では (1) Lagrange の補間多項式を用(2) 公開鍵に制約をいない $(t, n)$ 型押共有方式と,つけた Lagrange 補間法に基づく分散復号アルゴリ

ズムを示す.

の関係式を満たし, 各機関 $i(1\leq i\leq n)$ は$d_{i}$を保管している. 以下, 各機関$j$は$d_{i}$のディーラーとして機能する.

Step 2: 各ディーラー は乱数 $S_{j,k}(0\leq j\leq r,$ $0\leq$$t-2)$ を生成する. ここで,$i$3$(2,\mathrm{n})$

型閾値法

$l$

$[\mathrm{B}\mathrm{F}9‘ 7]$$\leq$$\lceil\log_{t}n\rceil$

Boneh と Franklin [BF97] は,

$r$

$=$

とする. また,$(2, 2)$ 型の秘密分

散から $(2, n)$ 型の秘密分散 ( $n\geq 3$ を効率的に構築する手法を示している (PP.237, footnote 参照)

そのアルゴリズムを以下に示す.
ここでは簡単のため, 秘密情報
ユーザがいて,このユーザか1 この集合を A とする

$d$

$d$

$S_{j,\iota}^{(}i)-\mathrm{J}$.

そのものを知るを $(2, n)$ 型で秘密分.

$=d_{i}- \sum_{01=}^{t-}2S_{j,\iota}$とする.

Step 3: 各ディーラ一 は以下のようにして機関$i$$T_{z}(1\leq z\leq n)$に情報を送る.

158

(a)

$z$

を

42

進数表示する.

$t$$n$$z=\beta_{r,z}tf+\beta\Gamma-1,ztr-1\beta+\cdots+0,z$

分散復号化の機関のうち, 任意の

$t$

つの機関

$T_{z}$(この集合

を A とする) はグループの公開鍵で暗号化された

簡単のため, 以下のように表記する.

(mod $N$ ) を以下のようにして分散

データ $C=M^{e}$

復号化する.
$z(t)=\beta_{r,z}\beta’-1,\chi\cdots\beta 0,z(\beta_{j,z}\in\{0, \ldots, t-1\})$

Step 1:(b) 機関$z$には,$(S_{\gamma\beta,,z}^{(i)},’ s^{(i}f-1,\beta r-1),z’\ldots,$を送信する.

Step 4: 各機関牲$1\leq z\leq n$$j\leq r$$j$$-..\text{ラー}$$i$か$(S_{r,\beta_{\mathrm{r},z}’ r\beta_{r-1,z}’\beta_{\text{。_{}z}}}^{(i)}s^{(},S^{(\dot{f}}i)\ldots,0,),)$$d_{j,k}$$k\in\{\beta_{f},z’\beta r-1,z’..\cdot.

を計算する.
, \beta_{0,z}.

である.

o-

\}$

,

$\llcorner$, 全ての $a,$ $b\in\Lambda(a\neq b)$$\beta_{i_{1}a}\neq\beta_{i,b}$であるようなける.

これを満たす$i$$i$$r+1$ 個の部分秘密情報

メンバーを入れ換えて Step 1 からやり直す.

Step 3: Step 2 で条件を満たす に対し, 各$d_{j,k}$との関係は以下のように桁に対応する部分鍵 $d_{i,k}(k=\beta_{i,z})$ を用

算する.

Step 4: 各機関からの部分出力 $X_{z}(z\in\Lambda)$ を合成することでメッセージを復元できる.
$\prod$$d_{0,0}+d_{0,\downarrow}+\cdots+d_{0,t-1}$$=$

はいて部分出力 $X_{z}=C^{d_{i,k}}$ (mod $N$ ) を計なっている.
$d$$T_{z}$$d_{j,k}$を保管する.

と部分秘密鍵を見つがない場合, この集

$i$

$d$

進

$(z(t)=\beta r_{l}z\beta f-1_{\}}z\ldots\beta 0,z).\cdot$に対し$t^{i}$

秘密鍵$t$

合による分散復号はできないものとし多少$\leq$$d_{j,k}= \sum_{i=1}S^{(},=S+s+\cdots+Stji)(1kj,kj,kj,k)(2)(t)$

各機関匹は,

を

である.

は, ディ

から, 以下のようにして

ただし,つの参加機関牲全ての識別番号

Step 2: $0\leq i\leq r$ に対$(1 \leq z\leq n)$

ら受信した

$t$

表示する

$g_{0,\beta}(i))\text{。},z$$=$$(M^{e})^{d+d}i,1:,2+\cdots+d_{i,t}$$=$$(M^{e})^{d}$

$=$

$M$

$(t^{0}\text{桁目})$$z\in\Lambda$$d_{1,0}+d_{1,1}+\cdots+d_{1,t-1}$

$=$

$=$

$d_{\Gamma,0+}d+\cdots+d_{r}r,1,\mathrm{r}-1$

例えば,$(t^{1}\text{桁目})$(tr 西目)$(3,27)$ 型秘密分散における機関 $z=20$の保管情報は以下の通りである.

5

拡張方式の問題点と比較

51

分散復号の処理不能性

文献$\log_{3}27=3$

$=$

$r$

(mod $N$ )$[\mathrm{P}\mathrm{e}\mathrm{d}9\mathrm{l}\mathrm{b}]$のうち任意の$t$で提案されている方式では,$n$

個

個の機関はグループの鍵で暗号化

20

$=$

$2\cross 3^{3}\cross 0+3^{2}+0\mathrm{x}3^{1}+2\cross 3^{0}$

された暗号文を復号することができる.

20(3)

$=$

0202 (3 進表示)

41 節に示した $(t, n)$ 型秘密分散への拡張法では, 選ばれた; って, 機関 20 は

$t$

しかし,

つの機関が分散復号できない場合がある.

$\Delta$$d$$(3, 27)$ 型の秘密分散を例にこれを示す.

$=$$\underline{d_{3,0}}+d_{3},1+d_{3,2}(3^{3}\mathrm{f}\mathrm{f}\mathrm{i})$$=$$d_{2,0}+d_{2},1.+\underline{d_{2,2}}(3^{2}7|\overline{\mathrm{T}})$$=$$\underline{d_{1,0}}+d_{1,1}+d_{1_{1}}2(3^{1}\hslash_{\vec{\mathrm{T}}})$$=$$d0,0+d0,1+\underline{d_{0,2}}(3^{0}h_{\overline{\mathrm{T}})}$

鍵

$d$

今, 秘密

について, 以下の $r+1$ 個の関係式が成り立って

いる.
$d$

$=$

$d_{3,0}+d_{3},1+d_{3,2}(3^{3}\hslash\hat{\mathrm{T}})$$=$$d_{2,0+}d_{2,1}+d_{2,2}(3^{2}\hslash’\overline{T})$$=$$d_{1,0}+d_{1},1+d_{1,2}(3^{1}\mathrm{f}\mathrm{f}\mathrm{i})$$=$$d_{0,0}+d_{0,1}+d_{0,2}(3^{0}\mathrm{f}\mathrm{f}\mathrm{i}^{arrow})$.
$(d_{3},0, d_{2,2}, d1,0, d_{0},2)$

る.

を

$d$

の部分鍵として保管す159

まず分散復号が可能な場合を示す. 27 つの機関のうち, 機関,がプロトコルに介入する時,$P_{20},$ $P_{23}$$P_{26}$により分散復号を行うという形である.
$n$.

が大きく, 閾値 以上の機関を比較的自由に選$t$択できるのであれば,,$P_{23}=0212$,

41 節の $(t, n)$ 型の秘密分散を行うことが考えられる. そこで復号不能状態の場合
行$P_{20}=0202$$n$が大きくなるほど必要な関係式の数は膨大になる.

復号操作 $C^{d}=M^{ed}=M$ は成功する. 今, 各機関の 3 進表示はしかし,$P_{26}=0222$$\mathrm{Y}$

は異なる

$t$

つの機関を再編成する. 再編成というよりも復元可能なグループで復号プロトコルを開始する形である.

であり, それぞれの保管情報は以下の通りである.

逆に

$n$

の数が小さく機関の選択余地がない場合

は, 全ての組み合わせに応じた関係式を作成する方

どちらの手法を取るかは, 使用する環境にもよりそうである. 復号プロセスに加わるこが適している.

$\ovalbox{\tt\small REJECT}_{3^{0}7\tau}^{d,d}3^{1}3^{2}3^{3}7\hslash\overline{\tau}_{\text{目}d_{0}’}\text{目}d_{1}|\overline{\mathrm{T}}\text{目}d_{3}\text{桁目}4arrow 2,20d3,00d_{1,1}2d0,2dd_{3,0}22d_{2,2}d_{1,2}0,2$とが大きな意味を持っており, 募ったメンバーによこの場合,$3^{1}$

る絶対の処理成功が要求されている環境には 41 節

桁に注目すると,の $(t, n)$ -sharing は向かない.

編成が比較的容易く, 様々な機関による代理が期待$d=d_{1,0}+d_{1},1+d_{1},2$

できそうな環境なら, あえて
から,

$d$

による復号化処理が可能となる.

$cd_{1,\mathrm{O}}cd_{1,1}cd\iota,2=M^{ed}=M$

ところが,$P_{20},$ $P_{2}3,$ $P_{11}$,${}_{n}C_{t}$つの独立関係式を用意する必要はないであろう. メンバーの数や処理の効率, 使用される環境に応じた使い分けを行うことができる.

(mod $N$ )の三つの機関では分散復52号を行うことができない. 各機関の 3 進表示は
凸 0 $=0202$

逆に復号メンバーの$P_{23}=0212$,

補間法に基づく方式との比較

Lagrange の補間法に基づく閾値法を用いた分散$P_{11}=0102$

復号化では, 秘密鍵が各機関の持つ部分鍵の単純和ではない. そこで各機関で選ばれた集合に対すであり, 各機関の保管情報は以下のようになる.

る Lagrange の補間係数を計算し合成する必要がある.

これを事前に計算して表として保管する場合,$-$ つの部分鍵情報と協力する機関の全ての組み合わせに応じた $\text{個の補間係数が必要であ_{る}}$方,41 節での $(t, n)$ 型秘密分散法は,.
$\log_{t}n+$個から機関の組み合わせに対応する部分鍵を選ぶだけである. よって保存情報としては $\log_{t}n+1$ 個

$1$

この場合,

$d$

を構成する 3 つの成分 $(d_{j},0, d_{j,1}, d_{j,2})$がどの桁を見ても揃わない. このように保管情報のである.

復号処理不能が許されない場では, 補間法に基づ衝突により, 復号操作の出来ない場合が考えられく閾値法が使用を余儀無くされるだろう. ただし,る.

このように衝突が生じる場合, その

$t$

つの機関で

は分散復号処理を行えないため, 別の

$t$

つの機関を

選び直す必要がある.
ように任意の$t$Pedersen 方式$[\mathrm{P}\mathrm{e}\mathrm{d}9\mathrm{l}\mathrm{b}]$には, 最悪, 秘密鍵に関する${}_{n}C_{t}$個の機関を比較的自由に選べ, また効率の良い処理が要求される場では 41 の方式が有効である.

のつの機関で分散復号・鍵復元が行う
$d$

$t$

個の独立な関係

6

ユークリッドアルゴリズムを用いた分散復号化

式を作れば良い. つまり, ある組み合わせ (A とする) の時は該当する関係式:$d=d_{1,\Lambda}+d_{2,\mathrm{A}}+\cdots+d_{t,\Lambda}$

ユークリッドアルゴリズムを用いた分散復号化法を提案する. 今, Non-Dealer
る Frankel$\cdot \mathrm{M}\mathrm{a}\mathrm{c}\kappa \mathrm{e}\mathrm{n}\mathrm{z}\mathrm{i}\mathrm{e}$

モデルにおけ. Yung の秘密分散共有

160[FMY98] を用いて,

法$n$個の機関乃が RSA 暗号化鍵 $(e, N)$ を生成かつ秘密鍵$d$

を $(t, n)$ 型の秘密分散共有を行っている. ここで, $t-1$ 個の乱数
$a_{1},$$a_{t-1}\in Z$$\ldots,$7

他方式との比較

7.1

各機関$\mathcal{P}_{j}$$q_{2}+\cdots$$=$$d+a_{1}x+a_{2}x^{2}+\cdots+a_{t-1^{X^{t1}}}-$

は,$N=pq=(p_{1}+p_{2}+\cdots+p_{n})(q_{1}+$+q のを満たす$(p_{j}, q_{j})$$n$と $s_{j}=f(j)$ を分散個の機関で成る組織の鍵で暗号$t$を A) に暗号文 $C$ を分散復号してもらう.
$\mathrm{g}\mathrm{c}\mathrm{d}(e, L^{2})=1$とする.

Step 2: 各機関乃は, 部分鍵勺を用いて部分
を計算し,
出力
に送る.
$\mathcal{U}$$Z_{j}$

ら,

は次のようにして変

$n!$

.

とする)

$H$

を満たす

$=$

$d$

を生成する

$\mathrm{g}\mathrm{c}\mathrm{d}(e, L2)$$(P,\tilde{s})$として,を計算する. それか$d\equiv P+L^{2}k(\mathrm{m}\mathrm{o}\mathrm{d} \phi(N))$

を満たす$k\equiv d\tilde{s}H^{-1}(\mathrm{m}\mathrm{o}\mathrm{d} \phi(N))$

を計算

$k$

である.

ここで $f(\mathrm{O})=L^{2}k$ であるような関数 $f(x)$ を以下の$f(x)=f0+f1x+f2x^{2}+.$ . . $+f_{t-1}xt-1$

は $C$ を各機関乃 $(\in\Lambda)$ に送る.

$\mathcal{U}$( $L=$

Dealerように定める.

ここで,分散復号化プロ トコル :Step 1:$\text{方}$個の機関に秘密を分散預

公開鍵 $(e, N)$ と秘密鍵する. ただし,は以下のようにして, 任意 個の機関 (この集合$L=n!$ かつ

RSA

形

$n$

まず

$eP+ \frac{L^{2}}{H}\tilde{s}=1$化された暗号文 $C=M^{e}$ (mod $N$ ) を持っている.
$\mathcal{U}$を閾値として託する際,

秘密情報として保管している.
今, ユーザ U は

-Yung

式

に対し, 以下の多項式を定める.
$t$$f(x)$$\mathrm{F}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\mathrm{e}\mathrm{l}- \mathrm{G}\mathrm{e}\mathrm{m}\mathrm{m}\mathrm{e}\mathrm{l}\mathrm{l}- \mathrm{M}\mathrm{a}\mathrm{C}\kappa \mathrm{e}\mathrm{n}\mathrm{z}\mathrm{i}\mathrm{e}$ただし,$f_{j}\in_{R}\{0, L, \ldots, 2L^{32+\epsilon}nt\}(1\leq i\leq t-1)$とする.

ディーラーは勺 $=f(j)$ を計算し,

を各機関

$j$

と

$P$

$s_{j}$に送信する.

ディーラーによる分散共有が完了した状況で, 複数の機関による分散復号プロトコルを考える. 今,
依頼人 $X$ は, ディーラーの公開鍵 $(e, N)$ で暗号化$\lambda_{j,\Lambda}$$=$$\sigma_{j}$$=$$Z_{j}$$=$

されたメッセージ$\prod_{l\in \mathrm{A}\backslash \{j\}}\frac{l}{l-j}$$s_{j}$.

$C^{\sigma_{\mathrm{j}}}$:(mod $N$ )$C=M^{e}$$L^{2}\cdot\lambda_{j,\lambda}$を持っている.

(mod $N$ )は複数の機関に暗号文 $C$ を入力$X$として与え, メッセージ $M$ を入手したい.

Step 3:$\mathcal{U}l3:t$

し,個の乃からの部分出力を合成$M^{L^{2}}$

(mod

$N$

(mod $N$ )$j\in\Lambda$

Step 4:は異なる二つの暗号文 $(c_{1}, c_{2})$$\mathcal{U}$$(M^{L^{2}}, M^{e})$

$M$

ここで

個の機関 (この集合を A) が処理に参加す

るものとする.

) を求める.

$\prod Z_{j}=(M^{e})^{L^{2}}\sum j\mathrm{e}\Lambda(Sj\lambda_{\mathrm{j},\mathrm{A}})=M^{L^{2}}$

任意の

$t$

$j$

に送信

する.

Step 2: 各機関 は を用いて. め, 以下を計算する.
$j$

$=$

から, 以下のようにしてを算出する.

Step 1: $X$ は $C$ を処理に関係する各機関$Z_{j}=C^{\sigma_{\mathrm{j}}}$$s_{j}$(mod $N$ ) ,$\sigma_{j}=s_{j}\lambda_{j,\mathrm{A}}$$\lambda_{j,\mathrm{A}}=$$\prod$を求$\frac{l}{l-j}$$\iota\epsilon\Lambda\backslash \{j\}$$[4\mathrm{a}]$:$a_{1}=(L^{2})^{-1}$$[4\mathrm{b}]$:$a_{2}=(a_{1}L^{2}-1)/e$:$M=c_{1}^{a_{1}}(C_{2}^{a}2)^{-1}$$[4\mathrm{c}]$(mod )$e$

機関月よを秘密吏に $X$ に送信する.

ずれかの機関は(mod $N$ )ここで, プロトコルの健全性を以下に示す.
$C_{1}^{a_{1}}(C_{2^{2}}a)-1=M^{L^{2}a_{1}-ea}2=M$$Z_{j}$(mod $N$ )

る

(誰でも

$(P,\tilde{s})$ので, 必ずしも

Step 3: $X$ は,$Z_{j}$$C^{P}$(mod $N$ ) を $X$ に送を計算することができるを送る必要はない\rangle .

$C^{P}$と $M^{P}$ (mod $N$ ) から,$C^{P+\sum_{j^{Sj}}\lambda_{j}}.\mathrm{A}$$C^{P} \prod Z_{j}$

い

$=$

$=$

$=$

$M^{ed}$$M(\mathrm{m}\mathrm{o}\mathrm{d} N)$

161を計算することで, メッセージ $M$ を復号する.

generation of shared $RSA$ keys,’) Advances in Cryptology CRYPTO ’97, LNCS 1294, pp. 425439, 1997.

[BF97] D. Boneh and M. Franklin,($‘ Effi_{C\dot{l}e}nt$–

RSA 暗号では署名と復号化操作が同じであるので,上記プロトコルにおいて依頼人が入力として文書 $M$を与えると, 出力として署名

72$M^{d}$[Des97] Y. Desmedt, “Some recent reserch aspectsof threshold cryptography,” Information Security, LNCS 1396, pp. 158-173, 1997.

が得られる.

比較Frankel-Gemmell-MacKenzie-Yung 方式も本提案方式も,$\alpha,$$\beta$を係数として以下のユークリッド公式を考えている.
$e\alpha+L^{2}\beta=1$

,

where

[DF89] Y. Desmedt and Y. Frankel, “Threshold cryptosystems,” Advances in Cryptology
CRYPTO ’89, LNCS 435, pp. 307-315, 1989.

-

Frankel, P. Gemmell, P. D.
and M. Yung, $‘ Optimal$-resilience
proactive public-key cryptosystems,” 38th Annual Symposium on Foundations of Computer
Science, pp. 384-393, 1997.

[FGMY97] Y.

$\mathrm{g}\mathrm{c}\mathrm{d}(e, L2)=1$($\mathrm{M}\mathrm{a}\mathrm{c}\mathrm{K}\mathrm{e}\mathrm{n}\mathrm{z}\mathrm{i}\mathrm{e}$ここで,Frankel らの方式では $(\alpha, \beta)=(P,\tilde{s}/H)$ ,本提案方式では $(\alpha, \beta)=(-a_{2}, a_{1})$ としたものであFrankel らの方式では, ディーラーが鍵分散時

る.

にユークリッド公式を作成するので, 復号時には各機関からの部分出力を合成するだけでよい. 本提案
方式では復号時に部分出力を合成し, その出力からユークリッドアルゴリズムにより処理を行う分, 効率が悪い. しかし Frankel らの方式は $\phi(N)$ を知っているディ.- ラーの存在が前提である.

-方, 本提案方式ではディーラーの存在有無に関わらず, 秘密を分散共有している$n$個の機関うち,

$t$

個の任意の

機関で RSA 署名復号が可能である.

8

$-$

おわりに

本稿では, ディーラーのいない環境下での $(t, n)$型分散復号について検討した.

Lagrange 補間法を用いない手法では, 分散復号時に補間係数を計算する手間が省ける分だけ効率が良い. ただし, 保持情報の衝突による復元不能の問題がある. 豪悪
独立多項式を用意すれば衝突の可能性はないが, 独立多項式を最小限に抑える手法を検討する必要があろう. もはやディーラーの有無は関係なく,

$n$

羽の

うち任意 羽の鳥を異なる巣箱に入れるような関数$t$群を見つける問題でもある$([\mathrm{K}\mathrm{S}96])$.

[FMY98] Y. Frankel, P. D.
and M.
Yung, “Robust efficient distributed RSA-key
generation,” Proceedings of the thirtieth annual
ACM symposium on theory of computing, pp.
663-672, 1998.
$\mathrm{M}\mathrm{a}\mathrm{c}\mathrm{K}\mathrm{e}\mathrm{n}\mathrm{z}\mathrm{i}\mathrm{e}$[FY98] Y. Frankel and M. Yung, “Distmbuted public key cryptosystems, ’ (Invited Paper) Public
Key Cryptography, LNCS 1431, pp. 1-13, 1998.
$\rangle$[KS96] K. Kurosawa and D. Stinson, Personalcommunication, June 1996 (Referred in
Desmedt’s paper [Des97] .
$)$T. P. Pedersen, $‘ Distnbuted$ provers
with applications to undeniable signatures,” Advances in Cryptology –Eurocrypt ’91, LNCS
547, pp. 221-238, 1991.
($[\mathrm{P}\mathrm{e}\mathrm{d}9\mathrm{l}\mathrm{a}]$T. P. Pedersen, “A threshold cryptosystem without a trusted party,” Advances in
Eurocrypt ’91, LNCS 547, pp.
Cryptology
522-526, 1991.

$[\mathrm{P}\mathrm{e}\mathrm{d}9\mathrm{l}\mathrm{b}]$

–

参考文献

[Sha79] A. Shamir, “How to share asecret,” Communication ACM, 22, pp. 612-613, 1979.

[BBDW96] S. R. Blackburn, M. Burmester, Y.
Desmedt and P. R. Wild, “Efficient multiplicative sharing schemes,” Advances in Cryptology-EUROCRYPT ’96, pp. 107-118, 1996.

[Sim83] G. J. Simmons, “A ‘weak’ privacy protocol using the RSA cryptoalgorithm,” Cryptolo, vol. 7, pp. 180-182, 1983.
$\mathrm{g}\mathrm{i}\mathrm{a}$