JPH08204697A - 複数の装置を有する通信システムにおける署名生成方法 - Google Patents

Abstract

(57)【要約】 【目的】 実用的な計算量と通信量とで分散して署名の
生成を可能とする。 【構成】 複数の装置が、個別の装置間で他の装置には
秘密に情報の通信を行なうための秘密通信路と、各装置
から他の全ての装置へ共通に情報を送信するための放送
通信路とを介して接続された通信システムにおいて、署
名者グループ内の各装置が、第１の秘密情報をランダム
に選び、前記グループ内の各装置に秘密に分散させ、各
装置が、前記第１の秘密情報に所定の第１の関数を作用
させ、得られた出力値を前記グループ内の全装置に放送
し、各装置の前記第１の秘密情報を分散加算し、各装置
の前記出力値を分散乗算し、当該乗算の結果とメッセー
ジとを所定の第２の関数で処理し、該処理結果と、前記
分散加算の結果と、公開された元とを用いて第２の秘密
情報を分散演算し、分散された第２の秘密情報を復元
し、前記分散乗算結果と共に署名として出力することを
特徴とする。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、通信路によって接続さ
れた複数の加入者の内の何人かの加入者によるグループ
におけるディジタル署名を、そのグループに参加する加
入者間で分散生成する方式に関するものである。

【０００２】

【従来の技術】通信路によって接続された複数の情報処
理装置を含む情報通信システムにおいて、送信された情
報が指定された受信装置以外に漏れないこと（情報の秘
匿）を保証するために役立つ技術の一つとして、暗号技
術が知られている（池野、小山：”現代暗号理論”、p
p. 224-225 、電子情報通信学会）。

【０００３】暗号技術は、上述した情報の秘匿機能の他
に、その通信システムにおいて受け取った情報が、指示
された装置から発信されたこと（途中で改竄されなかっ
たこと）を確認できる認証機能、及びその受け取った情
報が指示された装置から発信されたことを第三者にも証
明できるディジタル署名と呼ばれる機能を実現するため
に有効であることもよく知られている。

【０００４】特に、公開鍵暗号方式の１つであるＲＳＡ
暗号を用いた認証及びディジタル署名方式は広く用いら
れている（例えば、R. Rivest, A. Shamir, L. Adlema
n, "AMethod for Obtaining Digital Signatures and P
ublic-Key Cryptosystems",Communications of the AC
M, 21, 2, 1978, pp. 120-126. または米国特許4,405,8
28 号参照）。

【０００５】また、ＲＳＡ暗号以外の公開鍵暗号方式に
よるディジタル署名方式の１つとして、A. Fiat, A. Sh
amirによって提案された方式がよく知られている（"How
toProve Yourself: Practical Solutions to Identifi
cation and Signature Problems", Advances in Crypto
logy ーCrypto'87, Lecture Notes in Computer Scienc
e, 263, Springer-Verlag, 1988, pp. 186-194. また
は米国特許 4,748,668号参照）。この方式では、安全な
識別及び与えられたメッセージのディジタル署名を実現
するために次の処理を行う。

【０００６】(1) 与えられたメッセージのディジタル署
名を計算する装置、あるいは通信システムにおいて信頼
できるセンタの役割を果たす装置が、1,・・・,N-1 （但し
N は２つの素数p,q の積である）の内から元a をランダ
ムに選び、署名を計算する装置の秘密情報とする。

【０００７】(2) その秘密a を選んだ装置は、a^l mod N
（但し、l はgcd(l,lambda(N))=1を満たし、ここで、la
mbda(N)=lcm(p-1,q-1)、gcd(a,b)はa,b の最大公約数、
lcm(a,b)はa,b の最小公倍数を意味する）を計算し、そ
の装置によって生成されたディジタル署名を確認するた
めの公開情報とする。

【０００８】(3) その装置によって与えられたメッセー
ジm のディジタル署名の生成処理において、｛1,・・・,N-
1 ｝の内からランダムに選ばれた秘密の元r を用いて計
算されたR=r^l mod N と、与えられた公開のメッセージ
m を連続させた値R|m を入力として所定の関数h を用い
てe=h(R|m)を計算する。それらを入力としてs=r*a^e(mo
d N) の計算を実行することによって得られた出力s 及
びR を、与えられたメッセージのディジタル署名とす
る。

【０００９】(4) ある与えられたメッセージm に対する
ディジタル署名(s,R) を確認するためには、s^l mod N
とR*(a^l)^(h(R|m)) mod Nの計算を実行し、それらの結
果が等しいことを確認する。

【００１０】また、C.P.Schnorr によって提案された安
全な識別及び与えられたメッセージのディジタル署名を
実現する方式（"Efficient Identification and Signat
uresfor Smart Cards", Advances in Cryptology ーCry
pto'89, Lecture Notes inComputer Science, 435, Spr
inger-Verlag, 1990, pp. 239-252. または米国特許4,
995,082 号参照）は、次の処理を行う。

【００１１】(1) 与えられたメッセージのディジタル署
名を計算する装置、あるいは通信システムにおいて信頼
できるセンタの役割を果たす装置は｛1,・・・,p ｝（但し
p は素数である）の内から元a をランダムに選び、署名
を計算する装置の秘密情報とする。

【００１２】(2) その秘密a を選んだ装置は、g^-a mod
q （但し、q はp がq-1 の除数になるような素数であ
り、有限体 GF(q)に属する元g の位数がp となる）を計
算し、その装置によって生成されたディジタル署名を確
認するための公開情報とする。

【００１３】(3) その装置によって与えられたメッセー
ジm のディジタル署名の生成処理において、｛1,・・・,p
｝の内からランダムに選ばれた秘密の元r を用いて計
算された R=g^r mod q と、与えられた公開のメッセージ
m を連続させた値R|m を入力として所定の関数h を用い
てe=h(R|m)を計算する。それらを入力としてs=r+a*e (m
od p) の計算を実行することによって得られた出力s 及
びR を、与えられたメッセージのディジタル署名とす
る。

【００１４】(4) ある与えられたメッセージm に対する
ディジタル署名(s,R) を確認するためには、h(g^s((g^
(-a))^(h(R|m))) (mod q)|m)R|m))の計算（但しx^y はx
^yを表す）を実行し、この結果とe とが等しいことを確
認する。

【００１５】また、T. ElGamalによって提案された安全
な識別及び与えられたメッセージのディジタル署名を実
現する方式（"A Public-Key Cryptosystem and a Signa
tureScheme Based on Discrete Logarithms", IEEE Tra
nsactions on InformationTheory, IT-31, 4, 1985, p
p. 469-472. American National Standard X9.30-199x,
Digital Signature Algorithm, Feb. 1992参照）は、
次の処理を行う。

【００１６】(1) 与えられたメッセージのディジタル署
名を計算する装置、あるいは通信システムにおいて信頼
できるセンタの役割を果たす装置、は｛1,・・・,p ｝（但
しpは素数である）の内から元a をランダムに選び、署
名を計算する装置の秘密情報とする。

【００１７】(2) その秘密a を選んだ装置は、g^(-a) m
od q（但し、q はp がq-1 の除数になるような素数であ
り、 GF(q)に属する元g の位数がp となる）を計算し、
その装置によって生成されたディジタル署名を確認する
ための公開情報とする。

【００１８】(3) その装置によって与えられたメッセー
ジm のディジタル署名の生成処理において、｛1,・・・,p
｝の内からランダムに選ばれた秘密の元r を用いて計
算された R=g^r mod q と、所定の関数h を用いて与えら
れた公開のメッセージm を入力として得られた値e=h(m)
とを入力として、s=(e+R*a)*r^-1 mod p の計算を実行す
ることによって得られた出力s 、及びR を与えられたメ
ッセージのディジタル署名とする。

【００１９】(4) ある与えられたメッセージm に対する
ディジタル署名(s,R) を確認するためには、(g^(-a))^R
(g^r)^s とg^m (mod q) の計算を実行し、それらの結果
が等しいことを確認する。

【００２０】一方、前述のように守秘及び認証を実現す
る情報通信システムにおいて、秘密情報を守りながら信
頼性を高める手段として、秘密情報を分散し、与えられ
たメッセージのディジタル署名の計算を通信路によって
接続された複数の計算装置（以下、署名者グループとい
い、そのグループに参加する各計算装置を加入者とい
う、またそのグループに参加する加入者の数をn で表
す）の間で分散する方法がY. Desmedt,Y. Frankelによ
って提案されている（"Threshold Cryptosystems",Adva
nces in CryptologyーCrypto'89, 435, Springer-Verla
g, 1990, pp. 307-315; "Shared Generation of Authen
ticators and Signatures", Advances in Cryptologyー
Crypto'91, 576, Springer-Verlag, 1992, pp. 457-469
参照）。

【００２１】この分散ディジタル署名方式の基本的な部
分は、複数の加入者からなる通信システムにおいて秘密
情報を分散する方式である。具体的に、ある秘密情報x
が複数の加入者間で分散保持されるとは、以下の条件
(a), (b)が満たされるように各加入者i が秘密情報x に
対応する部分情報x_i を生成し、他の加入者に分配する
ことを意味する。

【００２２】(a) 秘密情報x を復元するためにt+1 人の
加入者の部分情報が必要である。以後、その秘密情報を
復元するための必要な加入者の数t+1 をしきい値と呼
ぶ。

【００２３】(b) しきい値未満の数（t 以下）の部分情
報ではその秘密情報に関するどのような情報も得ること
ができない。

【００２４】従来の基本的な秘密分散方式は、A. Shami
r によって提案され"How to Sharea Secret", Communic
ations of the ACM,Vol. 22, 11, 1979参照 )、次のよ
うに実現された。すなわち、ある加入者の情報を秘密に
複数の加入者に分散するために、定数項が前述の秘密情
報となるｔ次の多項式f(x)をランダムに選び、n 個の異
なる値に対するその多項式の値f(i)(i=1,・・・,n) を各加
入者に配る。この加入者i に配られる多項式の値f(i)が
前述の部分情報の一部分になる。よって、秘密情報はt+
1 個の部分情報を用いた多項式補間によって復元できる
（t 以下の部分情報では秘密情報に関するどのような情
報を得ることはできない）。

【００２５】前述のY. Desmedt, Y. Frankelによる秘密
分散方式に基づくＲＳＡ暗号を用いた分散型ディジタル
署名方式は以下の条件(I),(II)を満たす。

【００２６】(I) 署名者グループに対する与えられたメ
ッセージのディジタル署名を生成するためにt+1 人の加
入者の協力があれば十分である。

【００２７】(II)しきい値未満の数（t 以下）の加入者
では与えられたメッセージのディジタル署名を生成でき
ない。

【００２８】但し、(I),(II)の条件だけではディジタル
署名生成処理が分散されたとき、t+1 以上の加入者が協
力しても不正な加入者があった場合には、署名を生成で
きないことがありうる。

【００２９】それに対して、どのような誤りを持つ加入
者に対してもディジタル署名を生成できるような方式
は、確認可能な秘密分散方式に基づいて構成できること
が知られている。どのような誤りを持つ加入者にも耐え
られる秘密分散方式として提案された確認可能な秘密分
散（Verifiable Secret Sharing ）とは、前述の条件
(a), (b)に次の条件(c),(d) を付加することによって定
義される。

【００３０】(c) 不正な部分情報と正しい部分情報とが
混在していても、t+1 個の正しい部分情報があれば元の
秘密情報を復元するために十分である。

【００３１】(d) 全ての加入者がその秘密の部分情報を
受け取ったとき、その部分情報がある秘密情報x を復元
するために正しい情報であるかどうかを確認できる。

【００３２】前述の条件(c),(d) を満たす確認可能な秘
密分散方式に基づいて、次の条件を満たす分散ディジタ
ル署名方式を構成できる。

【００３３】(I')不正な加入者が正しい加入者と混在し
ていても与えられたメッセージのディジタル署名を生成
するためにt+1 人の正しい加入者の協力があれば十分で
ある。

【００３４】(II)しきい値未満の数（t 以下）の加入者
では与えられたメッセージのディジタル署名を生成でき
ない。

【００３５】秘密の通信路を持つ通信システムに対し
て、全加入者の３分の１より少ない数であればどのよう
な誤りを持つ加入者にも耐えられる確認可能な秘密分散
方式（しきい値ｔがｔ＜ｎ／３を満たす場合）を構成す
るためには、従来の誤り訂正符号技術で十分であること
が、M. Ben-Or, S. Goldwasser, A. Wigdersonによって
示されている ("Completeness Theorems for Non-Crypt
ographic Fault-Tolerant Distributed Computation",
ACM STOC 1988 参照。）。

【００３６】更に、全加入者の半分より少ない数であれ
ば、どのような誤りを持つ加入者にも耐えられる確認可
能な秘密分散方式を構成するためには、条件を更に追加
する必要があり、全ての加入者が同じメッセージを受信
したことを確認できる放送型通信路を、全ての加入者が
持つとした場合、次の２通りの構成方法が知られてい
る。

【００３７】(1) 零知識対話証明システム（辻井、笠
原：”暗号と情報セキュリティ”、昭晃堂、1990年、参
照）で用いられている`Cut and Choose'と呼ばれる技術
を利用し、前述のA.Shamirによる基本的な秘密分散方式
によって元の秘密s を分散した上に、配られた部分情報
s_i （i=1,・・・,n ）を更に分散する方式。つまり、確認
可能な分散方式によって配られた全ての部分情報は、秘
密部分s_i に対する秘密部分になるように生成された部
分行列と考えることができる。

【００３８】但し、前述の`Cut and Choose'技術を用い
ることで、前述の条件(d) による確認とは統計的確認に
なり、秘密情報を復元できる正しい分散が行われている
かどうかを示す判定出力に誤り確率が生じる。但し、そ
の誤り確率は設定する安全性のパラメータにより無視で
きる程度まで小さくすることができる。具体例として、
T. Rabin, M. Ben-Or による方式("Verifiable Secret
Sharing and Multiparty Protocols with Honest Major
ity", ACM STOC 1989 参照があげられる。

【００３９】(2) 非対話型で特殊な代数学的な性質を持
つ一方向性関数を利用する方法。但し、このように構成
された秘密分散方式の安全性は、その代数学的な性質を
満たす一方向性関数の逆元を計算するのが困難である
（実用的な逆元計算方式が存在しない）という暗号的な
仮定をする必要が生じる。具体例は、P. Feldmanによっ
て提案された ("A Practical Scheme for Non-Interact
ive Verifiable SecretSharing", IEEE FOCS, 1987 参
照。

【００４０】また、上述の確認可能な秘密分散方式を利
用することによって、ディジタル署名の分散生成処理を
含めた、ある与えられた有限体上の分散演算を安全に実
現する回路を構成できることが T. Rabin, M. Ben-Or
("Verifiable Secret Sharingand Multiparty Protoco
ls with Honest Majority", ACM STOC, 1989 参照）、
D. Beaver ("Secure Multiparty Protocols and Zero-K
nowledge Proof SystemsTolerating a Faulty Minorit
y", Journal of Cryptology, 1991, 4, pp. 75-122; "E
fficient Multiparty Protocols Using Circuit Random
ization", Advances in Cryptology-Crypto'91, 1992参
照) 及び M. Franklin, S. Haber ("JointEncryption a
nd Message-Efficient Secure Computation", Advances
in Cryptology-Crypto'93, 1994 参照) によって示さ
れている。

【００４１】このような確認可能な秘密分散方式を用い
た分散演算回路によって、前述のような種々のディジタ
ル署名方式に対する分散生成処理システムも構成できる
ことが知られている。

【００４２】

【発明が解決しようとしている課題】上述の条件(I),(I
I)を満たす分散ディジタル署名方式に必要な通信量及び
計算量は実用的であることが知られている。しかし、前
述したように署名の分散生成処理に参加する加入者が不
正を行った場合に署名の生成ができないことが有り得
る。

【００４３】それに対して、上述の確認可能な秘密分散
方式及び分散演算回路を利用する条件(I'),(II) を満た
す分散ディジタル署名方式は、以下のように非実用的な
通信量または計算量が必要であることが知られている。
例えば、対話型確認可能な秘密分散方式(1) において1
ビットを分散するために必要な通信量は、安全性のパラ
メータをk （通常は１００程度の値が用いられる）と表
したときn 個の秘密部分に対してn^3k^2のオーダーとな
ることが知られており、効率的ではない。

【００４４】また、一方向性関数を用い、通信量の少な
い非対話型確認可能な秘密分散方式(2) は、n 個の秘密
部分に対してn 回のオーダーの特殊な一方向性関数の計
算処理を行う必要があり、特に秘密分散処理を安全に分
散計算を実行するための部分処理として用いる場合に
は、実行すべき秘密分散処理の数が多くなり（例えば、
分散乗算においてはn²のオーダーとなる）、全体的に非
実用的な計算量になる。

【００４５】以上のように、上述の従来技術による対話
型確認可能な秘密分散方式(1) に基づいた分散ディジタ
ル署名は通信量が非常に大きく、非対話型確認可能な秘
密分散方式(2) に基づいた分散ディジタル署名は計算量
が非常に大きいという問題があった。

【００４６】本発明は、前述の対話的な方式(1) 及び非
対話的な方式(2) の中間に位置し、必要な計算量と通信
量の両方が実用的なオーダーになる確認可能な秘密分散
方式を利用し、条件(I) 、（不正を行う加入者があれば
署名を生成できないことが有り得る方式）及び条件(I')
（あるしきい値以下の不正を行う加入者の数があっても
署名を生成できる方式）の中間に位置する分散ディジタ
ル署名方式（あるしきい値以下の不正を行う加入者の数
があった場合、署名を生成できないことが有り得るが、
不正を行った加入者は識別できる方式）を提案する。

【００４７】

【課題を解決するための手段】上述の課題を解決するた
めに、本発明の署名生成方法は、複数の装置が、個別の
装置間で他の装置には秘密に情報の通信を行なうための
秘密通信路と、各装置から他の全ての装置へ共通に情報
を送信するための放送通信路とを介して接続された通信
システムにおいて、署名者グループ内の各装置が、第１
の秘密情報をランダムに選び、前記グループ内の各装置
に秘密に分散させ、各装置が、前記第１の秘密情報に所
定の第１の関数を作用させ、得られた出力値を前記グル
ープ内の全装置に放送し、各装置の前記第１の秘密情報
を分散加算し、各装置の前記出力値を分散乗算し、当該
乗算の結果とメッセージとを所定の第２の関数で処理
し、該処理結果と、前記分散加算の結果と、公開された
元とを用いて第２の秘密情報を分散演算し、分散された
第２の秘密情報を復元し、前記分散乗算結果と共に署名
として出力することを特徴とする。

【００４８】

【実施例】以下、図面を参照して本発明の実施例を詳細
に説明する。

【００４９】本実施例では、各加入者が、他の個々の加
入者にメッセージを秘密に送ることができる秘密通信路
と、全ての加入者が同じメッセージを受けたことを確認
できる放送型通信路とによって接続される分散システム
において、図３に示すように、後述する秘密部分行列を
生成し、その秘密の部分情報を分配すると同時に、後述
する部分情報の認証子として用いられる一方向性ハッシ
ュ値（但し、特殊な代数学的な性質を持つ必要はない）
を放送し、後述するCut and Choose処理を行う秘密分散
方式を用いて、署名者グループに参加する各加入者によ
ってランダムに選ばれた秘密の元をそのグループの全て
の加入者間で分散し、正しく分散されたランダムな秘密
の分散演算処理を実行することを特徴する。

【００５０】まず、本実施例で利用する技術及び用語の
いくつかについて説明する。

【００５１】図４は、秘密s と部分行列S との関係を示
す図である。

【００５２】本実施例において、ある秘密s に対する部
分行列S とは、従来の対話型確認可能な秘密分散方式に
用いられている部分行列に、以下に説明するように、更
に条件が付けられた秘密部分のn ×n 行列S=〔s(i,j)〕
(i,j=1,・・・,n）である。

【００５３】すなわち、各行ベクトル（S_r(i)=〔s(i,
1),・・・,s(i,n)〕,i=1,・・・,n）が、ある秘密s_r(i)に対
する秘密部分ベクトル（ベクトルの要素j が、ある秘密
分散方式における加入者j の秘密部分である）になり、
各列ベクトル（S_c(j)=〔s(1,j),・・・,s(n,j)〕,j=1,・・
・,n）が、ある秘密s_c(j)に対する秘密部分ベクトルに
なる。但し、前述の秘密のベクトル〔s_r(1),・・・,s_r
(n)〕 及び〔s_c(1),・・・,s_c(n)〕 の両方は、元の秘密
s に対する秘密部分ベクトルになる。

【００５４】秘密分散処理のときに、このように構成さ
れた部分行列の列ベクトルi （i=1,・・・,n ）及び秘密s_
r(i)を、加入者i の秘密部分情報として各加入者i に送
信することによって、秘密復元処理のときに、部分情報
を配った加入者が不正をしなければ、各加入者によって
放送された部分情報が正しいかどうかを非常に高い確率
で確認できる。

【００５５】また、本実施例では、元の秘密情報を持
ち、秘密部分情報を配った加入者が不正をした場合で
も、秘密復元処理のとき放送される部分情報が正しいか
どうかを確認するために、秘密部分情報を配る上で各加
入者i （i=1,・・・,n ）に対応する秘密s_r(i)の認証子の
ような役割を果たす値を、一方向性ハッシュ関数（池
野、小山：”現代暗号理論”、pp.224-225、電子情報通
信学会、1986、参照）によって生成する。

【００５６】次に、この一方向性ハッシュ関数について
説明する。

【００５７】一方向性ハッシュ関数とは、データ圧縮型
スクランブルを行う関数であり、入力値から出力値を求
める演算は容易であるが、出力値から入力値を求める逆
演算は困難である関数である。但し、本実施例では、従
来の非対話型確認可能な秘密分散方式に用いられる一方
向性関数に比べると、特殊な代数学的な性質を持たなく
てもよく、計算処理の高速な一方向性ハッシュ関数を利
用できる。

【００５８】一方向性ハッシュ関数の具体例として、R.
Merkle によってDES （Data Encryption Standard）の
ようなブロック暗号を用いた一方向性ハッシュ関数が提
案されている（"One Way Hash Functions and DES",Adv
ances in Cryptology −Crypto'89, Lecture Notes in
Computer Science, Vol. 435, Springer-Verlag, 1990
参照）。

【００５９】図６は、一方向性ハッシュ関数の具体的な
構成を説明する図である。

【００６０】同図において、(a) は、DES によるブロッ
ク暗号化を示しており、６１は、64ビットの入力及び56
ビットの鍵から64ビットの出力が得られる暗号化回路
（図８では、DES をE で表している）である。

【００６１】(b) は、このDES を部分処理として利用
し、入力の長さが119 ビットで出力の長さが112 ビット
となる関数F の処理を示しており、６２は、関数演算回
路である。この処理は、次のように定義される。

【００６２】まず、入力を二つの部分k,x に分ける（た
だし、その一つの部分k 長さを55ビットとし、残りの部
分x の長さを64ビットとする）。次に、その部分x をDE
S の入力とし、残りの部分k と'0' とを連続した値'0',
k を56ビットの鍵として得られた出力と、x とのXOR を
計算した結果を、関数F の出力における左側の64ビット
とする。同様に、同じ部分x を入力とし、残りの部分k
と'1' とを連続した値'1',k を鍵として得られた出力
と、x とのXOR を計算した結果（64ビット）より48ビッ
トを関数F の残りの部分（右側の48ビット）とする。こ
れによって得られた二つの出力を連続した結果が112 ビ
ットの関数F の出力となる。

【００６３】(c) は、与えられたメッセージを入力とし
て、一方向性ハッシュ関数のハッシュ値を出力とする処
理を示しており、６３は、ハッシュ関数処理部である。
この処理は、次のように実行される。

【００６４】まず、与えられたメッセージの最初の119
ビットを上述の関数F の入力として、最初の112 ビット
の出力を得る。次に、その出力を再び入力の112 ビット
分とし、以後メッセージから残りの7 ビット分を連続し
て繰り返し関数F に入力する。最後に、全メッセージを
入力したときに（メッセージの最後の7 ビットを入力す
るために足りないビットがあれば適当に'0' を加える）
得られた112 ビットの出力を、メッセージに対するハッ
シュ値とする。

【００６５】前述のように計算されたハッシュ関数の一
方向性（１つのハッシュ値が与えられたとき、同じハッ
シュ値が得られるような異なる入力のメッセージを求め
ることが極めて困難であること）は、用いられるDES の
ようなブロック暗号の安全性（入力が与えられたとき出
力は鍵によるランダムな変数になり、出力が与えられた
とき入力は鍵によるランダムな変数になる）によって与
えられることが、R. Merkle より示されている（前述の
論文参照）。

【００６６】更に、同じ論文では前述のハッシュ関数よ
り効率のよい一方向性ハッシュ関数も提案されている。
また、ブロック暗号を利用しない効率的な一方向性ハッ
シュ関数がR.Rivestによって提案されている（"The MD4
message digest algorithm", Advances in Cryptology
ーCrypto'90, Lecture Notes in Computer Science,Vo
l. 537, Springer-Verlag, 1991. NIST Federal Inform
ation Processing Standard for Secure Hash, America
n National Standard X9.30-199x参照）。

【００６７】次に、本実施例におけるCut and Choose処
理を説明する。

【００６８】従来の対話型確認可能な秘密分散方式で行
われるCut and Chooseのように、秘密分散処理のとき全
ての加入者が受け取った秘密部分情報が、確認可能に分
散された秘密の部分情報となるかどうかを確認するため
に、元の秘密s に対する部分行列及びハッシュ値を分配
すると同時にk 個のランダムに選ばれた秘密l1,・・・,lk
に対する部分行列及びハッシュ値を分配し、全加入者に
よってランダムに決められたk/2 の秘密（li(1),・・・,li
(k/2) ）に関する全ての秘密情報を放送し、残りのk/2
の秘密（lj(1),・・・,lj(k/2) ）に対してlj(1)+s,・・・,lj
(k/2)+s に関する全ての秘密情報を放送し、全ての放送
された情報の中には誤りを持つ部分の数がt より多けれ
ば、秘密分散処理が正しくないと判断される。

【００６９】以上によって、従来の確認可能な秘密分散
方式の条件(c),(d) の代わりに、次の条件(c'),(d') を
満たす秘密分散方式が実現でき、それを用いて安全に分
散計算を実行する方式及び通信システムが実現できる。

【００７０】(c')不正な部分情報が正しい部分情報と混
在したとき、t+1 個の正しい部分情報があっても元の秘
密情報を復元できない場合が存在するが、不正をした加
入者の識別は可能である。

【００７１】(d')全ての加入者がその秘密の部分情報を
受け取ったとき、その部分情報がある秘密情報x を復元
するための正しい情報でなければ、復元処理のときに不
正をした加入者の識別が可能である。

【００７２】これらの条件は、従来方式のように不正な
加入者があっても秘密を復元、すなわち誤り訂正は行え
ないが、不正な加入者は識別、すなわち誤り検出は可能
にするものである。条件(c),(d) があれば不正な加入者
がいても正しく分散演算が実行できる（正当性に対する
フォールトトレランスを実現できる）が、条件(c'),
(d') に変更しても不正な加入者は検出できるので警告
などを行い再実行することによって正しい出力を得るこ
とができ、正当性に対するフォールトトレランスを実現
することができる。

【００７３】よって、本実施例では、分散された秘密を
復元するとき不正な加入者があった場合には、復元でき
ないこともありえるが、不正を行った加入者の識別は可
能であるような確認可能な秘密分散方式を実現できる。

【００７４】そして、この秘密分散方式を利用して、署
名者グループに参加する各加入者がランダムに選ばれた
秘密の元をそのグループに参加する全加入者間で分散
し、分散された秘密を入力として分散演算の実行から得
られた分散出力の復元処理によって署名を生成する。

【００７５】従って、本実施例では、不正を行った加入
者の識別が可能であり、計算量と通信量の両方が実用的
なオーダーになる分散ディジタル署名方式が実現でき
る。

【００７６】図１は、本発明の１実施例である、分散し
た情報処理装置を有する情報処理システムを示す図であ
る。

【００７７】同図において、１１は、システムの各加入
者の利用する情報処理装置である。以下の説明では、各
装置とそれを利用する各加入者とを同一視して、加入者
と呼ぶことにする。１２は、全ての加入者に情報を公開
することができる放送型通信路であり、１３は、各加入
者毎に秘密の通信を行うことができる秘密通信路であ
る。

【００７８】図２は、情報処理装置１１のブロック構成
を示す図である。同図において、２１は、放送型通信路
１２または秘密通信路１３により他の装置と通信を行な
うための通信部である。２２は、演算処理部であり、記
憶部２４のプログラムに従って、上述した一方向性ハッ
シュ関数などの各種演算や判定の処理を行なうととも
に、装置各部を制御する。２３は、例えば疑似乱数発生
器のような乱数発生部であり、ランダムな値を生成する
ために利用される。２４は、演算処理部２２が実行すべ
きプログラムや、処理の過程で生成される演算結果等の
情報や、他の装置から受信した情報、各種パラメータな
どを記憶するための記憶部である。

【００７９】以下、上述した装置構成により、分散ディ
ジタル署名を実現する方法を具体的に説明する。

【００８０】〔実施例１〕この実施例では前述の C.P.
Schnorr によって提案されたディジタル署名方式を用い
た分散ディジタル署名方式を実現する具体的な構成につ
いて述べる。

【００８１】まず、｛1,・・・,p-1 ｝の内にある秘密の元
を確認可能に分散する具体的な構成を次に示す。

【００８２】ある与えられた秘密s に対する部分行列の
具体的な説明を行う（図４参照）。｛1,・・・,p-1 ｝の内
にある秘密の元s に対する部分行列S=〔s(i,j)〕,i,j=
1,・・・,nとは、各行ベクトル（S_r(i)=〔s(i,1),・・・,s
(i,n)〕,i=1,・・・,n）の要素がs_r(i)を定数項とするt
次の多項式fiのn 個の異なる値i1,・・・,in に対する値fi
(i1),・・・,fi(in) になり、各列ベクトル（S_c(j)=〔s
(1,j),・・・,s(n,j)〕,j=1,・・・,n）の要素がs_c(j)を定数
項とするt 次の多項式gjのn 個の異なる値j1,・・・,jnに
対する値gj(j1),・・・,gj(jn) になり、さらに前述の値の
ベクトル〔s_r(1),・・・,s_r(n)〕 及び〔s_c(1),・・・,s_c
(n)〕 の両方は、元の秘密s を定数項とするt次の多項
式f 及びg の値f(i1,・・・,in)及びg(j1,・・・,jn)になって
いるものである。

【００８３】秘密の元s を署名者グループに参加する全
加入者間で秘密に分散保持されるように秘密部分を分配
する秘密分散処理と、そのように分散された秘密または
（不正があった場合に）不正をした加入者を明らかにす
る秘密復元処理の二つの処理に分けて説明する。

【００８４】以下に、h は効率的な（高速な計算方式の
ある）一方向性ハッシュ関数を表す。例えば高速なブロ
ック暗号化関数によって構成されたハッシュ関数（前述
の”現代暗号理論”参照）が用いられる。安全性パラメ
ータk はある定数k'に対してk=nk' を満たす。この場
合、秘密分散処理の確認が誤る確率は、Cut and Choose
処理によって（前記 T. Rabin, M. Ben-Or "Verifiable
Secret Sharing and Multiparty Protocols with Hone
st Majority"参照 ）2^(-k'(t+1))になる。

【００８５】(1) 秘密分散処理（図５参照）：秘密の元
s を持っている加入者d がs に対する秘密部分を分配す
る処理 （ラウンド１）加入者d は（図５では処理R1.dと表す）
乱数発生手段を用いて、元の秘密s 及び｛1,・・・,p-1 ｝
の内にあるランダムに選ばれた秘密の元l1,・・・,lk に対
する部分行列を生成し、秘密値s_r(1),・・・,s_r(n),l1_r
(1),・・・,l1_r(n),・・・,lk_r(1),・・・,lk_r(n) に対するハ
ッシュ関数の値s*を計算する（図７参照）。

【００８６】加入者d は各加入者i （i=1,・・・,n 、但し
自分は除く）に秘密通信路を利用して、生成した各部分
行列の各列ベクトルS_c(i),L1_c(i),・・・,Lk_c(i)及び秘
密s_r(i),l1_r(i),・・・,lk_r(i)（図５では情報B1.i）を
秘密通信路を用いて送信し、全加入者間でハッシュ値s*
（図５では情報B1.d）を、放送通信路を用いて放送す
る。

【００８７】（ラウンド２）各加入者i （i=1,・・・,n ）
は（図５では処理R2.i）乱数発生手段を用いて、k'個の
ランダムに選択されたビットを放送する（図５ではB2.
i）。それらのランダムに選ばれたk'個のビットはBi_
1,..,Bi_k' 、n 人の全ての加入者に対する全ビットはB
1,・・・,Bk と呼ぶ。

【００８８】（ラウンド３）加入者d は（図５では処理
R3.d）ラウンド２で放送された各ビットBj（j=1,・・・,k
）に対して、Bjが1 であればラウンド１で加入者d が
生成した部分行列Ljを放送し、Bjが0 であればラウンド
１で加入者d が生成した部分行列S とLjの要素毎の有限
体上の加算結果（S+Ljと書く）を放送する。加入者d が
放送した情報は、図５でB3.dと表される。

【００８９】（ラウンド４）各加入者i （i=1,・・・,n ）
は（図５では処理R4.i）ラウンド１で秘密に受信した情
報B1.iのなかに、各値j （j=1,・・・,k ）に対して列ベク
トルLj_c(i) 及びlj_r(i) （ラウンド２で放送されたビ
ットBjが1 の場合）あるいはLj_c(i)+S_c(i) 及びlj_r
(i)+s_r(i)（Bjが0 の場合）がラウンド３で放送された
部分行列に対応する列ベクトル及び秘密値と等しいかど
うかを確認する。ある値j に対して、等しくなければ、
加入者d の判定メッセージ（図５では情報B4.i）を放送
する。

【００９０】（ラウンド５）加入者d は、ラウンド４で
判定メッセージが放送された場合に、判定メッセージを
放送した各加入者j に関してラウンド１で加入者d が秘
密に送信した情報B1.j（図５では処理B5.d）を放送する
（図５では処理R5.d）。

【００９１】（後処理）各加入者i （i=1,・・・,n ）は、
ラウンド５で放送された情報が正しくなければ、あるい
は、ラウンド４で放送された判定メッセージの個数が閾
値tより多ければ、加入者d が不正を働いたと判断する
（図５では処理Pi）。ラウンド１〜５で各加入者i が受
信した全ての情報をs_i と書く（図５参照）。

【００９２】(2) 秘密復元処理（図８参照）：秘密分散
処理による各加入者が持っている情報s_i から、全ての
加入者が元の秘密s を計算するための処理 （ラウンド１）各加入者i （i=1,・・・,n ）は（図８では
処理R1.i）部分情報s_i 含まれている秘密値s_c(i)及び
s_r(i)（図８では情報B1.i）を放送する。

【００９３】（ラウンド２）各加入者i （i=1,・・・,n ）
は（図８では処理R2.i）ラウンド１で放送された値の内
t+1 個の値s_c(i,1),・・・,s_c(i,t+1) 及びs_r(i,1),・・
・,s_r(i,t+1) を選び、多項式補間処理の結果s(c)及びs
(r)を求め、両方が等しくなり残りの放送された値がそ
の値s(c)=s(r) に対応する同じ多項式の正しい値になる
かどうかを確認する。全ての値が正しければ元の秘密s
はs(c)=s(r) と等しいと判断し復元処理が終わる。同じ
多項式に対応しない値が放送された場合に、部分情報s_
i に含まれている列ベクトルS_c(i)を放送する（図８で
は情報B2.i）。

【００９４】（ラウンド３）各加入者i （i=1,・・・,n ）
は（図８では処理R3.i）ラウンド２で放送された列ベク
トルS_c(j)（j=1,・・・,n ）から部分行列S'を生成し、1,
・・・,n ら異なるt+1 個の値を含む全ての集合t1,・・・,tm
（全部でm=n!/((t+1)!(n-t-1)!) 個の集合がある）に対
する列ベクトルの集合T1,・・・,Tm を選び、それぞれの行
と列に対する多項式補間処理の結果s'_r(1),・・・,s'_r
(n) 及びs'_c(1),・・・,s'_c(n) を求め、更にこれらの値
の多項式補間処理の結果s'(r) 及びs'(c) を求め、両方
が等しくなりそれらの列ベクトルの全ての要素がそれぞ
れの値s'_c(1),・・・,s'_c(n) 及びs'_r(1),..,s'_r(n)に
対応する同じ多項式の正しい値になるかどうかを確認す
る。

【００９５】このように確認されたt+1 個の列ベクトル
を含む集合T1,..,Tmの内の異なる正しい部分行列に対応
する集合の数は最大t+1 個になり、それらの部分行列を
S_1,・・・,S_T （ただし、T<t+1 ）と呼ぶ。正しい部分行
列が一個しかなければ（T=1）、その行列に対する秘密s
が元の秘密と等しいと判断し、対応しない列ベクトル
が不正をした加入者を表す。正しい部分行列が二つ以上
があれば、各加入者i(i=1,・・・,n ）は持っている全ての
部分情報s_i を放送する（図８では情報B3.i）。

【００９６】（後処理）各加入者i （i=1,・・・,n ）は
（図８では処理Pi）ラウンド３で放送された情報s_j
（j=1,・・・,n ）を用いて、ラウンド４で計算した正しい
部分行列S_1,・・・,S_T （ただし、T<t+1 ）に対して、秘
密分散処理と同じ一方向性ハッシュ関数を計算し、全て
の放送された情報を正しく、分散処理のラウンド１で放
送された値s*に対応するかどうかを確認する。これらの
確認に対して正しい（最大一つしかありえない）部分行
列に対応する秘密s'は元の秘密s と等しいと判断する。
それに対して前述の確認に対して正しい部分行列がなか
ったならば、秘密の分散を行った加入者d が不正したと
判断する。

【００９７】以上により、署名者グループのある加入者
が持っている秘密の元を、そのグループの全加入者間で
分散保持する処理が実現できる。次に、この秘密分散方
式を用いて、分散ディジタル署名方式における署名者グ
ループの秘密情報（秘密鍵に相当する、ただしそのグル
ープに参加する全加入者間で分散されている）、及びそ
の秘密情報に対応する公開情報（公開鍵に相当するその
グループによって生成された署名を確認するための公開
情報）を生成する処理について述べる。

【００９８】(3) 鍵生成処理（図９参照） （ラウンド１〜５）各加入者i が｛1,・・・,p-1 ｝の内に
ある秘密の元a(i)をランダムに選び、上述の秘密分散処
理を利用して署名者グループに参加する全加入者間で分
散する。さらに、各加入者i がg^(a(i)) mod q（ただ
し、q は前述のように選ばれた素数である）を計算し、
放送通信路を利用して放送する。

【００９９】（ラウンド６）上述の秘密分散処理の後処
理を実行し、正しく分散された秘密の元a(i)（i=1,・・・,
n ）を入力として以下の分散加算によって得られた分散
出力を秘密情報a とする。さらに、正しく分散された秘
密の元a(i)に対する前の処理のラウンド１〜５で放送さ
れた値 A(i)=g^(a(i)) mod qの乗算を計算し、得られた
結果A=g^a mod q をそのグループによる署名を確認する
ための公開情報（公開鍵）とする。

【０１００】ラウンド６で用いた分散加算について図１
０を参照にして説明する。

【０１０１】前述の秘密分散処理によって、｛1,・・・,p-
1 ｝の内にある二つの秘密の元x とy 分散されたとき
（各加入者i が秘密の元x とy に対応する秘密部分x_i
及びy_i 持つ）、通信を行わずに、｛1,・・・,p-1 ｝の内
にある和x+y に対応する秘密部分(x+y)_i を次のように
計算する。各加入者が持っている部分行列の列ベクトル
X_c(i)及びY_c(i)かつ秘密値x_r(i)及びy_r(i)の要素毎
の加算結果X_c(i)+Y_c(i) びx_r(i)+y_r(i) がx+y に対
する部分行列の列ベクトル及び秘密値になることは、部
分行列の定義（行と列の要素が多項式の値となる）から
明らかである。

【０１０２】秘密復元処理において部分情報を確認する
ために用いられる一方向性ハッシュ関数の値x*及びy*
は、両方を記憶し、加算結果x+y を復元処理のとき必要
であれば、両方を用いることによって秘密x+y に対応す
る部分行列X+Y を確認する。同じように、分散された一
つの秘密の元x と公開の元a との乗算を分散して計算す
るために、各加入者が持っている部分行列の各要素とa
との乗算を行った結果がx*a に対する部分行列の要素に
なる。

【０１０３】よって、上述の処理によって分散された二
つの秘密の元x とy 及び公開の元aとb の線形結合a*x+b
*y はそのグループに参加する加入者間で対話せずに分
散して計算できる。この線形結合処理を図１１のように
表現する。ただし、図は行う処理の名前と、その処理に
対する各加入者毎の入出力を示している。各加入者i（i
=1,・・・,n ）の入力は、分散された秘密の元x とy に対
する部分情報x_i とy_i 及び公開の元a とb になり、出
力は線形結合処理の結果z に対する部分情報z_i にな
る。

【０１０４】以上の処理によって得られた秘密鍵を利用
して、与えられたメッセージm のディジタル署名がその
グループによって次のように分散して生成される。

【０１０５】(4) 署名生成処理（図１２参照） （ラウンド１〜５）各加入者i が｛1,・・・,p-1 ｝の内に
ある秘密の元r(i)をランダムに選び、上述の秘密分散処
理を利用して署名者グループに参加する全加入者間で分
散する。さらに、各加入者i がg^(r(i)) mod q（ただ
し、q は前述のように選ばれた素数である）を計算し、
放送通信路を利用して放送する。

【０１０６】（ラウンド６）上述の秘密分散処理の後処
理を実行し、正しく分散された秘密の元r(i)（i=1,・・・,
n ）を入力として先述の分散加算によって分散結果r を
求める。さらに、正しく分散された秘密の元r(i)に対す
るラウンド１〜５で放送された値 R(i)=g^(r(i)) mod q
の乗算R=g^r mod q を計算する。

【０１０７】（ラウンド７）各加入者は与えられたメッ
セージm とラウンド６で計算された値R を連続した値R|
m を入力として前述の所定の関数h の出力e=h(R|m)を計
算し、署名者グループに参加する全加入者間で上述の分
散線形結合処理を利用して、s=r+h(R|m)*aを分散して計
算する。

【０１０８】（ラウンド８〜１０）上述の秘密分散方式
の秘密復元処理を利用して、分散秘密s を復元する。与
えられたメッセージの署名は(R,s) とする。公開鍵a 及
び前述のディジタル署名方式の署名確認処理を利用し
て、生成された署名を確認し、正しくないとき不正をし
た加入者が存在すると判断し、前述の秘密分散方式の秘
密復元処理を実行することによって不正した加入者を識
別する。

【０１０９】〔実施例２〕この実施例では前述のA. Fia
t, A. Shamirによって提案されたディジタル署名方式を
用いた分散ディジタル署名方式を実現する具体的な構成
について述べる。まず、｛1,・・・,N-1 ｝の内にある秘密
の元を確認可能に分散する具体的な構成を次に示す。

【０１１０】ある与えられた秘密s に対する部分行列の
具体的な説明を行う（図４参照）。｛1,・・・,N-1 ｝の内
にある秘密の元s に対する部分行列S=〔s(i,j)〕,i,j=
1,・・・,nとは、各行ベクトル（S_r(i)=〔s(i,1),・・・,s
(i,n)〕,i=1,・・・,n）の要素が次のように定義されるも
のである。

【０１１１】s(i,j)=s_r(i)*q_r(i,1)^(j)*q_r(i,2)^(j
^2)*・・・*q_r(i,t)^(j^t) mod N (j=1,・・・,n) ただし、q_r(i,1),・・・,q_r(i,t) は｛1,・・・,N-1 ｝の内
で以下の条件が満たされるように選ばれた元である。各
列ベクトル（S_c(j)=〔s(1,j),・・・,s(n,j)〕,j=1,・・・,
n）の要素は次のように定義される。

【０１１２】s(j,i)=s_c(j)*q_c(j,1)^(i)*q_c(j,2)^(i
^2)*・・・*q_c(j,t)^(i^t) mod N (i=1,・・・,n) ただし、q_c(j,1),・・・,q_c(j,t) は｛1,・・・,N-1 ｝の内
で以上の条件が満たされるように選ばれた元である。さ
らに前述の値のベクトル〔s_r(1),・・・,s_r(n)〕 及び
〔s_c(1),・・・,s_c(n)〕 の両方は、｛1,・・・,N-1 ｝の内
にあるq_r(1),・・・,q_r(t) 、q_c(1),・・・,q_c(t) に対し
て次の条件を満たす。

【０１１３】s_r(j)=s*q_r(1)^(j)*q_r(2)^(j^2)*・・・*q
_r(t)^(j^t) mod N (j=1,・・・,n) s_c(i)=s*q_c(1)^(i)*q_c(2)^(i^2)*・・・*q_c(t)^(i^t)
mod N (i=1,・・・,n) ただし、s は元の秘密を表す。

【０１１４】秘密の元s を署名者グループに参加する全
加入者間で秘密に分散保持されるように秘密部分を分配
する秘密分散処理と、そのように分散された秘密または
（不正があった場合に）不正をした加入者を明かにする
秘密復元処理の二つの処理が前述の実施例１の処理(1),
(2) のように行われる。ただし、秘密復元処理(2) にお
いて行われる多項式補間処理の代わりに、各行ベクトル
（S_r(i)=〔s(i,1),・・・,s(i,n)〕,i=1,・・・,n）の内にあ
るt+1 個の要素（s(i,j0),・・・,s(i,jt) ）から値s_r(i)
を求めるために、次の計算が行われる。

【０１１５】s_r(i)^(n!)=Prod_k(s(i,jk)^(Prod_l(l*n
!/(l-k)))) mod N ただし、Prod_k(f(k))はk=j0,・・・,jt に対する値f(k)の
乗算を表し、Prod_l(g(l))はl=j0,・・・,jt （l ≠k ）に
対する値g(l)の乗算を表す。

【０１１６】同じように、各列ベクトル（S_c(i)=〔s
(1,j),・・・,s(n,j)〕,j=1,・・・,n）の内にあるt+1 個の要
素（s(i0,j),・・・,s(it,j) ）から値s_c(j)を求めるため
に、次の計算が行われる。

【０１１７】s_c(j)^(n!)=Prod_k(s(ik,j)^(Prod_l(l*n
!/(l-k)))) mod N これらの部分ベクトル〔s_r(1)^(n!),・・・,s_r(n)^(n
!)〕 （あるいは〔s_c(1)^(n!),・・・,s_c(n)^(n!)〕 ）
の内にあるt+1 個の要素（s_r(i0)^(n!),・・・,s_r(it)^
(n!) 、あるいは（s_c(j0)^(n!),・・・,s_c(jt)^(n!) ）
から秘密s を求めるために次の計算が行われる（s_r(i)
^(n!) の場合）。

【０１１８】s^(n!*n!)=Prod_k(s_r(k)^(n!*Prod_l(l*n
!/(l-k)))) mod N s=(s^(n!*n!))^u*(s^l)^v mod N ただし、A.Fiat, A.Shamirによるディジタル署名方式に
用いられるl は、u*n!*n!+v*l=1 になるようなu,v が存
在するように選ばれる。分散された秘密s に対する値s^
l mod N は、後に(6) において説明する署名処理におい
て計算されている。

【０１１９】以上により、署名者グループのある加入者
が持っている秘密の元をそのグループの全加入者間で分
散保持する処理が実現できる。次に、この秘密分散方式
を用いて分散ディジタル署名方式における署名者グルー
プの秘密情報（秘密鍵に相当する、ただしそのグループ
に参加する全加入者間で分散されている）、及びその秘
密情報に対応する公開情報（公開鍵に相当するそのグル
ープによって生成された署名を確認するための公開情
報）を生成する処理について述べる。

【０１２０】(5) 鍵生成処理（図１３参照） （ラウンド１〜５）各加入者i が｛1,・・・,N-1 ｝の内に
ある秘密の元a(i)をランダムに選び、上述の秘密分散処
理を利用して署名者グループに参加する全加入者間で分
散する。さらに、各加入者i がa(i)^l mod N（ただし、
l は前述のように選ばれた元である）を計算し、放送通
信路を利用して放送する。

【０１２１】（ラウンド６）上述の秘密分散処理の後処
理を実行し、正しく分散された秘密の元a(i)（i=1,・・・,
n ）を入力として以下の分散乗算によって得られた分散
出力を秘密情報a とする。さらに、正しく分散された秘
密の元a(i)に対する前の処理のラウンド１〜５で放送さ
れた値 A(i)=a(i)^l mod Nの乗算を計算し、得られた結
果A=a^l mod N をそのグループによる署名を確認するた
めの公開情報（公開鍵）とする。

【０１２２】ラウンド６で用いた分散乗算について図１
４を参照にして説明する。

【０１２３】前述の秘密分散処理によって、｛1,・・・,N-
1 ｝の内にある二つの秘密の元x とy が分散されたとき
（各加入者i が秘密の元x とy に対応する秘密部分x_i
及びy_i 持つ）、通信を行わずに、｛1,・・・,N-1 ｝の内
にある積x*y に対応する秘密部分(x*y)_i を次のように
計算する。

【０１２４】各加入者が持っている部分行列の列ベクト
ルX_c(i)及びY_c(i)かつ秘密値x_r(i)及びy_r(i)の要素
毎の乗算結果X_c(i)*Y_c(i) びx_r(i)*y_r(i) がx*y に
対する部分行列の列ベクトル及び秘密値になることは、
部分行列の定義から明らかである。秘密復元処理におい
て部分情報を確認するために用いられる一方向性ハッシ
ュ関数の値x*及びy*は、両方を記憶し、乗算結果x*y を
復元処理のとき必要であれば、両方を用いることによっ
て秘密x*y に対応する部分行列X*Y を確認する。

【０１２５】同じように、分散された一つの秘密の元x
と公開の元a とのべき乗算を分散して計算するために、
各加入者が持っている部分行列の各要素とa とのべき乗
算を行った結果がx^a に対する部分行列の要素になる。
よって、上述の処理によって分散された二つの秘密の元
x とy 及び公開の元a b の結合x^a*y^b はそのグループ
に参加する加入者間で対話せずに分散して計算できる。
これを図１１と同様に図１５のように表す。

【０１２６】以上の処理によって得られた秘密鍵を利用
して、与えられたメッセージm のディジタル署名がその
グループによって次のように分散して生成される。

【０１２７】(6) 署名生成処理（図１６参照） （ラウンド１〜５）各加入者i が｛1,・・・,N-1 ｝の内に
ある秘密の元r(i)をランダムに選び、上述の秘密分散処
理を利用して署名者グループに参加する全加入者間で分
散する。さらに、各加入者i がr(i)^l mod N（ただし、
l は前述のように選ばれた）を計算し、放送通信路を利
用して放送する。

【０１２８】（ラウンド６）上述の秘密分散処理の後処
理を実行し、正しく分散された秘密の元r(i)（i=1,・・・,
n ）を入力として先述の分散乗算によって分散結果r を
求める。さらに、正しく分散された秘密の元r(i)に対す
るラウンド１〜５で放送された値 R(i)=r(i)^l mod Nの
乗算R=r^l mod N を計算する。

【０１２９】（ラウンド７）各加入者は与えられたメッ
セージm とラウンド６で計算された値R を連続した値R|
m を入力として前述の所定の関数h の出力e=h(R|m)を計
算し、署名者グループに参加する全加入者間で上述の分
散結合処理を利用して、s=r*a^(h(R|m))を分散して計算
する。

【０１３０】（ラウンド８〜１０）上述の秘密分散方式
の秘密復元処理を利用して、分散秘密s を復元する。与
えられたメッセージの署名は(R,s) とする。公開鍵a 及
び前述のディジタル署名方式の署名確認処理を利用し
て、生成された署名を確認し、正しくないとき不正をし
た加入者が存在すると判断し、前述の秘密分散方式の秘
密復元処理を実行することによって不正した加入者を識
別する。

【０１３１】〔実施例３〕この実施例では前述のT. ElG
amal（American National Standard, Digital Signatur
e Algorithm ）によって提案されたディジタル署名方式
を用いた分散ディジタル署名方式を実現する具体的な構
成について述べる。

【０１３２】署名者グループのある加入者が持っている
秘密の元をそのグループの全加入者間で分散保持する具
体的な方式として、実施例１に示した方式を利用する。
その秘密分散方式を用いて分散ディジタル署名方式にお
ける署名者グループの秘密情報（秘密鍵に相当する、た
だしそのグループに参加する全加入者間で分散されてい
る）、及びその秘密情報に対応する公開情報（公開鍵に
相当するそのグループによって生成された署名を確認す
るための公開情報）を生成する処理について次に述べ
る。

【０１３３】(7) 鍵生成処理（図９参照） （ラウンド１〜５）各加入者i が｛1,・・・,p-1 ｝の内に
ある秘密の元a(i)をランダムに選び、上述の秘密分散処
理を利用して署名者グループに参加する全加入者間で分
散する。さらに、各加入者i がg^(a(i)) mod q（ただ
し、q は前述のように選ばれた素数である）を計算し、
放送通信路を利用して放送する。

【０１３４】（ラウンド６）上述の秘密分散処理の後処
理を実行し、正しく分散された秘密の元a(i)（i=1,・・・,
n ）を入力として以下の分散加算によって得られた分散
出力を秘密情報a とする。さらに、正しく分散された秘
密の元a(i)に対するこの処理のラウンド１〜５で放送さ
れた値 A(i)=g^(a(i)) mod qの乗算を計算し、得られた
結果A=g^a mod q をそのグループによる署名を確認する
ための公開情報（公開鍵）とする。

【０１３５】前述の秘密分散処理によって、｛1,・・・,p-
1 ｝の内にある二つの秘密の元x とy 分散されたとき
（各加入者i が秘密の元x とy に対応する秘密部分x_i
及びy_i 持つ）、通信を行わずに、｛1,・・・,p-1 ｝の内
にある和x+y に対応する秘密部分(x+y)_i を実施例１に
示したように計算する。

【０１３６】前述の秘密分散処理によって、｛1,・・・,p-
1 ｝の内にある二つの秘密の元x とy 分散されたとき
（各加入者i が秘密の元x とy に対応する秘密部分x_i
及びy_i 持つ）、通信を行わずに、｛1,・・・,p-1 ｝の内
にある積x*y に対応する秘密部分(x*y)_i を次のように
計算する。

【０１３７】まず、ある加入者d が、｛1,・・・,p-1 ｝の
内にある秘密s を確認可能な分散を行いながら、その秘
密s と以前分散されたx の分散された積s*x を安全に計
算する。その処理を確認可能な秘密分散及び乗算処理と
呼ぶ。

【０１３８】(8) 確認可能な秘密分散及び乗算処理（図
１７、１８参照） 以下において、実施例１と同じように、h は効率的な一
方向性ハッシュ関数を表す。安全性パラメータk はある
定数k'に対してk=nk' を満たす。

【０１３９】（ラウンド１）加入者d は乱数発生手段を
用いて（図１７では処理R1.dと表す）、秘密の元s 及び
｛1,・・・,p-1 ｝の内にあるランダムに選ばれた秘密の元
l1,・・・,lk に対する部分行列を生成し、秘密値s_r(1),・
・・,s_r(n),l1_r(1),・・・,l1_r(n),・・・,lk_r(1),・・・,lk_r
(n) に対するハッシュ関数の値s*を計算する（図７参
照）。加入者d は各加入者i （i=1,・・・,n 、ただし自分
は除く）に秘密通信路を利用して、生成した各部分行列
の各列ベクトルS_c(i),L1_c(i),・・・,Lk_c(i)及び秘密s_
r(i),l1_r(i),・・・,lk_r(i)を秘密通信路を用いて送信
し、全加入者間にハッシュ値s*を( 図１７でB1.d) 、放
送通信路を用いて放送する。

【０１４０】（ラウンド２）各加入者i （i=1,・・・,n ）
（図１７では処理R2.i）は、ラウンド１で受け取った秘
密s_r(i),l1_r(i),・・・,lk_r(i)及び以前分散されたx に
対する秘密x_r(i)を入力として、t_r(i)=s_r(i)*x_r
(i), m1_r(i)=l1_r(i)*x_r(i),・・・, mk_r(i)*x_r(i) mo
d Nの計算を行い、乱数発生手段を用いて、得られた結
果に対する部分行列（T(i),M1(i),・・・,Mk(i) と呼び、
以前分散された秘密x の部分x_r(i)に対する部分行列を
X(i)と呼ぶ）を生成し、秘密値t(i)_r(1),・・・,t(i)_r
(n),m1(i)_r(1),・・・,m1(i)_r(n),・・・,mk(i)_r(1),・・・,m
k(i)_r(n) に対するハッシュ関数の値s*を計算する（図
７参照）。各加入者i は各加入者j （j=1,・・・,n 、ただ
し自分は除く）に秘密通信路を利用して、生成した各部
分行列の各列ベクトルT(i)_c(j),M1(i)_c(j),・・・,Mk(i)
_c(j) 及び秘密t(i)_r(j),m1(i)_r(j),・・・,mk(i)_r(j)
を秘密通信路を用いて送信し、全加入者間でハッシュ値
s*を、放送通信路を用いて放送する。加入者i が放送し
た情報は、図１７でB2.iと表される。

【０１４１】（ラウンド３）各加入者j （j=1,・・・,n ）
（図１７では処理R3.i）は、乱数発生手段を用いて、k'
個のランダムに選択されたビットを放送する。それらの
ランダムに選ばれたk'個のビットをBj_1,..,Bj_k' 、n
人の全ての加入者に対する全ビットをB1,・・・,Bk と呼
ぶ。加入者i が放送した情報は、図１７でB3.iと現され
る。

【０１４２】（ラウンド４）加入者d （図１７では処理
R4.d）は、ラウンド３で放送された各ビットBj（j=1,・・
・,k ）に対して、Bjが1 であればラウンド１で加入者d
が生成した部分行列Ljを放送し、Bjが0 であればラウン
ド１で加入者d が生成した部分行列S とLjの要素毎の有
限体上の加算結果（S+Ljと書く）を放送する( 図１７で
B4.d) 。

【０１４３】（ラウンド５）各加入者i （i=1,・・・,n ）
（図１７では処理R5.i）は、ラウンド１で秘密に受信し
た情報B1.iの中のj （j=1,・・・,k ）に対する各列ベクト
ルLj_c(i) 及びlj_r(i) （ラウンド２で放送されたビッ
トBjが1 の場合）あるいは Lj_c(i)+S_c(i) 及びlj_r
(i)+s_r(i)（Bjが0 の場合）がラウンド４で放送された
部分行列に対応する列ベクトル及び秘密値と等しいかど
うかを確認する。ある値j 対して等しくなければ加入者
d の判定メッセージを放送する。加入者i が放送した情
報は、図１７、１８でB5.iと表される。

【０１４４】（ラウンド６）各加入者i （図１８では処
理R6.i）は、ラウンド３で放送された各ビットBj（j=1,
・・・,k ）に対して、Bjが1 であればラウンド２で加入者
i が生成した部分行列 Mj(i)を放送し、Bjが0 であれば
ラウンド１で加入者d が生成した部分行列 T(i) とMj
(i) の要素毎の有限体上（mod p ）の加算結果（T(i)+M
j(i)と書く）を放送する。更に、加入者d は、ラウンド
５で判定した加入者の列ベクトルを放送する。加入者i
が放送した情報は、図１８でB6.iと表される。

【０１４５】（ラウンド７）各j に対して（j=1,・・・,k
）、各加入者i （図１８では処理R7.i）は、ラウンド
５〜６で放送された情報を確認する。しきい値t より多
くの行列が正しく、かつ、ラウンド３で放送された各ビ
ットBj（j=1,・・・,k ）に対して、Bjが1 であれば次の部
分行列を放送する。

【０１４６】(lj_r(i))^(-1)*Mj(i)-X(i) また、Bjが0 であれば次の部分行列を放送する。

【０１４７】 (s_r(i)+lj_r(i))^(-1)*(T(i)+Mj(i))-X(i) ただし、部分行列の線形結合は前述のように（要素毎
に）行われる。加入者iが放送した情報は、図１８でB7.
iと現される。

【０１４８】（ラウンド８）各j,o に対して（j,o=1,・・
・,k ）、各加入者i （i=1,・・・,n ）（図１８では処理R
8.i）は、ラウンド４で放送された情報を利用して、Bo
が1 であればlj_r(o) を復元した後に次の列ベクトルを
計算し、列ベクトル結果が正しくなること、及び値0 に
対応することを確認する。

【０１４９】 (lj_r(o))^(-1)*Mj(o)_r(i)-X(o)_r(i) Boが0 であれば(s_r(o)+lj_r(o))を復元した後に次の列
ベクトルを計算し、列ベクトル結果が正しくなること、
及び値0 に対応することを確認する。

【０１５０】(s_r(o)+lj_r(o))^(-1)*(T(o)_r(i)+Mj(o)
_r(i))-X(o)_r(i) ある値o に対して確認できなければ加入者o の判定メッ
セージを放送する。加入者i が放送した情報は、図１８
でB8.iと現される。

【０１５１】（ラウンド９）各加入者o （図１８では処
理R9.o）は、ラウンド８で自分に対して判定メッセージ
が放送された場合に、その列ベクトルを放送する。加入
者iが放送した情報は、図１８でB9.iと現される。

【０１５２】（ラウンド１０）各加入者i （図１８では
処理R10.i ）は、全ての放送された情報を確認し、不正
を行った他の加入者o に対して判定メッセージを放送す
る。加入者i が放送した情報は、図１８でB10.i と現さ
れる。

【０１５３】（後処理）全加入者によって（各加入者i
の処理が図１８では処理Piで表される）正しく分散され
た部分行列S(i)*X(i) の分散線形結合を行うことによっ
て正しい部分行列S*X を分散して計算する。不正によっ
てその行列を生成できない場合には、不正を行った加入
者を識別し、その結果を放送する。

【０１５４】以上の処理を行うことによって、ある加入
者ｉがランダムに選んだ｛1,・・・,p-1 の内にある秘密の
元s は、確認可能な形で分散が行われながら、同時にそ
の秘密s と以前に確認可能に分散された秘密x との積s*
x が計算される。次に、上述の処理を利用して構成され
る二つの分散されている秘密x とy の積を実現する計算
についてのべる。これを図１９に示す。

【０１５５】（ラウンド１〜１０）各加入者ｉがランダ
ムに｛1,・・・,p-1 ｝の内にある秘密の元r(i)を選択し、
上述の処理によって確認可能な分散を行いながらr(i)*y
を同時に計算する。

【０１５６】（ラウンド１１）正しく確認可能な分散が
行われている全ての加入者jl(l=1,・・・,m) に対する秘密
の加算r = r(j1)+r(j2)+・・・+r(jm) と r*y = r(j1)*y+r
(j2)*y+・・・+r(jm)*yが前述の分散加算によって計算され
る。

【０１５７】（ラウンド１２）秘密の加算u=x-r が分散
加算される。

【０１５８】（ラウンド１３〜１５）全ての加入者によ
って、秘密u が復元される。

【０１５９】（ラウンド１６）秘密の線形結合z=r*y-u*
y=x*y が分散計算される。

【０１６０】上述の処理によって分散された二つの秘密
の元x とy の積x*y はそのグループに参加する加入者間
で分散して計算できる。以上の処理によって得られた秘
密鍵を利用して、与えられたメッセージm のディジタル
署名がそのグループによって次のように分散して生成さ
れる。

【０１６１】(8) 署名生成処理（図２０参照） （ラウンド１〜５）各加入者i が｛1,・・・,p-1 ｝の内に
ある秘密の元r(i)をランダムに選び、上述の秘密分散処
理を利用して署名者グループに参加する全加入者間で分
散する。さらに、各加入者i がg^(r(i)) mod q（ただ
し、q は前述のように選ばれた素数である）を計算し、
放送通信路を利用して放送する。

【０１６２】（ラウンド６）上述の秘密分散処理の後処
理を実行し、正しく分散された秘密の元r(i)（i=1,・・・,
n ）を入力として先述の分散加算によって分散結果r を
求める。さらに、正しく分散された秘密の元r(i)に対す
るラウンド１〜５で放送された値 R(i)=g^(r(i)) mod q
の乗算R=g^r mod q を計算する。

【０１６３】（ラウンド７）各加入者は与えられたメッ
セージm を入力として前述の所定の関数h の出力e=h(m)
を計算し、署名者グループに参加する全加入者間で上述
の分散線形結合処理を利用して、b=(e+R*a) を分散して
計算する。

【０１６４】（ラウンド８〜１７）署名者グループに参
加する全加入者間で上述の分散乗算処理を利用して、s=
b*r^(-1)を分散して計算する。ただし、r^(-1)の分散逆
元処理を避けるためには、乱数生成処理（ラウンド１〜
５参照）においてg^(r(i)) mod qの代わりにg^((r(i))^
(-1)) mod q を計算すればよい。

【０１６５】（ラウンド１８〜２０）上述の秘密分散方
式の秘密復元処理を利用して、分散秘密s を復元する。
与えられたメッセージの署名は(R,s) とする。公開鍵a
及び前述のディジタル署名方式の署名確認処理を利用し
て、生成された署名を確認し、正しくないとき不正をし
た加入者が存在すると判断し、前述の秘密分散方式の秘
密復元処理を実行することによって不正した加入者を識
別する。

【０１６６】〔他の実施例〕本発明は、実施例１〜３に
示した部分行列の次元数等に限定されるものではなく、
さらに多次元の部分配列でもよく、用いる関数は一方向
性ハッシュ関数でなくても、一方向性が保証されれば他
の関数でもよい。また、Cut and Choose技術も実施例１
に具体的に示した手順でなくても、全ての秘密を漏らす
ことなくその正当性を確認できる手法であればよい。

【０１６７】以上説明したように、本実施例では、通信
システムによって接続されている複数の計算装置（署名
者）からなる署名者グループによって、そのグループの
中のあるしきい値t より多くの署名者が正しければ署名
を生成でき、不正があった場合には不正をした署名者を
識別できるという意味の分散ディジタル署名方式を前述
の通り構成できる。この方式は従来技術による不正があ
っても正しい署名を生成できるという分散ディジタル署
名方式に比べて、通信量と計算量がより効率的になって
いる。

【０１６８】また、従来技術による不正があった場合に
不正者が識別できず署名も生成できないという分散ディ
ジタル署名方式に対しては、不正を行った署名者を識別
できるという点において、本発明による方式の方が安全
であると言える。

【０１６９】具体的に、ある署名者グループに参加する
各署名者に必要な計算量は、一番計算量がかかる処理が
べき乗演算となるので、従来の後者のディジタル署名方
式においてある署名者に必要な計算量とほぼ同じと考え
られる。しかし、各署名者に必要な通信量は、l*n^2*k
のオーダー（n は加入者の数、k は安全パラメータ、l
は用いられる整数の長さ）になり、従来の前者のディジ
タル署名方式に比べて実用的であると考えられる。

【０１７０】ただし、秘密復元処理（前述の実施例１の
処理(2) のラウンド３参照）で行うm=n!/((t+1)!(n-t-
1)!) の異なるt+1 列ベクトルを含む集合の数によっ
て、n は十分小さく（n ＜20）なければ、不正を行った
加入者の識別は実用上で困難であると考えられる。よっ
て、本実施例による秘密分散方式は加入者の数が小さい
場合に対して効果的であると言える。しかし、従来の確
認可能な秘密分散方式は加入者の数が小さい場合に対し
ても非実現的な通信量と計算量であった。

【０１７１】

【発明の効果】以上説明したように、本発明による署名
生成方法を用いることによって通信量及び計算量が削減
できる。また、これにより、通信量が少ないことによっ
て通信システムのトラフィックや通信料金等が改善さ
れ、計算量が少ないことによって処理が高速化されると
いう効果を生じる。

【図面の簡単な説明】

【図１】本発明の１実施例の通信システムの機能構成を
示すブロック図である。

【図２】情報処理装置のブロック構成を示す図である。

【図３】確認可能な秘密分散方式の手順を示す図であ
る。

【図４】秘密部分行列の説明図である。

【図５】秘密分散処理手順の説明図である。

【図６】一方向性ハッシュ関数の具体例を示す図であ
る。

【図７】一方向性ハッシュ関数の説明図である。

【図８】秘密復元処理手順の説明図である。

【図９】秘密鍵及び公開鍵生成処理手順の説明図であ
る。

【図１０】分散秘密の加算処理の説明図である。

【図１１】分散秘密の線形結合処理の入出力関係の説明
図である。

【図１２】分散署名生成処理手順の説明図である。

【図１３】秘密鍵及び公開鍵生成処理手順の説明図であ
る。

【図１４】分散秘密の乗算処理の説明図である。

【図１５】分散秘密の結合処理の入出力関係の説明図で
ある。

【図１６】分散署名生成処理手順の説明図である。

【図１７】確認可能な秘密及び分散乗算処理手順の説明
図である。

【図１８】確認可能な秘密及び分散乗算処理手順の説明
図である。

【図１９】分散秘密の乗算処理手順の説明図である。

【図２０】分散署名生成処理手順の説明図である。

【符号の説明】

１１ 情報処理装置 １２ 放送通信路 １３ 秘密通信路 ２１ 通信部 ２２ 演算処理部 ２３ 乱数発生部 ２４ 記憶部 ６１ 暗号化回路 ６２ 関数演算回路 ６３ ハッシュ演算処理部

Claims (7)

【特許請求の範囲】
1. 【請求項１】 複数の装置が、個別の装置間で他の装置
   には秘密に情報の通信を行なうための秘密通信路と、各
   装置から他の全ての装置へ共通に情報を送信するための
   放送通信路とを介して接続された通信システムにおい
   て、 署名者グループ内の各装置が、第１の秘密情報をランダ
   ムに選び、前記グループ内の各装置に秘密に分散させ、 各装置が、前記第１の秘密情報に所定の第１の関数を作
   用させ、得られた出力値を前記グループ内の全装置に放
   送し、 各装置の前記第１の秘密情報を分散加算し、 各装置の前記出力値を分散乗算し、当該乗算の結果とメ
   ッセージとを所定の第２の関数で処理し、 該処理結果と、前記分散加算の結果と、公開された元と
   を用いて第２の秘密情報を分散演算し、 分散された第２の秘密情報を復元し、前記分散乗算結果
   と共に署名として出力することを特徴とする署名生成方
   法。
2. 【請求項２】 前記第２の秘密情報の分散演算が線形結
   合であることを特徴とする請求項１に記載の署名生成方
   法。
3. 【請求項３】 前記第２の秘密情報の分散演算がべき乗
   を含む積による結合であることを特徴とする請求項１に
   記載の署名生成方法。
4. 【請求項４】 前記第２の秘密情報の分散演算が線形結
   合と乗算との組み合わせであることを特徴とする請求項
   １に記載の署名生成方法。
5. 【請求項５】 前記第２の関数が一方向性の関数である
   ことを特徴とする請求項１に記載の署名生成方法。
6. 【請求項６】 前記第１の秘密情報は所定の有限体上の
   元であり、各演算は該有限体上の演算を利用することを
   特徴とする請求項１に記載の署名生成方法。
7. 【請求項７】 前記第１の秘密情報の分散を、 該第１の秘密情報を有する第１の装置が、当該秘密情報
   から所定の部分配列を生成し、 前記第１の装置が、前記部分配列より他の装置の各々に
   対する第１の部分情報を夫々抽出して、各装置に前記秘
   密通信路を介して送信し、 前記第１の装置が、前記第１の部分情報に所定の関数を
   作用させ、得られた出力値を、各装置に前記放送通信路
   を介して放送し、 前記各装置が、乱数を生成し、生成された乱数を前記放
   送通信路を介して放送し、 前記第１の装置が、放送された前記乱数の値に応じて、
   前記部分配列より第２の部分情報を生成し、生成された
   第２の部分情報を前記放送通信路を介して放送し、 前記各装置が、前記第１の部分情報及び前記生成された
   乱数に応じて、前記第１の情報処理装置で第２の部分情
   報として生成されるべき第３の部分情報を生成し、 前記各装置が、前記第３の部分情報と放送された第２の
   部分情報とを比較して、前記第１の装置による秘密の分
   散を確認することを特徴とする請求項１に記載の署名生
   成方法。