(57)【要約】【課題】  効率的な紛失通信路構成方法を提供する。【解決手段】  受信者Ｂが送信者Ａに対して一般の伝送経路を介して（ａ1，…，ａn，α1，…，αk）を送ることで送信者Ａは自らｎ個の公開鍵をｙj＝Ｈj（ｆ（ｊ））◎ａjとして求めることができるので、送信者Ａに対して公開鍵を送信する必要はなく、そして、送信者Ａは、離散対数型の公開鍵をα0＝Ｈ0（ａ1，ａ2，…，ａn）を多項式上の点に持つｋ次多項式上の点から一意に定まる形で求めていることにより、受信者Ｂがｋ個以上の公開鍵に対応する秘密鍵を知り得ないことを納得することができるので、更に、何れの公開鍵も同様の手順により求めることにより、受信者が秘密鍵を知っている公開鍵が何れであるかを見分けることができない仕組みが構成され、従来通信コストが非効率であったのに対して、効率的な紛失通信路を構成する紛失通信路構成方法。【選択図】  図１
2006108840.tif 000002
【特許請求の範囲】
【請求項１】
Ｇjを位数ｑjの可換群とし、ｘ∈Ｚqjに対してＧj（ｘ）はインデックスがｘである様なＧjの元を表すものとし、秘密鍵ｘj∈Ｚqjに対して、ｙj＝Ｇj（ｘj）なるｙjおよびＧjを離散対数型公開鍵とし、Ｈjを入力域がＺpであって出力域がＺqである一方向性ハッシュ関数とし、或るｋ個の公開鍵に対応する秘密鍵ｘj を使用してｎ個の暗号化された送信情報からｋ個を復号して平文情報を得る紛失通信路構成方法において、
秘密鍵ｘjを任意に設定すると共にこれらに対応する離散対数の公開鍵ｙj＝ｇxjを設定する公開鍵秘密鍵生成部、ｋ次多項式ｆ（ｗ）を満足する点としてｋ個の値ｆ（ｊ）をｋ個設定する第１ｋ次多項式点設定部、第１ｋ次多項式点設定部により設定された値ｆ（ｊ）を入力してそのハッシュ演算出力値ｃj＝Ｈj（ｆ（ｊ））を計算する第１ハッシュ演算部、第１ハッシュ演算部から出力されるハッシュ演算出力ｃj＝Ｈj（ｆ（ｊ））を入力すると共に第１ｋ次多項式点設定部により設定された公開鍵ｙjを入力して排他的論理和ａj＝ｃj◎ｙj を得る第１排他的論理和演算部、第１排他的論理和演算部の出力を入力して公開鍵の数を判断する第１公開鍵リスト数判断部を有し、
更に、任意にｎ−ｋ個の乱数ａj を設定する乱数生成部、乱数生成部の設定したｎ−ｋ個の乱数ａj を入力すると共に第１排他的論理和演算部のｋ個の演算結果ａj＝ｃj◎ｙj を入力してα0 ＝Ｈ0（ａ1、・・・・、ａn）を得る第３ハッシュ演算部、第３ハッシュ演算部の出力であるα0および第１ｋ次多項式点設定部の出力であるｋ個の（ｊ、ｆ（ｊ））を入力としてｋ次多項式ｆ（ｗ）を設定するｋ次多項式設定部を有する公開鍵秘密鍵生成装置を具備し、
送信されてきた（ａ1，…，ａn）を入力してα0＝Ｈ0（ａ1，…，ａn）を設定する第４ハッシュ演算部、設定されたα0 と送信されてきたｋ個の（α1，…，αk）の合計ｋ＋１個のαによりｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkを一意的に設定するｋ次多項式演算部、ｋ次多項式からｆ（ｊ）を計算するｋ次多項式点演算部、ｃj＝Ｈj（ｆ（ｊ））を計算する第２ハッシュ演算部、第２ハッシュ演算部により得られたｃj＝Ｈj（ｆ（ｊ））を入力すると共に送信されてきた（ａ1，…，ａn）を入力して排他的論理和演算を実行し、ｙj＝ｃj◎ａjを計算する第２排他的論理和演算部、排他的論理和演算により計算された値ｙjおよび送信する平文を入力して暗号文を生成する暗号文生成部より成る暗号文生成装置を具備し、
暗号文選別部と暗号文復号部とより成る復号装置を具備し、ここで、
Ｓｔｅｐ１：受信者は、
・ｋ個の秘密鍵公開鍵のペア（ｙj，ｘj）を任意に設定し、
・ｋ次多項式の上の点としてｋ個の値ｆ（ｊ）を任意に設定し、ｃj＝Ｈj（ｆ（ｊ））を計算し、
・ｋ個のａj＝ｃj◎ｙjを求め、
・ｎ−ｋ個の残りのａjを任意に設定し、
・α0 ＝Ｈ0（ａ1、・・・・、ａn）により求められたα0 およびｋ個の任意に設定した点（ｊ、ｆ（ｊ））を合計したｋ＋１個の点を使用し、ｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗk を一意に求め、
・（ａ1，…，ａn，α1，…，αk）を送信者へ渡し、
Ｓｔｅｐ２：送信者は、
送られてきた（ａ1，…，ａn，α1，…，αk）から、α0 ＝Ｈ0（ａ1、・・・・、ａn）と、ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗk と、ｙj＝Ｈ（ｆ（ｊ））◎ａj  とを求め、これにより公開鍵（ｙ1，…，ｙn）を求め、
・送信者は求めたｎ個の公開鍵を用いて、送信するｎ個の秘密情報を暗号化し、ｎ個の暗号文を生成し、
・生成したｎ個の暗号文を受信者に送信し、
Ｓｔｅｐ３：受信者は、
・受信した暗号文ｎ個の内の、自分が秘密鍵を知っているｋ個について、復号し、秘密情報ｍi をｋ個入手し、
ｎ個の秘密情報の内の、何れかｋ個の秘密情報ｍj を、送信者から受信者にｎ個の秘密情報の内の何れを受信者が得られたかを匿名にし更に、送信者は受信者がｋ個以上の秘密鍵を知り得ないことが確信できる公開鍵を用いて行う紛失通信路の構成を実行することを特徴とする紛失通信路構成方法。
【請求項２】
Ｇjを位数ｑjの可換群とし、ｘ∈Ｚqjに対してＧj（ｘ）はインデックスがｘである様なＧjの元を表すものとし、秘密鍵ｘj∈Ｚqjに対して、ｙj＝Ｇj（ｘj）なるｙjおよびＧjを離散対数型公開鍵とし、Ｈjを入力域がＺpであって出力域がＺqである一方向性ハッシュ関数とし、或るｋ個の公開鍵に対応する秘密鍵ｘj を使用してｎ個の暗号化された送信情報からｋ個を復号して平文情報を得る紛失通信路構成方法において、
秘密鍵ｘjを任意に設定すると共にこれらに対応する離散対数の公開鍵ｙjを設定する公開鍵秘密鍵生成部、ｋ次多項式ｆ（ｗ）を満足する点としてｋ個の値ｆ（ｊ）を設定する第１ｋ次多項式点設定部、第１ｋ次多項式点設定部により設定されたｋ次多項式上の点の値ｆ（ｊ）を入力してそのハッシュ演算出力値ｃj＝Ｈj（ｆ（ｊ））を計算する第１ハッシュ演算部、第１ハッシュ演算部から出力されるハッシュ演算出力ｃj＝Ｈj（ｆ（ｊ））を入力すると共に第１ｋ次多項式点設定部により設定された公開鍵ｙjを入力して排他的論理和ａj＝ｃj◎ｙj を得る第１排他的論理和演算部、第１排他的論理和演算部の出力を入力して公開鍵の数を判断する第１公開鍵リスト数判断部を有し、
更に、任意にｎ−ｋ個の乱数ａj を設定する乱数生成部、乱数生成部の設定したｎ−ｋ個の乱数ａj を入力すると共に第１排他的論理和演算部のｋ個の演算結果ａj＝ｃj◎ｙj を入力してα0 ＝Ｈ0（ａ1、・・・・、ａn）を得る第３ハッシュ演算部、第３ハッシュ演算部の出力であるα0および第１ｋ次多項式点設定部の出力であるｋ個の（ｊ、ｆ（ｊ））を入力としてｋ次多項式ｆ（ｗ）を設定するｋ次多項式設定部を有する公開鍵秘密鍵生成装置を具備し、
送信されてきたｋ＋１個の（α0，…，αk）の合計ｋ＋１個のαによりｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkを一意的に設定するｋ次多項式演算部、ｋ次多項式からｆ（ｊ）を計算するｋ次多項式点演算部、ｃj＝Ｈj（ｆ（ｊ））を計算する第２ハッシュ演算部、第２ハッシュ演算部により得られたｃj＝Ｈj（ｆ（ｊ））を入力すると共に送信されてきた（ａ1，…，ａn）を入力して排他的論理和演算を実行し、ｙj＝ｃj◎ａjを計算する第２排他的論理和演算部、排他的論理和演算により計算された値ｙjおよび送信する平文を入力して暗号文を生成する暗号文生成部より成る暗号文生成装置を具備し、
暗号文選別部と暗号文復号部とより成る復号装置を具備し、ここで、
Ｓｔｅｐ１：受信者は、
・ｋ個の秘密鍵公開鍵のペア（ｙj，ｘj）を任意に設定し、
・ｋ次多項式の上の点としてｋ個の値ｆ（ｊ）を任意に設定し、ｃj＝Ｈj（ｆ（ｊ））を計算し、
・ｋ個のａj＝ｃj◎ｙjを求め、
・ｎ−ｋ個の残りのａjを任意に設定し、
・ｆ（０）＝Ｈ0（ａ1，…，ａn）＝α0を計算し、このα0とｋ個の任意に設定した点（ｊ、ｆ（ｊ））を合計したｋ＋１個の点を使用してｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkを求め、
・（ａ1，…，ａn，α0，…，αk）を送信者へ渡し、
Ｓｔｅｐ２：送信者は、
送られてきた（ａ1，…，ａn，α0，…，αk）から、ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗk と、ｙj＝Ｈ（ｆ（ｊ））◎ａj  とを求め、これにより公開鍵（ｙ1，…，ｙn）を求め、
・送信者は求めたｎ個の公開鍵を用いて、送信するｎ個の秘密情報を暗号化し、ｎ個の暗号文を生成し、
・生成したｎ個の暗号文を受信者に送信し、
Ｓｔｅｐ３：受信者は、
・受信した暗号文ｎ個の内の、自分が秘密鍵を知っているｋ個について、復号し、秘密情報をｋ個入手し、
ｎ個の秘密情報の内の、何れかｋ個の秘密情報ｍj を、送信者から受信者にｎ個の秘密情報の内の何れを受信者が得られたかを匿名にし更に、送信者は受信者がｋ個以上の秘密鍵を知り得ないことが確信できる公開鍵を用いて行う紛失通信路の構成を実行することを特徴とする紛失通信路構成方法。
【請求項３】
請求項１に記載される紛失通信路構成方法において、
公開鍵秘密鍵生成装置は、更に、ｋ次多項式ｆ（ｗ）からｆ（ｊ）を設定する第２ｋ次多項式点設定部、値ｆ（ｊ）にハッシュ演算を施しｃj＝Ｈ（ｆ（ｊ））を計算する第２ハッシュ演算部、第２ハッシュ演算部の演算結果を入力すると共に乱数生成部からｎ−ｋ個の乱数ａj を入力して論理和演算を実行する第２排他的論理和演算部、第２排他的論理和演算部の出力を入力して公開鍵の数を判断する第２公開鍵リスト数判断部を有し、
Ｓｔｅｐ１において、受信者は、更に、
・ｎ−ｋ個の残りのｆ（ｊ）をｋ次多項式から求め、ｃj＝Ｈj（ｆ（ｊ））を計算し、
・ｎ−ｋ個のｙj＝ｃj◎ａjを計算し、
・秘密鍵を知っているｋ個の公開鍵と秘密鍵を知らないｎ−ｋ個の公開鍵（ｙ1，…，ｙn）を設定する、
ことを特徴とする紛失通信路構成方法。
【請求項４】
請求項２に記載される紛失通信路構成方法において、
公開鍵秘密鍵生成装置は、更に、ｋ次多項式ｆ（ｗ）からｆ（ｊ）を設定する第２ｋ次多項式点設定部、値ｆ（ｊ）にハッシュ演算を施しｃj＝Ｈ（ｆ（ｊ））を計算する第２ハッシュ演算部、第２ハッシュ演算部の演算結果を入力すると共に乱数生成部６からｎ−ｋ個の乱数ａj を入力して論理和演算を実行する第２排他的論理和演算部、第２排他的論理和演算部の出力を入力して公開鍵の数を判断する第２公開鍵リスト数判断部を有し、
Ｓｔｅｐ１において、受信者は、更に、
・ｎ−ｋ個の残りのｆ（ｊ）をｋ次多項式から求め、ｃj＝Ｈj（ｆ（ｊ））を計算し、
・ｎ−ｋ個のｙj＝ｃj◎ａjを計算し、
・秘密鍵を知っているｋ個の公開鍵と秘密鍵を知らないｎ−ｋ個の公開鍵（ｙ1、・・・・、ｙn ）を設定する、
ことを特徴とする紛失通信路構成方法。
【請求項５】
Ｇjを位数ｑjの可換群とし、ｘ∈Ｚqjに対してＧj（ｘ）はインデックスがｘである様なＧjの元を表すものとし、秘密鍵ｘj∈Ｚqjに対して、ｙj＝Ｇj（ｘj）なるｙjおよびＧjを離散対数型公開鍵とし、Ｈjを入力域がＺpであって出力域がＺqである一方向性ハッシュ関数とし、或るｋ個の公開鍵に対応する秘密鍵ｘj を使用してｎ個の暗号化された送信情報からｋ個を復号して平文情報を得る紛失通信路構成装置において、
秘密鍵ｘjを任意に設定すると共にこれらに対応する離散対数の公開鍵ｙj＝ｇxjを設定する公開鍵秘密鍵生成部、ｋ次多項式ｆ（ｗ）を満足する点としてｋ個の値ｆ（ｊ）をｋ個設定する第１ｋ次多項式点設定部、第１ｋ次多項式点設定部により設定された値ｆ（ｊ）を入力してそのハッシュ演算出力値ｃj＝Ｈj（ｆ（ｊ））を計算する第１ハッシュ演算部、第１ハッシュ演算部から出力されるハッシュ演算出力ｃj＝Ｈj（ｆ（ｊ））を入力すると共に第１ｋ次多項式点設定部により設定された公開鍵ｙjを入力して排他的論理和ａj＝ｃj◎ｙj を得る第１排他的論理和演算部、第１排他的論理和演算部の出力を入力して公開鍵の数を判断する第１公開鍵リスト数判断部を有し、
更に、任意にｎ−ｋ個の乱数ａj を設定する乱数生成部、乱数生成部の設定したｎ−ｋ個の乱数ａj を入力すると共に第１排他的論理和演算部のｋ個の演算結果ａj＝ｃj◎ｙj を入力してα0 ＝Ｈ0（ａ1、・・・・、ａn）を得る第３ハッシュ演算部、第３ハッシュ演算部の出力であるα0および第１ｋ次多項式点設定部の出力であるｋ個の（ｊ、ｆ（ｊ））を入力としてｋ次多項式ｆ（ｗ）を設定するｋ次多項式設定部を有する公開鍵秘密鍵生成装置を具備し、
送信されてきた（ａ1，…，ａn）を入力してα0＝Ｈ0（ａ1，…，ａn）を設定する第４ハッシュ演算部、設定されたα0 と送信されてきたｋ個の（α1，…，αk）の合計ｋ＋１個のαによりｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkを一意的に設定するｋ次多項式演算部、ｋ次多項式からｆ（ｊ）を計算するｋ次多項式点演算部、ｃj＝Ｈj（ｆ（ｊ））を計算する第２ハッシュ演算部、第２ハッシュ演算部により得られたｃj＝Ｈj（ｆ（ｊ））を入力すると共に送信されてきた（ａ1，…，ａn）を入力して排他的論理和演算を実行し、ｙj＝ｃj◎ａjを計算する第２排他的論理和演算部、排他的論理和演算により計算された値ｙjおよび送信する平文を入力して暗号文を生成する暗号文生成部より成る暗号文生成装置を具備し、
暗号文選別部と暗号文復号部とより成る復号装置を具備する、
ことを特徴とする紛失通信路構成装置。
【請求項６】
Ｇjを位数ｑjの可換群とし、ｘ∈Ｚqjに対してＧj（ｘ）はインデックスがｘである様なＧjの元を表すものとし、秘密鍵ｘj∈Ｚqjに対して、ｙj＝Ｇj（ｘj）なるｙjおよびＧjを離散対数型公開鍵とし、Ｈjを入力域がＺpであって出力域がＺqである一方向性ハッシュ関数とし、或るｋ個の公開鍵に対応する秘密鍵ｘj を使用してｎ個の暗号化された送信情報からｋ個を復号して平文情報を得る紛失通信路構成装置において、
秘密鍵ｘjを任意に設定すると共にこれらに対応する離散対数の公開鍵ｙjを設定する公開鍵秘密鍵生成部、ｋ次多項式ｆ（ｗ）を満足する点としてｋ個の値ｆ（ｊ）を設定する第１ｋ次多項式点設定部、第１ｋ次多項式点設定部により設定されたｋ次多項式上の点の値ｆ（ｊ）を入力してそのハッシュ演算出力値ｃj＝Ｈj（ｆ（ｊ））を計算する第１ハッシュ演算部、第１ハッシュ演算部から出力されるハッシュ演算出力ｃj＝Ｈj（ｆ（ｊ））を入力すると共に第１ｋ次多項式点設定部により設定された公開鍵ｙjを入力して排他的論理和ａj＝ｃj◎ｙj を得る第１排他的論理和演算部、第１排他的論理和演算部の出力を入力して公開鍵の数を判断する第１公開鍵リスト数判断部を有し、
更に、任意にｎ−ｋ個の乱数ａj を設定する乱数生成部、乱数生成部の設定したｎ−ｋ個の乱数ａj を入力すると共に第１排他的論理和演算部のｋ個の演算結果ａj＝ｃj◎ｙj を入力してα0 ＝Ｈ0（ａ1、・・・・、ａn）を得る第３ハッシュ演算部、第３ハッシュ演算部の出力であるα0および第１ｋ次多項式点設定部の出力であるｋ個の（ｊ、ｆ（ｊ））を入力としてｋ次多項式ｆ（ｗ）を設定するｋ次多項式設定部を有する公開鍵秘密鍵生成装置を具備し、
送信されてきたｋ＋１個の（α0，…，αk）の合計ｋ＋１個のαによりｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkを一意的に設定するｋ次多項式演算部、ｋ次多項式からｆ（ｊ）を計算するｋ次多項式点演算部、ｃj＝Ｈj（ｆ（ｊ））を計算する第２ハッシュ演算部、第２ハッシュ演算部により得られたｃj＝Ｈj（ｆ（ｊ））を入力すると共に送信されてきた（ａ1，…，ａn）を入力して排他的論理和演算を実行し、ｙj＝ｃj◎ａjを計算する第２排他的論理和演算部、排他的論理和演算により計算された値ｙjおよび送信する平文を入力して暗号文を生成する暗号文生成部より成る暗号文生成装置を具備し、
暗号文選別部と暗号文復号部とより成る復号装置を具備する、
ことを特徴とする紛失通信路構成装置。
【請求項７】
請求項５に記載される紛失通信路構成装置において、
公開鍵秘密鍵生成装置は、更に、ｋ次多項式ｆ（ｗ）からｆ（ｊ）を設定する第２ｋ次多項式点設定部、値ｆ（ｊ）にハッシュ演算を施しｃj＝Ｈ（ｆ（ｊ））を計算する第２ハッシュ演算部、第２ハッシュ演算部の演算結果を入力すると共に乱数生成部からｎ−ｋ個の乱数ａj を入力して論理和演算を実行する第２排他的論理和演算部、第２排他的論理和演算部の出力を入力して公開鍵の数を判断する第２公開鍵リスト数判断部を有する、
ことを特徴とする紛失通信路構成装置。
【請求項８】
請求項６に記載される紛失通信路構成装置において、
公開鍵秘密鍵生成装置は、更に、ｋ次多項式ｆ（ｗ）からｆ（ｊ）を設定する第２ｋ次多項式点設定部、値ｆ（ｊ）にハッシュ演算を施しｃj＝Ｈ（ｆ（ｊ））を計算する第２ハッシュ演算部、第２ハッシュ演算部の演算結果を入力すると共に乱数生成部からｎ−ｋ個の乱数ａj を入力して論理和演算を実行する第２排他的論理和演算部、第２排他的論理和演算部の出力を入力して公開鍵の数を判断する第２公開鍵リスト数判断部を有する、
ことを特徴とする紛失通信路構成装置。
【請求項９】
受信者に対して、ｋ個の秘密鍵公開鍵のペア（ｙj，ｘj）を任意に設定し、ｋ次多項式の上の点としてｋ個の値ｆ（ｊ）を任意に設定し、ｃj＝Ｈj（ｆ（ｊ））を計算し、ｋ個のａj＝ｃj◎ｙjを求め、ｎ−ｋ個の残りのａjを任意に設定し、α0 ＝Ｈ0（ａ1、・・・・、ａn）により求められたα0 およびｋ個の任意に設定した点（ｊ、ｆ（ｊ））の合計したｋ＋１個の点を使用し、ｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗk を求め、（ａ1，…，ａn，α1，…，αk）を送信者へ渡す指令をし、
送信者に対して、送られてきた（ａ1，…，ａn，α1，…，αk）から、α0 ＝Ｈ0（ａ1、・・・・、ａn）と、ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗk と、ｙj＝Ｈ（ｆ（ｊ））◎ａj  とを求め、これにより公開鍵（ｙ1，…，ｙn）を求め、求めたｎ個の公開鍵を用いて送信するｎ個の秘密情報を暗号化し、ｎ個の暗号文を生成し、生成したｎ個の暗号文を受信者に送信する指令をし、
受信者に対して、受信した暗号文ｎ個の内の、自分が秘密鍵を知っているｋ個について、復号し、秘密情報ｍi をｋ個入手すべき指令を、
コンピュータに対してする紛失通信路構成プログラム。
【請求項１０】
受信者に対して、ｋ個の秘密鍵公開鍵のペア（ｙj，ｘj）を任意に設定し、ｋ次多項式の上の点としてｋ個の値ｆ（ｊ）を任意に設定し、ｃj＝Ｈj（ｆ（ｊ））を計算し、ｋ個のａj＝ｃj◎ｙjを求め、ｎ−ｋ個の残りのａjを任意に設定し、ｆ（０）＝Ｈ0（ａ1，…，ａn）＝α0を計算し、このα0とｋ個の任意に設定した点（ｊ、ｆ（ｊ））の合計したｋ＋１個の点を使用してｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkを求め、（ａ1，…，ａn，α0，…，αk）を送信者へ渡す指令をし、
送信者に対して、送られてきた（ａ1，…，ａn，α0，…，αk）から、ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗk と、ｙj＝ｆ（ｊ）◎ａj  とを求め、これによりｎ個の公開鍵（ｙ1，…，ｙn）を求め、送信者は求めたｎ個の公開鍵（ｙ1，…，ｙn）を用いて送信するｎ個の秘密情報を暗号化し、ｎ個の暗号文を生成し、生成したｎ個の暗号文を受信者に送信する指令をし、
受信者に対して、受信した暗号文ｎ個の内の、自分が秘密鍵を知っているｋ個について、復号し、秘密情報をｋ個入手すべき指令を、
コンピュータに対してする紛失通信路構成プログラム。
【請求項１１】
請求項９に記載される紛失通信路構成プログラムにおいて、
受信者に対して、更に、ｎ−ｋ個の残りのｆ（ｊ）をｋ次多項式から求め、ｃj＝Ｈj（ｆ（ｊ））を計算し、ｎ−ｋ個のｙj＝ｃj◎ａjを計算し、秘密鍵を知っているｋ個の公開鍵と秘密鍵を知らないｎ−ｋ個の公開鍵（ｙ1，…，ｙn）を設定すべき指令を、
コンピュータに対してする紛失通信路構成プログラム。
【請求項１２】
請求項１０に記載される紛失通信路構成プログラムにおいて、
受信者に対して、更に、ｎ−ｋ個の残りのｆ（ｊ）をｋ次多項式から求め、ｃj＝Ｈj（ｆ（ｊ））を計算し、ｎ−ｋ個のｙj＝ｃj◎ａjを計算し、秘密鍵を知っているｋ個の公開鍵と秘密鍵を知らないｎ−ｋ個の公開鍵（ｙ1、・・・・、ｙn ）を設定すべき指令を、
コンピュータに対してする紛失通信路構成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、紛失通信路構成方法、この方法を実施する装置、プログラムに関し、特に、暗号通信に用いる公開鍵の生成が比較的に簡易であり、通信量、計算量を低く抑えた効率的な紛失通信路構成方法、この方法を実施する装置、プログラムに関する。
【背景技術】
【０００２】
送信側装置（送信者）から受信側装置（受信者）にｎ個の秘密情報を暗号化して送信し、受信者はこれら暗号化されたｎ個の秘密情報の内のｋ個を復号化して入手するが、送信者は何れの秘密情報が受信者により入手されたかを特定することができない紛失通信路構成方法が開発されている。この紛失通信路構成方法の従来技術として、Bellare他による紛失通信路構成方法が知られている（非特許文献１  参照）。
【非特許文献１】Bellare，Rivest“Translucent Cryptography-An Alternative too Key Escrow，and its Implementation via Fractional Oblivious Transfer”，Journal of Cryptology，vol.12,No.2,pp.117-140，Springer-Verlag 1999。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上述の紛失通信路構成方法の従来例は、全体構成が複雑であり、通信量も冗長性を保つ必要上、通信量および計算量共に多くなり、非効率的な構成となっている。
この発明は、ｋ次多項式から求めた離散対数型の公開鍵を用いることにより、受信者Ｂがｋ個以上の公開鍵に対応する秘密鍵を知り得ないことを、送信者Ａは納得することができることにより、送信者の持つｎ個の秘密情報の内の何れの秘密情報を受信者が得たかを送信者に特定されることなくｋ個の秘密情報を受信者が入手することのできる、上述の問題を解消した紛失通信路構成方法、この方法を実施する装置、プログラムを提供するものである。
【課題を解決するための手段】
【０００４】
請求項１：Ｇjを位数ｑjの可換群とし、ｘ∈Ｚqjに対してＧj（ｘ）はインデックスがｘである様なＧjの元を表すものとし、秘密鍵ｘj∈Ｚqjに対して、ｙj＝Ｇj（ｘj）なるｙjおよびＧjを離散対数型公開鍵とし、Ｈjを入力域がＺpであって出力域がＺqである一方向性ハッシュ関数とし、或るｋ個の公開鍵に対応する秘密鍵ｘj を使用してｎ個の暗号化された送信情報からｋ個を復号して平文情報を得る紛失通信路構成方法において、
秘密鍵ｘjを任意に設定すると共にこれらに対応する離散対数の公開鍵ｙj＝ｇxjを設定する公開鍵秘密鍵生成部１、ｋ次多項式ｆ（ｗ）を満足する点としてｋ個の値ｆ（ｊ）をｋ個設定する第１ｋ次多項式点設定部２、第１ｋ次多項式点設定部２により設定された値ｆ（ｊ）を入力してそのハッシュ演算出力値ｃj＝Ｈj（ｆ（ｊ））を計算する第１ハッシュ演算部３、第１ハッシュ演算部３から出力されるハッシュ演算出力ｃj＝Ｈj（ｆ（ｊ））を入力すると共に第１ｋ次多項式点設定部２により設定された公開鍵ｙjを入力して排他的論理和ａj＝ｃj◎ｙj を得る第１排他的論理和演算部４、第１排他的論理和演算部４の出力を入力して公開鍵の数を判断する第１公開鍵リスト数判断部５を有し、
更に、任意にｎ−ｋ個の乱数ａj を設定する乱数生成部６、乱数生成部６の設定したｎ−ｋ個の乱数ａj を入力すると共に第１排他的論理和演算部４のｋ個の演算結果ａj＝ｃj◎ｙj を入力してα0 ＝Ｈ0（ａ1、・・・・、ａn）を得る第３ハッシュ演算部２２、第３ハッシュ演算部２２の出力であるα0および第１ｋ次多項式点設定部２の出力であるｋ個の（ｊ、ｆ（ｊ））を入力としてｋ次多項式ｆ（ｗ）を設定するｋ次多項式設定部７を有する公開鍵秘密鍵生成装置を具備し、
送信されてきた（ａ1，…，ａn）を入力してα0＝Ｈ0（ａ1，…，ａn）を設定する第４ハッシュ演算部２２’、設定されたα0 と送信されてきたｋ個の（α1，…，αk）の合計ｋ＋１個のαによりｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkを一意的に設定するｋ次多項式演算部７’、ｋ次多項式からｆ（ｊ）を計算するｋ次多項式点演算部８’、ｃj＝Ｈj（ｆ（ｊ））を計算する第２ハッシュ演算部９’、第２ハッシュ演算部９’により得られたｃj＝Ｈj（ｆ（ｊ））を入力すると共に送信されてきた（ａ1，…，ａn）を入力して排他的論理和演算を実行し、ｙj＝ｃj◎ａjを計算する第２排他的論理和演算部１０’、排他的論理和演算により計算された値ｙjおよび送信する平文を入力して暗号文を生成する暗号文生成部２１より成る暗号文生成装置を具備し、
暗号文選別部３１と暗号文復号部３２とより成る復号装置を具備し、ここで、
Ｓｔｅｐ１：受信者Ｂは、
・ｋ個の秘密鍵公開鍵のペア（ｙj，ｘj）を任意に設定し、
・ｋ次多項式の上の点としてｋ個の値ｆ（ｊ）を任意に設定し、ｃj＝Ｈj（ｆ（ｊ））を計算し、
・ｋ個のａj＝ｃj◎ｙjを求め、
・ｎ−ｋ個の残りのａjを任意に設定し、
・α0 ＝Ｈ0（ａ1、・・・・、ａn）により求められたα0 およびｋ個の任意に設定した点（ｊ、ｆ（ｊ））を合計したｋ＋１個の点を使用し、ｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗk を一意に求め、
・（ａ1，…，ａn，α1，…，αk）を送信者Ａへ渡し、
Ｓｔｅｐ２：送信者Ａは、
送られてきた（ａ1，…，ａn，α1，…，αk）から、α0 ＝Ｈ0（ａ1、・・・・、ａn）と、ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗk と、ｙj＝Ｈ（ｆ（ｊ））◎ａj  とを求め、これにより公開鍵（ｙ1，…，ｙn）を求め、
・送信者Ａは求めたｎ個の公開鍵を用いて、送信するｎ個の秘密情報を暗号化し、ｎ個の暗号文を生成し、
・生成したｎ個の暗号文を受信者Ｂに送信し、
Ｓｔｅｐ３：受信者Ｂは、
・受信した暗号文ｎ個の内の、自分が秘密鍵を知っているｋ個について、復号し、秘密情報ｍi をｋ個入手し、
ｎ個の秘密情報ｍj の内の、何れかｋ個の秘密情報を、送信者Ａから受信者Ｂにｎ個の秘密情報の内の何れを受信者Ｂが得られたかを匿名にし更に、送信者Ａは受信者Ｂがｋ個以上の秘密鍵を知り得ないことが確信できる公開鍵を用いて行う紛失通信路の構成を実行する紛失通信路構成方法を構成した。
【０００５】
請求項２：Ｇjを位数ｑjの可換群とし、ｘ∈Ｚqjに対してＧj（ｘ）はインデックスがｘである様なＧjの元を表すものとし、秘密鍵ｘj∈Ｚqjに対して、ｙj＝Ｇj（ｘj）なるｙjおよびＧjを離散対数型公開鍵とし、Ｈjを入力域がＺpであって出力域がＺqである一方向性ハッシュ関数とし、或るｋ個の公開鍵に対応する秘密鍵ｘj を使用してｎ個の暗号化された送信情報からｋ個を復号して平文情報を得る紛失通信路構成方法において、
秘密鍵ｘjを任意に設定すると共にこれらに対応する離散対数の公開鍵ｙjを設定する公開鍵秘密鍵生成部１、ｋ次多項式ｆ（ｗ）を満足する点としてｋ個の値ｆ（ｊ）を設定する第１ｋ次多項式点設定部２、第１ｋ次多項式点設定部２により設定されたｋ次多項式上の点の値ｆ（ｊ）を入力してそのハッシュ演算出力値ｃj＝Ｈj（ｆ（ｊ））を計算する第１ハッシュ演算部３、第１ハッシュ演算部３から出力されるハッシュ演算出力ｃj＝Ｈj（ｆ（ｊ））を入力すると共に第１ｋ次多項式点設定部２により設定された公開鍵ｙjを入力して排他的論理和ａj＝ｃj◎ｙj を得る第１排他的論理和演算部４、第１排他的論理和演算部４の出力を入力して公開鍵の数を判断する第１公開鍵リスト数判断部５を有し、
更に、任意にｎ−ｋ個の乱数ａj を設定する乱数生成部６、乱数生成部６の設定したｎ−ｋ個の乱数ａj を入力すると共に第１排他的論理和演算部４のｋ個の演算結果ａj＝ｃj◎ｙj を入力してα0 ＝Ｈ0（ａ1、・・・・、ａn）を得る第３ハッシュ演算部２２、第３ハッシュ演算部２２の出力であるα0および第１ｋ次多項式点設定部２の出力であるｋ個の（ｊ、ｆ（ｊ））を入力としてｋ次多項式ｆ（ｗ）を設定するｋ次多項式設定部７を有する公開鍵秘密鍵生成装置を具備し、
送信されてきたｋ＋１個の（α0，…，αk）の合計ｋ＋１個のαによりｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkを一意的に設定するｋ次多項式演算部７’、ｋ次多項式からｆ（ｊ）を計算するｋ次多項式点演算部８’、ｃj＝Ｈj（ｆ（ｊ））を計算する第２ハッシュ演算部９’、第２ハッシュ演算部９’により得られたｃj＝Ｈj（ｆ（ｊ））を入力すると共に送信されてきた（ａ1，…，ａn）を入力して排他的論理和演算を実行し、ｙj＝ｃj◎ａjを計算する第２排他的論理和演算部１０’、排他的論理和演算により計算された値ｙjおよび送信する平文を入力して暗号文を生成する暗号文生成部２１より成る暗号文生成装置を具備し、
暗号文選別部３１と暗号文復号部３２とより成る復号装置を具備し、ここで、
Ｓｔｅｐ１：受信者Ｂは、
・ｋ個の秘密鍵公開鍵のペア（ｙj，ｘj）を任意に設定し、
・ｋ次多項式の上の点としてｋ個の値ｆ（ｊ）を任意に設定し、ｃj＝Ｈj（ｆ（ｊ））を計算し、
・ｋ個のａj＝ｃj◎ｙjを求め、
・ｎ−ｋ個の残りのａjを任意に設定し、
・ｆ（０）＝Ｈ0（ａ1，…，ａn）＝α0を計算し、このα0とｋ個の任意に設定した点（ｊ、ｆ（ｊ））を合計したｋ＋１個の点を使用してｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkを求め、
・（ａ1，…，ａn，α0，…，αk）を送信者Ａへ渡し、
Ｓｔｅｐ２：送信者Ａは、
送られてきた（ａ1，…，ａn，α0，…，αk）から、ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗk と、ｙj＝Ｈ（ｆ（ｊ））◎ａj  とを求め、これにより公開鍵（ｙ1，…，ｙn）を求め、
・送信者Ａは求めたｎ個の公開鍵を用いて、送信するｎ個の秘密情報を暗号化し、ｎ個の暗号文を生成し、
・生成したｎ個の暗号文を受信者Ｂに送信し、
Ｓｔｅｐ３：受信者Ｂは、
・受信した暗号文ｎ個の内の、自分が秘密鍵を知っているｋ個について、復号し、秘密情報をｋ個入手し、
ｎ個の秘密情報の内の、何れかｋ個の秘密情報ｍj を、送信者Ａから受信者Ｂにｎ個の秘密情報の内の何れを受信者Ｂが得られたかを匿名にし更に、送信者Ａは受信者Ｂがｋ個以上の秘密鍵を知り得ないことが確信できる公開鍵を用いて行う紛失通信路の構成を実行する紛失通信路構成方法を構成した。
【０００６】
請求項３：請求項１に記載される紛失通信路構成方法において、
公開鍵秘密鍵生成装置は、更に、ｋ次多項式ｆ（ｗ）からｆ（ｊ）を設定する第２ｋ次多項式点設定部８、値ｆ（ｊ）にハッシュ演算を施しｃj＝Ｈ（ｆ（ｊ））を計算する第２ハッシュ演算部９、第２ハッシュ演算部９の演算結果を入力すると共に乱数生成部６からｎ−ｋ個の乱数ａj を入力して論理和演算を実行する第２排他的論理和演算部１０、第２排他的論理和演算部１０の出力を入力して公開鍵の数を判断する第２公開鍵リスト数判断部１１を有し、
Ｓｔｅｐ１において、受信者Ｂは、更に、
・ｎ−ｋ個の残りのｆ（ｊ）をｋ次多項式から求め、ｃj＝Ｈj（ｆ（ｊ））を計算し、
・ｎ−ｋ個のｙj＝ｃj◎ａjを計算し、
・秘密鍵を知っているｋ個の公開鍵と秘密鍵を知らないｎ−ｋ個の公開鍵（ｙ1，…，ｙn）を設定する、
紛失通信路構成方法を構成した。
【０００７】
請求項４：請求項２に記載される紛失通信路構成方法において、
公開鍵秘密鍵生成装置は、更に、ｋ次多項式ｆ（ｗ）からｆ（ｊ）を設定する第２ｋ次多項式点設定部８、値ｆ（ｊ）にハッシュ演算を施しｃj＝Ｈ（ｆ（ｊ））を計算する第２ハッシュ演算部９、第２ハッシュ演算部９の演算結果を入力すると共に乱数生成部６からｎ−ｋ個の乱数ａj を入力して論理和演算を実行する第２排他的論理和演算部１０、第２排他的論理和演算部１０の出力を入力して公開鍵の数を判断する第２公開鍵リスト数判断部１１を有し、
Ｓｔｅｐ１において、受信者Ｂは、更に、
・ｎ−ｋ個の残りのｆ（ｊ）をｋ次多項式から求め、ｃj＝Ｈj（ｆ（ｊ））を計算し、
・ｎ−ｋ個のｙj＝ｃj◎ａjを計算し、
・秘密鍵を知っているｋ個の公開鍵と秘密鍵を知らないｎ−ｋ個の公開鍵（ｙ1、・・・・、ｙn ）を設定する、
紛失通信路構成方法を構成した。
【０００８】
そして、請求項５：Ｇjを位数ｑjの可換群とし、ｘ∈Ｚqjに対してＧj（ｘ）はインデックスがｘである様なＧjの元を表すものとし、秘密鍵ｘj∈Ｚqjに対して、ｙj＝Ｇj（ｘj）なるｙjおよびＧjを離散対数型公開鍵とし、Ｈjを入力域がＺpであって出力域がＺqである一方向性ハッシュ関数とし、或るｋ個の公開鍵に対応する秘密鍵ｘj を使用してｎ個の暗号化された送信情報からｋ個を復号して平文情報を得る紛失通信路構成装置において、
秘密鍵ｘjを任意に設定すると共にこれらに対応する離散対数の公開鍵ｙj＝ｇxjを設定する公開鍵秘密鍵生成部１、ｋ次多項式ｆ（ｗ）を満足する点としてｋ個の値ｆ（ｊ）をｋ個設定する第１ｋ次多項式点設定部２、第１ｋ次多項式点設定部２により設定された値ｆ（ｊ）を入力してそのハッシュ演算出力値ｃj＝Ｈj（ｆ（ｊ））を計算する第１ハッシュ演算部３、第１ハッシュ演算部３から出力されるハッシュ演算出力ｃj＝Ｈj（ｆ（ｊ））を入力すると共に第１ｋ次多項式点設定部２により設定された公開鍵ｙjを入力して排他的論理和ａj＝ｃj◎ｙj を得る第１排他的論理和演算部４、第１排他的論理和演算部４の出力を入力して公開鍵の数を判断する第１公開鍵リスト数判断部５を有し、
更に、任意にｎ−ｋ個の乱数ａj を設定する乱数生成部６、乱数生成部６の設定したｎ−ｋ個の乱数ａj を入力すると共に第１排他的論理和演算部４のｋ個の演算結果ａj＝ｃj◎ｙj を入力してα0 ＝Ｈ0（ａ1、・・・・、ａn）を得る第３ハッシュ演算部２２、第３ハッシュ演算部２２の出力であるα0および第１ｋ次多項式点設定部２の出力であるｋ個の（ｊ、ｆ（ｊ））を入力としてｋ次多項式ｆ（ｗ）を設定するｋ次多項式設定部７を有する公開鍵秘密鍵生成装置を具備し、
送信されてきた（ａ1，…，ａn）を入力してα0＝Ｈ0（ａ1，…，ａn）を設定する第４ハッシュ演算部２２’、設定されたα0 と送信されてきたｋ個の（α1，…，αk）の合計ｋ＋１個のαによりｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkを一意的に設定するｋ次多項式演算部７’、ｋ次多項式からｆ（ｊ）を計算するｋ次多項式点演算部８’、ｃj＝Ｈj（ｆ（ｊ））を計算する第２ハッシュ演算部９’、第２ハッシュ演算部９’により得られたｃj＝Ｈj（ｆ（ｊ））を入力すると共に送信されてきた（ａ1，…，ａn）を入力して排他的論理和演算を実行し、ｙj＝ｃj◎ａjを計算する第２排他的論理和演算部１０’、排他的論理和演算により計算された値ｙjおよび送信する平文を入力して暗号文を生成する暗号文生成部２１より成る暗号文生成装置を具備し、
暗号文選別部３１と暗号文復号部３２とより成る復号装置を具備する、
紛失通信路構成装置を構成した。
【０００９】
請求項６：Ｇjを位数ｑjの可換群とし、ｘ∈Ｚqjに対してＧj（ｘ）はインデックスがｘである様なＧjの元を表すものとし、秘密鍵ｘj∈Ｚqjに対して、ｙj＝Ｇj（ｘj）なるｙjおよびＧjを離散対数型公開鍵とし、Ｈjを入力域がＺpであって出力域がＺqである一方向性ハッシュ関数とし、或るｋ個の公開鍵に対応する秘密鍵ｘj を使用してｎ個の暗号化された送信情報からｋ個を復号して平文情報を得る紛失通信路構成装置において、
秘密鍵ｘjを任意に設定すると共にこれらに対応する離散対数の公開鍵ｙjを設定する公開鍵秘密鍵生成部１、ｋ次多項式ｆ（ｗ）を満足する点としてｋ個の値ｆ（ｊ）を設定する第１ｋ次多項式点設定部２、第１ｋ次多項式点設定部２により設定されたｋ次多項式上の点の値ｆ（ｊ）を入力してそのハッシュ演算出力値ｃj＝Ｈj（ｆ（ｊ））を計算する第１ハッシュ演算部３、第１ハッシュ演算部３から出力されるハッシュ演算出力ｃj＝Ｈj（ｆ（ｊ））を入力すると共に第１ｋ次多項式点設定部２により設定された公開鍵ｙjを入力して排他的論理和ａj＝ｃj◎ｙj を得る第１排他的論理和演算部４、第１排他的論理和演算部４の出力を入力して公開鍵の数を判断する第１公開鍵リスト数判断部５を有し、
更に、任意にｎ−ｋ個の乱数ａj を設定する乱数生成部６、乱数生成部６の設定したｎ−ｋ個の乱数ａj を入力すると共に第１排他的論理和演算部４のｋ個の演算結果ａj＝ｃj◎ｙj を入力してα0 ＝Ｈ0（ａ1、・・・・、ａn）を得る第３ハッシュ演算部２２、第３ハッシュ演算部２２の出力であるα0および第１ｋ次多項式点設定部２の出力であるｋ個の（ｊ、ｆ（ｊ））を入力としてｋ次多項式ｆ（ｗ）を設定するｋ次多項式設定部７を有する公開鍵秘密鍵生成装置を具備し、
送信されてきたｋ＋１個の（α0，…，αk）の合計ｋ＋１個のαによりｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkを一意的に設定するｋ次多項式演算部７’、ｋ次多項式からｆ（ｊ）を計算するｋ次多項式点演算部８’、ｃj＝Ｈj（ｆ（ｊ））を計算する第２ハッシュ演算部９’、第２ハッシュ演算部９’により得られたｃj＝Ｈj（ｆ（ｊ））を入力すると共に送信されてきた（ａ1，…，ａn）を入力して排他的論理和演算を実行し、ｙj＝ｃj◎ａjを計算する第２排他的論理和演算部１０’、排他的論理和演算により計算された値ｙjおよび送信する平文を入力して暗号文を生成する暗号文生成部２１より成る暗号文生成装置を具備し、
暗号文選別部３１と暗号文復号部３２とより成る復号装置を具備する、
紛失通信路構成装置を構成した。
【００１０】
請求項７：請求項５に記載される紛失通信路構成装置において、
公開鍵秘密鍵生成装置は、更に、ｋ次多項式ｆ（ｗ）からｆ（ｊ）を設定する第２ｋ次多項式点設定部８、値ｆ（ｊ）にハッシュ演算を施しｃj＝Ｈ（ｆ（ｊ））を計算する第２ハッシュ演算部９、第２ハッシュ演算部９の演算結果を入力すると共に乱数生成部６からｎ−ｋ個の乱数ａj を入力して論理和演算を実行する第２排他的論理和演算部１０、第２排他的論理和演算部１０の出力を入力して公開鍵の数を判断する第２公開鍵リスト数判断部１１を有する、
紛失通信路構成装置を構成した。
【００１１】
請求項８：請求項６に記載される紛失通信路構成装置において、
公開鍵秘密鍵生成装置は、更に、ｋ次多項式ｆ（ｗ）からｆ（ｊ）を設定する第２ｋ次多項式点設定部８、値ｆ（ｊ）にハッシュ演算を施しｃj＝Ｈ（ｆ（ｊ））を計算する第２ハッシュ演算部９、第２ハッシュ演算部９の演算結果を入力すると共に乱数生成部６からｎ−ｋ個の乱数ａj を入力して論理和演算を実行する第２排他的論理和演算部１０、第２排他的論理和演算部１０の出力を入力して公開鍵の数を判断する第２公開鍵リスト数判断部１１を有する、
紛失通信路構成装置を構成した。
【００１２】
また、請求項９：受信者Ｂに対して、ｋ個の秘密鍵公開鍵のペア（ｙj，ｘj）を任意に設定し、ｋ次多項式の上の点としてｋ個の値ｆ（ｊ）を任意に設定し、ｃj＝Ｈj（ｆ（ｊ））を計算し、ｋ個のａj＝ｃj◎ｙjを求め、ｎ−ｋ個の残りのａjを任意に設定し、α0 ＝Ｈ0（ａ1、・・・・、ａn）により求められたα0 およびｋ個の任意に設定した点（ｊ、ｆ（ｊ））の合計したｋ＋１個の点を使用し、ｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗk を求め、（ａ1，…，ａn，α1，…，αk）を送信者Ａへ渡す指令をし、
送信者Ａに対して、送られてきた（ａ1，…，ａn，α1，…，αk）から、α0 ＝Ｈ0（ａ1、・・・・、ａn）と、ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗk と、ｙj＝Ｈ（ｆ（ｊ））◎ａj  とを求め、これにより公開鍵（ｙ1，…，ｙn）を求め、求めたｎ個の公開鍵を用いて送信するｎ個の秘密情報を暗号化し、ｎ個の暗号文を生成し、生成したｎ個の暗号文を受信者Ｂに送信する指令をし、
受信者Ｂに対して、受信した暗号文ｎ個の内の、自分が秘密鍵を知っているｋ個について、復号し、秘密情報ｍi をｋ個入手すべき指令を、
コンピュータに対してする紛失通信路構成プログラムを構成した。
【００１３】
請求項１０：受信者Ｂに対して、ｋ個の秘密鍵公開鍵のペア（ｙj，ｘj）を任意に設定し、ｋ次多項式の上の点としてｋ個の値ｆ（ｊ）を任意に設定し、ｃj＝Ｈj（ｆ（ｊ））を計算し、ｋ個のａj＝ｃj◎ｙjを求め、ｎ−ｋ個の残りのａjを任意に設定し、ｆ（０）＝Ｈ0（ａ1，…，ａn）＝α0を計算し、このα0とｋ個の任意に設定した点（ｊ、ｆ（ｊ））の合計したｋ＋１個の点を使用してｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkを求め、（ａ1，…，ａn，α0，…，αk）を送信者Ａへ渡す指令をし、
送信者Ａに対して、送られてきた（ａ1，…，ａn，α0，…，αk）から、ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗk と、ｙj＝ｆ（ｊ）◎ａj  とを求め、これによりｎ個の公開鍵（ｙ1，…，ｙn）を求め、送信者Ａは求めたｎ個の公開鍵（ｙ1，…，ｙn）を用いて送信するｎ個の秘密情報を暗号化し、ｎ個の暗号文を生成し、生成したｎ個の暗号文を受信者Ｂに送信する指令をし、
受信者Ｂに対して、受信した暗号文ｎ個の内の、自分が秘密鍵を知っているｋ個について、復号し、秘密情報をｋ個入手すべき指令を、
コンピュータに対してする紛失通信路構成プログラムを構成した。
【００１４】
請求項１１：請求項９に記載される紛失通信路構成プログラムにおいて、
受信者Ｂに対して、更に、ｎ−ｋ個の残りのｆ（ｊ）をｋ次多項式から求め、ｃj＝Ｈj（ｆ（ｊ））を計算し、ｎ−ｋ個のｙj＝ｃj◎ａjを計算し、秘密鍵を知っているｋ個の公開鍵と秘密鍵を知らないｎ−ｋ個の公開鍵（ｙ1，…，ｙn）を設定すべき指令を、
コンピュータに対してする紛失通信路構成プログラムを構成した。
請求項１２：請求項１０に記載される紛失通信路構成プログラムにおいて、
受信者Ｂに対して、更に、ｎ−ｋ個の残りのｆ（ｊ）をｋ次多項式から求め、ｃj＝Ｈj（ｆ（ｊ））を計算し、ｎ−ｋ個のｙj＝ｃj◎ａjを計算し、秘密鍵を知っているｋ個の公開鍵と秘密鍵を知らないｎ−ｋ個の公開鍵（ｙ1、・・・・、ｙn ）を設定すべき指令を、
コンピュータに対してする紛失通信路構成プログラムを構成した。
【発明の効果】
【００１５】
この発明に依れば、受信者Ｂが送信者Ａに対して一般の伝送経路を介して（ａ1，…，ａn，α1，…，αk）を送ることで、送信者Ａは自らｎ個の公開鍵をｙj＝Ｈj（ｆ（ｊ））◎ａjとして求めることができるので、送信者Ａに対して公開鍵を送信する必要はなく、
そして、送信者Ａは、離散対数型の公開鍵をα0＝Ｈ0（ａ1，ａ2，…，ａn）を多項式上の点に持つｋ次多項式上の点から一意に定まる形で求めていることにより、受信者Ｂがｋ個以上の公開鍵に対応する秘密鍵を知り得ないことを納得することができるので、更に、何れの公開鍵も、同様の手順により求めることにより、受信者が秘密鍵を知っている公開鍵が何れであるかを見分けることができない仕組みが構成され、従来通信コストが非効率であったのに対して、効率的な紛失通信路を構成することができるという効果を奏す。
【発明を実施するための最良の形態】
【００１６】
Ｇjを可換群とし、その位数をｑjとする。Ｇj（ｘ）はインデックスがｘ∈ＺqjであるようなＧjの元を表すものとする。また、Ｇj（ｘ）はｘからそのような元を計算する行為をも表すものとする。ｙj＝Ｇj（ｘj）とし、ｙj，Ｇjを公開鍵、ｘjを秘密鍵とする。
Ｌを、上記公開鍵（ｙj，Ｇj）を合計ｎ個含む公開鍵のリストとする。これらｎ個の公開鍵の内のｋ個についてのみ、秘密鍵を知っている公開鍵として設定し、残りのｎ−ｋ個については、秘密鍵を知らない公開鍵として以下の様に構成する。
受信者Ｂは、ｋ個の公開鍵（ｙj，Ｇj）を秘密鍵ｘjと対応させて、ｋ個の秘密鍵公開鍵のペア（ｙj，ｘj）を任意に設定する。次に、ｋ次多項式を満足する点として、ｋ個の値ｆ（ｊ）を任意に設定する。そして、ｋ個の値ｆ（ｊ）のハッシュ演算出力値ｃj＝Ｈj（ｆ（ｊ））を求める。求めたｃj およびｙj からｋ個のａj＝ｙj◎ｃjを求める。但し、◎は排他的論理和演算を意味し、ａj はｙj とｃj の排他的論理和演算結果である。
【００１７】
ここで、残りのｎ−ｋ個の秘密鍵を知らない公開鍵を設定する。これには、先ず、乱数生成部６から任意にｎ−ｋ個の乱数ａjを選択する。そして、ハッシュ演算部に（ａ1，ａ2，…，ａn）を入力することにより、α0＝ｆ（０）＝Ｈ0（ａ1，ａ2，…，ａn）を求める。求めた値ｆ（０）とｋ個の値ｆ（ｊ）の合計ｋ＋１個の値からｋ次多項式、ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkが一意に求まる。求めたｋ次多項式ｆ（ｗ）から、未だ未設定であったｋ次多項式ｆ（ｗ）を満足する点として、ｎ−ｋ個の値ｆ（ｊ）を求め、ｎ−ｋ個のｃj＝Ｈj（ｆ（ｊ））を求める。求めたｎ−ｋ個のｃjとａjとから、ｎ−ｋ個のｙj＝ａj◎ｃjを秘密鍵を知らない公開鍵として設定することができる。送信者は、受信者から送られてきた（ａ1，…，ａn，α1，…，αk）から、α0＝Ｈ0（ａ1，ａ2，…，ａn）を求め、ｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗk  を設定し、ｃ＝Ｈj（ｆ（ｊ））◎ｃjを計算し、ｙj＝ｃj◎ａj（＝Ｈ（ｆ（ｊ））◎ａj）を計算するという手順で、ｎ個の公開鍵を求める。
【００１８】
何れの公開鍵も同様の手順により求まるので、受信者が秘密鍵を知っている公開鍵は何れであるかを見分けることはできない。また、α0＝Ｈ0（ａ1，ａ2，…，ａn）を多項式上の点として持ったｋ次多項式ｆ（ｗ）と（ａ1，ａ2，…，ａn）とから公開鍵が一意に定まることから、送信者は、受信者が公開鍵に対応する秘密鍵をｎ個の内のｋ個より多くは知り得ないことを確信することができる。
以上の通りにして、送信者には何れの公開鍵について受信者が秘密鍵を知っているのか見分けのつかない公開鍵であり、受信者はｋ個については秘密鍵を知り、ｎ−ｋ個については秘密鍵を知らないことを送信者が確信することができる、合計ｎ個の公開鍵を設定することができる。
【実施例１】
【００１９】
発明を実施するための最良の形態を図１〜図４を参照して説明する。図１は公開鍵秘密鍵設定装置を説明する図、図２はｋ次多項式設定部の詳細を説明する図、図３は暗号文生成部を説明する図、図４は暗号文復号部を説明する図である。
図１において、１は公開鍵秘密鍵生成部、２は第１ｋ次多項式点設定部、３は第１ハッシュ演算部、４は第１排他的論理和演算部（加算演算部）、５は第１公開鍵リスト数判断部、１２は公開鍵初期化部である。
６は乱数生成部、７はｋ次多項式設定部、８は第２ｋ次多項式点設定部、９は第２ハッシュ演算部、１０は第２排他的論理和演算部、１１は第２公開鍵リスト数判断部である。
【００２０】
ここで、図１を参照して公開鍵鍵秘密鍵設定の手順を説明する。
受信者Ｂは、公開鍵秘密鍵生成部１を実行し、送信者Ａとは独立に受信者Ｂが独自に秘密鍵をｘj∈Ｚqjを任意に設定する。そして、公開鍵に対応する秘密鍵を離散対数、ｙj ＝ｇjxj modｐj、ｇj，ｑj，ｐjと設定して、秘密鍵公開鍵ペア（ｙj，ｘj）ｋ個を設定する。具体的には、ｊとして、ｊ＝１、３、５、・・・、ｋの如くに任意のｋ個を設定し、次に、第１ｋ次多項式点設定部２を実行し、ｋ次多項式ｆ（ｗ）を満足する点として、ｋ個の値ｆ（ｊ）を設定する。即ち、ｙ1＝ｆ（１）＝ｇx1、ｙ3＝ｆ（３）＝ｇx3、ｙ5＝ｆ（５）＝ｇx5、ｙk＝ｆ（ｋ）を公開鍵：ｇxkとして設定する。
【００２１】
第１ｋ次多項式点設定部２により設定された値ｆ（ｊ）を第１ハッシュ演算部３に入力してハッシュ演算を実行し、値ｆ（ｊ）のハッシュ演算出力値ｃj＝Ｈj（ｆ（ｊ））を計算する。即ち、ｙ1＝ｆ（１）＝ｇx1、ｙ3＝ｆ（３）＝ｇx3、ｙ5＝ｆ（５）＝ｇx5、ｙk＝ｆ（ｋ）＝ｇxkを入力して、ｃ1＝Ｈ1（ｆ（１））、ｃ3＝Ｈ3（ｆ（３））、ｃ5＝Ｈ5（ｆ（５））、ｃk＝Ｈk（ｆ（ｋ））を計算する。
次に、第１排他的論理和演算部（加算演算部）４に対して、第１ハッシュ演算部３から出力されるハッシュ演算出力ｃj＝Ｈj（ｆ（ｊ））を入力すると共に第１ｋ次多項式点設定部２により設定された公開鍵ｙj＝Ｇj（ｘj）を入力して排他的論理和演算を実行し、排他的論理和ａj＝ｃj◎ｙj を得る。ここで、排他的論理和ａj は、多項式上の点ｆ（ｊ）と公開鍵とを一意に決定づけている値を意味する。
【００２２】
第１排他的論理和演算部４の出力を第１公開鍵リスト数判断部５に入力して生成した公開鍵の数を判断し、この数がｋ個となる迄、以上の動作を繰り返す。
以上の通りにして、秘密鍵ｘj に対応するｋ個の公開鍵ｙjが生成された。次いで、秘密鍵を知らない残りのｎ−ｋ個の公開鍵を生成する操作をする。先ず、乱数生成部６を実行し、任意にｎ−ｋ個の乱数ａj を選択する。ここで、図２をも参照するに、第３ハッシュ演算部２２に乱数生成部６から選択したｎ−ｋ個の乱数ａj と先の第１排他的論理和演算部４の演算結果であるｋ個のａj＝ｃj◎ｙjにより構成されるｎ個の乱数（ａ1，ａ2，…，ａn）を入力することにより、α0＝ｆ（０）＝Ｈ0（ａ1，ａ2，…，ａn）を求める。求められた値α0＝ｆ（０）を（０，ｆ（０））とし、先の第１ｋ次多項式点設定部２の出力であるｋ個の点（ｊ，ｆ（ｊ））の合計であるｋ＋１個の点に相当する値がｋ次多項式設定部７に入力されることにより、点（０，ｆ（０））を含む合計ｋ＋１個の点（ｊ，ｆ（ｊ））からｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkが一意的に求まる。
【００２３】
ｋ次多項式ｆ（ｗ）が決定したところで、受信者Ｂは（α1，…，αk）および（ａ1，…，ａn）を送信者Ａに送る。送信者Ａは送信されてきた（α1，…，αk）および（ａ1，…，ａn）を用いて、公開鍵を次の手順で求める。第１：α0＝Ｈ0（ａ1，ａ2，…，ａn）を求め、第２：ｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkを設定し、第３：ｃj＝Ｈj（ｆ（ｊ））を計算し、第４：ｙj＝ｃj◎ａjによりｙjを求める。求めた公開鍵を使用し、暗号アルゴリズムを用いて秘密情報ｍj の暗号文を生成する。送信者Ａに対して一般の伝送経路を介して（ａ1，…，ａn，α1，…，αk）を送ることで、送信者Ａは自らｎ個の公開鍵をｙj＝Ｈj（ｆ（ｊ））◎ａjとして求めることができるので、送信者Ａに対して公開鍵を送信する必要はない。
【００２４】
図３を参照して暗号文生成を説明する。７’はｋ次多項式設定部、８’は第２ｋ次多項式点設定部、９’は第２ハッシュ演算部、１０’は第２排他的論理和演算部である。これらは図１において図示説明される共通する参照符合の部位と同等のものであるので、同一の参照符号に「’」を付与して表現した。２１は暗号文生成部、２２は第３ハッシュ演算部である。
送信者Ａは、送信されてきた（α1，…，αk）および（ａ1，…，ａn）を公開鍵生成に用いる。（ａ1，…，ａn）を第３ハッシュ演算部２２’に入力してハッシュ演算を実行し、α0＝Ｈ0（ａ1，…，ａn）を設定する。次に、ｋ次多項式設定部７’を実行し、設定されたα0 と送信されてきたｋ個の（α1，…，αk）の合計ｋ＋１個のαにより、ｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkを一意的に設定する。次に、第２ｋ次多項式点演算部８’を実行し、ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkから、ｆ（ｊ）を計算し、次に、第２ハッシュ演算部９’を実行し、ｃj＝Ｈj（ｆ（ｊ））を計算する。
【００２５】
次に、第２排他的論理和演算部１０’に対して、第２ハッシュ演算部９’により得られたｃj＝Ｈj（ｆ（ｊ））を入力すると共に、送信されてきた（ａ1，…，ａn）を入力して排他的論理和演算を実行し、ｙj＝ｃj◎ａjを計算する。次に、送信者Ａ自身でｙj＝Ｈj（ｆ（ｊ））◎ａjとして求めたｎ個の公開鍵ｙj を用い、暗号文生成部２１を実行し、ｎ個の暗号文を生成し、生成したｎ個の暗号文を受信者Ｂへ送信する。
図４を参照して、暗号文復号手順を説明する。
受信者Ｂは、暗号文選別部３１に、暗号文（Ｍ1，・・・，Ｍn）および秘密鍵情報と共に設定した公開鍵ｙjを入力として供給し、この公開鍵ｙjにより暗号化されている暗号文（Ｍ1，・・・，Ｍn）を選別する。次に、暗号文復号部３２を実行し、秘密鍵ｘj を知るｋ個の公開鍵ｙj で、選別した暗号文（Ｍ1，・・・，Ｍn）からｋ個の平文を得ることができる。
【実施例２】
【００２６】
実施例１においては、α0＝Ｈ0（ａ1，ａ2，…，ａn）により求めたα0 は、受信者Ｂから送信者Ａに送られないので、送信者Ａは送られてきた（ａ1，ａ2，…，ａn）に基づいてα0 を計算する必要があった。そこで、α0 をも受信者Ｂから送信者Ａに送ることで、送信者Ａは自らα0 を求める必要がなくなり、ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗk を設定することができるので、このα0 をも受信者Ｂから送信者Ａに送る構成を採用し、これを実施例２とすることができる。ここで、
Ｓｔｅｐ１：受信者Ｂは、
・ｋ個の秘密鍵公開鍵のペア（ｙj，ｘj）を任意に設定し、
・ｋ次多項式の上の点としてｋ個の値ｆ（ｊ）を任意に設定し、ｃj＝Ｈj（ｆ（ｊ））を計算し、
・ｋ個のａj＝ｃj◎ｙjを求め、
・ｎ−ｋ個の残りのａjを任意に設定し、
・α0＝Ｈ0（ａ1，ａ2，…，ａn）により求めたα0 を使用し、ｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗkを求め、
・（ａ1，…，ａn，α0，…，αk）を送信者Ａへ渡し、
Ｓｔｅｐ２：送信者Ａは、
送られてきた（ａ1，…，ａn，α0，…，αk）から、ｋ次多項式ｆ（ｗ）＝α0＋α1ｗ＋…＋αkｗk を設定し、ｙj＝Ｈj（ｆ（ｊ））◎ａjを求めて公開鍵（ｙ1，…，ｙn）を求め、
・送信者Ａは求めたｎ個の公開鍵を用いて、送信するｎ個の秘密情報を暗号化し、ｎ個の暗号文を生成し、
・生成したｎ個の暗号文を受信者Ｂに送信し、
Ｓｔｅｐ３：受信者Ｂは、
・受信した暗号文ｎ個の内の、自分が秘密鍵を知っているｋ個について、復号し、秘密情報をｋ個入手し、
ｎ個の秘密情報の内の、何れかｋ個の秘密情報ｍj を、送信者Ａから受信者Ｂにｎ個の秘密情報の内の何れを受信者Ｂが得られたかを匿名にしたまま行う紛失通信路の構成を実行する。
【００２７】
ここで、詳細な説明は以上の図示説明の繰り返しになるので省略するが、請求項５および請求項７に対応する紛失通信路構成装置、および請求項６および請求項８に対応する紛失通信路構成装置のそれぞれに、図１の☆印で包囲される構成を付加することにより、更なる実施例を構成することができる。そして、請求項５および請求項７に対応する紛失通信路構成装置に関連して、請求項３に対応する紛失通信路構成方法、請求項７に対応する紛失通信路構成装置、請求項１１に対応する紛失通信路構成プログラムをも構成することができる。また、請求項６および請求項８に対応する紛失通信路構成装置に関連して、請求項４に対応する紛失通信路構成方法、請求項８に対応する紛失通信路構成装置、請求項１２に対応する紛失通信路構成プログラムをも構成することができる。
【図面の簡単な説明】
【００２８】
【図１】公開鍵秘密鍵設定装置を説明する図。
【図２】ｋ次多項式設定部を説明する図。
【図３】暗号文生成部を説明する図。
【図４】暗号文復号部を説明する図。
【符号の説明】
【００２９】
１  公開鍵秘密鍵生成部                ２  第１ｋ次多項式点設定部
３  第１ハッシュ演算部                ４  第１排他的論理和演算部
５  第１公開鍵リスト数判断部          ６  乱数生成部
７、７’ｋ次多項式設定部              ８、８’第２ｋ次多項式点設定部
９、９’第２ハッシュ演算部        １０、１０’第２排他的論理和演算部
１１  第２公開鍵リスト数判断部        １２  公開鍵初期化部
２１  暗号文生成部                    ２２  第３ハッシュ演算部
２２’第４ハッシュ演算部              ３１  暗号文選別部                        ３２  暗号文復号部
【図１】
2006108840.tif 000003
【図２】
2006108840.tif 000004
【図３】
2006108840.tif 000005
【図４】
2006108840.tif 000006