(57)【要約】【課題】送信者に対する適応的な攻撃に対して安全な通信方法を提供する。【解決手段】送信端末と受信端末を通信路を介して接続し、送信端末と受信端末は、ｇを位数ｑ（ｑは大きな素数）の群Ｇqの生成源、ｇと異なる生成源ｈ∈Ｇqを保持し、さらに送信端末はメッセージｍ∈Ｇqおよびｍ＝ｇs∈Ｇq（ｓ∈Ｚq、ｓ：メッセージの種，Ｚq：０〜ｑ−１の整数）を保持し、送信端末は、乱数ｒ（ｒ1，ｒ2）∈Ｚqを生成し、【数１７】2005258289.tif 000019受信端末に送信し、受信端末は、ｕを記憶するとともに、乱数ｘ∈Ｚqを生成し、ｙ＝ｇx，ｚ＝ｈxを計算し、（ｙ，ｚ）を送信端末に送信し、【数１８】2005258289.tif 000020受信端末は、ｍ＝ｃｕ-xを計算してメッセージｍを得る。【選択図】図１
2005258289.tif 000002
【特許請求の範囲】
【請求項１】
送信端末と受信端末を通信路を介して接続し、
送信端末と受信端末は、ｇを位数ｑ（ｑは大きな素数）の群Ｇqの生成源、ｇと異なる生成源ｈ∈Ｇqを保持するメモリと、さらに送信端末はメッセージｍ∈Ｇqおよびｍ＝ｇs∈Ｇq（ｓ∈Ｚq、ｓ：メッセージの種，Ｚq：０〜ｑ−１の整数）なるｓを保持するメモリを有し、
送信端末は、
乱数（ｒ1，ｒ2）∈Ｚqを生成する乱数生成器と、
【数１】
2005258289.tif 000015
受信端末は、
ｕを記憶するとともに、乱数ｘ∈Ｚqを生成し、ｙ＝ｇx，ｚ＝ｈxを計算し、（ｙ，ｚ）を送信端末に送信する演算器を有し、
送信端末は、
【数２】
2005258289.tif 000016
受信端末は、
ｍ＝ｃｕ-xを計算してメッセージｍを得る演算器を有することを特徴とする検証不可能な通信装置。
【請求項２】
送信端末と受信端末を通信路を介して接続し、
送信端末と受信端末は、ｇを位数ｑ（ｑは大きな素数）の群Ｇqの生成源、ｇと異なる生成源ｈ∈Ｇqを保持し、さらに送信端末はメッセージｍ∈Ｇqおよびｍ＝ｇs∈Ｇq（ｓ∈Ｚq、ｓ：メッセージの種，Ｚq：０〜ｑ−１の整数）なるｓを保持する手順と、
送信端末は、
乱数（ｒ1，ｒ2）∈Ｚqを生成する手順と、
【数３】
2005258289.tif 000017
受信端末は、
ｕを記憶するとともに、乱数ｘ∈Ｚqを生成し、ｙ＝ｇx，ｚ＝ｈxを計算し、（ｙ，ｚ）を送信端末に送信する手順と、
送信端末は、
【数４】
2005258289.tif 000018
受信端末は、
ｍ＝ｃｕ-xを計算してメッセージｍを得る手順を備えたことを特徴とする検証不可能な通信方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電気通信システムに関し、特に送信者に対する適応的な攻撃に対して安全な通信システムおよび方法を提供するものである。
【背景技術】
【０００２】
攻撃者による盗聴の可能性がある公開通信路を通じて送信者から受信者へメッセージｍを送付する通信システムの安全性の概念について説明する。
２入力２出力の関数：ｆ（outs，outr）＝ｆ（ins，inr）を、公開の手順πに従って２名のプレイヤーが協力して計算する場合、その手順πをｆを計算するための２者間プロトコルと呼ぶ。ここで、ins，outsはプレイヤー１の入力および出力であり、inr，outrはプレイヤー２の入力および出力である。プレイヤー１を送信者Ｓ、プレイヤー２を受信者Ｒと考えると、送信者から受信者へメッセージｍを送信する関数ｆは、入力ins＝（ｍ；ｒs），inr＝（⊥；ｒs）に対して出力がouts＝⊥，outr＝ｍである関数と考えることができる。（ここで、ｒは乱数であり、⊥は何も入力あるいは出力がないことを表す。）
【０００３】
ある２者間プロトコルに関して、攻撃者にとって実際のプロトコル実行と区別の付かないシミュレーションが可能な場合、その２者間プロトコルは安全であると考える。より正確には以下のように安全性を定義する。攻撃者Ａがプレイヤーを攻撃するとは、攻撃者がそのプレイヤーのもつすべての情報を入手し、さらに、それ以降そのプレイヤーの行動を完全に制御することができることを意味する。（実際にどのような手段で攻撃したかは問題ではない。攻撃によって得られる情報とその後の行動だけが安全性を論じる上での関心事である。）一般的な暗号プロトコルπの安全性は、そのプロトコルを実際に実行してｆの計算を行った場合と、信頼できる第三者Ｆによって理想的に安全な状況でｆの計算が行われた場合との比較によって定義される。理想的に安全な状況での計算とは、各プレーヤーからＦへの入力が安全な通信路（完全秘匿で相互認証可能な同期通信路）で絶対的に信頼できる第三者に送信され、計算結果が安全な通信路で各プレイヤーへ送信される状況を指す。プロトコルπが理想状態での計算Ｆを安全にエミュレートするとは、プロトコルπに対するどのような攻撃者Ａに対しても、理想状態での計算ＦにおいてＡと同等の結果を出力するシミュレータＳが存在することである。もう少し正確には、攻撃者の存在の下で計算を実行したときの全プレイヤーの出力と攻撃者の出力のビット結合をその計算におけるグローバル出力と定義し、プロトコルπの実行におけるグローバル出力の分布と理想状態での計算のグローバル出力の分布が識別不可能であるとき、プロトコルπが理想状態での計算Ｆを安全にエミュレートしているという。
【０００４】
直観的には、理想状態ではどのような意味の攻撃も成功し得ないので、常に攻撃者ＡとシミュレータＳの出力分布が識別不可能ならば、Ａも攻撃には成功していないと考えられる。従って、プロトコルπは理想状態Ｆと同等の安全性を有していると見なすことができる。
【０００５】
公開鍵暗号を用いた単純な方式は上記の安全性を満たさないことについて説明する。
pkr，skrをそれぞれ受信者の公開鍵、秘密鍵とする。公開鍵は予め送信者と受信者で共有されており、秘密鍵は受信者のみが安全に保管しているもととする。Ｅ，Ｄを確率的暗号の暗号化関数、復号関数とする。
【数５】
2005258289.tif 000003
は受信者の公開鍵 pkrでメッセージｍを暗号化して、その出力を暗号文ｃと呼ぶことを意味する。ここでｒは乱数である。同様に
【数６】
2005258289.tif 000004
は暗号文ｃを復号してメッセージｍを得ることを意味する。
【数７】
2005258289.tif 000005
いま、実環境での攻撃者Ａがプロトコル実行後に受信者を攻撃した場合を考える。Ａはメッセージｍ，秘密鍵skrを入手し、それらが送受信された暗号文と矛盾しないかどうかを
【数８】
2005258289.tif 000006
【０００６】
このＡの状況をシミュレートするシミュレータを構成することが困難なことは次のように説明できる。理想環境においてＡの行動を全くまねるシミュレータＳは、通常、Ａをサブルーチン（あるいはブラックボックス）として用いて構成される。Ａは実環境でしか動作しないので、まず、Ｓは送信者の役を演じて暗号文ｃを公開通信路へ送出し、Ａにこれを与えなければならない。ところが、シミュレータＳは実際のメッセージを知らないため、この段階では、メッセージｍ’を適当に選び、それに対する暗号文ｃ’を公開するしかない。Ａが（実環境をシミュレートするためにＳが演じている）受信者を攻撃した場合、Ｓも同様に（理想環境での）受信者を攻撃し、本物のｍ，skrを入手する。この本物のｍ，skrをＡに渡すことで、シミュレートしている実環境での攻撃に対処するが、ｃ’を復号してもｍにはならないため、それ以降、Ａは本来の動作を行わなくなる可能性がある。よって、Ｓは本来のＡと同様の出力を行えず、シミュレーションは失敗する。
【０００７】
上記安全性を満たす従来の技術として、Jareckiらによる方法（非特許文献１  参照）を説明する。
ｑを大きな素数とし、ｇを位数ｑの乗法群Ｇqの生成源とする。集合αから一つの元βをランダムに選ぶ行為をβ←αと書くことにする。特に断りのない限り、演算はすべてｇの生成する群で行うものとする。
送信者Ｓはメッセージｍ∈Ｇqを保持し、ｍ＝ｇsなるメッセージの種ｓ∈Ｚq（０〜ｑ−１の整数）をも保持するものとする。さらに、送信者と受信者はｇ，ｈ∈Ｇqを共有しているものとする。あるいは、このｇ，ｈは受信者が生成し、事前に送信者へ送付しておいてもよい。
１．受信者はｘ，ｙ←Ｚqを選び、ｚ＝ｇxｈyを計算して送信者へ送る。
２．送信者はｒ（乱数）←Ｚqを選び、ｕ＝ｇr，ｖ＝ｈr，ｃ＝ｍｚrを計算して（ｕ，ｖ，ｃ）を受信者に送る。
３．受信者は、ｍ＝ｃ／（ｕx，ｖy）としてメッセージｍを復元する。
【０００８】
上記従来法は、受信者に対する事後的な攻撃、すなわち、送信完了後に行われる攻撃に対して安全であることが、以下のようなシミュレータを構成できることで示される。シミュレータは、まず、ｈ＝ｇa，ｚ＝ｇx'ｈy'をランダムなａ，ｘ’，ｙ’で生成し、実環境の送信者として第一ステップを実行する、
【数９】
2005258289.tif 000007
二ステップを実行する。プロトコル実行後に受信者が攻撃を受けた場合に、受信者はあたかも本物のメッセージｍ＝ｇsを受信したかのように見せかけるため、シミュレータは、ｍ＝ｃ／（ｕx，ｖy）およびｚ＝ｇxｈyが成り立つｘ，ｙを計算する。ｘ，ｙの値は、上記関係から導かれる連立方程式ｓ＝γ−αｘ−βｙ  modｑ，ｘ’＋ａｙ’＝ｘ＋ａｙ  modｑを解くことで容易に得ることができる。シミュレータはこの（ｍ，ｘ，ｙ）を受信者の内部情報として攻撃者に渡す。攻撃者が入手した（ｍ，ｘ，ｙ）は上記シミュレートされた通信履歴に矛盾しない。また、シミュレートされた通信履歴と実環境での通信履歴を見分けることはｇ，ｕ，ｈ，ｖがloggｕ＝loghｖを満たすか否かを判定することと等価であり、これはDiffie-Hellman判定問題を解くことに相当するため、計算量的に困難であると考えられている。
【非特許文献１】S.Jarecki and A.Lysyanskaya, “Adaptively Secure Threshold Cryptography: Introducing Concurrency, Removing Erasures ”, Eurocrypt 2000,LNCS 1807, pp 221-242,Springer-Verlag
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上記の従来法は、受信者に対する事後的な攻撃に対して安全性を有する送信方法であるが、送信者に対する攻撃に対して安全性を有する方式ではない。
これは正しく作られたｕ，ｖ，ｃから乱数ｒ，メッセージｍが一意に定まるため、送信者が攻撃された場合にシミュレータが送信者の内部情報を操作する余地が全くないためである。上記と同様にシミュレートした通信履歴を作成した場合には、ｒ＝loggｕ≠loghｖであり、無矛盾なｒが存在しなくなってしまう。いずれにしても、当初からｍを知らなければ、シミュレータは受信者の内部情報に対して無矛盾な通信履歴を作ることができない。
本発明の目的は、送信者に対する攻撃に対して安全性を有する通信システム及び通信方法を提供することにある。
【課題を解決するための手段】
【００１０】
ｑを大きな素数とし、ｇを位数ｑの群Ｇqの生成源とする。ｘ，ｙ∈Ｇqに対する二項演算ｘ×ｙをＧqの群演算とし、ａ∈Ｚ（整数），ｘ∈Ｇqに対する二項演算ｘaを群演算のａ  mod q回の繰り返しｘｘ・・・ｘとする。送信者はメッセージｍ∈Ｇqを保持し、ｍ＝ｇsなるｓ∈Ｚq（ｓ：メッセージの種）をも保持するものとする。さらに、送信者と受信者はｈ∈Ｇqを共有しているものとする。共有していない場合は受信者がｈを生成し、送信者へ送る。
送信者と受信者は以下の手順によりメッセージを送受する。ここでアルゴリズムは公開されているものとする。
【数１０】
2005258289.tif 000008
２．受信者は乱数ｘ←Ｚqを選び、ｙ＝ｇx、ｚ＝ｈxを計算して（ｙ，ｚ）を送信者へ送る。
【数１１】
2005258289.tif 000009
４．受信者は、ｍ＝ｃ／ｕxとしてメッセージｍを復元する。
【００１１】
（作用）
上記手段によれば、送信者に対する事後的な攻撃、すなわち、送信完了後に行われる攻撃に対して安全あることが以下のように示される。
まず、シミュレータはｈ＝ｇaをランダムなａで生成する。次に、送信者と受信者を、
【数１２】
2005258289.tif 000010
と受信者を演じてプロトコルをシミュレートする。プロトコル実行後に送信者が攻撃を受けた場合に、送信者はあたかも本物のメッセージｍ＝ｇsを送信したかのように見せかけるため、シミュレータは、
【数１３】
2005258289.tif 000011
そのようなｒ1，ｒ2の値は、上記関係から導かれる連立方程式ｓ＝γ−αｒ1−βｒ2  mod q，ω＝ｒ1＋ａｒ2  mod qを解くことで容易に得ることができる。
シミュレータはこの（ｍ，ｒ1，ｒ2）を受信者の内部情報として攻撃者に渡す。攻撃者が入手した（ｍ，ｒ1，ｒ2）は、
【数１４】
2005258289.tif 000012
また、シミュレートされた通信履歴と実環境での通信履歴を見分けることは、ｇ，ｙ，ｈ，ｚがloggｙ＝loghｚを満たすか否かを判定することと等価であり、これはDiffie-Hellman判定問題を解くことに相当するため、計算量的に困難と考えられている。すなわち、攻撃者が検証をすることができない。
【発明の効果】
【００１２】
プロトコル終了後に攻撃者が送信者を攻撃してその内部情報を入手したとしても、その情報はシミュレータが作成できる偽の情報と区別がつかないため、本発明の通信方法は、送信者に対する攻撃に対して安全性を有する。
【発明を実施するための最良の形態】
【００１３】
発明の通信手段による通信装置は、送信端末、受信端末、及びそれらを接続する通信路から構成される。
送信端末、受信端末はそれぞれ、少なくとも共通パラメータとして大きな素数ｑ、位数ｑの群Ｇqの生成源ｇ、および、ｇと異なる生成源ｈ∈Ｇqが格納されているメモリを備えている。
送信端末のメモリには、さらに、メッセージｍ∈Ｇqおよびｍ＝ｇs∈Ｇqなるｓ∈Ｚq（ｓ：メッセージの種，Ｚq：０〜ｑ−１の整数）が格納されている。
送信端末、受信端末はさらにＧq，Ｚq上で演算を行うための演算器、乱数を生成するための乱数生成器を具備する。
【００１４】
動作の説明
１．送信端末は乱数生成器を駆動して乱数ｒ（ｒ1，ｒ2）∈Ｚqを生成し、演算器を駆動して
【数１５】
2005258289.tif 000013
２．受信端末はｕを受信し、乱数生成器を駆動して乱数ｘ∈Ｚqを生成し、演算器を駆動してｙ＝ｇx，ｚ＝ｈyを計算し、送信端末へ（ｙ，ｚ）を送信する。
３．（ｙ，ｚ）を受信した送信端末は、演算器を駆動して
【数１６】
2005258289.tif 000014
４．受信端末は、ｃ，ｕおよびｘを演算器に入力してｃｕ-xを計算し、その結果を受信メッセージｍとする。
【図面の簡単な説明】
【００１５】
【図１】本発明の電気通信システムの構成例を示す図。
【図１】
2005258289.tif 000021