(57)【要約】【課題】送信者及び受信者間の転送処理の通信回数、計算量、及び通信量を小さくする。【解決手段】送信者が、送信者から受信者への通信により、受信者に初期化処理に用いる原信号を送る第１のステップ、受信者が、前記原信号を用いて初期化処理することによって得られた、初期化処理された信号を、送信者に送る第２のステップ、送信者が、前記初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、ｎ（２以上の整数）種類の情報ｍ１，…，ｍｎを受信者に送信する第３のステップ、受信者は、ｎ種類の情報ｍ１，…，ｍｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第４のステップを有し、前記第１乃至前記第３のステップをＲＳＡ暗号方式で行うことを特徴とする紛失通信方法。【選択図】図２
2005189273.tif 000002
【特許請求の範囲】
【請求項１】
送信者がｎ（ただし、ｎは２以上の整数）種類の情報ｍ１，…，ｍｎを持ち、受信者がその中から１つの情報ｍｉ（ただし、ｉは１以上ｎ以下の整数）を取り出す方法であって、受信者が選択した情報がどれかを送信者に知られることなく、また、受信者は選択したもの以外の情報を入手することができない、１アウトオブｎ紛失通信方法において、
送信者が、送信者から受信者への通信により、受信者に初期化処理に用いる原信号を送る第１のステップと、
受信者が、前記原信号を用いて初期化処理することによって得られた、初期化処理された信号を、送信者に送る第２のステップと、
送信者が、前記初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、ｎ種類の情報ｍ１，…，ｍｎを受信者に送信する第３のステップと、
受信者は、ｎ種類の情報ｍ１，…，ｍｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第４のステップとを有し、
前記第１乃至前記第３のステップをＲＳＡ暗号方式で行うことを特徴とする紛失通信方法。
【請求項２】
送信者が別のｎ種類の情報ｍ’１，…，ｍ’ｎを更に持っている請求項１に記載の紛失通信方法において、
受信者が、前記原信号を用いて別の初期化処理することによって得られた、別の初期化処理された信号を、送信者に送る第５のステップと、
送信者が、前記別の初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎを受信者に送信する第６のステップと、
受信者は、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第７のステップとを更に有し、
前記第５及び前記第６のステップもＲＳＡ暗号方式で行うことを特徴とする紛失通信方法。
【請求項３】
送信者がｎ（ただし、ｎは２以上の整数）種類の情報ｍ１，…，ｍｎを持ち、受信者がその中から１つの情報ｍｉ（ただし、ｉは１以上ｎ以下の整数）を取り出す方法であって、受信者が選択した情報がどれかを送信者に知られることなく、また、受信者は選択したもの以外の情報を入手することができない、１アウトオブｎ紛失通信方法において、
送信者が、送信者から受信者への通信により、受信者に初期化処理に用いる原信号を送る第１のステップと、
受信者が、前記原信号を用いて初期化処理することによって得られた、初期化処理された信号を、送信者に送る第２のステップと、
送信者が、前記初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、ｎ種類の情報ｍ１，…，ｍｎを受信者に送信する第３のステップと、
受信者は、ｎ種類の情報ｍ１，…，ｍｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第４のステップとを有し、
前記第１乃至前記第３のステップで、巡回群の複数の生成元を使用することを特徴とする紛失通信方法。
【請求項４】
送信者が別のｎ種類の情報ｍ’１，…，ｍ’ｎを更に持っている請求項３に記載の紛失通信方法において、
受信者が、前記原信号を用いて別の初期化処理することによって得られた、別の初期化処理された信号を、送信者に送る第５のステップと、
送信者が、前記別の初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎを受信者に送信する第６のステップと、
受信者は、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第７のステップとを更に有し、
前記第５及び前記第６のステップでも、巡回群の複数の生成元を使用することを特徴とする紛失通信方法。
【請求項５】
送信者がｎ（ただし、ｎは２以上の整数）種類の情報ｍ１，…，ｍｎを持ち、受信者がその中から１つの情報ｍｉ（ただし、ｉは１以上ｎ以下の整数）を取り出すシステムであって、受信者が選択した情報がどれかを送信者に知られることなく、また、受信者は選択したもの以外の情報を入手することができない、１アウトオブｎ紛失通信システムにおいて、
送信者が、送信者から受信者への通信により、受信者に初期化処理に用いる原信号を送る第１の手段と、
受信者が、前記原信号を用いて初期化処理することによって得られた、初期化処理された信号を、送信者に送る第２の手段と、
送信者が、前記初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、ｎ種類の情報ｍ１，…，ｍｎを受信者に送信する第３の手段と、
受信者は、ｎ種類の情報ｍ１，…，ｍｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第４の手段とを有し、
前記第１乃至前記第３の手段の信号のやりとりをＲＳＡ暗号方式で行うことを特徴とする紛失通信システム。
【請求項６】
送信者が別のｎ種類の情報ｍ’１，…，ｍ’ｎを更に持っている請求項５に記載の紛失通信システムにおいて、
受信者が、前記原信号を用いて別の初期化処理することによって得られた、別の初期化処理された信号を、送信者に送る第５の手段と、
送信者が、前記別の初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎを受信者に送信する第６の手段と、
受信者は、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第７の手段とを更に有し、
前記第５及び前記第６の手段の信号のやりとりもＲＳＡ暗号方式で行うことを特徴とする紛失通信システム。
【請求項７】
送信者がｎ（ただし、ｎは２以上の整数）種類の情報ｍ１，…，ｍｎを持ち、受信者がその中から１つの情報ｍｉ（ただし、ｉは１以上ｎ以下の整数）を取り出すシステムであって、受信者が選択した情報がどれかを送信者に知られることなく、また、受信者は選択したもの以外の情報を入手することができない、１アウトオブｎ紛失通信システムにおいて、
送信者が、送信者から受信者への通信により、受信者に初期化処理に用いる原信号を送る第１の手段と、
受信者が、前記原信号を用いて初期化処理することによって得られた、初期化処理された信号を、送信者に送る第２の手段と、
送信者が、前記初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、ｎ種類の情報ｍ１，…，ｍｎを受信者に送信する第３の手段と、
受信者は、ｎ種類の情報ｍ１，…，ｍｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第４の手段とを有し、
前記第１乃至前記第３の手段の信号のやりとりに、巡回群の複数の生成元を使用することを特徴とする紛失通信システム。
【請求項８】
送信者が別のｎ種類の情報ｍ’１，…，ｍ’ｎを更に持っている請求項７に記載の紛失通信システムにおいて、
受信者が、前記原信号を用いて別の初期化処理することによって得られた、別の初期化処理された信号を、送信者に送る第５の手段と、
送信者が、前記別の初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎを受信者に送信する第６の手段と、
受信者は、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第７の手段とを更に有し、
前記第５及び前記第６の手段の信号のやりとりにも、巡回群の複数の生成元を使用することを特徴とすることを特徴とする紛失通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、紛失通信方法に関する。
【背景技術】
【０００２】
紛失通信(oblivious transfer)方式には、例えば、１アウトオブｎ(1 out of n)紛失通信方法がある。この１アウトオブｎ紛失通信方法は、送信者がｎ（ただし、ｎは２以上の整数）種類の情報を持ち、受信者がその中から１つの情報を取り出す方法であって、受信者が選択した情報がどれかを送信者に知られることなく、また、受信者は選択したもの以外の情報を入手することができない方式である。この紛失通信方法は、例えば、データベース会社が１００個のビデオ情報を持ち、ユーザは１００個のビデオ情報のなかの一個を有料で取得観賞するが、ユーザがどれを取得観賞したかは隠すというものである。
【０００３】
従来の紛失通信方法は、ＲＳＡ暗号方式（Rivest, Shamir, Adlemanによって考案された暗号方式）を利用する場合は初期化処理が無く転送処理のみで構成され、巡回群の生成元を利用しかつ初期化処理を有する場合には、一つの生成元のみを利用する構成となっていた。
【０００４】
第１の従来技術として、ＲＳＡ暗号方式を利用するが、初期化処理が無い紛失通信方法は、例えば、特許文献１、特許文献２、非特許文献１に開示されている。
【０００５】
第２の従来技術として、初期化処理が有るが、巡回群の生成元を１つのみ利用する紛失通信方法は、例えば、非特許文献２に開示されている。
【０００６】
第３の従来技術として、巡回群の生成元を２つ利用する場合で、初期化処理が無い紛失通信方法は、例えば、非特許文献３に開示されている。
【０００７】
上記の第１の従来技術として例示した特許文献１及び特許文献２に開示された紛失通信方法は、いずれも、初期化処理が無いので、転送処理に次の(step1)〜(step3)からなる３回の通信を必要とする。
【０００８】
(step1)  送信者から受信者への通信。  
(step2)  受信者から送信者への通信。  
(step3)  送信者から受信者への通信。
【０００９】
次に、上記非特許文献２に開示された第２の従来技術（初期化処理が有るが、巡回群の生成元を１つのみ利用する紛失通信方法）について図５を用いて説明する。
【００１０】
図５には、送信者が有する情報の数は３（すなわち、ｎ＝３）の例が図示されている。
【００１１】
位数が素数ｑの巡回群をＧとし、
巡回群Ｇの生成元をｇとする。
【００１２】
初期化処理において、送信者は、集合Ｚｑからランダムに要素（元）であるｋを選択し（すなわち、ｋ∈ＲＺｑ：ここで、∈Ｒはランダムに選択することを意味する）、乱数ｋを生成し、集合Ｇからランダムにｇを選択し（すなわち、ｇ∈ＲＧ）、ｇをｋ乗をした値βを受信者に送信する。また、（ｎ−１）個のランダムな値Ｃ２，…，Ｃｎを受信者に送信する。さらに、それらをｋ乗した値Ｃ２ｋ，…，Ｃｎｋを計算しておく。
【００１３】
受信者の秘密のインデックス値をｉとする。ただし、iは１からｎの中から選ばれる。
【００１４】
転送処理において、まず、受信者は、乱数ｒ（ただし、ｒ∈ＲＺｑ）を生成し、ｇをr乗した値ｇrを計算する。次に、ｉ＝１の場合、ｇrをｙとする。ｉが１以外の場合、Ｃｉ／ｇrをｙとする。そして値ｙを送信者に送信する。
【００１５】
送信者は、ｙをｋ乗した値をＫ１とし（すなわち、Ｋ１＝ｙｋ）、Ｋ２＝Ｃ２ｋ／Ｋ１，…，Ｋｎ＝Ｃｎｋ／Ｋ１を計算する。次に、ランダムな文字列Ｒを生成し、各jについてＫｊ，Ｒとｊの連結のハッシュ値Ｈ（Ｋｊ，Ｒ，ｉ）と送信者の秘密情報ｍｊとの排他的論理和Ｅｊを計算する。最後に、（Ｅ１，…，Ｅｎ）とＲを受信者に送信する。なお、Ｈはハッシュ関数を表す。
【００１６】
受信者はβのr乗βrを計算し、βrとＲとiの連結のハッシュ値Ｈ（βr，Ｒ，ｉ）とＥｉとの排他的論理和を計算することによって、i番目の秘密情報ｍｉを得ることができる。
【００１７】
次に、上記非特許文献３に開示された第３の従来技術（巡回群の生成元を２つ利用する場合で、初期化処理が無い紛失通信方法）について図６を用いて説明する。
【００１８】
図６にも、送信者が有する情報の数は３（すなわち、ｎ＝３）の例が図示されている。
【００１９】
位数が素数ｑの巡回群をＧとし、
巡回群Ｇの二つの生成元をｇ，ｈとする（ここで、ｇ，ｈ∈ＲＧ）。
【００２０】
受信者の秘密のインデックス値をｉとする。ただし、ｉは１からｎの中から選ばれる。
【００２１】
送信処理において、受信者は乱数ｒ（すなわち、ｒ∈ＲＺｑ）を生成し、ｇのr乗とｈのｉ乗を乗算した値ｙ（ｙ＝ｇｒｈｉ）を送信者に送信する。
【００２２】
送信者は、ｎ個のランダムな値ｋ１，…，ｋｎを生成し（すなわち、ｋ１，…，ｋｎ∈ＲＺｑ）、ｇをそれぞれの値でべき乗した値ｇｋ１，…，ｇｋｎを受信者に送信する。次に、各jについて（ｙ／ｈｊ）ｋｊとjの連結のハッシュ値Ｈ（（ｙ／ｈｊ）ｋｊ，ｊ）と送信者の秘密情報ｍｊとの排他的論理和Ｅｊを計算する。最後に、（Ｅ１，…，Ｅｎ）を受信者に送信する。
【００２３】
受信者は、（ｇｋｉ）ｒとiの連結のハッシュ値Ｈ（（ｇｋｉ）ｒ，ｉ）とＥｉの排他的論理和を計算することにより、i番目の秘密情報ｍｉを得ることができる。
【００２４】
【特許文献１】特開２０００−１１５１５７号公報
【特許文献２】特開平１１−１４５９５１号公報
【非特許文献１】Bruce Schneier ,“Applied Cryptography” ,John Wiley & Sons,Inc. ,p116-117
【非特許文献２】M. Naor and B. Pinkas, “Efficient oblivious transfer protocols,” 12th Annual Symposium on Discrete Algorithms (SODA), pp.448-457 (2001)
【非特許文献３】W.G. Tzeng, “Efficient 1-Out-n Oblivious Transfer Schemes,” Proc. Of PKC’02, LNCS Vol.2274, pp.159-172 (2002)
【発明の開示】
【発明が解決しようとする課題】
【００２５】
上記特許文献１及び上記特許文献２の問題点は、初期化処理が無いので、転送処理に３回の通信を必要とし、送受信者間で何回も転送処理を行う場合に有効ではないことである。
【００２６】
図６の第３の従来技術など、初期化処理が無い場合の問題点は、転送処理における計算量が大きくなることである。
【００２７】
図５の第２の従来技術の問題点は、巡回群に基づく方式においては、初期化処理における計算量と転送量が大きくなることである。
【００２８】
本発明の目的は、ＲＳＡ暗号を利用する場合、初期化処理を有することにより、各転送処理を２回と少ない回数の通信で済ませることができ、従って送受信者間で何回も転送処理を行う場合に有効な紛失通信方法及びシステムを提供することにある。
【００２９】
本発明の別の目的は、巡回群を利用する紛失通信方法及びシステムにおいて、初期化処理における計算量と転送量を小さくすることにある。
【課題を解決するための手段】
【００３０】
本発明は、ＲＳＡ暗号方式を利用し初期化処理を有する方法及びシステムと、初期化処理を有しかつ巡回群の複数の生成元を利用する方法及びシステムである。
【００３１】
すなわち、本発明の紛失通信方法及びシステムは、ＲＳＡ暗号方式を利用する場合初期化処理を行い、また初期化処理を有し巡回群を利用する方式においては、複数の生成元を利用することを特徴とする。
【００３２】
すなわち、本発明による紛失通信方法及びシステムは、以下のとおりである。
【００３３】
（１）  送信者がｎ（ただし、ｎは２以上の整数）種類の情報ｍ１，…，ｍｎを持ち、受信者がその中から１つの情報ｍｉ（ただし、ｉは１以上ｎ以下の整数）を取り出す方法であって、受信者が選択した情報がどれかを送信者に知られることなく、また、受信者は選択したもの以外の情報を入手することができない、１アウトオブｎ紛失通信方法において、
送信者が、送信者から受信者への通信により、受信者に初期化処理に用いる原信号を送る第１のステップと、
受信者が、前記原信号を用いて初期化処理することによって得られた、初期化処理された信号を、送信者に送る第２のステップと、
送信者が、前記初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、ｎ種類の情報ｍ１，…，ｍｎを受信者に送信する第３のステップと、
受信者は、ｎ種類の情報ｍ１，…，ｍｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第４のステップとを有し、
前記第１乃至前記第３のステップをＲＳＡ暗号方式で行うことを特徴とする紛失通信方法。
【００３４】
（２）  送信者が別のｎ種類の情報ｍ’１，…，ｍ’ｎを更に持っている上記（１）に記載の紛失通信方法において、
受信者が、前記原信号を用いて別の初期化処理することによって得られた、別の初期化処理された信号を、送信者に送る第５のステップと、
送信者が、前記別の初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎを受信者に送信する第６のステップと、
受信者は、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第７のステップとを更に有し、
前記第５及び前記第６のステップもＲＳＡ暗号方式で行うことを特徴とする紛失通信方法。
【００３５】
（３）  送信者がｎ（ただし、ｎは２以上の整数）種類の情報ｍ１，…，ｍｎを持ち、受信者がその中から１つの情報ｍｉ（ただし、ｉは１以上ｎ以下の整数）を取り出す方法であって、受信者が選択した情報がどれかを送信者に知られることなく、また、受信者は選択したもの以外の情報を入手することができない、１アウトオブｎ紛失通信方法において、
送信者が、送信者から受信者への通信により、受信者に初期化処理に用いる原信号を送る第１のステップと、
受信者が、前記原信号を用いて初期化処理することによって得られた、初期化処理された信号を、送信者に送る第２のステップと、
送信者が、前記初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、ｎ種類の情報ｍ１，…，ｍｎを受信者に送信する第３のステップと、
受信者は、ｎ種類の情報ｍ１，…，ｍｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第４のステップとを有し、
前記第１乃至前記第３のステップで、巡回群の複数の生成元を使用することを特徴とする紛失通信方法。
【００３６】
（４）  送信者が別のｎ種類の情報ｍ’１，…，ｍ’ｎを更に持っている上記（３）に記載の紛失通信方法において、
受信者が、前記原信号を用いて別の初期化処理することによって得られた、別の初期化処理された信号を、送信者に送る第５のステップと、
送信者が、前記別の初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎを受信者に送信する第６のステップと、
受信者は、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第７のステップとを更に有し、
前記第５及び前記第６のステップでも、巡回群の複数の生成元を使用することを特徴とする紛失通信方法。
【００３７】
（５）  送信者がｎ（ただし、ｎは２以上の整数）種類の情報ｍ１，…，ｍｎを持ち、受信者がその中から１つの情報ｍｉ（ただし、ｉは１以上ｎ以下の整数）を取り出すシステムであって、受信者が選択した情報がどれかを送信者に知られることなく、また、受信者は選択したもの以外の情報を入手することができない、１アウトオブｎ紛失通信システムにおいて、
送信者が、送信者から受信者への通信により、受信者に初期化処理に用いる原信号を送る第１の手段と、
受信者が、前記原信号を用いて初期化処理することによって得られた、初期化処理された信号を、送信者に送る第２の手段と、
送信者が、前記初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、ｎ種類の情報ｍ１，…，ｍｎを受信者に送信する第３の手段と、
受信者は、ｎ種類の情報ｍ１，…，ｍｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第４の手段とを有し、
前記第１乃至前記第３の手段の信号のやりとりをＲＳＡ暗号方式で行うことを特徴とする紛失通信システム。
【００３８】
（６）  送信者が別のｎ種類の情報ｍ’１，…，ｍ’ｎを更に持っている上記（５）に記載の紛失通信システムにおいて、
受信者が、前記原信号を用いて別の初期化処理することによって得られた、別の初期化処理された信号を、送信者に送る第５の手段と、
送信者が、前記別の初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎを受信者に送信する第６の手段と、
受信者は、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第７の手段とを更に有し、
前記第５及び前記第６の手段の信号のやりとりもＲＳＡ暗号方式で行うことを特徴とする紛失通信システム。
【００３９】
（７）  送信者がｎ（ただし、ｎは２以上の整数）種類の情報ｍ１，…，ｍｎを持ち、受信者がその中から１つの情報ｍｉ（ただし、ｉは１以上ｎ以下の整数）を取り出すシステムであって、受信者が選択した情報がどれかを送信者に知られることなく、また、受信者は選択したもの以外の情報を入手することができない、１アウトオブｎ紛失通信システムにおいて、
送信者が、送信者から受信者への通信により、受信者に初期化処理に用いる原信号を送る第１の手段と、
受信者が、前記原信号を用いて初期化処理することによって得られた、初期化処理された信号を、送信者に送る第２の手段と、
送信者が、前記初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、ｎ種類の情報ｍ１，…，ｍｎを受信者に送信する第３の手段と、
受信者は、ｎ種類の情報ｍ１，…，ｍｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第４の手段とを有し、
前記第１乃至前記第３の手段の信号のやりとりに、巡回群の複数の生成元を使用することを特徴とする紛失通信システム。
【００４０】
（８）  送信者が別のｎ種類の情報ｍ’１，…，ｍ’ｎを更に持っている上記（７）に記載の紛失通信システムにおいて、
受信者が、前記原信号を用いて別の初期化処理することによって得られた、別の初期化処理された信号を、送信者に送る第５の手段と、
送信者が、前記別の初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎを受信者に送信する第６の手段と、
受信者は、前記別のｎ種類の情報ｍ’１，…，ｍ’ｎの何番目を選んだのかを送信者に知られないようにして選択した情報だけを得る第７の手段とを更に有し、
前記第５及び前記第６の手段の信号のやりとりにも、巡回群の複数の生成元を使用することを特徴とすることを特徴とする紛失通信システム。
【発明の効果】
【００４１】
本発明による効果は、ＲＳＡ暗号を利用する場合、初期化処理を有することにより、各転送処理を２回と少ない回数の通信で済ませることができ、従って送受信者間で初期化処理に続いて何回も転送処理を行う場合に有効なことである。
【００４２】
その理由は、あらかじめ初期化処理を行うことにより、転送処理時に必要な通信回数を減らすことができるからである。
【００４３】
本発明による別の効果は、巡回群を利用する場合には、初期化処理の計算量と通信量を減らすことができることである。
【００４４】
その理由は、複数の生成元を利用することにより、必要な計算量を減らすことができるからである。
【発明を実施するための最良の形態】
【００４５】
次に本発明の実施形態による紛失通信方法の構成について図面を参照して説明する。
【００４６】
図１を参照すると、本発明の一実施形態による紛失通信方法は、ｎ（図示の例では、ｎ＝４）種類の情報ｍ１，…，ｍ４を持つ送信者（sender）と、その中から一つを選び出す受信者（chooser）とから構成されている。
【００４７】
主たる動作は、以下の（初期化処理）及び（転送処理-１）である。図示の例では、（転送処理−１）に続いて（転送処理−２），…が行われている。
【００４８】
（初期化処理）：  送信者は、送信者から受信者への通信により受信者に初期化処理に用いる原信号を送っておく。
【００４９】
（転送処理−１）：  送信者は、ｎ種類の情報ｍ１，…，ｍ４を持ち、受信者からの前記原信号を用いて初期化処理された信号を受け、初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、ｎ種類の情報ｍ１，…，ｍ４を受信者に送信する。
【００５０】
受信者は、ｎ種類の情報ｍ１，…，ｍ４の何番目を選んだのかを送信者に知られないようにして選択した情報ｍ３だけを得る。
【００５１】
（転送処理−２）：  送信者は、別のｎ種類の情報ｍ’１，…，ｍ’４を持ち、受信者からの前記原信号を用いて別の初期化処理された信号を受け、別の初期化処理された信号を用いて、受信者には受信者自身が選択した情報以外は得られないように、ｎ種類の情報ｍ’１，…，ｍ’４を受信者に送信する。
【００５２】
受信者は、ｎ種類の情報ｍ’１，…，ｍ’４の何番目を選んだのかを送信者に知られないようにして選択した情報ｍ’４だけを得る。
【００５３】
後の実施例の説明からも明らかになるように、（転送処理−１）及び（転送処理−２）の各々は、詳細には、次の(step1)及び(step2)を含む。
【００５４】
(step1)  受信者から送信者への通信（初期化処理された信号或いは別の初期化処理された信号の送信）。
【００５５】
(step2)  送信者から受信者への通信（情報ｍ１，…，ｍ４の暗号文或いは情報ｍ’１，…，ｍ’４の暗号文の送信）。
【００５６】
また、後の実施例の説明からも明らかになるように、ＲＳＡ暗号を利用した場合、或いは、巡回群を利用した場合に、処理の計算量と通信量を減らすことができる。
【００５７】
［第１の実施例］
次に、本発明の第１の実施例について説明する。
【００５８】
第１の実施例は、ＲＳＡ暗号を利用し、かつ初期化処理を有する紛失通信方法であり、第１の実施例について図２を用いて説明する。
【００５９】
図２には、送信者が有する情報の数は３（すなわち、ｎ＝３）の例が図示されている。
【００６０】
初期化処理において、送信者は、ＲＳＡ暗号方式の公開鍵（Ｎ，ｅ）と秘密鍵ｄと乱数ｓとを生成し、受信者に送信する。この際、乱数ｓは、集合ＺＮからランダムに要素（元）であるｓを送信者が選択したものである（すなわち、ｓ∈ＲＺＮ）。
【００６１】
また、送信者は、（ｓ＋１）から（ｓ＋ｎ）をそれぞれｄ乗した値（ｓ＋１）ｄ，…，（ｓ＋ｎ）ｄを計算しておく。
【００６２】
受信者の秘密のインデックス値をｉとする。ただし、iは１からｎの中から選ばれる。
【００６３】
転送処理において、受信者は、集合ＺＮからランダムに要素（元）である乱数ｒを選択する（すなわち、ｒ∈ＲＺＮ）ことによって、乱数rを生成し、ｒをｅ乗した値rｅと（ｓ＋ｉ）をかけた値ｙ＝rｅ（ｓ＋ｉ）を送信者に送信する。
【００６４】
送信者は、まず、Ｙ＝ｙｄを計算する。次に、乱数Ｒを生成し、各ｊについてＫｊ＝Ｙ／（ｓ＋ｊ）ｄを計算し、ＲとＫｊとｊの連結のハッシュ値Ｈ（Ｋｊ，Ｒ，ｊ）と送信者の秘密情報ｍｊの排他的論理和Ｅｊ（すなわち、Ｅ１，…，Ｅｎ）を計算する。最後に、（Ｅ１，…，Ｅｎ）およびＲを受信者に送信する。
【００６５】
受信者は、ｒとＲとｉの連結のハッシュ値Ｈ（ｒ，Ｒ，ｉ）とＥｉとの排他的論理和を計算することにより、自分が選択した秘密情報ｍｉ（図示の例ではｍ２）を得ることができる。
【００６６】
［第２の実施例］
次に、本発明の第２の実施例について説明する。
【００６７】
第２の実施例は、初期化処理を有し、かつ巡回群の複数の生成元を利用する紛失通信方法であり、第２の実施例について図３を用いて説明する。
【００６８】
図３にも、送信者が有する情報の数は３（すなわち、ｎ＝３）の例が図示されている。
【００６９】
位数が素数ｑの巡回群をＧとし、
巡回群Ｇの二つの生成元をｇ，ｈとする。
【００７０】
初期化処理において、送信者は、集合Ｚｑからランダムに要素（元）である乱数ｋを選択する（すなわち、ｋ∈ＲＺｑ）ことによって、乱数ｋを生成し、ｇをｋ乗をした値β＝ｇｋを受信者に送信する。また、ｈｋ，ｈ２ｋ，…，ｈ（ｎ−１）ｋを計算しておく。
【００７１】
受信者の秘密のインデックス値をｉとする。ただし、ｉは１からｎの中から選ばれる。
【００７２】
転送処理において、まず、受信者は乱数ｒを生成し、ｇｒとｈｉ−１の積ｙを送信者に送信する。
【００７３】
送信者は、ｙをｋ乗した値をＫ１とし、Ｋ２＝Ｋ１／ｈｋ，…，Ｋｎ＝Ｋ１／ｈ（ｎ−１）ｋを計算する。次に、ランダムな文字列Ｒを生成し、各jについてＫｊ，Ｒとjの連結のハッシュ値Ｈ（Ｋｊ，Ｒ，j）と送信者の秘密情報ｍｊとの排他的論理和Ｅｊ（すなわち、Ｅ１，…，Ｅｎ）を計算する。最後に、（Ｅ１，…，Ｅｎ）とＲを受信者に送信する。
【００７４】
受信者は、βのｒ乗βｒを計算し、βｒとＲとｉの連結のハッシュ値Ｈ（βｒ，Ｒ，ｉ）とＥｉとの排他的論理和を計算することによって、ｉ番目の秘密情報ｍｉ（図示の例ではｍ２）を得ることができる。
【００７５】
図２及び図３の実施例のいずれにおいても、以下にまとめたように、初期化処理が有るので、転送処理に次の(step1)及び(step2)からなる２回の通信で済む。
【００７６】
（初期化処理）  送信者から受信者への通信。
【００７７】
（転送処理）
(step1)  受信者から送信者への通信。  
(step2)  送信者から受信者への通信。
【００７８】
従って、送受信者間で初期化処理に続いて何回も転送処理を行う場合（例えば、図１のように転送処理−１及び転送処理−２を行う場合）に有効である。
【００７９】
ＲＳＡ暗号を利用する図２の実施例によれば、従来、３回必要であった通信回数を２回に減らすことができる。
【００８０】
というのは、あらかじめ初期化処理を行うことにより、転送処理時に必要な通信回数を減らすことができるからである。
【００８１】
更に、巡回群を利用する図３の実施例によれば、初期化処理の計算量と通信量を減らすことができることである。
【００８２】
その理由は、複数の生成元を利用することにより、必要な計算量を減らすことができるからである。図４に、図３の実施例の場合（巡回群複数生成元を用いた場合）と巡回群一つの生成元を用いた場合との初期化処理における送信者の計算量及び通信量の比較を示す。情報の個数ｎが３以上の場合に、計算量及び通信量は、図３の実施例の場合（巡回群複数生成元を用いた場合）の方が巡回群一つの生成元を用いた場合よりも大幅に減らすことができる。
【図面の簡単な説明】
【００８３】
【図１】本発明の一実施形態による紛失通信方法を説明するための図である。
【図２】本発明の第１の実施例による紛失通信方法を説明するための図である。
【図３】本発明の第２の実施例による紛失通信方法を説明するための図である。
【図４】図３の実施例の場合（巡回群複数生成元を用いた場合）と巡回群一つの生成元を用いた場合との初期化処理における送信者の複雑さを比較して示した図である。
【図５】第２の従来技術（初期化処理が有るが、巡回群の生成元を１つのみ利用する紛失通信方法）を説明するための図である。
【図６】第３の従来技術（巡回群の生成元を２つ利用する場合で、初期化処理が無い紛失通信方法）を説明するための図である。
【符号の説明】
【００８４】
ｍ１  情報
ｍ２  情報
ｍ３  情報
ｍ４  情報
【図１】
2005189273.tif 000003
【図２】
2005189273.tif 000004
【図３】
2005189273.tif 000005
【図４】
2005189273.tif 000006
【図５】
2005189273.tif 000007
【図６】
2005189273.tif 000008