(57)【特許請求の範囲】
【請求項１】
利用者装置と検証者装置、及び少くとも１つの鍵寄託者装置Ｔ1 ,…,ＴM （Ｍ≧１）を設け、
任意の整数に、ｇ∈（Ｚ／ｎＺ）X （ｎを法とする既約剰余類群）及びｅを利用者装置の公開鍵とし、ｎi ＝ｐi2ｑi （ｐi ,ｑi は素数）,ｇi ∈（Ｚ／ｎi Ｚ）X ,ｈi 及びｋを鍵寄託者装置Ｔi （ｉ＝１，２，…,Ｍ）の岡本−内山暗号の公開鍵とし、（Ｚ／ｎＺ）X と（Ｚ／ｎi Ｚ）X を入力とするハッシュ関数Ｈをｋ1 ビットとし、
利用者装置は、秘密鍵ｄ（ｄｅ＝１）をｄ＝ｄ1 ＋…＋ｄM と分解し、これら分割された秘密鍵ｄ1 ，ｄ2 ，…,ｄM をそれぞれ秘密に鍵寄託者装置Ｔ1 ，Ｔ2 ，…,ＴM に各１つずつ寄託し、
利用者装置はまた１＜ｉ＜Ｍに対してそれぞれ、
乱数ｒi を生成し、公開鍵ｎi ，ｇi ，ｈi によりｄi を暗号化して
ｃi ＝ｇidiｈiri mod ｎi 、
を求め、また公開鍵ｎ，ｇを用いてｄi に一方向性関数ｆを適用して
ｗi ＝ｇdimod ｎi 
を求め、利用者装置は更に、１＜ｉ＜Ｍに対して、ランダムにｕi ∈［０，２k ）, ｖi ∈［０，２3k）をそれぞれ生成し、
ａi ＝ｇiuiｈivi mod ｎi ,  ｂi ＝ｇuimod ｎ．
を計算してａi ,ｂi を求め、これらａi ,ｂi にハッシュ関数を適用して
ｅi ＝Ｈ（ａi ,ｂi ）
を計算し、
ｘi ＝ｕi −ｅi ｄi ∈Ｚ，ｙi ＝ｖi −ｅi ｒi ∈Ｚ．
をそれぞれ計算してｘi ,ｙi を求め（ここで∈Ｚはその式が単なる数値の乗算、減算を行うことを示す）、利用者装置は暗号化された分割鍵（ｃ1 ,…，ｃM ）、分割鍵の一方向性関数値（ｗ1 ,…，ｗM ）と証明用情報（ｘ1 ,ｙ1 ,ｅ1 ）,…,（ｘM ,ｙM ,ｅM ）を検証者装置へ送信する。
検証者装置は（ｃ1 ,…，ｃM ）,（ｗ1 ,…，ｗM ）,（ｘ1 ,ｙ1 ,ｅ1 ）,…,（ｘM ,ｙM ,ｅM ）を受信すると、
公開鍵ｅ，ｇ，ｎを用い、
受信した一方向性関数値ｗ1 ,…，ｗM に対し
（ｗ1 ×…×ｗM ）e ≡ｇ（mod ｎ）
が成立つかを検証し、
全てのｉに対して、ｘi ∈［０，２k ）であること、更に公開鍵ｇi ,ｈi を用いて
ｅi ＝Ｈ（ｇixiｈiyiｃiei，ｇxiｗiei）
が成立するかを検証し、
これら全ての検証に合格するか否かを出力することを特徴とする公開検証可鍵寄託方法。
【請求項２】
利用者の秘密鍵ｄに対する公開鍵（ｎ，ｅ，ｇ）と、鍵寄託者装置Ｔ1 ,…,ＴM （Ｍ＞１）の各公開鍵（ｎi ，ｇi ，ｈi ，ｋ）（ｉ＝１，…,Ｍ）とを格納した記憶部と、
秘密鍵ｄが入力され、Ｍ個の分割秘密鍵ｄ1 ，…，ｄM（ｄ＝ｄ1＋…＋ｄM ）に分割する鍵分割部と、
各ｉ（１＜ｉ＜Ｍ）についてｄi ，ｇi ，ｈi ，ｎi が入力され、乱数ｒi を生成し
ｃi ＝ｇidiｈiri mod ｎi 
を計算する暗号部と、
各ｉについてｄi ，ｇ，ｎが入力され、
ｗi ＝ｇdimod ｎ
を計算する一方向性関数部と、
各ｉについて乱数ｕi （０＜ｕi＜２k）を生成する第１乱数生成部と、
各ｉについて乱数ｖi （０＜ｖi＜２3k）を生成する第２乱数生成部と、
各ｉについてｕi ,ｖi ,ｇi ,ｈi ,ｎi が入力され、
ａi ＝ｇiuiｈivi mod ｎi 
を計算する剰余べき乗乗算部と、
各ｉについてｕi ，ｇ，ｎが入力され、
ｂi ＝ｇuimod ｎ
を計算する剰余べき乗計算部と、
各ｉについてａi とｂiが入力され、ハッシュ関数
ｅi ＝Ｈ（ａi ,ｂi ）
を計算するハッシュ関数部と、
各ｉについてｕi ,ｅi ,ｄi が入力され、
ｘi ＝ｕi −ｅi ｄi 
を計算する第１乗算減算部と、
各ｉについて、ｖi ,ｅi ,ｒi が入力され
ｙi ＝ｖi −ｅi ｒi 
を計算する第２乗算減算部と、
（ｃ1 ,…，ｃM ）,（ｗ1 ,…，ｗM ）,（ｘ1 ,ｙ1 ,ｅ1 ）,…,（ｘM ,ｙM ,ｅM ）を検証者装置へ送信する送信部と、
を具備する公開検証可鍵寄託利用者装置。
【請求項３】
利用者の秘密鍵ｄに対する公開鍵（ｎ，ｅ，ｇ）と、鍵寄託者装置Ｔ1 ,…,ＴM （Ｍ＞１）の公開鍵（ｎi ，ｇi ，ｈi ，ｋ）（ｉ＝１，…,Ｍ）を格納した記憶部と、
秘密鍵が入力され、Ｍ個の分割秘密鍵ｄ1 ，…，ｄM （ｄ＝ｄ1 ＋…＋ｄM ）に分割する鍵分割部と、
剰余べき乗乗算部と、
一方向性関数部と、
剰余べき乗計算部と、
乱数生成部と、
ハッシュ関数部と、
乗算減算部と、
送信部と、
上記各部を制御させ、
各ｉ（１＜ｉ＜Ｍ）について、上記剰余べき乗乗算部にて乱数ｒi を生成し、ｃi ＝ｇidiｈiri mod ｎi を計算させ、
上記一方向性関数部にｗi ＝ｇdimod ｎを計算させ、
上記乱数生成部に、乱数ｕi （０＜ｕi ＜２k ）及び乱数ｖi （０＜ｖi ＜２3k）をそれぞれ生成させ、
上記剰余べき乗乗算部に、ｄi ＝ｇiuiｈivi mod ｎi を計算させ、
上記一方向性関数部にｂi ＝ｇui mod ｎを計算させ、
上記ハッシュ関数部にｅi ＝Ｈ（ａi ,ｂi ）を計算させ、
上記乗算減算部にｘi ＝ｕi −ｅi ｄi及びｙi ＝ｖi −ｅi ｒi を計算させ、
上記送信部に（ｃ1 ,…，ｃM ）,（ｗ1 ,…，ｗM ）,（ｘ1 ,ｙ1 ,ｅ1 ）,…,（ｘM ,ｙM ,ｅM ）を検証者装置に送信させる制御部と
を具備する公開検証可鍵寄託利用者装置。
【請求項４】
利用者装置の公開鍵ｎ，ｅ，ｇ、各鍵寄託者装置Ｔ1 ,…,ＴM （Ｍ＞１）の各公開鍵ｇi ，ｈi （ｉ＝１，…,Ｍ）を記憶する記憶部と、
利用者装置から全ての暗号化鍵分割情報（ｃ1 ，…,ｃM ）及び鍵分割一方向性関数値（ｗ1 ，…,ｗM ）、全ての証明情報（ｘ1 ,ｙ1 ,ｅ1 ）,…,（ｘM ,ｙM ,ｅM ）を受信する受信部と、
上記ｗ1 ，…,ｗM 及び上記ｅが入力され、
ｇ′＝（ｗ1 ×…×ｗM ）e
を計算する乗算べき乗計算部と、
上記ｇ′と上記ｇが入力され、両者が等しいか否か比較する第１比較部と、
上記各ｘi が入力され、ｘi が０以上ｋより小であるか否か判定する判定部と、
上記各ｘi ,ｙi ,ｃi ,ｅi ,ｇi ,ｈi が入力され、
ａi′＝ｇixiｈiyi ciei
を計算する第１べき乗乗算部と、
上記ｘi ,ｅi ,ｗi ,ｇが入力され、
ｂi ′＝ｇxiｗiei
を計算する第２べき乗乗算部と、
上記ａi ′,ｂi ′が入力され、
Ｈ（ａi ′,ｂi ′）
を計算するハッシュ関数部と、
上記ｅi と上記Ｈ（ａi ′,ｂi ′）が入力され、これらが等しいか否か比較する第２比較部と、
上記各部を順次動作させ、上記第１比較部が真を出力し、上記判定部が真を出力し、かつ上記全てのｉについて上記第２比較部が真を出力した場合に、検証合格を出力する制御部と
を具備する公開検証可鍵寄託検証者装置。
【請求項５】
利用者装置においてその秘密鍵ｄに対し、公開検証可鍵寄託証明情報を生成するためにコンピュータを、
鍵寄託者装置Ｔ1 ,…,ＴM （Ｍ＞１）の各Ｔi （ｉ＝１，…,Ｍ）に対し、
乱数ｒi を生成し、鍵寄託者装置Ｔi の公開鍵ｇi ,ｈi ,ｎi を用いて、対応寄託分割秘密鍵ｄi （ｄ＝ｄ1 ＋…＋ｄM ）を暗号化計算
ｃi ＝ｇidiｈiri mod ｎi 
を行って、暗号化分割秘密鍵ｃi を求めることを全てのｉについて行う暗号化手段、
全てのｉについて上記利用者装置の公開鍵ｇ，ｎを用いて、ｄi に対し一方向性関数ｆを計算、
ｗi ＝ｇdimod ｎ
を行って、一方向性関数値ｗi を求める一方向性関数手段、
全てのｉについて乱数ｕi （０＜ｕi ＜２k ）を生成する手段、
全てのｉについて乱数ｖi （０＜ｖi ＜２3k）を生成する手段、
全てのｉについてｕi ,ｖi ,ｇi ,ｈi ,ｎi を用いて、
ａi ＝ｇiuiｈivi mod ｎi 
を計算する手段、
全てのｉについてｕi ,ｇ,ｎを用いて
ｂi ＝ｇuimod ｎ
を計算する手段、
全てのｉについてａi とｂi を用いてハッシュ関数
ｅi ＝Ｈ（ａi ,ｂi ）
を計算する手段、
全てのｉについてｕi ,ｅi ,ｄi ,を用いて
ｘi ＝ｕi −ｅi ｄi 
を計算する手段、
全てのｉについてｖi ,ｅi ,ｒi を用いて、
ｙi ＝ｖi −ｅiｒi 
を計算する手段、
暗号化された分割鍵（ｃ1 ，…,ｃM ）、分割鍵の一方向性関数値（ｗ1 ，…,ｗM ）、証明用情報（ｘ1 ,ｙ1 ,ｅ1 ）,…,（ｘM ,ｙM ,ｅM ）を検証者装置へ送信する手段、
として機能させるための公開鍵検証可鍵寄託証明情報生成プログラム。
【請求項６】
請求項５記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、例えば電気通信システムで使用され、公開鍵暗号方式における秘密鍵の鍵寄託方法、その利用者装置、そのプログラム、その記録媒体及び検証者者装置に関する。
【０００２】
【従来の技術】
例えば図６に示すように利用者装置１１において、その秘密鍵ｄをｄ＝ｄ1 ＋…＋ｄM のようにＭ個の分割鍵ｄi （ｉ＝１，…,Ｍ）に分割し、これら各分割鍵ｄi をＭ個の鍵寄託者装置Ｔ1 ,…,ＴM のＴi に１個づつ寄託し、秘密鍵ｄの公開鍵ｅを検証者装置（この場合は公開鍵登録装置）１２に登録する場合において、従来においては鍵寄託者装置Ｔ1 ,…,ＴM はその各寄託された分割鍵ｄi を加算すれば、正しい秘密鍵ｄが得られ、つまり、その各分割鍵ｄi が正しいものであり、かつその秘密鍵ｄに対する公開鍵がｅであることを確認し、その確認を検証者装置１２に通知し、検証者装置１２は利用者装置１１から送られた公開鍵ｅが、正しい秘密鍵ｄに対するものであることの確認を鍵寄託者装置Ｔ1 ,…,ＴM からの保証を受信して、始めて、その利用者装置１１の秘密鍵ｄに対する公開鍵ｅとして登録し、又はその公開鍵ｅを利用することができる。
【０００３】
このようにして初めて、後で正当な秘密鍵ｄが必要になった場合に、鍵寄託者装置Ｔ1 ,…,ＴM の各分割鍵ｄi から秘密鍵ｄを生成することができる。
【０００４】
【発明が解決しようとする課題】
従来の鍵寄託方法によれば、鍵寄託者装置Ｔ1 ,…,ＴM 間でその寄託された分割鍵ｄi が、正しい秘密鍵ｄから分割されたものであって、これら分割鍵ｄiにより秘密鍵ｄを復元できることを確認し、かつ、その秘密鍵ｄが公開鍵ｅに対するものであることを確認し、このことを検証者装置１２へ通知して初めて検証者装置１２は利用者装置１１よりの公開鍵ｅを利用又は登録できるものであり、利用者装置１１自体で対応する秘密鍵ｄの正当性を確認することができず、不便であった。
【０００５】
この発明の目的は検証者装置だけで、公開鍵ｅと対応する正しい秘密鍵ｄが鍵寄託者装置に寄託されていることを検証できる公開検証可鍵寄託方法、その利用者装置、そのプログラム、その記録媒体及び検証者装置を提供することにある。
【０００６】
【課題を解決するための手段】
この発明によれば、利用者装置はＭ個（Ｍ＞１）の鍵寄託者装置Ｔ1 ,…,ＴM に対し、利用者装置の秘密鍵ｄをＭ個に分割鍵ｄ1 ,…,ｄM に分割し（ｄ＝ｄ1 ＋…＋ｄn ）、各分割鍵ｄi を対応する鍵寄託者装置Ｔi に寄託する。利用者装置は各分割鍵ｄi ごとに、その分割鍵ｄi を寄託した鍵寄託者装置Ｔi の公開鍵を用いて暗号化して暗号化された分割鍵ｃi を作ると共に、その分割鍵ｄi に一方向性関数ｆを適用した値ｗi を作り、更にｄi を明かすことなく、ｃi を復号した値と、一方向性関数値ｗi に対し、逆関数を施した値とが等しいことを証明できる証明用情報Ｃi を乱数と上記暗号化関数と上記一方向性関数を用いて作り、全ての分割鍵についての暗号化分割鍵ｃ1 ,…，ｃM と一方向性関数値ｗ1 ,…，ｗM と、証明用情報Ｃ1 ,…,ＣM とを検証者装置へ送り、
検証者装置は、これら受信した情報について、利用者装置及び各鍵寄託者装置の公開鍵を用いて、各分割鍵ｄi が正しいものであり、かつこれら分割鍵ｄi より秘密鍵ｄを作成できることを、これらｄi ,ｄを明かすことなく、検証する。
【０００７】
【発明の実施の形態】
この発明の方法が適用されるシステム構成は例えば図６に示したように利用者装置１１と検証者装置１２及び（複数の）鍵寄託者Ｔ1 ,…,ＴM （１＜Ｍ）よりなる。これらは通信網１３により互いに接続することができる。（ｎ，ｅ，ｇ）を利用者装置１２の公開鍵とし、鍵寄託者装置Ｔi の公開鍵を（ｎi ，ｇi ，ｈi ，ｋ）とする。ここでｉ＝１，…,Ｍであり、（ｎ，ｅ）はＲＳＡ公開鍵暗号方式の公開鍵であり、（ｎi ，ｇi ，ｈi ，ｋ）は、岡本−内山暗号の公開鍵である。ｎは任意の整数で、ｇ∈（Ｚ／ｎＺ）X （ｎを法とする既約剰余類群）、ｎi ＝ｐi2ｑi でｐi ,ｑi は素数である。岡本−内山暗号については文献（１）T.Okamoto and S.Uchiyama．A new public-key cryptosystem as secure as factoring.In K.Nyberg,editor,Advances in Cryptology-EUROCRYPT'98，Lecture Notes in Computer Science,pages 308-318.Springer-Verlag,1998.に示されている。
【０００８】
利用者装置１１は図１に示すように、記憶部１０１内に利用者装置１１の公開鍵ｎ，ｅ，ｇ、各鍵寄託者装置Ｔi の公開鍵ｎi ，ｇi ，ｈi ，ｋが格納されてあり、乱数生成部１０２,１０３、暗号化部１０４、一方向性関数部１０５、剰余べき乗乗算部１０６、剰余べき乗計算部１０７、送信部１０８、鍵分割部１０９、Ｈ関数演算部１１１、乗算減算部１１２，１１３及び記憶部１０１が図に示していないが制御部１１４に接続されている。
図２に利用者装置１１の処理手順を示す。
【０００９】
まず秘密鍵ｄは鍵分割部１０９に入力され、鍵寄託者装置Ｔ1 ,…，ＴM の個数に分割される（Ｓ１）。ここでｅｄ＝１とする。これら分割鍵ｄ1 ,…，ｄM はｄ＝ｄ1 ＋…＋ｄMである。これら分割鍵ｄi （ｉ＝１，２，…,Ｍ）に対応する鍵寄託者装置Ｔi へ秘密に送られ寄託される（Ｓ２）。
各分割鍵ｄi について、ｄi とその鍵寄託者装置Ｔi の公開鍵ｇi ，ｈi ，ｎiが暗号化部１０４へ入力され、暗号化部１０４では内部の乱数生成部１０４ａで乱数ｒi を生成し、ｄi に対し、次の暗号化演算を行い暗号化分割鍵ｃi を生成する（Ｓ３）。
【００１０】
ｃi ＝ｇidiｈiri mod ｎi                   （１）
またｄi と利用者装置１１の公開鍵ｇ，ｎが一方向性関数部１０５に入力され、次式により一方向性関数値ｗi が計算される（Ｓ４）。
ｗi ＝ｇdimod ｎ                        （２）
ステップＳ３とＳ４は何れを先に行ってもよい。全ての分割鍵ｄ1 ,…，ｄM に対し、ステップＳ３とＳ４を行い、これら暗号化分割鍵及び一方向性関数値（ｃ1 ,…，ｃl ,ｗ1 ,…，ｗl ）を検証者装置１２へ送信し、検証者装置１２でＤi （ｃi ）＝ｆ-1（ｗi ）、つまり暗号化分割鍵ｃi を復号した値と、一方向性関数値ｗi に逆関数を施した値とが等しいことが証明できるように証明用情報Ｃi も付けて利用者装置１２へ送信する。検証者装置１２では実際には
Ｄi （ｃi ）≡±｛ｌｏｇgｗi ｝（mod ｐi ）      （３）
且つ、
ｄ＝ｌｏｇgｗ1 ＋…＋ｌｏｇgｗM               （４）
であることを証明できる必要がある。
【００１１】
式（３）かつ（４）の関係をｄ，ｄi を明すことなく、非対話証明方法で証明するための証明用情報Ｃi の生成方法を以下に述べる。
利用者装置１１は、各ｄi について、ランダムにｕi ∈［０，２k ）,ｖi ∈［０，２3k）を選ぶ、つまり乱数生成部１０２から０＜ｕi ＜２k の乱数ｕi を生成し、また乱数生成部１０３から０＜ｖi ＜２3k の乱数ｖi を生成する（Ｓ５）。
これら乱数ｕi ,ｖi と公開鍵ｇi ,ｈi ,ｎi が剰余べき乗乗算部１０６へ入力されて下記の計算がなされる（Ｓ６）。
【００１２】
ａi ＝ｇiuiｈivi mod ｎi                     （５）
またｕi と公開鍵ｇ,ｎが剰余べき乗計算部１０７に入力されて下記の計算がなされる（Ｓ７）。
ｂi ＝ｇui mod ｎ                          （６）
これら計算結果ａi ,ｂi はハッシュ関数部１１１に入力されて
ｅi ＝Ｈ（ａi ,ｂi ）                      （７）
が計算される（Ｓ８）。ここでハッシュ関数Ｈは（Ｚ／ｎＺ）X の数と（Ｚ／ｎi Ｚ）Xの数を入力して０，１のｋ′ビットの演算結果を出力するものである。
【００１３】
このハッシュ関数値ｅi と乱数ｕi 、分割鍵ｄi が乗算減算部１１２に入力され、
ｘi ＝ｕi −ｅi ｄi ∈Ｚ                    （８）
が計算される（Ｓ９）。ここで∈Ｚは数値ｕi ，ｅi ｄiの異なる乗算、減算を示す。またｅi と乱数ｖi と乱数ｒi が乗算減算部１１３に入力され、
ｙi ＝ｖi −ｅi ｒi ∈Ｚ                （９）
が計算される（Ｓ１０）。このようにして分割鍵ｄi についての証明用情報Ｃi ＝（ｘi ,ｙi ,ｅi ）が作られ、全ての分割鍵ｄi についての証明用情報を作った後、全ての暗号化分割鍵ｃ1 ，…，ｃM 、全ての一方向性関数値ｗ1 ，…，ｗM 、全ての証明用情報Ｃ1， …，ＣM を送信部１０８より検証者装置１２へ送信する（Ｓ１１）。なおステップＳ５とＳ６は何れを先にしてもよく、同様にステップＳ９とＳ１０も何れを先にしてもよい。ここで上述した各種パラメータの関係を示す。
・ｋ．ｋ′（Ｈの出力値サイズ（ビット数）），ｌｏｇ  ｎ（ｎのサイズ）は、
ｋ−（ｌｏｇ  ｎ＋ｋ′）∈Ｏ（ｋ）（ｋのオーダを表す）の関係を満たす。
【００１４】
例えば推奨値としては、ｋ＝１２８０（ｂｉｔ）、ｌｏｇ  ｎ＝１０２４（ｂｉｔ）、ｋ′＝１２８（ｂｉｔ）である。
・ｒi（岡本−内山暗号の乱数）は、
ｒi∈｛０，１｝2k+CONST（つまりｌｏｇ  ｒi＝２ｋ＋ＣＯＮＳＴ）
ここでＣＯＮＳＴ＞３であり、ＣＯＮＳＴ＝３が好ましい。
・ｈiは、ｈi＝ｇinit  mod  ｎiとし、ｔは適当なサイズｔ∈｛０，１｝  3kの乱数で秘密に保たれなければいけない（なお岡本―内山暗号ではｈi＝ｇ  ini  mod  ｎiである）。
・以上の条件を満たした時、安全性の証明が可能になる。
【００１５】
次に検証者装置１２における検証処理について説明する。
検証者装置１２の機能構成例を図３に示し、その処理手順の例を図４に示す。
検証者装置１２の記憶部２０１には利用者装置１１の公開鍵ｎ，ｅ，ｙ及び各鍵寄託者装置Ｔ1 ，…，ＴM の公開鍵ｇi ，ｈi ，ｋ（ｉ＝１，…，Ｍ）が格納されてある。
検証者装置１２の受信部２０２に利用者装置１１から暗号化鍵ｃ1 ，…，ｃM 、一方向性関数値ｗ1 ，…，ｗM 、証明用情報Ｃ1 ＝（ｘ1 ，ｙ1 ，ｅ1 ），…，ＣM ＝（ｘM ，ｙM ，ｅM ）を受信すると、必要に応じて記憶部２０１に格納する（Ｓ１）。
【００１６】
その後、受信したｗ1 ，…，ｗM と公開鍵ｅとが剰余乗算べき乗計算部２０３に入力され、
ｙ′＝（ｗ1 ×…×ｗM ）e mod ｎ            （１０）
が計算される（Ｓ２）。式（２）より
0003738969.tif 000002
ｄ＝ｄ1 ＋ｄ2 ＋…＋ｄM であり、前記定義ｅｄ＝１であるから、受信したｗ1 ，…，ｗM が全て正しいものであれば、ｇ′＝ｇとなる。このことは式（４）が成立することを示すことになる。
【００１７】
よって比較部２０４に計算結果ｇ′と公開鍵ｇが入力され、両者が等しいか否か調べられる（Ｓ３）。両者が等しければ受信した各ｘi と公開鍵ｋが判定部２０５に入力され、全てのｘi が０＜ｘi ＜２k の範囲にあるかが調べられる（Ｓ４）。
全てこの条件を満していれば、受信したｘi ，ｙi ，ｃi ，ｅi と公開鍵ｇi ，ｈi がべき乗乗算部２０６に入力され、
ａi′＝ｇixiｈiyiｃiei                             （１１）
が計算される（Ｓ５）。ｘi に式（８）を、ｙi に式（９）をｃi に式（１）をそれぞれ代入すると、
0003738969.tif 000003
となる。またべき乗乗算部２０７に受信したｘi ，ｅi ，ｗi と公開鍵ｇが入力され、
ｂi′＝ｇxiｗiei                                （１３）
が計算される（Ｓ６）。ｘi に式（８）をｗi に式（２）を代入すると、
ｂi′＝ｇ(ui-eidi)ｇdiei＝ｇui                      （１４）
となる。これら計算結果ａi′，ｂi′がハッシュ関数部２０８に入力され、
ｅi′＝Ｈ（ａi′，ｂi′）                      （１５）
が計算される（Ｓ７）。この計算結果ｅi′と受信したｅi とが比較部２０９に入力され、両者が等しいか否か調べられる（Ｓ８）。全てのｉについて等しければ合格が出力される（Ｓ９）。式（１１）、式（１２）からｃi を復号した値がｄi であればａi′＝ａi になり、式（１３）と式（１４）からｗi の逆関数値がｄi であれば、ｂi′＝ｂiとなり、式（７）と式（１５）からｅi′＝ｅi であれば、ｃi の復号したｄi とｗi の逆関数値のｄi とが等しいことになり、式（３）が成立することが証明される。
【００１８】
従って比較部２０４からの等しいことを示す出力と、判定部２０５からの全てのｘi が条件を満す出力と、比較部２０９からの全てのｅi について等しいことを示す出力が出力部２１１に入力されると合格を示す、つまり受信したｃ1 ，…，ｃM ，ｗ1 ，…，ｗM は式（３）及び（４）を満していることを示す信号が出力される。比較部２０４で等しくないことを示す出力、判定部２０５から何れか１つでも条件を満さないものがあることを示す出力、比較部２０９から何れか１つでも等しくないことを示す出力が出力部２１１に入力されると、受信したｃ1 ，…，ｃM ，ｗ1 ，…，ｗM は利用者装置１１の公開鍵に対する正しい秘密鍵、又は正しい分割鍵ｄ1 ，…，ｄM を用いて作られたものでないことを示す信号が出力される（Ｓ１０）。なおステップＳ３，Ｓ４，Ｓ８の検証の順番は任意でよい。ステップＳ５とＳ６は何れを先にしてもよい。検証者装置１２において各部は制御部２１２により制御される。
【００１９】
このようにこの構成によれば検証者装置１２は利用者装置１１から受信した情報のみを用いて、利用者装置１１の秘密鍵ｄが正しいものであり、かつ分割された各分割鍵ｄ1 ，…，ｄM が鍵寄託者装置Ｔ1 ，…，ＴM にそれぞれ正しく寄託されていることを検証することができ、この検証に合格すれば対応する利用者装置の公開鍵をその利用者装置のものとして登録したり、利用することができる。しかも検証者装置１２に対し秘密鍵ｄ、分割鍵ｄ1 ，…，ｄM の何れも明かさないで済む。
【００２０】
利用者装置１１及び検証者装置１２は何れもコンピュータによりプログラムを実行して機能させることもできる。その場合は例えば、利用者装置１１について示すと図５に示すように、記憶部１２１、乱数生成部１２２、ハッシュ関数部１２３、暗号化関数演算部１２４、一方向性関数演算部１２５、乗算減算部１２６、プログラムメモリ１２７、ＣＰＵ（マイクロプロセッサ）１２８、送信部１２９がバス１３１に接続され、プログラムメモリ１２７に、ＣＤ−ＲＯＭ、フロッピーディスク、磁気ディスクなどから例えば図２に示した方法をコンピュータに実行させるためのプログラムがインストールされ、又は通信回線を介してダウンロードされ、このメモリ１２７内のプログラムをＣＰＵ１２８が実行して、ステップＳ３で暗号化関数演算部１２４にサブルーチンとして式（１）を計算させ、ステップＳ４では一方向性関数演算部１２５に式（２）を計算させ、ステップＳ５で乱数生成部１２２に乱数ｕi ，ｖi を生成させ、ステップＳ６で暗号化関数演算部１２４に式（５）を計算させ、ステップＳ７で一方向性関数演算部１２５に式（６）を計算させ、ステップＳ８でハッシュ関数演算部１２３に式（７）を計算させ、ステップＳ９で乗算減算部１２６に式（８）を計算させ、ステップＳ１０で乗算減算部１２６に式（９）を計算させ、ステップＳ１１で送信部１２９に検証者装置への送信を行わせる。
【００２１】
【発明の効果】
以上述べたようにこの発明によれば検証者装置でのみ、利用者装置の秘密鍵の正当性と、それが分割寄託された状態とを検証することができ、鍵寄託者装置よりの検証結果の通知を得、必要がなく頗る便利である。
しかもこの発明は、以下の性質を満たす。
この発明は、ｎ＝ｐ2 ｑ型のＳｔｒｏｎｇ  ＲＳＡ仮定が真であれば、公開検証性を持つ。
【００２２】
この発明は、ｐ−Ｓｙｌｏｗ部分群仮定が真であれば、ランダムオラクルモデル上で安全である。
【図面の簡単な説明】
【図１】この発明の実施形態における利用者装置の機能構成例を示す図。
【図２】図１に示した装置の処理手順の例を示す流れ図。
【図３】この発明の実施形態における検証者装置の機能構成例を示す図。
【図４】図３に示した装置の処理手順の例を示す流れ図。
【図５】この発明の実施形態における利用者装置をコンピュータにより機能させる場合の構成例を示す図。
【図６】この発明が適用されるシステム構成例を示す図。
【図１】
0003738969.tif 000004
【図２】
0003738969.tif 000005
【図３】
0003738969.tif 000006
【図４】
0003738969.tif 000007
【図５】
0003738969.tif 000008
【図６】
0003738969.tif 000009