(57)【特許請求の範囲】
【請求項１】
データを記憶するメモリ、メッセージ通信を行う通信インターフェース、機能を提供する制御論理を有するデータ処理システム（１）において公開鍵の下で秘密データを暗号化するための公開鍵暗号化方法であって、前記制御論理が、
双線形マップ
【数１】
0006041864.tif 000023
を満たす基礎群Ｇ１、Ｇ２のペアのうちの少なくとも１つの要素を含むメッセージ（ｍ）として前記メモリに記憶された前記秘密データを提供するステップであって、ここでＧＴは前記メモリに記憶されたターゲット群である、提供するステップ、
暗号化済みメッセージ（ｃ）を生成するために前記公開鍵を使用して前記メッセージ（ｍ）を暗号化するステップ、
前記暗号化済みメッセージ（ｃ）および前記双線形マップを使用して、前記暗号化済みメッセージの妥当性検査を行うための整合性構成要素（ｖ）を生成するステップ、および
前記暗号化済みメッセージ（ｃ）および前記整合性構成要素（ｖ）を含む暗号文（ｃｔ）を送信するステップ、
を含む、方法。
【請求項２】
前記整合性構成要素（ｖ）が、前記整合性構成要素（ｖ）を公開せずに前記暗号化済みメッセージ（ｃ）の妥当性検査を許可するように生成される、請求項１に記載の方法。
【請求項３】
前記暗号化済みメッセージ（ｃ）が前記基礎群のペアの少なくとも１つの要素を含み、前記整合性構成要素（ｖ）が前記双線形マップを前記暗号化済みメッセージ（ｃ）に適用するステップによって生成される、請求項１または２に記載の方法。
【請求項４】
前記整合性構成要素（ｖ）が前記ターゲット群のうちの少なくとも１つの要素を含む、前記請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記整合性構成要素（ｖ）がそれぞれの基礎群からの要素の少なくとも１つのペアを含む、請求項１から３のいずれか一項に記載の方法。
【請求項６】
ランダム構成要素を生成するステップ、および前記ランダム構成要素を使用して前記整合性構成要素（ｖ）を生成するステップを含み、前記暗号文（ｃｔ）が前記ランダム構成要素を含む、前記請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記ランダム構成要素が前記基礎群のペアのうちの少なくとも１つの要素を含み、前記整合性構成要素（ｖ）の生成が前記双線形マップを前記ランダム構成要素に適用するステップを含む、請求項６に記載の方法。
【請求項８】
前記整合性構成要素（ｖ）が、前記暗号文（ｃｔ）を公開せずに前記暗号化済みメッセージ（ｃ）の妥当性検査を許可するように生成される、前記請求項１〜７のいずれか一項に記載の方法。
【請求項９】
前記メッセージ（ｍ）が前記基礎群のペアのうちの少なくとも１つの要素に対応するラベルに関連付けられ、前記ラベルに対応する前記少なくとも１つの要素を使用して前記整合性構成要素（ｖ）を生成するステップを含む、前記請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
前記整合性構成要素（ｖ）の生成が、前記双線形マップを前記ラベルに対応する前記少なくとも１つの要素に適用するステップを含む、請求項９に記載の方法。
【請求項１１】
前記暗号化済みメッセージ（ｃ）を知っていることの暗号証明を実行するステップ、および、前記暗号化済みメッセージの妥当性検査のために前記整合性構成要素（ｖ）を使用するステップを含む、前記請求項１〜１０のいずれか一項に記載の方法。
【請求項１２】
請求項１から１０のいずれか一項に記載の方法によって生成された暗号文（ｃｔ）を受信するステップ、および
前記暗号化済みメッセージ（ｃ）を知っていることの暗号証明を実行するステップ、および前記暗号化済みメッセージの妥当性検査のために前記整合性構成要素（ｖ）を使用するステップ、
を含む、暗号文を知っていることの証明のための方法。
【請求項１３】
前記暗号化済みメッセージ（ｃ）および前記暗号化済みメッセージの妥当性を検査する整合性構成要素（ｖ）の、両方を知っていることの暗号証明を実行するステップを含む、請求項１１または１２に記載の方法。
【請求項１４】
前記請求項１〜１３のいずれか一項に記載の方法の各ステップをコンピュータに実行させる、コンピュータ・プログラム。
【請求項１５】
公開鍵の下で秘密データを暗号化するための装置（２）であって、
双線形マップ
【数２】
0006041864.tif 000024
を満たす基礎群Ｇ１、Ｇ２のペアのうちの少なくとも１つの要素を含むメッセージ（ｍ）として前記秘密データを記憶するためのメモリ（６）であって、ここでＧＴはターゲット群である、メモリと、
前記暗号化済みメッセージ（ｃ）を生成するために前記公開鍵を使用して前記メッセージ（ｍ）を暗号化すること、
前記暗号化済みメッセージ（ｃ）および前記双線形マップを使用して、前記暗号化済みメッセージの妥当性検査を行うための整合性構成要素（ｖ）を生成すること、および
前記暗号化済みメッセージ（ｃ）および前記整合性構成要素（ｖ）を含む暗号文（ｃｔ）を送信すること、
を実行するように適合された制御論理（５）と、
を備える、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般にデータの暗号化に関し、データ処理システムにおける秘密データの公開鍵暗号化のための方法および装置を提供する。
【背景技術】
【０００２】
公開鍵暗号化は、データ処理システム内で通信されるデータの保護を目的とするほぼどのようなセキュリティ・プロトコルにおいても、重要な暗号ツールである。暗号化方式は、システム内での通信に特定の当事者に関連付けられた暗号鍵ペア、すなわち秘密鍵および公開鍵に依拠する。当事者の公開鍵はその方式のすべてのユーザが使用可能であるが、秘密鍵はその当事者にとっての秘密のままである。送信者がメッセージ・データを他者に秘密にしておきながら受信者との通信を希望する、基本メッセージング・プロセスで使用される場合、送信者は受信者の公開鍵を使用し、暗号符号化プロセスを介して秘密データを暗号化することができる。セキュリティは、結果として生じる暗号文が、対応する鍵ペアのうちの秘密鍵を使用して元の平文メッセージ、すなわち秘密データを回復するためにのみ復号可能であるという前提に依拠する。したがって、この秘密鍵を所有する許可された受信者のみが、平文を復号して秘密データを公開することができる。暗号化方式は、他のシナリオで使用することも可能であり、たとえば信頼できる第三者（ＴＴＰ）の公開鍵の下でデータを暗号化することで、結果として生じる暗号文の受信者がある環境においてＴＴＰに適用し、暗号文を復号することができることになる。こうしたシステムを採用し、たとえば、ユーザがたとえば請求書の支払いをしないなどの不正を行った場合に、暗号文中の暗号化済みユーザ識別データを、暗号文の受信者に公開することができる。
【０００３】
実際には、暗号化方式によって提供されるセキュリティのレベルは、最終的には、攻撃者が秘密鍵を知らずに暗号文から情報を推測できる範囲に依存する。暗号化方式に関する現行の事実上の標準セキュリティ概念は「選択暗号文攻撃に対するセキュリティ」（ＣＣＡ）として知られている。これは、指定された制約（攻撃者によって選択された暗号文の復号のために復号オラクルへの制限付きアクセスを許可する）の下で動作する概念上の攻撃者が、２つのメッセージ（平文）のうちのどちらが所与の暗号文に対応するかを検出できる確率に関して定義される。より弱いセキュリティ概念、たとえばいわゆる「意味論的セキュリティ」（選択平文攻撃（ＣＰＡ）に対するセキュリティ）を満たす方式は、ある種の攻撃に対して脆弱であることが明らかになってきたため、今やＣＣＡセキュリティは標準要件である。
【０００４】
効率的な公開鍵暗号化方式は数多くあるが、ほとんどが衝突耐性ハッシュ関数または暗号学的ハッシュ関数などの何らかのハッシュ関数を使用する必要がある。特にＣＣＡセキュア暗号化方式は、観察された暗号文が検出されずに攻撃者によって修正されるのを防ぐ整合性チェックを追加することにより、典型的には意味論的にセキュアな暗号化方式から取得される。最終的な暗号文は、平文メッセージの暗号化によって生成される暗号化済みメッセージと、ハッシュ関数を使用して暗号化済みメッセージから生成される整合性チェック構成要素の、両方を含む。暗号文の受信者は、整合性構成要素が暗号化済みメッセージに対して正しいこと、したがって暗号化済みメッセージが有効である（すなわち、送信者によって正当に計算され、攻撃者によって修正されていない）ことを検証することができる。これによりＣＣＡセキュリティの基本は提供されるが、これらの方式でのハッシュ関数または同様の関数の使用により、結果として生じる暗号文に関して一定の証明が行われないことになる。特に、これらの関数の入力と出力との一定の関係は、実際に入力および出力を公開しなければ証明できない。したがって、たとえば暗号文自体を公開しなければ、暗号文が正当に計算されたことを証明するのは不可能である。これは、高度なプライバシを保持しながら一定の証明が行われなければならない高度なセキュリティ・プロトコルにおける、重要な要件である。具体的に言えば、いくつかのプロトコルは、ユーザが暗号文を公開しないが、その暗号文の一定の特性に関する証拠は提供できることを必要とする。たとえばユーザは、自分が正当に計算された暗号文を所有していることを、検証者に公開することなく単に証明すれば良い場合がある。たとえば暗号文内の暗号化済みメッセージが一定の要件を満たしているという、追加の証明が必要な場合もあるが、ここでもその事実以外は何も検証者に公開しない。
【０００５】
ハッシュ関数に基づくセキュア暗号化方式の例は、１９９８年のR.CramerおよびV.Shoupによる「A Practical Public Key Cryptosyste ProvableSecure against Adaptive Chosen Ciphertext Attack」、CRYPTO ’98、１３〜２５ページ、Springer-Verlag、ならびに、２００１年のR.CramerおよびV.Shoupによる「Designand Analysis of Practical Public-Key Encryption Schemes Secure against AdaptiveChosen Ciphertext Attack」、SIAM Journal on Computing、33:167-226に記載されている。Cramer-Shoup暗号化方式のハッシュなし変形態も記載されている。このハッシュなし方式では、暗号文のある一部（素数位数（prime-order）群内の要素）をビットのシーケンスとして扱い、そのシーケンスをビットのブロックに分け、分けられた値を、その後特定の関数評価に送られる素数位数を法とする数として扱うことによって、ハッシングが回避される。本質的に、このプロセスは目的固有のハッシュ関数を構築するものであり、これによって入力と出力との間の一定の関係を証明することができるが、入力と出力はどちらも完全には公開されない。もちろんこれでは、どちらも公開された場合、入力上で適切な関数を評価し、その結果を所与の出力に照らしてチェックすることのみが可能であるため、入力と出力との間の関係を証明するという目的は達成されない。線形Cramer-Shoup暗号化方式は、２００７年のH.Shachamによる「A Cramer-ShoupEncryption Scheme from the Linear Assumption and from Progressively WeakerLinear Variants」、Cryptology ePrint Archive、Report 2007/074でも開示されている。この方式のセキュリティは決定線形仮定（ＤＬＩＮ）（Decisional Linear Assumption）に基づき、ハッシュ関数の使用に決定的に依拠しており、ここでも暗号文を公開せずに証明することはできない。
【０００６】
デジタル署名の分野では、検証者に署名を公開せずに署名を知っていることを証明することができる。こうした知っていることの証明を可能にする署名方式は、様々な方法で実装できる。１つの例では、署名方式を実装する際に双線形群を使用する。この「構造保持」署名方式については、２０１０年のAbe等による「Structure-PreservingSignatures and Commitments to Group Elements」、CRYPTO2010、LNCS 6223、２０９〜２３６ページで考察されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】欧州特許出願第ＣＨ９−２０１０−００８５号
【非特許文献】
【０００８】
【非特許文献１】１９９８年のR.CramerおよびV.Shoupによる「A Practical Public Key Cryptosyste ProvableSecure against Adaptive Chosen Ciphertext Attack」、CRYPTO ’98、１３〜２５ページ、Springer-Verlag
【非特許文献２】２００１年のR.CramerおよびV.Shoupによる「Design and Analysis of Practical Public-KeyEncryption Schemes Secure against Adaptive Chosen Ciphertext Attack」、SIAM Journal on Computing、33:167-226
【非特許文献３】２００７年のH.Shachamによる「A Cramer-Shoup Encryption Schemefrom the Linear Assumption and from Progressively Weaker Linear Variants」、Cryptology ePrint Archive、Report 2007/074
【非特許文献４】２０１０年のAbe等による「Structure-Preserving Signaturesand Commitments to Group Elements」、CRYPTO 2010、LNCS 6223、２０９〜２３６ページ
【非特許文献５】JensGroth、Amit Sahaiによる「Efficient Non-interactive Proof Systems forBilinear Groups」、EUROCRYPT 2008:415-432
【非特許文献６】２００９年のCamenisch等による「On the Portability of GeneralizedSchnorr Proofs」、Eurocrypt 2009、LNCS 5479、４２５〜４４２ページ
【発明の概要】
【発明が解決しようとする課題】
【０００９】
これまで、暗号文とその暗号文が正当に計算されたことの証明とを有するユーザが、自分がそうした正当に計算された暗号文を所有していることを、暗号文を公開せずに検証者に証明する際に使用できる、実用的な暗号化方式はない。
【課題を解決するための手段】
【００１０】
本発明の一態様は、データ処理システムにおいて公開鍵の下で秘密データを暗号化するための公開鍵暗号化方法を提供する。方法は、
双線形マップ
【数１】
0006041864.tif 000002
を満たす基礎群Ｇ１、Ｇ２のペアのうちの少なくとも１つの要素を含むメッセージとして秘密データを提供することであって、ここでＧＴはターゲット群である、提供すること、
暗号化済みメッセージを生成するために当該公開鍵を使用してメッセージを暗号化すること、
暗号化済みメッセージおよび当該双線形マップを使用して整合性構成要素を生成することであって、整合性構成要素がそれによって暗号化済みメッセージを公開せずに暗号化済みメッセージの妥当性検査を可能にする、生成すること、および
暗号化済みメッセージおよび整合性構成要素を含む暗号文を出力すること、
を含む。
【００１１】
本発明を具体化する公開鍵暗号化方法は、双線形マップを使用して暗号文内に暗号化済みメッセージに対する整合性構成要素を生成する。暗号化済みメッセージは、ターゲット群に対する双線形マップを満たす基礎群のペアの１つまたは複数の要素を含むメッセージの公開鍵暗号化によって生成される。その後整合性構成要素は、暗号化済みメッセージおよび双線形マップを使用して生成され、結果として生じる整合性構成要素を使用して、暗号化済みメッセージ自体を公開せずに暗号化済みメッセージの妥当性検査を行うことができる。これにより、ＣＣＡセキュアであり、さらに暗号文に関して、たとえば証明の際に暗号文を公開する必要なしに暗号文が正当に計算されたことを証明することも可能な、高度に効率的な暗号化方式の基礎が提供される。したがってこれらの方式は、「構造保持暗号化方式」とみなすことが可能であり、ここで「構造保持」という用語は、一定の構造がこうした証明の可能な暗号文全体に組み込まれることを意味する。
【００１２】
一般に、内部で本発明を具体化する暗号化方法が実行されるデータ処理システムは、データを処理するための１つまたは複数の（局在または分散）デバイスまたは構成要素を含むことが可能であり、秘密データは、無許可のアクセスから保護されることになる任意のデータを含むことが可能である。いくつかの実施形態では、群要素を含む秘密データをメッセージとして提供するステップは、それによって入力ユーザ・データが符号化され、そのユーザ・データを表す群要素を含むメッセージが取得される、符号化ステップを含むことができる。他の実施形態では、秘密データを表すメッセージは、単にシステム内に提供すること、たとえば、暗号化プロセスで使用するためにシステム・メモリ内に記憶することが可能である。いずれの場合でも、メッセージは一般に基礎群Ｇ１、Ｇ２のうちの１つまたは複数の要素を含むことが可能であり、ここでＧ１はＧ２に等しいかまたは等しくない場合がある。
【００１３】
整合性構成要素は、暗号化済みメッセージおよび双線形マップに加え、１つまたは複数の他のアイテムを使用して生成可能であり、最終暗号文は１つまたは複数の追加の構成要素ならびに暗号化済みメッセージおよび整合性構成要素を含むことができる。
（依然として秘密の）暗号化済みメッセージの妥当性を検査するために整合性構成要素を検証者に公開することが可能なシナリオが想定できるが、好ましい実施形態では、整合性構成要素は、整合性構成要素または暗号化済みメッセージを公開せずに暗号化済みメッセージの妥当性検査を可能にする。これは、整合性構成要素内で双線形マップを使用することによって容易に達成される。より一般的には、暗号化済みメッセージは暗号文のいかなる構成要素も公開せずに妥当性検査が可能であり、それによって暗号文全体の秘匿性を保持しながら有効な暗号文の所有が証明できる。ここでも、双線形マップの使用を通じて、これを達成するような様式で整合性構成要素が生成可能である。
【００１４】
メッセージは、暗号文に含められることになる暗号化済みメッセージを生成するための任意の便利な様式で、公開鍵を使用して暗号化することができる。以下で詳述される好ましい実施形態では、暗号化済みメッセージは基礎群のペアのうちの少なくとも１つの要素を含み、整合性構成要素は双線形マップを暗号化済みメッセージに適用することによって生成される。しかしながら既に示されているように、整合性構成要素の生成には他のアイテムを使用することができる。たとえば本発明を具体化する方法は、典型的にはランダム構成要素を生成するステップを含むことになり、その後このランダム構成要素は最終暗号文の生成に使用される。整合性構成要素は、特にこのランダム構成要素を使用して生成することができる。こうしたランダム構成要素は、基礎群Ｇ１、Ｇ２のペアのうちの少なくとも１つの要素を含むことが可能であり、整合性構成要素の生成は、ランダム構成要素に双線形マップを適用することを含むことが可能である。その後ランダム構成要素は、最終出力暗号文の構成要素として含めることができる。
【００１５】
暗号化方式の使用に関する実際上の理由から、暗号化されることになるメッセージをラベルに関連付けることができる。ラベルの使用は暗号適用例では良く知られており、たとえば特定のコンテキスト情報をトランザクションに関連付けることができる。以下で説明する好ましい暗号化方法では、所与のメッセージに関連付けられたラベルは、対応する整合性構成要素の生成に使用される。より具体的に言えば、こうしたラベルは基礎群Ｇ１、Ｇ２のペアのうちの少なくとも１つの要素に対応し、整合性構成要素の生成はラベルに対応する要素に双線形マップを適用することを含む。
【００１６】
本発明を具体化する暗号化方法によって生成される暗号文は、メモリに出力し、後続の証明プロトコルで使用するために記憶することが可能である。別の方法として、たとえば暗号文はリモートの当事者に送信することが可能であり、その後この当事者は、暗号文の秘匿性を保持しながら証明プロトコルでこの暗号文を使用することができる。たとえば暗号文は、データ通信チャネルを介して別のデバイスに伝送することが可能であり、別のデバイスにおいて暗号文は最終的に証明プロトコルで使用されることになる。いずれの場合も、本発明を具体化する方法は、暗号化済みメッセージを知っていることの暗号証明を実行するステップと、暗号化済みメッセージの妥当性検査に対して整合性構成要素を使用するステップとを含むことができる。こうした証明は、一般に、妥当性検査のための様々な方法で整合性構成要素を使用することができるが、理想的には整合性構成要素はこのプロセスでは公開されない。したがって好ましい方法は、暗号化済みメッセージとその暗号化済みメッセージの妥当性を検査する整合性構成要素の両方を知っていることの暗号証明を実行する。本方法は、本発明の第１の態様に従った方法を実行することによって生成される暗号文を受信すること、ならびに、暗号化済みメッセージを知っていることの暗号証明を実行すること、および暗号化済みメッセージの妥当性を検査するために整合性構成要素を使用することを含む、暗号文を知っていることを証明するための方法も提供する。
【００１７】
本発明の他の態様は、本発明の前述の態様に従った方法をコンピュータに実行させるためのプログラム・コード手段を備える、コンピュータ・プログラムを提供する。「コンピュータ」という用語は最も一般的な意味で使用され、コンピュータ・プログラムを実装するためのデータ処理機能を有する任意のデバイス、構成要素、またはシステムを含み、したがって、単一のデバイスまたはデバイスの分散型システムの１つまたは複数のプロセッサを含むことが可能であることを理解されよう。さらに本発明を具体化するコンピュータ・プログラムは独立したプログラムまたはプログラム・セットを構築することが可能であるか、あるいはより大きなプログラムまたはプログラム・セットの一部とすることが可能であり、さらにコンピュータ内にロードするためのディスクまたは電子伝送などのコンピュータ読み取り可能媒体を供給し、たとえばその内部で具体化することが可能である。コンピュータ・プログラムのプログラム・コード手段は、直接、あるいは（ａ）別の言語、コード、または表記への変換および（ｂ）異なる材料形式での再生成のうちの、いずれかまたは両方の後に、当該方法をコンピュータに実行させることが意図された、命令セットの任意の言語、コード、または表記での任意の表現を含むことができる。
【００１８】
本発明の他の態様は、公開鍵の下で秘密データを暗号化するための装置を提供する。装置は
双線形マップ
【数２】
0006041864.tif 000003
を満たす基礎群Ｇ１、Ｇ２のペアのうちの少なくとも１つの要素を含むメッセージとして秘密データを記憶するためのメモリであって、ここでＧＴはターゲット群である、メモリと、
暗号化済みメッセージを生成するために当該公開鍵を使用してメッセージを暗号化すること、
暗号化済みメッセージおよび当該双線形マップを使用して整合性構成要素を生成することであって、整合性構成要素がそれによって暗号化済みメッセージを公開せずに暗号化済みメッセージの妥当性検査を可能にする、生成すること、および
暗号化済みメッセージおよび整合性構成要素を含む暗号文を出力すること、
を実行するように適合された制御論理と、を備える。
【００１９】
一般に、本発明の一態様の実施形態を参照しながら本明細書で特徴が説明される場合、対応する特徴を本発明の別の態様の実施形態で提供することができる。
【００２０】
次に、本発明の好ましい態様について、添付の図面を参照しながら例として説明する。
【図面の簡単な説明】
【００２１】
【図１】本発明を具体化する方法を実装するための、例示のデータ処理システムを示す概略図である。
【図２】本発明を具体化する暗号化／復号プロセスを実装する、システム・デバイスによって実行されるステップを示す図である。
【図３】本発明を具体化する暗号化方式の例示の適用例における、システム・デバイス間の対話を示す図である。
【発明を実施するための形態】
【００２２】
図１は、説明されることになる暗号化ベース技法の動作に関与する主な構成要素を示す、データ処理システムの簡略概略図である。この説明のために、図内ではそれぞれコンピュータ２、３、および４によって表される３人の当事者Ｐ１、Ｐ２、およびＰ３を含む例示システム１を考えてみる。コンピュータ２は、説明されることになる例において秘密データを暗号化するための、本発明を具体化する暗号化装置を実装している。コンピュータ２は、コンピュータの動作を全体として制御し、暗号化プロセスの主要なステップを実装するための、制御論理６を含む。コンピュータ２は、暗号化プロセスにおいて使用されるデータを記憶するためのメモリ６、および通信インターフェース７も含む。コンピュータ３は、コンピュータ３の動作を制御するための制御論理８、メモリ９、および通信インターフェース１０を含む。制御論理８は、以下で説明されるシナリオにおいて、コンピュータ２から受信されるメッセージを復号するための機能を含む。制御論理８は、以下で説明される別のシナリオにおいて、ここではコンピュータ４によって表される検証者を用いて証明プロトコルを実装するための機能も含む。特に制御論理８は、説明されることになるシナリオにおいて、検証者４を用いてゼロ知識証明（ＺＫＰ）プロトコルを実装することができる。検証者コンピュータ４は、コンピュータを全体として制御するため、およびコンピュータ３によって実行される証明の検証に関する機能を含むための、制御論理１１を有する。検証者コンピュータは、これらのプロセスで使用するためのメモリ１２、および通信インターフェース１３もさらに含む。
【００２３】
システム１の動作時に、コンピュータ２、３、および４は、それらのそれぞれの通信インターフェースを通じ、データ通信ネットワーク１５を介して通信することができる（ネットワーク１５は実際には複数の構成要素ネットワークあるいはインターネットワークまたはその両方を含むことができる）。これらのコンピュータの制御論理５、８、１１は、以下で説明される暗号化プロセスの適切なステップを実装するために構成される。一般にこの制御論理は、ハードウェアまたはソフトウェアあるいはそれらの組み合わせにおいて実装可能であり、当事者Ｐ１からＰ３を実装するデバイスの精密な形は、説明されるプロセスの基礎的な動作とは大部分が無関係である。しかしながらこの特定の例では、これらのデバイスが汎用コンピュータによって実装されること、ならびに、制御論理５、８、および１１が、説明される機能を実行するためのホスト・コンピュータを構成するそれぞれのコンピュータ・プログラムによって実装されることを想定している。当業者であれば、本明細書での説明から好適なソフトウェアが明らかとなろう。
【００２４】
本発明を具体化する暗号化方式について、第１に容易な通信動作との関連において説明するが、この動作によって「送信者」として動作する当事者Ｐ１は、当該データのプライバシを保持しながら、「受信者」である当事者Ｐ２にメッセージを送信する必要がある。この動作における主要なステップは、図２に示されている。送信者コンピュータ２によって実行されるステップはこの図の左側に示され、受信者コンピュータ３によって実行されるステップは右側に示されている。この動作は、受信者３に関連付けられた暗号鍵ペア（ｓｋ、ｐｋ）を利用する。どちらの鍵も受信者３に知られており、受信者メモリ９内に保持されている。鍵ｐｋは、システム１内で受信者３によって公開される公開鍵である。したがってこの鍵は、送信者２によるアクセスが可能であり、送信者メモリ６に記憶されることが可能である。鍵ｓｋは秘密鍵であり、受信者３には依然として秘密である。
【００２５】
メッセージング動作の第１のステップ、ステップ（ａ）では、送信者２の暗号化論理５が通信されることになる秘密データを含むメッセージｍを構築する。このステップで秘密データは、以下でさらに考察されるように、代数群のペアのうちの１つまたは複数の要素によって表される。適切であれば、このステップは、秘密データを群要素に符号化するための任意の便利な符号化プロセスを含むことができる。いずれの場合も、結果として生じる（１つまたは複数の群要素）のセットは、メッセージｍとしてメモリ６内に記憶される。プロセスのステップ（ｂ）で、送信者コンピュータ２の暗号化論理５は、受信者の公開鍵ｐｋを使用してメッセージｍを暗号化し、それによって暗号化済みメッセージｃが生成される。暗号化プロセスについては、以下でより詳細に説明する。次にステップ（ｃ）で、暗号化論理は、暗号化済みメッセージに関する整合性構成要素ｖを生成する。以下で詳述するように、整合性構成要素は暗号化済みメッセージｃと、メッセージｍの構築元である代数群に関連付けられた双線形マップとを使用して生成される。暗号化済みメッセージｃおよびその検証構成要素ｖの両方を含む暗号文ｃｔは、論理５によって暗号化プロセスの出力を形成する。ステップ（ｄ）で、暗号文ｃｔは、ネットワーク１５を通じ、送信者コンピュータ２の通信インターフェース７を介して受信者コンピュータ３に伝送される。暗号文はその通信インターフェース１０を介してコンピュータ３によって受信され、メモリ９に記憶される。その後受信者３の復号論理８は、ステップ（ｅ）で、暗号文が有効であるかどうかを判定する。特に復号論理８は、暗号文内の暗号化済みメッセージｃについて、整合性構成要素ｖが正しい（すなわち整合している）かどうかを判定する。このプロセスの詳細は以下で説明する。整合性構成要素が正しいものと判定された場合、暗号化済みメッセージが有効であること、すなわち送信者によって正当に計算され、ネットワーク１５を介した移行時に改ざんされていないことが確認される。ステップ（ｅ）で暗号文の妥当性が検査されるものと仮定すると、復号論理８はステップ（ｆ）に進み、その秘密鍵ｓｋを使用して暗号化済みメッセージｃを復号する。復号プロセスは元のメッセージｍおよび送信者２によって送信された秘密データを回復する。（本来はデータをメッセージ要素に符号化するために使用される任意の符号化方式は、送信者および受信者の両方の共通の知識となり、これにより、必要であれば論理８によってメッセージ要素のユーザ・データへの復号が実行できることに留意されたい。）
【００２６】
基礎となる暗号化プロセスの詳細を含む前述の暗号化方式の特に好ましい実施形態について、以下で説明する。
【００２７】
本方式のために、メッセージｍは、
双線形マップ
【数３】
0006041864.tif 000004
を満たす基礎群Ｇ１、Ｇ２のペアのうちの少なくとも１つの要素を含み、ここでＧＴはターゲット群である。この例では話を簡潔にするために、Ｇ１およびＧ２は、Ｇで示される同一群であるものとみなされる。特にＧおよびＧＴは、非縮退（non-degenerate）の効率的に計算可能な双線形マップ
【数４】
0006041864.tif 000005
を備える、素数位数群ｑを表す。
【００２８】
説明されることになる方式は、決定線形仮定（ＤＬＩＮ）の下でセキュアである。この仮定は当分野で周知であり、Ｇを素数位数群ｑとし、ｇ１，ｇ２，ｇ３←Ｇ、およびｒ，ｓ，ｔ←Ｚｑとして表すことができる。
【数５】
0006041864.tif 000006
および
【数６】
0006041864.tif 000007
という２つの分布は、計算上は区別できない。
【００２９】
この例では話を簡潔にするために、方式は、Ｇ内の単一の群要素であるメッセージｍを暗号化するものとして説明されることになる。方式はラベルもサポートしている。特にメッセージｍは、基礎群Ｇ１、Ｇ２のペア（ここでは同じ群Ｇ）のうちの少なくとも１つの要素に対応する、ラベルに関連付けられるものとみなされる。ラベルの使用は暗号分野では周知であり、ここで詳細に論じる必要はない。ラベルがメッセージに追加の情報を関連付けることができるものと理解すれば十分である。たとえばラベルを使用して、コンテキスト情報をトランザクションに付属させ、各トランザクションで異なるラベルを使用することによって、同じメッセージｍに関与する異なるトランザクションを区別することができる。この例では話を簡潔にするために、ラベルＬは基礎群のペア内（したがってここでは単一の群Ｇ内）の単一の群要素であるものと仮定される。
【００３０】
方式で使用されることになる鍵ペア（ｓｋ、ｐｋ）は、以下のように生成される。
ＫｅｙＧｅｎ（１λ）：ランダム群ジェネレータｇ，ｇ１，ｇ２，ｇ３←Ｇ＊を選択する。ランダムに選択された
【数７】
0006041864.tif 000008
の場合、
【数８】
0006041864.tif 000009
を設定する。次に、
【数９】
0006041864.tif 000010
を選択し、ｉ＝０、…、５の場合、
【数１０】
0006041864.tif 000011
を計算する。公開鍵
【数１１】
0006041864.tif 000012
および秘密鍵
【数１２】
0006041864.tif 000013
を出力する。
【００３１】
図２のステップ（ｂ）から（ｄ）で採用されるような暗号化方式は、以下によって定義される。
【数１３】
0006041864.tif 000014
：ランダムおよびｒ，ｓ←Ｚｑを選択する。
３つの要素ｕ１、ｕ２、およびｕ３からなるランダム構成要素は、以下のように生成される。
【数１４】
0006041864.tif 000015
暗号化済みメッセージｃは公開鍵ｐｋを使用して以下のように生成される。
【数１５】
0006041864.tif 000016
検証構成要素ｖは以下のように生成され、
【数１６】
0006041864.tif 000017
上式で、ｕ０＝ｇである。
次に、出力暗号文は以下のように構築される。
【数１７】
0006041864.tif 000018
【００３２】
このアルゴリズムにおける暗号化済みメッセージおよびランダム構成要素は、どちらも基礎群のペア（ここでは同じ群Ｇ）からの要素のセットを含む。この特定の例では、暗号化済みメッセージは単一の群要素からなり、ランダム構成要素は３つの群要素からなる。整合性構成要素ｖは、双線形マップを暗号化済みメッセージｃ、ランダム構成要素ｕ１からｕ３、およびラベルＬに適用することによって生成される。双線形マップの各適用により、ターゲット群ＧＴの要素が引き出される。これら要素の積は、上記で与えられた式に従って計算され、この例ではＧＴの単一の要素を含む最終的な整合性構成要素を引き出す。ここで出力暗号文ｃｔは、ランダム構成要素、暗号化済みメッセージｃ、および検証構成要素ｖの連鎖である。
【００３３】
図２のステップ（ｅ）から（ｆ）で採用されるような復号方式は、以下によって定義される。
【数１８】
0006041864.tif 000019
：
【数１９】
0006041864.tif 000020
を（ｕ１，ｕ２，ｕ３，ｃ，ｖ）として解析し、
【数２０】
0006041864.tif 000021
かどうかをチェックし、上式で、ｕ０＝ｇである。これが成功した場合、暗号文の妥当性は評価された。不成功であった場合、暗号文は無効として拒否される。妥当性検査を想定すると、暗号文は秘密鍵ｓｋを使用して、以下を通じて復号され、
【数２１】
0006041864.tif 000022
元のメッセージｍを公開する。
【００３４】
上記は、ＤＬＩＮの下でセキュアはＣＣＡ暗号化方式に関する効率的な構造を定義する。ＣＣＡセキュリティは当業者であれば容易に明らかとなるため、ここでは再生成する必要のない、通常のゲーム分析を介して容易に実証可能である。さらに上記の方式は、以前のＣＣＡ暗号化方式に勝る大きな利点を有する。前述のように、以前の方式は、暗号学的ハッシュ関数、衝突耐性ハッシュ関数、または、整合性チェック構成要素の計算において基礎となる意味論的にセキュアな暗号化方式の要素を分けることなどの、技法を採用する。たとえこうした方式が、たとえば秘密鍵およびランダム構成要素などにおいて代数群の要素を使用する場合であっても、整合性チェックは暗号化方式の要素を代数群外に移動するように実装される。この基礎となる構造を失うことにより、前に説明したように、整合性チェック機能の入力と出力との間の関係を証明できないようにする。対照的に、前述の暗号化方式は、代数群の領域を出ないような整合性チェックの実装によって構造を保持する。具体的に言えば、上記システムにおける整合性チェック機能は、意味論的にセキュアな暗号化方式が組み込まれた異なる代数群の間で双線形マップを使用する。したがって、上記の構造が構造保持ＣＣＡ暗号化方式を提供し、これによって、暗号文の一定の特性を証明することが必要であると同時に高度なプライバシを保持するプロトコルにとって重要な暗号文全体に、一定の構造が組み込まれる。特にこの方式は、暗号化済みメッセージを、または実際にいずれの暗号文構成要素も公開せずに、暗号化済みメッセージに関する証明を可能にする。したがって、この方式によって生成される暗号文を所有している当事者は、暗号文を検証者に公開せずに、自分が正当に計算された暗号文を所有していることを検証者に証明することができる。
【００３５】
この暗号化方式は、秘密の暗号文に関して検証者に証明する必要のある様々なシナリオで使用可能である。これらのシナリオでは、暗号化は様々な異なる当事者の公開鍵の下で実行可能である。たとえばある当事者が、暗号文自体を検証者に公開せずに、自分が有効な暗号文を所有していることを検証者に対して証明する必要がある適用例では、暗号化は、検証者が信用する何らかの当事者の公開鍵の下で実行可能である。こうしたシナリオの例を、図１の単純なデータ処理システムに関して以下で説明する。このシナリオでは、当該暗号文は、あるユーザに対して発行された証明書の一部を形成し、このユーザはこの証明書を使用して、検証者によって提供されるサービスへのアクセス権を得ることを希望する。このシナリオでは、図１の当事者Ｐ１が証明書発行者を表し、当事者Ｐ２がユーザ、Ｐ３が検証者を表す。この方式の実装における主要なステップが図３に示されている。この図で、発行者、ユーザ、および検証者という３人の当事者は、それぞれ左側、中央、および右側の列で示されている。
【００３６】
プロセスのステップ（ａ）で、証明書が発行されることになるユーザ・データは、ユーザ・コンピュータ３によって発行者コンピュータ２に送信される。この例示のシナリオでは、ユーザ・データはユーザ識別（ＩＤ）データであるものと想定される。ここで発行者コンピュータ２は、ユーザおよび検証者の双方に信用されている。ステップ（ｂ）で、必要に応じてユーザＩＤの妥当性が確認された後、発行者２の暗号化論理５は、それ自体の秘密鍵ｓｋに対応する公開鍵ｐｋの下で、ＩＤデータ（および証明書に含まれることになる任意の他のデータ）を表すメッセージｍを暗号化する。結果として生じる暗号化済みメッセージｃを含む暗号文ｃｔは、ステップ（ｃ）で、上記で詳述されたように生成される。この暗号文ｃｔは、それ自体で証明書としての役割を果たすこと、またはいずれかの便利な様式で発行者２によって生成される証明書の一部を形成することができる。いずれの場合も、暗号文ｃｔを含む証明書はステップ（ｄ）でユーザ・コンピュータ３に戻され、メモリ９に記憶される。
【００３７】
このシナリオでは、ユーザ３は受信した証明書を使用して、検証者４によって提供されるサービスへのアクセス権を得ることができる。サービスへアクセスするための条件として、ユーザは、自分のＩＤデータに関する正当に計算された暗号文ｃｔの所有を証明しなければならない。これは、（ｂ）およびステップ（ｃ）で採用される構造保持暗号化方式によって、暗号文ｃｔを検証者に公開せずに実行することができる。ユーザ３は図３のプロセスのステップ（ｅ）で、サービスへのアクセス要求を送信する。その後ステップ（ｆ）で、ユーザ・コンピュータ３の制御論理８は、検証者コンピュータ４の検証論理１１を、暗号化済みＩＤ  ｃおよび暗号化済みＩＤ  ｃの妥当性を検査する整合性構成要素ｖを知っていることのＺＫＰ証明に従事させる。このようにしてユーザ３は、自分のＩＤデータに関する正当に計算された暗号文の所有を証明する。暗号化方式の構造保持の性質により、この証明は一般に知られた様式で標準の暗号化技法を使用して実行することが可能であり、当業者であれば好適な実装が容易に明らかとなろう。例を挙げると、ＺＫＰ証明は、Jens Groth、Amit Sahaiによる「EfficientNon-interactive Proof Systems for Bilinear Groups」、EUROCRYPT2008:415-432に記載された、Groth Sahai証明システムを活用することによって実行可能である。別の方法として、たとえばＺＫＰ証明は、たとえば２００９年のCamenisch等による「On the Portability of Generalized SchnorrProofs」、Eurocrypt 2009、LNCS 5479、４２５〜４４２ページに記載されるような通常の離散対数に基づく証明を使用して、実行可能である。こうしたＺＫＰ証明は、証明されることになるもの以外は何も検証者に公開しない。さらに暗号化方式の構造は、いっさい知識なしでの証明、特に、暗号文内に暗号化されたメッセージｍに関する証明を実行可能にする。たとえばメッセージ自体を公開せずに、メッセージが一定の特性を有することが証明できる。したがって、たとえばＩＤ自体を公開せずに、いっさいの知識なしで暗号文が有効なユーザＩＤを暗号化していることが証明可能である。ステップ（ｆ）で証明がユーザによって正しく実行され、コンピュータ４によって検証されたかどうかに応じて、ステップ（ｇ）で検証者４は、検証手順の結果に従い、サービスへのユーザ・アクセスを許可または拒否する。
【００３８】
図３のようなシナリオの特定の例は、その構成要素が暗号文である、いわゆる「漏洩防止署名」を知っていることをユーザが証明しなければならない。しかしながら、前述の基本原理に関与する多数のシナリオを予測することができる。いくつかの適用例では、暗号化は信頼できる第三者（ＴＴＰ）の公開鍵の下で実行可能である。暗号化を実行する当事者が、結果として生じる暗号文に関する証明も実行する適用例も、予測可能である。たとえば図１では、コンピュータ２が何らかの公開鍵の下でメッセージを暗号化した後、検証者４に対して正当に計算された暗号文を知っていることを証明できるシナリオが予測可能である。こうしたシナリオの特定の例が、２人の当事者が自分たちのメッセージを公開せずに、そのメッセージの暗号化を合同で計算するものである。これが、出願人の参照の下で本明細書と同時に出願された同時係属の欧州特許出願第ＣＨ９−２０１０−００８５号の対象を形成している。
【００３９】
以上、例示の実施形態について説明してきたが、多くの代替および修正が予測可能である。たとえば、単一の群要素であるメッセージｍに関して詳細な構造を例示してきたが、当業者であれば、この方式が簡単な様式で群要素のベクトルを含むメッセージに拡張されることが明らかとなろう。同様にこの方式は、ラベルＬが群要素のベクトルであるケースにも自明に拡張される。またスペース｛０，１｝＊からのラベルを１つまたは複数の群要素にハッシュすることが可能であるため、一般にラベルは、群要素に対応する任意のビット文字列とすることができる。
【００４０】
詳細な暗号化プロトコルに対する様々な修正も予測可能である。たとえば、様々な異なる暗号化方式を採用して、平文メッセージｍから暗号化済みメッセージｃを生成することができる。整合性構成要素ｖを異なる方法で生成することもできる。たとえば上記の式で、整合性構成要素はターゲット群ＧＴのうちの少なくとも１つの要素を含む。これは特に効率的な式である。しかしながら代替の構造では、整合性構成要素はそれぞれの基礎群Ｇ１およびＧ２からの要素の１つまたは複数のペアを含むことができる。この場合、双線形マップが満たされる群要素のペアを使用することによって、整合性構成要素内で双線形マップが使用され、これは対応する検証手順の中で検証することができる。この種の実装により、異なるシナリオで使用する場合により優れた柔軟性を提供することができる。当業者であれば、こうした実装の細部は容易に明らかとなろう。
【００４１】
上記では単なる例示の目的で、単純なデータ処理システム１が使用されているが、本発明を具体化する暗号化方式は、たとえば携帯電話、ＰＤＡ（携帯情報端末）、スマート・カード、カード・リーダなどの、汎用コンピュータ以外の処理デバイスを含む様々なシステムで実装可能である。いくつかの適用例では、たとえばユーザ・データを暗号化している暗号文を、たとえばユーザＩＤデータを記憶している識別カードなどのスマート・カード上に記憶し、様々な適用例の証明プロトコルで使用することができる。
【００４２】
本発明の範囲を逸脱することなく、説明された実施形態への多くの他の変更および修正が可能であることを理解されよう。
【図１】
0006041864.tif 000025
【図２】
0006041864.tif 000026
【図３】
0006041864.tif 000027