(57)【特許請求の範囲】
【請求項１】
複数の第１鍵のうちのいずれかの第１鍵と平文とを使用して排他的論理和を計算することにより、前記平文が暗号化されたデータであり、同一の平文であっても暗号化に使用される前記第１鍵の値が異なれば異なる値を持つデータである第１暗号化データを生成する暗号化部と、
前記平文の暗号化に使用された前記第１鍵と、ｋビットのランダムな値である第２鍵との排他的論理和を計算することにより、第３鍵を生成する第３鍵生成部と、
前記第３鍵を前記第１暗号化データに適用することで、同一の平文が使用されている前記第１暗号化データを、前記第１暗号化データの暗号化に使用されている前記第１鍵の値によらず同一の値となる第２暗号化データに変換する暗号化データ変換部と、
を備える暗号システム。
【請求項２】
第１要素と、第２要素と、第３要素とを含む複数の第１鍵のうちのいずれかの第１鍵に含まれる前記第１要素及び前記第２要素と平文とを使用して、前記平文が暗号化されたデータであり、同一の平文であっても暗号化に使用される前記第１鍵の値が異なれば異なる値を持つデータである第１暗号化データを生成する暗号化部と、
前記平文の暗号化に使用された前記第１鍵に含まれる前記第３要素に、ｍｏｄ＝ｐの整数の集合Ｚｐに属する要素ｘである第２鍵を適用し、適用して得られた値と、前記平文の暗号化に使用された前記第１鍵との組を、第３鍵として生成する第３鍵生成部と、
前記第３鍵を前記第１暗号化データに適用することで、同一の平文が使用されている前記第１暗号化データを、前記第１暗号化データの暗号化に使用されている前記第１鍵の値によらず同一の値となる第２暗号化データに変換する暗号化データ変換部と、
を備える暗号システム。
【請求項３】
前記暗号システムは、さらに、
２つの前記第２暗号化データどうしの前記値が一致するかどうかを判定する一致判定部を備える請求項１または請求項２に記載の暗号システム。
【請求項４】
複数の第１鍵のうちのいずれかの第１鍵と平文とを使用して排他的論理和を計算することにより、前記平文が暗号化されたデータであり、同一の平文であっても暗号化に使用される前記第１鍵の値が異なれば異なる値を持つデータである第１暗号化データを取得する取得部と、
前記平文の暗号化に使用された前記第１鍵と、ｋビットのランダムな値である第２鍵との排他的論理和を計算することにより生成された第３鍵を取得する第３鍵取得部と、
同一の平文が使用されている前記第１暗号化データを、前記第１暗号化データの暗号化に使用されている前記第１鍵の値によらず同一の値となる第２暗号化データに変換する変換部と、
２つの前記第２暗号化データどうしの前記値が一致するかどうかを判定する一致判定装置に、前記第２暗号化データを送信する送信制御部と
を備える暗号化データ変換装置。
【請求項５】
第１要素と、第２要素と、第３要素とを含む複数の第１鍵のうちのいずれかの第１鍵に含まれる前記第１要素及び前記第２要素と平文とを使用して、前記平文が暗号化されたデータであり、同一の平文であっても暗号化に使用される前記第１鍵の値が異なれば異なる値を持つデータである第１暗号化データを取得する取得部と、
前記平文の暗号化に使用された前記第１鍵に含まれる前記第３要素にｍｏｄ＝ｐの整数の集合Ｚｐに属する要素ｘである第２鍵を適用して得られた値と、前記平文の暗号化に使用された前記第１鍵との組として生成された第３鍵を取得する第３鍵取得部と、
同一の平文が使用されている前記第１暗号化データを、前記第１暗号化データの暗号化に使用されている前記第１鍵の値によらず同一の値となる第２暗号化データに変換する変換部と、
２つの前記第２暗号化データどうしの前記値が一致するかどうかを判定する一致判定装置に、前記第２暗号化データを送信する送信制御部と
を備える暗号化データ変換装置。
【請求項６】
コンピュータに、
複数の第１鍵のうちのいずれかの第１鍵と平文とを使用して排他的論理和を計算することにより、前記平文が暗号化されたデータであり、同一の平文であっても暗号化に使用される前記第１鍵の値が異なれば異なる値を持つデータである第１暗号化データを取得する取得処理と、
前記平文の暗号化に使用された前記第１鍵と、ｋビットのランダムな値である第２鍵との排他的論理和を計算することにより生成された第３鍵を取得する第３鍵取得処理と、
同一の平文が使用されている前記第１暗号化データを、前記第１暗号化データの暗号化に使用されている前記第１鍵の値によらず同一の値となる第２暗号化データに変換する変換処理と、
２つの前記第２暗号化データどうしの前記値が一致するかどうかを判定する一致判定装置に、前記第２暗号化データを送信する送信制御処理と、
を実行させる変換プログラム。
【請求項７】
コンピュータに、
第１要素と、第２要素と、第３要素とを含む複数の第１鍵のうちのいずれかの第１鍵に含まれる前記第１要素及び前記第２要素と平文とを使用して、前記平文が暗号化されたデータであり、同一の平文であっても暗号化に使用される前記第１鍵の値が異なれば異なる値を持つデータである第１暗号化データを取得する取得処理と、
前記平文の暗号化に使用された前記第１鍵に含まれる前記第３要素にｍｏｄ＝ｐの整数の集合Ｚｐに属する要素ｘである第２鍵を適用して得られた値と、前記平文の暗号化に使用された前記第１鍵との組として生成された第３鍵を取得する第３鍵取得処理と、
同一の平文が使用されている前記第１暗号化データを、前記第１暗号化データの暗号化に使用されている前記第１鍵の値によらず同一の値となる第２暗号化データに変換する変換処理と、
２つの前記第２暗号化データどうしの前記値が一致するかどうかを判定する一致判定装置に、前記第２暗号化データを送信する送信制御処理と、
を実行させる変換プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２つの暗号化データが重複する際に、一方の暗号化データを除外する、重複除外システムに関する。
【背景技術】
【０００２】
重複する暗号化データを除外することができる暗号システムは、暗号化データを復号することなく、暗号化されている平文が、暗号化データどうしで、一致しているか、いないかを判定可能である（例えば、特許文献１及び非特許文献１）。【０００３】
特許文献１、非特許文献１のような、通常の重複除外可能な暗号の核となるアイディアは、平文をハッシュ関数により固定長のビット列へ変換し、それを暗号鍵とし、その暗号鍵で暗号化を実施する。これにより、もし同じ平文であれば、同じ平文から生成された暗号鍵どうしは同じ鍵となり、ＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）のような確定的暗号を用いれば、同じ平文は同じ値の暗号文となる。
一方で、平文が１ビットでも異なるのならば全く異なる鍵が生成され、生成される暗号文の値も異なる。このようなシステムによって、ユーザは鍵を持つことなく、暗号文の重複を除外可能な暗号を利用できる。【０００４】
このような重複除外可能な暗号では、暗号文は識別不可能性という、暗号におけるデファクトスタンダードの安全性を持たないことが知られている。
また、ユーザごとの鍵が存在せず、ユーザごとの暗号文の区別がつかないため、前述の識別不可能性を持たないことと組み合わせて、従来技術のような暗号では、ほかのユーザから自身の暗号文の平文情報が、漏洩する危険性がある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特表２０１４−５０７８４１号公報
【非特許文献】
【０００６】
【非特許文献１】Ｍｉｈｉｒ  Ｂｅｌｌａｒｅ，  Ｓｒｉｒａｍ  Ｋｅｅｌｖｅｅｄｈｉ，  Ｔｈｏｍａｓ  Ｒｉｓｔｅｎｐａｒｔ：“Ｍｅｓｓａｇｅ−Ｌｏｃｋｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  ａｎｄ  Ｓｅｃｕｒｅ  Ｄｅｄｕｐｌｉｃａｔｉｏｎ”．  ＥＵＲＯＣＲＹＰＴ  ２０１３：  ２９６−３１２
【発明の概要】
【発明が解決しようとする課題】
【０００７】
この発明は、以下の（１）（２）（３）の可能な暗号システムの提供を目的とする。
（１）ユーザごとに暗号鍵が設定できる。
（２）ユーザが暗号鍵で暗号文を生成した時点では暗号文は重複除外不可能である。しかし、暗号文は識別不可能性を満たす。
（３）ユーザが許可した場合のみ、暗号鍵で生成された暗号文を、重複除外可能な暗号文に変換できる。
【課題を解決するための手段】
【０００８】
この発明の暗号システムは、
第１鍵と平文とを使用して、前記平文が暗号化された第１暗号化データを生成する暗号化部と、
前記第１鍵と第２鍵とを使用して、第３鍵を生成する第３鍵生成部と、
前記第３鍵を前記第１暗号化データに適用することで、同一の平文が使用されている前記第１暗号化データを、前記第１暗号化データに使用されている前記第１鍵の値によらず同一の値となる第２暗号化データに変換する暗号化データ変換部と、
を備える。
【発明の効果】
【０００９】
この発明の暗号システムにより、以下の（１）（２）（３）の可能な暗号システムを提供できる。
（１）ユーザごとに暗号鍵が設定できる。
（２）ユーザが暗号鍵で暗号文を生成した時点では暗号文は重複除外不可能である。しかし、暗号文は識別不可能性を満たす。
（３）ユーザが許可した場合のみ、暗号鍵で生成された暗号文を、重複除外可能な暗号文に変
【図面の簡単な説明】
【００１０】
【図１】実施の形態１の図で、重複除外システム１００の構成を示すブロック図。
【図２】実施の形態１の図で、共通パラメータ生成装置２００の構成を示すブロック図。
【図３】実施の形態１の図で、ユーザ鍵生成装置３００の構成を示すブロック図。
【図４】実施の形態１の図で、暗号化装置４００の構成を示すブロック図。
【図５】実施の形態１の図で、変換鍵生成装置５００の構成を示すブロック図。
【図６】実施の形態１の図で、タグ変換装置６００の構成を示すブロック図。
【図７】実施の形態１の図で、一致判定装置７００の構成を示すブロック図。
【図８】実施の形態１の図で、共通パラメータ生成装置２００の動作を示すフローチャート。
【図９】実施の形態１の図で、ユーザ鍵生成装置３００の動作を示すフローチャート。
【図１０】実施の形態１の図で、暗号化装置４００の動作を示すフローチャート。
【図１１】実施の形態１の図で、変換鍵生成装置５００の動作を示すフローチャート。
【図１２】実施の形態１の図で、タグ変換装置６００の動作を示すフローチャート。
【図１３】実施の形態１の図で、一致判定装置７００の動作を示すフローチャート。
【図１４】実施の形態１の図で、重複除外システム１００の動作を示す図。
【図１５】実施の形態２の図で、共通パラメータ生成装置２００の構成を示すブロック図。
【図１６】実施の形態２の図で、ユーザ鍵生成装置３００の動作を示すフローチャート。
【図１７】実施の形態２の図で、暗号化装置４００の動作を示すフローチャート。
【図１８】実施の形態２の図で、変換鍵生成装置５００の動作を示すフローチャート。
【図１９】実施の形態２の図で、タグ変換装置６００の動作を示すフローチャート。
【図２０】実施の形態２の図で、一致判定装置７００の動作を示すフローチャート。
【図２１】実施の形態２の図で、重複除外システム１００の動作を示す図。
【図２２】実施の形態２の図で、重複除外システム１００の備える各装置のハードウェア資源を示す図。
【図２３】実施の形態２の図で、重複除外システム１００の備える各装置のハードウェア資源を補足する図。
【発明を実施するための形態】
【００１１】
以下、実施の形態について、図を用いて説明する。なお、各図中、同一又は相当する部分には、同一符号を付している。実施の形態の説明において、同一又は相当する部分については、その説明を適宜省略又は簡略化する。
【００１２】
実施の形態１．
実施の形態１の重複除外システム１００を説明する。重複除外システム１００は、暗号文が重複する暗号文を除外する暗号システムである。
図１は、重複除外システム１００のシステム構成を示す。
図１に示すように、重複除外システム１００は、共通パラメータ生成装置２００、複数のユーザ鍵生成装置３００、複数の暗号化装置４００、変換鍵生成装置５００、タグ変換装置６００及び一致判定装置７００を備える。タグ変換装置６００は、暗号化タグＥＴａｇを暗号化タグＴに変換する。暗号化タグＥＴａｇは第１暗号化データであり暗号化タグＴは第２暗号化データである。暗号化装置４００は暗号化部に相当し、変換鍵生成装置５００は第３鍵生成部に相当し、タグ変換装置６００は暗号化データ変換部に相当し、一致判定装置７００は一致判定部に相当する。
【００１３】
共通パラメータ生成装置２００、複数のユーザ鍵生成装置３００、複数の暗号化装置４００、変換鍵生成装置５００、タグ変換装置６００及び一致判定装置７００は、コンピュータである。
【００１４】
重複除外システム１００では、共通パラメータ生成装置２００、複数のユーザ鍵生成装置３００、複数の暗号化装置４００、変換鍵生成装置５００、タグ変換装置６００及び一致判定装置７００は、ネットワーク１０１に接続している。ネットワーク１０１はインターネットでも良いし、企業内に敷設されたＬＡＮ（Ｌｏｃａｌ・Ａｒｅａ・Ｎｅｔｗｏｒｋ）でも良い。
ネットワーク１０１は、共通パラメータ生成装置２００と、複数のユーザ鍵生成装置３００と、複数の暗号化装置４００と、変換鍵生成装置５００と、タグ変換装置６００と、一致判定装置７００とを接続する通信路である。
【００１５】
共通パラメータ生成装置２００は、重複除外システム１００で用いる共通のパラメータを作成し、ネットワーク１０１を介して、複数のユーザ鍵生成装置３００と、複数の暗号化装置４００と、変換鍵生成装置５００とタグ変換装置６００へ、共通パラメータを送信する。なお、この共通パラメータは、ネットワーク１０１を介さず、郵送のような手段で、直接的に重複除外システム１００の関係者に送信してもよい。
【００１６】
ユーザ鍵生成装置３００は、ユーザ鍵を生成し、ユーザ鍵を暗号化装置４００及び変換鍵生成装置５００に送信する。暗号化装置４００は、平文Ｍと、ユーザ鍵生成装置３００から送信されたユーザ鍵を入力として暗号化タグＥＴａｇを生成し、ＥＴｔａｇをタグ変換装置６００へ送信する。変換鍵生成装置５００は、ユーザ鍵生成装置３００からユーザ鍵を受信し、ユーザ鍵から変換鍵ｃｋを生成する。タグ変換装置６００は、変換鍵生成装置５００から変換鍵ｃｋを受信し、暗号化装置４００から暗号化タグＥＴａｇを受信する。タグ変換装置６００は、変換鍵ｃｋを用いて、第１暗号化データである暗号化タグＥＴａｇを、第２暗号化データである、重複除外可能な暗号化タグＴに変換する。タグ変換装置６００は、暗号化タグＴを一致判定装置７００へ送信する。一致判定装置７００は、タグ変換装置６００から、複数の暗号化タグＴを受信し、暗号化タグＴどうしが一致するかどうかを判定し、判定結果を出力する。
【００１７】
なお、一台のコンピュータによって、ユーザ鍵生成装置３００、暗号化装置４００、変換鍵生成装置５００、タグ変換装置６００のいずれか二台の装置、いずれか三台の装置、あるいは四台の装置が実現されても良い。
【００１８】
図２は、共通パラメータ生成装置２００の構成を示すブロック図である。共通パラメータ生成装置２００は、入力部２０１、共通パラメータ生成部２０２及び送信部２０３を備えている。図示していないが、共通パラメータ生成装置２００は、共通パラメータ生成装置２００の各部で使用されるデータを記憶する記録媒体を備えている。入力部２０１には、重複除外システム１００で用いる鍵のビット長ｋが入力される。共通パラメータ生成部２０２は、重複除外システム１００で実行される演算の基本となる共通パラメータを生成する。図示していないが、共通パラメータを生成するために、共通パラメータ生成部２０２は乱数生成機能を備えてもよい。送信部２０３は、共通パラメータ生成部２０２で生成された共通パラメータを、複数のユーザ鍵生成装置３００へ送信する。
【００１９】
図３は、ユーザ鍵生成装置３００の構成を示すブロック図である。ユーザ鍵生成装置３００は、パラメータ受信部３０１、鍵生成部３０２及び鍵送信部３０３を備えている。図示していないが、ユーザ鍵生成装置３００は、ユーザ鍵生成装置３００の各部で使用されるデータを記憶する記録媒体を備えている。パラメータ受信部３０１は、共通パラメータを受信する。鍵生成部３０２は、暗号鍵ｅｋ及び変換鍵生成鍵ｔｋを生成する。図示していないが、これらの鍵を生成するために、鍵生成部３０２は乱数生成機能を備えてもよい。鍵送信部３０３は、暗号鍵ｅｋを暗号化装置４００へ送信し、暗号鍵ｅｋ及び変換鍵生成鍵ｔｋを変換鍵生成装置５００へ送信する。
【００２０】
図４は、暗号化装置４００の構成を示すブロック図である。図４に示すように、暗号化装置４００は、入力部４０１と、受信部４０２と、タグ生成部４０３と、タグ送信部４０４とを備える。図示していないが、暗号化装置４００は、暗号化装置４００の各部で使用されるデータを記憶する記録媒体を備えている。入力部４０１には、平文Ｍが入力される。受信部４０２は、暗号鍵ｅｋを受信する。タグ生成部４０３は暗号化タグＥＴａｇを生成する。図示していないが、暗号ＥＴａｇを生成するために、タグ生成部４０３は乱数生成機能を備えてもよい。タグ送信部４０４は、タグ生成部４０３で生成され暗号化タグＥＴａｇを、タグ変換装置６００へ送信する。
【００２１】
図５は、変換鍵生成装置５００の構成を示すブロック図である。変換鍵生成装置５００は、鍵受信部５０１と、変換鍵生成部５０２と、送信部５０３を備えている。図示していないが、変換鍵生成装置５００は、変換鍵生成装置５００の各部で使用されるデータを記憶する記録媒体を備えている。鍵受信部５０１は、暗号鍵ｅｋ及び変換鍵生成鍵ｔｋを受信する。変換鍵生成部５０２は、暗号鍵ｅｋと変換鍵生成鍵ｔｋとから変換鍵ｃｋを生成する。図示していないが、変換鍵ｃｋを生成するために、変換鍵生成部５０２は乱数生成機能を備えてもよい。送信部５０３は、変換鍵ｃｋをタグ変換装置６００へ送信する。
【００２２】
図６は、タグ変換装置６００の構成を示すブロック図である。タグ変換装置６００は、暗号化データ変換装置である。
タグ変換装置６００は、受信部６０１、入力部６０２、鍵保管部６０３、変換部６０４及び送信部６０５を備えている。図示していないが、タグ変換装置６００は、タグ変換装置６００の各部で使用されるデータを記憶する記録媒体を備えている。
受信部６０１は、変換鍵ｃｋを受信する。入力部６０２は暗号化タグＥｔａｇを受信する。鍵保管部６０３は、変換鍵ｃｋを保管している。変換部６０４は、鍵保管部６０３に保管されている変換鍵ｃｋを用いて、入力部６０２で入力された暗号ＥＴａｇを、重複除外可能な暗号化タグＴに変換する。図示していないが、暗号化タグＥＴａｇを暗号化タグＴに変換するために、変換部６０４は乱数生成機能を備えてもよい。送信部６０５は、重複除外可能な暗号データである暗号化タグＴを一致判定装置７００へ送信する。
【００２３】
図７は、一致判定装置７００の構成を示すブロック図である。一致判定装置７００は、タグ入力部７０１、判定部７０２及び送信部７０３を備えている。図示していないが、一致判定装置７００は、一致判定装置７００の各部で使用されるデータを記憶する記録媒体を備えている。タグ入力部７０１には、重複除外可能な暗号化された暗号化タグＴ１と、重複除外可能な暗号化された暗号化タグＴ２とが入力される。判定部７０２は、暗号化タグＴ１と暗号化タグＴ２との値が一致するかどうかを判定する。送信部７０３は、一致するかどうかの判定結果を出力する。
【００２４】
以下では、重複除外システム１００の各装置の動作を説明する。
図８は、共通パラメータ生成装置２００の動作を示すフローチャートである。
図９は、ユーザ鍵生成装置３００の動作を示すフローチャートである。
図１０は、暗号化装置４００の動作を示すフローチャートである。暗号化装置４００は、暗号鍵ｅｋと平文Ｍとを使用して、平文Ｍが暗号化された暗号化タグＥＴａｇを生成する。
図１１は、変換鍵生成装置５００動作を示すフローチャートである。変換鍵生成装置５００は、暗号鍵ｅｋと変換鍵生成鍵ｔｋとを使用して、変換鍵ｃｋを生成する。
図１２は、タグ変換装置６００の動作を示すフローチャートである。タグ変換装置６００は、変換鍵ｃｋを暗号化タグＥＴａｇに適用することで、同一の平文Ｍが使用されている暗号化タグＥＴａｇを、暗号化タグＥＴａｇに使用されている暗号鍵ｅｋの値によらず同一の値となる暗号化タグＴに変換する。
図１３は、一致判定装置７００の動作を示すフローチャートである。一致判定装置７００は、２つの第２暗号化データＴどうしの値が一致するかどうかを判定する。
図１４は、図８から図１２のフローチャートをシーケンスとして示す図である。
図１４と図１３を参照して重複除外システム１００の各装置の動作を説明する。
【００２５】
図１４に示す重複除外システム１００の動作概要は以下のようである。暗号化装置４００は、暗号化タグＥＴａｇとして、暗号鍵ｅｋと平文Ｍとの排他的論理和を計算する。変換鍵生成装置５００は、暗号鍵ｅｋと変換鍵生成鍵ｔｋとの排他的論理和を計算し、計算結果を変換鍵ｃｋとして生成する。タグ変換装置６００は、変換鍵ｃｋを第１暗号化データである暗号化タグＥＴａｇに適用することで、暗号化タグＥＴａｇを、第２暗号化データである暗号化タグＴに変換する。
【００２６】
＜共通パラメータ生成装置２００＞
ステップＳ２０１において、入力部２０１にはビット長ｋが入力される。
ステップＳ２０２において、共通パラメータ生成部２０２は、ｋビットのランダムな値ｓｋを、共通パラメータとして生成する。
ステップＳ２０３において、送信部２０３は、ビット長ｋと共通パラメータｓｋをユーザ鍵生成装置３００へと送信する。
【００２７】
＜ユーザ鍵生成装置３００＞
ステップＳ３０１において、パラメータ受信部３０１は、共通パラメータ生成装置２００から、ビット長ｋと共通パラメータｓｋを受信する。
ステップＳ３０２において、鍵生成部３０２は、ｋビットのランダムな値ｓｋＡを暗号鍵ｅｋとして生成する。また、鍵生成部３０２は、変換鍵生成鍵ｔｋを暗号鍵ｓｋとして設定する。
ステップＳ３０３において、鍵送信部３０３は、暗号鍵ｅｋを暗号化装置４００へ送信し、暗号鍵ｅｋ及び変換鍵生成鍵ｔｋを変換鍵生成装置５００へと送信する。
【００２８】
＜暗号化装置４００＞
ステップＳ４０１において、入力部４０１には、平文Ｍが入力される。
ステップＳ４０２において、受信部４０２は、ユーザ鍵生成装置３００から、暗号鍵ｅｋを受信する。
ステップＳ４０３において、タグ生成部４０３は、
ＥＴａｇ＝Ｈａｓｈ（Ｍ）＜ＸＯＲ＞ｓｋＡ      （式１）
を計算する。ここでＨａｓｈは暗号学的ハッシュ関数を指し、例えばＳＨＡ２５６である。＜ＸＯＲ＞は排他的論理和を表す。
ステップＳ４０４において、タグ送信部４０４は、暗号ＥＴａｇをタグ変換装置６００へ送信する。
【００２９】
＜変換鍵生成装置５００＞
ステップＳ５０１において、鍵受信部５０１は、ユーザ鍵生成装置３００から、暗号鍵ｅｋ及び変換鍵生成鍵ｔｋを受信する。
ステップＳ５０２において、変換鍵生成部５０２は、
ｃｋ＝ｅｋ＜ＸＯＲ＞ｔｋ＝ｓｋＡ＜ＸＯＲ＞ｓｋ      （式２）
を計算する。
ステップＳ５０３において、送信部５０３は、変換鍵ｃｋを、タグ変換装置６００へ送信する。
【００３０】
＜タグ変換装置６００＞
ステップＳ６０１において、第３鍵取得部である受信部６０１は、暗号鍵ｅｋと第２鍵である変換鍵生成鍵ｔｋとを使用して生成された第３鍵である変換鍵ｃｋを取得する。
ステップＳ６０２において、取得部である入力部６０２は、第１鍵である暗号鍵ｅｋと平文Ｍとを使用して平文Ｍが暗号化された第１暗号化データである暗号化タグＥＴａｇを取得する。
ステップＳ６０３において、変換部６０４は、同一の平文Ｍが使用されている暗号化タグＥＴａｇを、暗号化タグＥＴａｇに使用されている暗号鍵ｅｋの値によらず同一の値となる第２暗号化データである暗号化タグＴに変換する。具体的には、以下のようである。
実施の形態１の重複除外システム１００では、ステップＳ９０２で設定される変換鍵生成鍵ｔｋ＝Ｓｋは、異なるユーザに同じ鍵が設定される。よって、以下の（式３）によれば、同一の平文Ｍが使用されている暗号化タグＥＴａｇは、暗号化タグＥＴａｇに使用されている暗号鍵ｅｋの値によらず同一の値となる暗号化タグＴに変換される。
Ｔ＝ｃｋ＜ＸＯＲ＞ＥＴａｇ
＝｛ｅｋ＜ＸＯＲ＞ｔｋ｝＜ＸＯＲ＞｛Ｈａｓｈ（Ｍ）＜ＸＯＲ＞ｅｋ｝
＝ｔｋ＜ＸＯＲ＞Ｈａｓｈ（Ｍ）      （式３）
を計算する。
ステップＳ６０４において、送信制御部である送信部６０５は、２つの暗号化タグＴどうしの値が一致するかどうかを判定する一致判定装置７００に、暗号化タグＴを送信する。
【００３１】
ステップＳ７０１において、タグ入力部７０１には、２つの暗号化タグＴ１、暗号化タグＴ２が入力される。
ステップＳ７０２において、判定部７０２は、暗号化タグＴ１と暗号化タグＴ２とのビット列が等しいかどうかを検証する。判定部７０２によって暗号化タグＴ１と暗号化タグＴ２とのビット列が等しいと判定された場合、ステップＳ７０３において結果送信部７０３は１を出力し、暗号化タグＴ１と暗号化タグＴ２とのビット列が異なると判定された場合はステップＳ７０４において０を出力する。
【００３２】
＊＊＊実施の形態１の効果＊＊＊
実施の形態１では、個人ごとに異なる暗号鍵ｅｋを用いて生成された暗号化タグＥＴａｇは、変換鍵ｃｋを用いることによって、暗号化タグＴに変換可能である。
暗号化タグＥＴａｇは重複除外不可能であるけれども、暗号のデファクトスタンダードな安全性を持つ。また、暗号化タグＥＴａｇから変換された暗号化タグＴは、重複除外が可能である。これにより、実施の形態１によれば、重複除外の利便性を失うことなく高い安全性を持つ暗号システムを提供することができる。
【００３３】
実施の形態２．
図１５から図２３を参照して実施の形態２の重複除外システム１００を説明する。実施の形態１ではステップＳ４０３において、暗号化タグＥＴａは平文Ｍのハッシュ値と、暗号鍵ｅｋとの排他的論理和で生成された。実施の形態２では、暗号化タグＥＴａはペアリング演算を用いて生成される。
【００３４】
重複除外システム１００の構成は実施の形態１の図１と同じである。また、共通パラメータ生成装置２００、ユーザ鍵生成装置３００、暗号化装置４００、変換鍵生成装置５００、タグ変換装置６００及び一致判定装置７００の構成は、実施の形態１の図２から図７と同じである。
【００３５】
図１５は、共通パラメータ生成装置２００の動作を示すフローチャートである。
図１６は、ユーザ鍵生成装置３００の動作を示すフローチャートである。
図１７は、暗号化装置４００の動作を示すフローチャートである。
図１８は、変換鍵生成装置５００の動作を示すフローチャートである。
図１９は、タグ変換装置６００の動作を示すフローチャートである。
図２０は、一致判定装置７００の動作を示すフローチャートである。
図２１は、図１５から図２１のフローチャートをシーケンスとして示す図である。
図２１と図２０を参照して重複除外システム１００の各装置の動作を説明する。
【００３６】
＜共通パラメータ生成装置２００＞
ステップＳ８０１において、入力部２０１にはビット長ｋが入力される。
ステップＳ８０２において、共通パラメータ生成部２０２は、ビット長ｋをもとに、ペアリング演算可能な要素、
ＢＧ＝（ｐ、Ｇ、ＧＴ、ｅ）      （式４）
を生成する。
ここで、ｐは、群Ｇと群ＧＴの位数を表す。
ｅは、Ｇ×Ｇ→ＧＴの写像を持つ双線形写像とする。
双線形写像とは、全てのｇ∈Ｇ、及びａ、ｂ∈Ｚｐに対して、
ｅ（ｇａ、ｇｂ）＝ｅ（ｇ、ｇ）ａｂ∈ＧＴ      （式５）
となる写像である。このｅを用いた演算を、ペアリング演算と呼ぶ。
なお、Ｚｐはｍｏｄ＝ｐの整数の集合である。
ｇ∈Ｇをランダムに選ぶ。
ステップＳ８０３において、送信部２０３は、ビット長ｋとｇと要素ＢＧをユーザ鍵生成装置３００へと送信する。
【００３７】
＜ユーザ鍵生成装置３００＞
ステップＳ９０１において、パラメータ受信部３０１は、共通パラメータ生成装置２００から、ビット長ｋ、ｇ及びＢＧを受信する。
ステップＳ９０２において、鍵生成部３０２が、ｘ∈Ｚｐをランダムに選び、
ｙ＝ｇｘ
を計算する。
また、鍵生成部３０２は、Ｙ∈Ｇを選ぶ。
鍵生成部３０２は、
暗号鍵ｅｋ＝（ｇ，ｙ，Ｙ）      （式６）
、及び
変換鍵生成鍵ｔｋ＝ｘ      （式７）
を設定する。
第１鍵である暗号鍵ｅｋは、第１要素、第２要素及び第３要素を含む。暗号鍵ｅｋにおいて、ｇは第１要素であり、ｙは第２要素であり、Ｙは第３要素である。
ステップＳ９０３において、鍵送信部３０３は、暗号化装置４００に暗号鍵ｅｋを送信し、変換鍵生成装置５００へ暗号鍵ｅｋ及び変換鍵生成鍵ｔｋを送信する。
【００３８】
＜暗号化装置４００＞
ステップＳ１００１において、入力部４０１には、平文Ｍが入力される。
ステップＳ１００２において、受信部４０２は、ユーザ鍵生成装置３００から暗号鍵ｅｋを受信する。
ステップＳ１００３において、タグ生成部４０３は、
Ｃ１＝ｇｒ、Ｃ２＝ｙｒ＋Ｈａｓｈ（ｇ、Ｍ）      （式８）
を計算し、
ＥＴａｇ＝（Ｃ１、Ｃ２）
＝（ｇｒ，ｙｘ｛ｒ＋Ｈａｓｈ（ｇ、Ｍ）｝）      （式９）
と暗号ＥＴａｇを設定する。
ここでＨａｓｈは暗号学的ハッシュ関数を指し、例えばＳＨＡ２５６である。
ステップＳ１００４において、タグ送信部４０４は、暗号ＥＴａｇをタグ変換装置６００へ送信する。
式９に示すように、暗号化部である暗号化装置４００は、第１暗号化データである。
ＥＴａｇとして、第１要素ｇと第２要素ｙとを使用して平文Ｍを暗号化し、平文Ｍが暗号化されたデータを生成する。
【００３９】
＜変換鍵生成装置５００＞
ステップＳ１１０１において、鍵受信部５０１は、ユーザ鍵生成装置３００から、
暗号鍵ｅｋ＝（ｇ，ｙ，Ｙ）＝（ｇ，ｇｘ，Ｙ）
、及び変換鍵生成鍵ｔｋ＝ｘを受信する。
ステップＳ１１０２において、変換鍵生成部５０２は、
ｃｋ’＝Ｙ１／ｘ      （式１０）
を計算する。
ステップＳ１１０３において、送信部５０３は、
変換鍵ｃｋ＝（ｃｋ’，ｅｋ）
を、タグ変換装置６００へ送信する。
式１０及び上記の変換鍵ｃｋの式のように、第３鍵生成部である変換鍵生成装置５００は、第３要素Ｙに第２鍵である変換鍵生成鍵ｔｋを適用し、適用して得られた値ｃｋ’と、第１鍵である暗号鍵ｅｋとの組を、第３鍵である変換鍵ｃｋとして生成する。
【００４０】
＜タグ変換装置６００＞
ステップＳ１２０１において、受信部６０１は、変換鍵生成装置５００から
変換鍵ｃｋ＝（ｃｋ’，ｅｋ）＝＝（Ｙ１／ｘ，ｇ，ｇｘ，Ｙ）
を受信する。
ステップＳ１２０２において、入力部６０２には、暗号化タグ
ＥＴａｇ＝（Ｃ１，Ｃ２）＝（ｇｒ，ｇｘ｛ｒ＋Ｈａｓｈ（ｇ、Ｍ）｝）
が入力される。
ステップＳ１２０３において、変換部６０４は、同一の平文Ｍが使用されている暗号化タグＥＴａｇを、暗号化タグＥＴａｇに使用されている暗号鍵ｅｋの値によらず同一の値となる第２暗号化データである暗号化タグＴに変換する。具体的には、以下のようである。
実施の形態２の重複除外システム１００では、ステップＳ８０２で選択されるｇ及びステップＳ９０２で選択されるＹは、異なるユーザに同じ値が設定される。よって、以下の（式１１）によれば、同一の平文Ｍが使用されている暗号化タグＥＴａｇは、暗号化タグＥＴａｇに使用されている暗号鍵ｅｋの値によらず同一の値となる暗号化タグＴに変換される。
変換部６０４は、
Ｔ＝ｅ（Ｃ２，ｃｋ’）／ｅ（Ｃ１，Ｙ）      （式１１）
＝ｅ（ｇｘ｛ｒ＋Ｈａｓｈ（ｇ、Ｍ）｝，Ｙ１／ｘ）／ｅ（ｇｒ，Ｙ）
＝ｅ（ｇ，Ｙ）ｘ｛ｒ＋Ｈａｓｈ（ｇ、Ｍ）｝＊１／ｘ／ｅ（ｇ，Ｙ）ｒ
＝ｅ（ｇ，Ｙ）｛ｒ＋Ｈａｓｈ（ｇ、Ｍ）｝／ｅ（ｇ，Ｙ）ｒ
＝ｅ（ｇ，Ｙ）Ｈａｓｈ（ｇ、Ｍ）
を計算する。
ｅはペアリング演算を表す。
ステップＳ１２０４において、送信部６０５は、暗号化タグＥＴａｇから変換された暗号化タグＴを一致判定装置７００に送信する。
【００４１】
＜一致判定装置７００＞
ステップＳ１３０１において、タグ入力部７０１には、２つの暗号化タグＴ１、暗号化タグＴ２が入力される。
ステップＳ１３０２において、判定部７０２は、暗号化タグＴ１と暗号化タグＴ２とのビット列が等しいかどうかを検証する。
ステップＳ１３０３において、判定部７０２によって暗号化タグＴ１と暗号化タグＴ２とのビット列が等しいと判定された場合、ステップＳ１３０３で結果送信部７０３は１を出力し、暗号化タグＴ１と暗号化タグＴ２とのビット列が異なると判定された場合はステップＳ１３０４で０を出力する。
【００４２】
＊＊＊実施の形態２の効果＊＊＊
実施の形態２によれば、公開鍵方式の暗号システムを、重複除外の利便性を失うことなく高い安全性を持つ暗号システムとすることができる。
【００４３】
図２２は、実施の形態１及び実施の形態２の、共通パラメータ生成装置２００、複数のユーザ鍵生成装置３００、暗号化装置４００、変換鍵生成装置５００、タグ変換装置６００及び一致判定装置７００のハードウェア構成を示す図である。
共通パラメータ生成装置２００、複数のユーザ鍵生成装置３００、暗号化装置４００、変換鍵生成装置５００、タグ変換装置６００及び一致判定装置７００は、コンピュータである。図２２は、コンピュータである、共通パラメータ生成装置２００から一致判定装置７００の、ハードウェア構成である。
共通パラメータ生成装置２００から一致判定装置７００のハードウェア構成は同じであるので、暗号化装置４００を代表として説明する。
【００４４】
図２２において、
暗号化装置４００は、ＣＰＵ１１０１（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を備えている。
ＣＰＵ１１０１は、バス１００２を介してＲＯＭ１００３、ＲＡＭ１１０４、通信ボード１１０５、ディスプレイ１１１１、キーボード１１１２、マウス１１１３、ドライブ１１１４、磁気ディスク装置１１２０などのハードウェアデバイスと接続され、これらのハードウェアデバイスを制御する。
ドライブ１１１４は、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）などの記憶媒体を読み書きする装置である。
ＲＯＭ１１０３、ＲＡＭ１１０４、磁気ディスク装置１１２０およびドライブ１１１４は記憶装置の一例である。
キーボード１１１２、マウス１１１３および通信ボード１１０５は入力装置の一例である。ディスプレイ１１１１および通信ボード１０５は出力装置の一例である。
通信ボード１１０５は、有線または無線で、ＬＡＮ、インターネット、電話回線などの通信網に接続している。
磁気ディスク装置１１２０には、オペレーティングシステム１１２１、プログラム群１１２２、ファイル群１１２３が記憶されている。
なお図２２ではオペレーティングシステム１１２１はＯＳ１１２１と表記している。
プログラム群１１２２には、実施の形態１、２において「〜部」として説明する機能を実行するプログラムが含まれる。
プログラムは、ＣＰＵ１１０１により読み出され実行される。
すなわち、プログラムは、「〜部」としてコンピュータを機能させるものであり、また「〜部」の手順や方法をコンピュータに実行させる。
ファイル群１１２３には、実施の形態１，２において説明する「〜部」で使用される入力データ、出力データ、判定結果、計算結果、処理結果のような各種のデータが含まれる。
実施の形態１，２において構成図およびフローチャートに含まれている矢印は主としてデータや信号の入出力を示す。
フローチャートなどに基づいて説明する実施の形態１，２の処理は、ＣＰＵ１１０１、記憶装置、入力装置、出力装置などのハードウェアを用いて実行される。
実施の形態１，２において「〜部」として説明するものは「〜回路」、「〜装置」、「〜機器」であってもよく、また「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明するものは、ファームウェア、ソフトウェア、ハードウェアまたはこれらの組み合わせのいずれで実装されても構わない。
【００４５】
＜ハードウェア構成の補足＞
図２２に示すハードウェア構成では各装置の機能がソフトウェアで実現される。しかし、各装置の機能がハードウェアで実現されてもよい。
図２２と同様に暗号化装置４００を代表として説明する。
図２３は、暗号化装置４００の機能がハードウェアで実現される構成を示す。図２３の電子回路９１０は、暗号化装置４００の、入力部４０１、受信部４０２、タグ生成部４０３、タグ送信部４０４の機能を実現する専用の電子回路である。電子回路９１０は、信号線９１１に接続している。電子回路９１０は、具体的には、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ、ＡＳＩＣ、または、ＦＰＧＡである。ＧＡは、Ｇａｔｅ  Ａｒｒａｙの略語である。ＡＳＩＣは、Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔの略語である。ＦＰＧＡは、Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙの略語である。暗号化装置４００の構成要素の機能は、１つの電子回路で実現されてもよいし、複数の電子回路に分散して実現されてもよい。また、暗号化装置４００の構成要素の一部の機能が電子回路で実現され、残りの機能がソフトウェアで実現されてもよい。
【００４６】
ＣＰＵ１１０１と電子回路９１０との各々は、プロセッシングサーキットリとも呼ばれる。暗号化装置４００において、入力部４０１、受信部４０２、タグ生成部４０３及びタグ送信部４０４の機能がプロセッシングサーキットリにより実現されてもよい。あるいは、図２か図７に示す「〜部」の機能が、プロセッシングサーキットリにより実現されてもよい。
【符号の説明】
【００４７】
ｃｋ  変換鍵、ＥＴａｇ  暗号化タグ、ＥＴ  暗号化タグ、ｅｋ  暗号鍵、Ｍ  平文、ｔｋ  変換鍵生成鍵、１００  重複除外システム、１０１  ネットワーク、２００  共通パラメータ生成装置、２０１  入力部、２０２  共通パラメータ生成部、２０３  送信部、３００  ユーザ鍵生成装置、３０１  パラメータ受信部、３０２  鍵生成部、３０３  鍵送信部、４００  暗号化装置、４０１  入力部、４０２  受信部、４０３  タグ生成部、４０４  タグ送信部、５００  変換鍵生成装置、５０１  鍵受信部、５０２  変換鍵生成部、５０３  送信部、６００  タグ変換装置、６０１  受信部、６０２  入力部、６０３  鍵保管部、６０４  変換部、６０５  送信部、７００  一致判定装置、７０１  タグ入力部、７０２  判定部、７０３  送信部、９１０  電子回路、９１１  信号線。
【要約】
重複除外システム（１００）は、暗号化装置（４００）、変換鍵生成装置（５００）、タグ変換装置（６００）及び一致判定装置（７００）を備えている。暗号化装置（４００）は、暗号鍵（ｅｋ）と平文（Ｍ）とを使用して暗号化（ＥＴａｇ）を生成する。変換鍵生成装置（５００）は、暗号鍵（ｅｋ）と変換鍵生成鍵（ｔｋ）とを使用して、変換鍵（ｃｋ）を生成する。タグ変換装置（６００）は、変換鍵（ｃｋ）を暗号化タグ（ＥＴａｇ）に適用することで、同一の平文（Ｍ）が使用されている暗号化タグ（ＥＴａｇ）を、暗号化タグ（ＥＴａｇ）に使用されている暗号鍵（ｅｋ）の値によらず同一の値となる暗号化タグ（Ｔ）に変換する。一致判定装置（７００）は、２つの暗号化タグ（Ｔ）どうしの値が一致するかどうかを判定する。【図１】
0006865899.tif 000002
【図２】
0006865899.tif 000003
【図３】
0006865899.tif 000004
【図４】
0006865899.tif 000005
【図５】
0006865899.tif 000006
【図６】
0006865899.tif 000007
【図７】
0006865899.tif 000008
【図８】
0006865899.tif 000009
【図９】
0006865899.tif 000010
【図１０】
0006865899.tif 000011
【図１１】
0006865899.tif 000012
【図１２】
0006865899.tif 000013
【図１３】
0006865899.tif 000014
【図１４】
0006865899.tif 000015
【図１５】
0006865899.tif 000016
【図１６】
0006865899.tif 000017
【図１７】
0006865899.tif 000018
【図１８】
0006865899.tif 000019
【図１９】
0006865899.tif 000020
【図２０】
0006865899.tif 000021
【図２１】
0006865899.tif 000022
【図２２】
0006865899.tif 000023
【図２３】
0006865899.tif 000024