説明

関数暗号を用いた時限暗号システム、時限暗号方法、装置、プログラム

【課題】指定された復号基準時刻以降に生成された時刻トークンを用いて暗号文を復号できる時限暗号技術を提供する。
【解決手段】次のような暗号を利用して時限暗号を構成する。暗号は、公開パラメータpkとマスター秘密鍵skが定められており、KeyGen(sk,i)→ski(マスター秘密鍵skと情報iを入力とし、情報iに対応する秘密鍵skiを出力するアルゴリズム)と、Enc(pk,j,x)→cj(公開パラメータpkと情報jと平文xを入力とし、暗号文cjを出力するアルゴリズム)と、Dec(pk,ski,cj)→y(公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、情報yを出力するアルゴリズム)を含み、情報iと情報jが関係Rを満たすときに情報yとして平文xを得る。情報iを時刻tを含む情報とし、情報jを復号アルゴリズムの実行の時的制限に係る予め定められた時間に関する情報t'を含む情報とする。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は時限暗号技術に関する。
【背景技術】
【0002】
時限暗号は、Mayによって1993年に提案された特殊な暗号で、正規の受信者でも送信者が指定した時刻になるまで復号できないような暗号である。Blakeらが2004年にpairing関数を用いた構成手法を提案して以来、時刻サーバがユーザと対話をしない時刻トークンブロードキャスト型時限暗号が盛んに研究されている。このタイプの時限暗号が復号が可能となる時刻より前の時刻において受信者に対して秘匿を実現する仕組みは、概ね、時刻をIDとしたIDベース暗号によって実現されていると言ってよい。
【0003】
IDベース暗号は、下記の4つのアルゴリズム(Setup,KeyGen,Enc,Dec)を枠組みとする暗号である。プロトコルの概略は下記のとおりである。
《プロトコルIBE》
========================================
・Setup(1λ)→(pk,sk):セットアップアルゴリズム
セキュリティパラメータ1λを入力とし、公開パラメータpkとマスター秘密鍵skを出力する確率的多項式時間アルゴリズム
・KeyGen(sk,i)→ski:鍵生成アルゴリズム
マスター秘密鍵skと鍵識別子iを入力とし、当該鍵識別子iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズム
・Enc(pk,j,x)→cj:暗号化アルゴリズム
公開パラメータpkと受信者識別子jと暗号化対象の情報(平文)xを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズム
・Dec(pk,ski,cj)→y:復号アルゴリズム
公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、平文yを出力する確率的多項式時間アルゴリズム
========================================
【0004】
あらゆる識別子i∈{0,1}poly(λ)およびあらゆる平文x∈{0,1}poly(λ)に対して式(1)で表される確率Prがλに関して圧倒的(1との差が無視しうる)とき、そのIDベース暗号は正当であると云い、この性質を正当性と呼ぶ。なお、poly(λ)はλで決まる多項式長を表している。
【数1】

【0005】
このIDベース暗号を用いて時限暗号は例えば次のように構成される。プロトコルの概略は下記のとおりである。
《プロトコルTRC-IBE》
========================================
・まず、時刻サーバ装置は、上記セットアップアルゴリズムSetup(1λ)を実行して公開パラメータpkとマスター秘密鍵skを生成し、公開パラメータpkを公開する。
・時刻サーバ装置は、定期あるいは不定期に、上記鍵生成アルゴリズムKeyGen(sk,t)を実行して時刻トークンsktを生成し、時刻トークンsktをブロードキャストする。ただし、tはKeyGen(sk,t)を実行するときの時刻である。
・送信者装置は、復号時刻をt'、平文をmとして、上記暗号化アルゴリズムEnc(pk,t',m)を実行して暗号文ct'を生成し、暗号文ct'を受信者装置に送信する。
・受信者装置は、時刻サーバ装置から時刻t'の時刻トークンskt'を取得して、上記復号アルゴリズムDec(pk,skt',ct')を実行して平文mを得る。
========================================
【先行技術文献】
【非特許文献】
【0006】
【非特許文献1】A. C-F. Chan and I. F. Blake, "Scalable, Server-Passive, User Anonymous Timed Release Cryptography", in the proceeding of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS 2005), p.504-513, June 2005.
【発明の概要】
【発明が解決しようとする課題】
【0007】
従来の上記構成では、時刻サーバ装置がブロードキャストした時刻トークンskt'を受信者装置が取りこぼした場合、受信者装置が上記復号アルゴリズムDec(pk,skt',ct')を実行できないという問題がある。
【0008】
そこで本発明は、指定された復号基準時刻以降に生成された時刻トークンを用いて暗号文を復号できる時限暗号技術を提供することを目的とする。
【課題を解決するための手段】
【0009】
本発明の時限暗号技術は、次のとおりである。公開パラメータpkとマスター秘密鍵skが定められた暗号(KeyGen,Enc,Dec)が、KeyGen(sk,i)→ski:鍵生成アルゴリズム(マスター秘密鍵skと情報iを入力とし、当該情報iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズム)と、Enc(pk,j,x)→cj:暗号化アルゴリズム(公開パラメータpkと情報jと暗号化対象の情報(以下、平文という)xを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズム)と、Dec(pk,ski,cj)→y:復号アルゴリズム(公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、情報yを出力する確率的多項式時間アルゴリズム)とを含み、情報iと情報jが予め定められた関係Rを満たすときに情報yとして平文xが得られるように構成されている。時限暗号システムを構成する時刻サーバ装置では、定期あるいは不定期に、情報iを時刻tを含む情報として、暗号の鍵生成アルゴリズムKeyGen(sk,i)を実行して時刻トークンskt←KeyGen(sk,i)を生成する[時刻トークン生成処理]。時限暗号システムを構成する送信者成装置では、情報jを復号アルゴリズムの実行の時的制限に係る予め定められた時間に関する情報t'(時的制限情報t')を含む情報とし、平文xを平文mとして、暗号の暗号化アルゴリズムEnc(pk,j,m)を実行して暗号文ct'←Enc(pk,j,m)を生成する[暗号文生成処理]。時限暗号システムを構成する受信者装置では、秘密鍵skiを時刻トークンsktとし、暗号文cjを暗号文ct'として、暗号の復号アルゴリズムDec(pk,skt,ct')を実行する[復号処理]。
【発明の効果】
【0010】
本発明に拠れば、暗号を利用して時限暗号を構成するので、指定された復号基準時刻以降に生成された時刻トークンを用いて暗号文を復号できる。従って、例えば復号基準時刻として指定された時刻にブロードキャストされた時刻トークンを受信者装置が取得できなかったとしても、受信者装置は、当該復号基準時刻以降に生成された時刻トークンを用いて当該暗号文を復号することができる。
【図面の簡単な説明】
【0011】
【図1】実施形態の時限暗号システムを示す図。
【図2】実施形態における時限暗号の処理手順を示す図。
【図3】各実施例に関わる時限暗号システムの構成要素である時刻サーバ装置、送信者装置、受信者装置の機能構成を示す図。
【図4】ビット表現された整数変数tと定数t'とを比較する述語の構成方法(t>t')。
【図5】ビット表現された整数変数tと定数t'とを比較する述語の構成方法(t≧t')。
【図6】命題変数PRO(1),PRO(2)と命題変数PRO(3)の否定¬PRO(3)と論理記号∧,∨とを含む標準形論理式PRO(1)∧PRO(2)∨¬PRO(3)を表現する木構造データを例示する図。
【図7】命題変数PRO(1),PRO(2),PRO(3),PRO(6),PRO(7)と命題変数PRO(4),PRO(5)の否定¬PRO(4),¬PRO(5)と論理記号∧,∨とを含む標準形論理式PRO(1)∧PRO(2)∨PRO(2)∧PRO(3)∨PRO(1)∧PRO(3)∨¬PRO(4)∨(¬PRO(5)∧PRO(6))∧PRO(7)を表現する木構造データを例示する図。
【発明を実施するための形態】
【0012】
《原理》
本発明の時限暗号は関数暗号を利用して実現される。そこでまず関数暗号について説明する。
【0013】
<関数暗号>
近年、関数暗号と呼ばれるIDベース暗号の拡張暗号が話題となっている。関数暗号とIDベース暗号には構文の違いは全く無い。即ち、関数暗号も下記の4つのアルゴリズム(Setup,KeyGen,Enc,Dec)から構成される。プロトコルの概略は下記のとおりである。
《プロトコルFE》
========================================
・Setup(1λ)→(pk,sk):セットアップアルゴリズム
セキュリティパラメータ1λを入力とし、公開パラメータpkとマスター秘密鍵skを出力する確率的多項式時間アルゴリズム
・KeyGen(sk,i)→ski:鍵生成アルゴリズム
マスター秘密鍵skと鍵識別子iを入力とし、当該鍵識別子iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズム
・Enc(pk,j,x)→cj:暗号化アルゴリズム
公開パラメータpkと受信者識別子jと暗号化対象の情報(平文)xを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズム
・Dec(pk,ski,cj)→y:復号アルゴリズム
公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、平文yを出力する確率的多項式時間アルゴリズム
========================================
【0014】
関数暗号では、IDベース暗号の正当性が拡張されており、暗号文の受信者は鍵識別子iを持つ秘密鍵と受信者識別子jを持つ暗号文から平文xに関する何らかの関数fi,j(x)を評価することができるようになっている。即ち、或る関数fi,j(x)が存在し∀i,∀j,∀x∈{0,1}poly(λ)に対して式(2)で表される確率Prがλに関して圧倒的であるとき、その関数暗号(Setup,KeyGen,Enc,Dec)は正当であると云う。
【数2】

【0015】
特に、或る関係R(・,・)が存在し、式(3)で表されるタイプの関数fi,j(x)を持つ関数暗号は様々な暗号を包含している(⊥は正常に復号できなかったことを表す記号である)。
【数3】

【0016】
例えばIDベース暗号は式(4)で表される関数fi,j(x)を持つ関数暗号と定義することができる。
【数4】

【0017】
より高度な関係R(・,・)を持つ様々な関数暗号が研究されている。このタイプの関数暗号のうち最も汎用性の高いものは属性ベース暗号(attribute-based encryption, ABE)あるいは述語暗号(predicate encryption, PE)等と呼ばれ、よく研究されている。2010年に岡本龍明らは多項式サイズの述語および述語変数の集合に対応し、標準的な暗号学的仮定の下で適応的識別子攻撃に対してCCA安全が証明できる比較的実用的なこのタイプの関数暗号を提案した(参考文献1参照)。
(参考文献1)Tatsuaki Okamoto and Katsuyuki Takashima, "Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption," International Cryptology Conference CRYPTO, pp.191-208, November 2010.
【0018】
鍵識別子iを述語、受信者識別子jを述語変数のインスタンスとして式(5)で表される関係R(・,・)を持つ関数暗号は鍵ポリシー属性ベース暗号(key-policy attribute-based encryption, KP-ABE)と呼ばれる。
【数5】

【0019】
鍵識別子iを述語変数、受信者識別子jを述語のインスタンスとして式(6)で表される関係R(・,・)を持つ関数暗号は暗号文ポリシー属性ベース暗号(ciphertext-policy attribute-based encryption, CP-ABE)と呼ばれる。
【数6】

【0020】
<関数暗号を用いた時限暗号>
IDベース暗号と関数暗号の構文(アルゴリズムの入出力インターフェイス)は完全に一致している。従って、同じような安全性を持つならば時限暗号に関してIDベース暗号の代わりに関数暗号を利用できる。
【0021】
mを平文、tを時刻サーバ装置が時刻トークンを生成した時刻、t'を送信者装置が暗号文に設定した時的制限情報(復号アルゴリズムの実行の時的制限に係る予め定められた時間に関する情報である。以下、時的制限情報を特に断りのない限り復号基準時刻と呼ぶことにする)として、式(7)で表される関数ft,t'(m)を持つ関数暗号を利用できるならば受信者装置が時刻トークンを取得できなかった場合の上記問題を克服できる。
【数7】

【0022】
式(7)で表される関数ft,t'(m)によると、時刻tが時刻t'より小さい時(早い時)は復号時に⊥が出力され、時刻tが時刻t'以上の時(時刻tが時刻t'以降の時)は平文mが出力される。t≧t'あるいはその否定であるt<t'は関係Rによって表現できるところ、このような関数暗号を属性ベース暗号に基づいて構成する方法は2通り存在する。
【0023】
一つは鍵ポリシー属性ベース暗号を用いる方法である。この場合、時刻サーバ装置はtを現在時刻、t'を述語変数としてt≧t'なる述語(鍵識別子)に関して時刻トークンsktを生成して、時刻トークンsktをブロードキャストする。送信者装置は目的の復号基準時刻t'を属性に持つ暗号文ct'を生成し、当該暗号文ct'を受信者装置に送信する。
【0024】
もう一つは暗号文ポリシー属性ベース暗号を用いる方法である。この場合、時刻サーバ装置は、現在時刻tを属性に持つ時刻トークンsktを生成して、時刻トークンsktをブロードキャストする。送信者装置はtを述語変数、t'を目的の復号基準時刻としてt≧t'なる述語(受信者識別子)に関して暗号文ct'を生成し、当該暗号文ct'を受信者装置に送信する。
【0025】
いずれの場合であっても時刻トークンsktおよび暗号文ct'を持つ受信者装置はt≧t'なる時に暗号文ct'を復号できる。
【0026】
述語変数(現在時刻が代入される)と復号基準時刻をビット表現された整数と見做せば、現在時刻と復号基準時刻との大小判定を、述語変数を用いた述語として表現できる。従って、述語の充足によって復号可能か否かが決まる関数暗号があれば、ビット表現された整数の大小判定の結果によって復号可能か否かが決定される関数暗号を構成することができる。例えば、図4と図5に示すように比較する定数のビットイメージに対応して論理積andや論理和orで述語変数を合成することによって述語を決定できる。図4では整数変数tと定数t'との間におけるt>t'の関係を記述する述語を示してある。なお、t≦t'の関係を記述する述語は、t>t'の関係を記述する述語の否定(¬(t>t'))によって表される。図5では整数変数tと定数t'との間におけるt≧t'の関係を記述する述語を示してある。なお、t<t'の関係を記述する述語は、t≧t'の関係を記述する述語の否定(¬(t≧t'))によって表される。
【0027】
<公開検証可能関数暗号>
関数暗号のうち暗号文に対してKeyGenアルゴリズムから得られる如何なる鍵を持たなくとも、その暗号文が正しく作られていることが納得できるものを公開検証可能関数暗号と呼ぶ。暗号化手続きが正しく行われたことを証明する非対話零知識証明を暗号文に付加すれば、そのような暗号を構成することができる(参考文献2参照)。非対話零知識証明を用いることによって、暗号文に対して復号可能な如何なる鍵を使っても同じ結果が得られることを納得できる。
(参考文献2)Jens Groth and Amit Sahai, "Efficient Non-interactive Proof Systems for Bilinear Groups," Advances in Cryptology - EUROCRYPT 2008, LNCS 4965, pp.415-432, March 2010.
【0028】
《実施形態》
[時限暗号システム]
実施形態の時限暗号システム1は、図1に示すように、時刻サーバ装置100と、送信者装置200と、受信者装置300とを少なくとも含んで構成される。これらの各装置は、例えばインターネットなどの通信網5を経由して、相互に通信可能とされている。
【0029】
本発明の時限暗号システムは、ユーザの数に応じて一つまたは複数の送信者装置200と一つまたは複数の受信者装置300を含みえるが、本発明の理解を容易にするため、後述の実施形態では、時限暗号システム1は、1個の時刻サーバ装置100と1個の送信者装置200とN個の受信者装置300−1,・・・,300−i,・・・,300−Nを含むとする。ただし、Nは1以上の整数とする。
【0030】
時限暗号システム1における時限暗号処理を、図2を参照しながら叙述する。各装置の機能構成については、図3を参照されたい。なお、N個の受信者装置300−1,・・・,300−i,・・・,300−Nのうちのどの受信者装置についても同じ情報処理となるから、この説明では、任意性を考慮してi番目の受信者装置300−iにおける情報処理を想定する。
【0031】
[[実施例1]]
tを鍵識別子、t'を受信者識別子として、上記式(7)で表される関数ft,t'(m)を持つ関数暗号(Setup,KeyGen,Enc,Dec)を利用する。プロトコルの概略は下記のとおりである。なお、このような関数暗号であれば何ら限定はないので、ここでは一般的な説明をするに留めるが、実用の局面ではSetup,KeyGen,Enc,Decの各アルゴリズムが具体的に決まっているから、当然、当該各アルゴリズムを実行することになる。
《プロトコルTRC-FE》
========================================
・まず、時刻サーバ装置は、《プロトコルFE》で説明したセットアップアルゴリズムSetup(1λ)を実行して公開パラメータpkとマスター秘密鍵skを生成し、公開パラメータpkを公開する。
・時刻サーバ装置は、定期あるいは不定期に、《プロトコルFE》で説明した鍵生成アルゴリズムKeyGen(sk,t)を実行して時刻トークンsktを生成し、時刻トークンsktをブロードキャストする。ただし、tはKeyGen(sk,t)を実行するときの時刻である。
・送信者装置は、復号基準時刻をt'、平文をmとして、《プロトコルFE》で説明した暗号化アルゴリズムEnc(pk,t',m)を実行して暗号文ct'を生成し、暗号文ct'を受信者装置に送信する。
・受信者装置は、時刻サーバ装置から時刻tの時刻トークンsktを取得して、《プロトコルFE》で説明した復号アルゴリズムDec(pk,skt,ct')を実行して、t≧t'を満たす場合に平文mを得る。
========================================
【0032】
まず、時刻サーバ装置100の初期設定部101が、《プロトコルFE》で説明したセットアップアルゴリズムSetup(1λ)を実行して公開パラメータpkとマスター秘密鍵skを生成し(ステップS1)、公開パラメータpkを公開する(ステップS1a)。公開パラメータpkの公開は、例えば、送信者装置200や受信者装置300−iから時刻サーバ装置100にアクセスがあった場合に時刻サーバ装置100の送信部108が時刻サーバ装置100の記憶部(図示せず)に記憶されている公開パラメータpkを送信者装置200や受信者装置300−iに対して送信する手順や、送信者装置200や受信者装置300−iからのアクセスを問わず、時刻サーバ装置100の送信部108が時刻サーバ装置100の記憶部(図示せず)に記憶されている公開パラメータpkを送信者装置200や受信者装置300−iに対して送信する手順によって達成される。
【0033】
そして、時刻サーバ装置100の時刻トークン生成部102は、定期あるいは不定期に、《プロトコルFE》で説明した鍵生成アルゴリズムKeyGen(sk,t)を実行して時刻トークンsktを生成する(ステップS2)。ただし、tはKeyGen(sk,t)を実行するときの時刻である。この時刻tは時刻サーバ装置100の内部時計から取得した時刻であってもよいし、外部から供給される協定世界時(UTC - Universal Time, Coordinated)や日本標準時(JST - Japan Standard Time)などであってもよい。
【0034】
なお、時刻サーバ装置100の内部時計から取得した時刻を時刻tとする場合、少なくとも時刻サーバ装置100と送信者装置200との間で可能な限り(つまり、例えば数秒程度の誤差を許容するとしても)相互の時間を同期させておくことが望ましい。同期方法としては、例えば、時刻サーバ装置100が通信網5を経由して送信者装置200に、時刻サーバ装置100の内部時計の時刻を常時提供するようにすればよい。時刻tとして協定世界時や日本標準時を利用する場合、送信者装置200も協定世界時や日本標準時を受信できる構成としておくことが望ましい。なお、このことは、他の実施例でも同様である。
【0035】
時刻サーバ装置100の送信部108は、時刻トークン生成部102によって生成された時刻トークンsktをブロードキャストする(ステップS3)。ブロードキャストの対象に制限はないが、少なくとも受信者装置300−iはブロードキャストされた時刻トークンsktを受信できるシステム構成であることが必須である(ただし、既述のように、受信者装置300−iがブロードキャストされた時刻トークンsktを取りこぼしてしまう可能性は否定されない)。
【0036】
送信者装置200の暗号文生成部201は、復号基準時刻をt'、平文をmとして、送信者装置200の受信部209が受信した公開パラメータpkを用いて、《プロトコルFE》で説明した暗号化アルゴリズムEnc(pk,t',m)を実行して暗号文ct'を生成する(ステップS4)。当然であるが、復号基準時刻t'は、暗号文ct'を生成した時刻よりも遅い時刻である。
【0037】
送信者装置200の送信部208は、暗号文生成部201によって生成された暗号文ct'を受信者装置300−iに対して送信する(ステップS5)。なお、暗号文の送信対象となる受信者装置は一つであっても複数であってもよい。
【0038】
受信者装置300−iの復号部301は、受信者装置300−iの受信部309が受信した時刻トークンskt、公開パラメータpk、暗号文ct'を用いて、《プロトコルFE》で説明した復号アルゴリズムDec(pk,skt,ct')を実行する(ステップS6)。上記式(7)で表されるタイプの関数ft,t'(m)を持つ関数暗号(Setup,KeyGen,Enc,Dec)によると、多くの場合、復号アルゴリズムDec(pk,skt,ct')にて、関係R(ここではt≧t'である)の真偽を判定するための論理式やこれと等価な演算を通して当該関数ft,t'(m)の出力が決せられる暗号構造が組み込まれており、当該関係Rが真となる場合、つまりt≧t'を満たす場合に復号部301は平文mを得ることができる。
【0039】
[[実施例2]]
実施例2は、実施例1における関数暗号(Setup,KeyGen,Enc,Dec)として鍵ポリシー属性ベース暗号による場合の実施例である。実施例1を鍵ポリシー属性ベース暗号として具体化した事項について説明を加え、実施例1と同じ事項は説明を省略する。
【0040】
実施例2では、実施例1のステップS2の処理にて、次のような処理を行う。時刻サーバ装置100の時刻トークン生成部102が、定期あるいは不定期に、tを現在時刻(KeyGen(sk,t≧T)を実行するときの時刻)、Tを述語変数として、t≧Tなる述語に関して、《プロトコルFE》で説明した鍵生成アルゴリズムKeyGen(sk,t≧T)を実行して時刻トークンskt≧Tを生成する。現在時刻tは時刻サーバ装置100の内部時計から取得した時刻であってもよいし、外部から供給される協定世界時(UTC - Universal Time, Coordinated)や日本標準時(JST - Japan Standard Time)などであってもよい。
【0041】
実施例2では、実施例1のステップS6の処理にて、次のような処理を行う。受信者装置300−iの復号部301は、受信者装置300−iの受信部309が受信した時刻トークンskt≧T、公開パラメータpk、暗号文ct'を用いて、《プロトコルFE》で説明した復号アルゴリズムDec(pk,skt≧T,ct')を実行する。上記式(7)で表されるタイプの関数ft,t'(m)を持つ関数暗号(Setup,KeyGen,Enc,Dec)によると、多くの場合、復号アルゴリズムDec(pk,skt≧T,ct')にて、式(5)で表される関係R(ここではR(t≧T,T=t')である)の真偽を判定するための論理式やこれと等価な演算を通して当該関数ft,t'(m)の出力が決せられる暗号構造が組み込まれており、当該関係RがTrueとなる場合、つまりt≧t'を満たす場合に復号部301は平文mを得ることができる。
【0042】
IDベース暗号を用いた時限暗号では、時刻トークン生成に用いられた時刻tが復号基準時刻t'に一致していないと復号ができない構成であった。これに対して、実施例2によると、一つの復号基準時刻t'が組み込まれた暗号文が、“指数的多数に及びうる「復号基準時刻t'以降の時刻t」”で生成された時刻トークンのいずれによっても復号可能となっている。ここで指数的多数に及びうる時刻tとは、「時刻tが例えばnビットで表されるとすると2通りの時刻tが考えられる」というように、多項式長で表される時刻tとして指数関数的な数の種類の時刻が考えられることを意味している。IDベース暗号を用いた時限暗号は、指数関数的な数となる可能性のある処理対象に対して効率的な暗号処理が困難であるが、関数暗号を用いた時限暗号は、このような処理対象に対して効率的な暗号処理が可能である。
【0043】
[[実施例3]]
実施例3は、実施例1における関数暗号(Setup,KeyGen,Enc,Dec)として暗号文ポリシー属性ベース暗号による場合の実施例である。実施例1を暗号文ポリシー属性ベース暗号として具体化した事項について説明を加え、実施例1と同じ事項は説明を省略する。
【0044】
実施例3では、実施例1のステップS4の処理にて、次のような処理を行う。送信者装置200の暗号文生成部201は、述語変数をT、復号基準時刻をt'、平文をmとして、T≧t'なる述語に関して、送信者装置200の受信部209が受信した公開パラメータpkを用いて、《プロトコルFE》で説明した暗号化アルゴリズムEnc(pk,T≧t',m)を実行して暗号文cT≧t'を生成する。
【0045】
実施例3では、実施例1のステップS5の処理にて、次のような処理を行う。送信者装置200の送信部208は、暗号文生成部201によって生成された暗号文cT≧t'を受信者装置300−iに対して送信する。なお、暗号文の送信対象となる受信者装置は一つであっても複数であってもよい。
【0046】
実施例3では、実施例1のステップS6の処理にて、次のような処理を行う。受信者装置300−iの復号部301は、受信者装置300−iの受信部309が受信した時刻トークンskt、公開パラメータpk、暗号文cT≧t'を用いて、《プロトコルFE》で説明した復号アルゴリズムDec(pk,skt,cT≧t')を実行する。上記式(7)で表されるタイプの関数ft,t'(m)を持つ関数暗号(Setup,KeyGen,Enc,Dec)によると、多くの場合、復号アルゴリズムDec(pk,skt,cT≧t')にて、式(6)で表される関係R(ここではR(T≧t',T=t)である)の真偽を判定するための論理式やこれと等価な演算を通して当該関数ft,t'(m)の出力が決せられる暗号構造が組み込まれており、当該関係RがTrueとなる場合、つまりt≧t'を満たす場合に復号部301は平文mを得ることができる。
【0047】
IDベース暗号を用いた時限暗号では、時刻トークン生成に用いられた時刻tが復号基準時刻t'に一致していないと復号ができない構成であった。これに対して、実施例3によると、“指数的多数に及びうる「復号基準時刻t'以降の時刻」”が組み込まれた暗号文が、「復号基準時刻t'以降の時刻」を満たす時刻tで生成された時刻トークンによって復号可能となっている。ここで指数的多数に及びうる時刻とは、「時刻が例えばnビットで表されるとすると2通りの時刻が考えられる」というように、多項式長で表される時刻として指数関数的な数の種類の時刻が考えられることを意味している。ここで実施例3の有用性を理解するために、次のような事例を考える。送信者装置200が、受信者装置300−1に対しては、復号基準時刻をt'1とする述語に関する暗号化アルゴリズムEnc(pk,T≧t'1,m)を実行して暗号文cT≧t'1を生成してこれを送信し、受信者装置300−2に対しては、復号基準時刻をt'2とする述語に関する暗号化アルゴリズムEnc(pk,T≧t'2,m)を実行して暗号文cT≧t'2を生成してこれを送信し、受信者装置300−iに対しては、復号基準時刻をt'iとする述語に関する暗号化アルゴリズムEnc(pk,T≧t'i,m)を実行して暗号文cT≧t'iを生成してこれを送信する、という事例を考える(ただし、t'1,t'2,t'iは互いに異なるとする。平文mは受信者装置ごとに異なってもよいが、ここでは全ての受信者装置について同じとした)。このような事例では、IDベース暗号を用いた時限暗号によると、時刻サーバ装置100は、各受信者装置で復号可能となるために、各時刻t'1,t'2,t'iに応じた3種類の時刻トークンを作成することが必須となる。つまり、時刻サーバ装置100は、異なる3種類の時刻トークンを作成しこれらをブロードキャストするという、異なる3種類の時刻トークンに応じた「資源の消費」が避けられない。他方、関数暗号を用いた時限暗号によると、各時刻t'1,t'2,t'iのうち最も遅い時刻以降の時刻tにおいて時刻トークンを作成し、この一つの時刻トークンを各受信者装置にブロードキャストすることによって、どの受信者装置でも暗号文を復号することができるのである。よって、実施例3によると、さらに強く、“指数的多数に及びうる「復号基準時刻t'以降の時刻」”が組み込まれた暗号文の集合について、当該集合に含まれる暗号文ごとに復号基準時刻t'が異なるような場合においても、「これら異なる復号基準時刻t'のうち最も遅い時刻以降の時刻」を満たす時刻tで生成された一つの時刻トークンによって復号可能となっている、と云うことができる。
【0048】
[[実施例4]]
実施例4は、実施例2の変形例である。実施例2では、時刻サーバ装置100の時刻トークン生成部102が、tを現在時刻、Tを述語変数として、t≧Tなる述語に関して鍵生成アルゴリズムKeyGen(sk,t≧T)を実行して時刻トークンskt≧Tを生成していた。実施例4は、述語が拡張された例である。
【0049】
実施例4では、t≧Tなる述語ではなく、時刻tが経過する任意の有限個の時間区間[bi,ei](i=1,2,…,n)と復号基準時刻t'が代入されうる述語変数Tで構成される論理和∨i∈{1,2,…,n}(bi≦T≦ei)=(b1≦T≦e1)∨(b2≦T≦e2)∨・・・∨(bn≦T≦en)を述語とする。なお、n個の時間区間[bi,ei](i=1,2,…,n)のうち少なくともいずれかにおいてbi=eiであってもよい。
【0050】
従って、実施例4では、実施例1のステップS2の処理にて、次のような処理を行う。時刻サーバ装置100の時刻トークン生成部102が、定期あるいは不定期に、tを現在時刻(KeyGen(sk,t≧T)を実行するときの時刻)、Tを復号基準時刻t'が代入されうる述語変数として、∨i∈{1,2,…,n}(bi≦T≦ei)なる述語に関して、《プロトコルFE》で説明した鍵生成アルゴリズムKeyGen(sk,∨i∈{1,2,…,n}(bi≦T≦ei))を実行して時刻トークンskt,Tを生成する。現在時刻tは時刻サーバ装置100の内部時計から取得した時刻であってもよいし、外部から供給される協定世界時(UTC - Universal Time, Coordinated)や日本標準時(JST - Japan Standard Time)などであってもよい。
【0051】
そして、実施例4では、実施例1のステップS6の処理にて、次のような処理を行う。受信者装置300−iの復号部301は、受信者装置300−iの受信部309が受信した時刻トークンskt,T、公開パラメータpk、暗号文ct'を用いて、《プロトコルFE》で説明した復号アルゴリズムDec(pk,skt,T,ct')を実行する。上記式(7)で表されるタイプの関数ft,t'(m)を持つ関数暗号(Setup,KeyGen,Enc,Dec)によると、多くの場合、復号アルゴリズムDec(pk,skt,T,ct')にて、式(5)で表される関係R(ここではR(∨i∈{1,2,…,n}(bi≦T≦ei),T=t')である)の真偽を判定するための論理式やこれと等価な演算を通して当該関数ft,t'(m)の出力が決せられる暗号構造が組み込まれており、当該関係RがTrueとなる場合、つまりt≧t'を満たす場合に復号部301は平文mを得ることができる。
【0052】
[[実施例5]]
実施例5は、実施例3の変形例である。実施例3では、送信者装置200の暗号文生成部201が、述語変数をT、復号基準時刻をt'、平文をmとして、T≧t'なる述語に関して暗号化アルゴリズムEnc(pk,T≧t',m)を実行して暗号文cT≧t'を生成していた。実施例5は、述語が拡張された例である。
【0053】
実施例5では、T≧t'なる述語ではなく、時的制限情報t'としての任意の有限個の時間区間[bi,ei](i=1,2,…,n)と時刻tが代入されうる述語変数Tで構成される論理和∨i∈{1,2,…,n}(bi≦T≦ei)=(b1≦T≦e1)∨(b2≦T≦e2)∨・・・∨(bn≦T≦en)を述語とする。なお、n個の時間区間[bi,ei](i=1,2,…,n)のうち少なくともいずれかにおいてbi=eiであってもよい。
【0054】
従って、実施例5では、実施例1のステップS4の処理にて、次のような処理を行う。送信者装置200の暗号文生成部201は、時刻tが代入されうる述語変数をT、時的制限情報t'を有限個の時間区間[bi,ei](i=1,2,…,n)、平文をmとして、∨i∈{1,2,…,n}(bi≦T≦ei)なる述語に関して、送信者装置200の受信部209が受信した公開パラメータpkを用いて、《プロトコルFE》で説明した暗号化アルゴリズムEnc(pk,∨i∈{1,2,…,n}(bi≦T≦ei),m)を実行して暗号文cT,t'を生成する。
【0055】
実施例5では、実施例1のステップS5の処理にて、次のような処理を行う。送信者装置200の送信部208は、暗号文生成部201によって生成された暗号文cT,t'を受信者装置300−iに対して送信する。なお、暗号文の送信対象となる受信者装置は一つであっても複数であってもよい。
【0056】
実施例5では、実施例1のステップS6の処理にて、次のような処理を行う。受信者装置300−iの復号部301は、受信者装置300−iの受信部309が受信した時刻トークンskt、公開パラメータpk、暗号文cT,t'を用いて、《プロトコルFE》で説明した復号アルゴリズムDec(pk,skt,cT,t')を実行する。上記式(7)で表されるタイプの関数ft,t'(m)を持つ関数暗号(Setup,KeyGen,Enc,Dec)によると、多くの場合、復号アルゴリズムDec(pk,skt,cT,t')にて、式(6)で表される関係R(ここではR(∨i∈{1,2,…,n}(bi≦T≦ei),T=t)である)の真偽を判定するための論理式やこれと等価な演算を通して当該関数ft,t'(m)の出力が決せられる暗号構造が組み込まれており、当該関係RがTrueとなる場合、つまりt≧t'を満たす場合に復号部301は平文mを得ることができる。
【0057】
実施例4と実施例5は、例えば次のような事例において有用である。例えば、送信者装置200を扱うユーザの意図として、受信者装置300−iに時間(b1≦T≦e1)または(b2≦T≦e2)(ただし、b1≦e1<b2≦e2とする)のみで復号可能とさせたいという意図がある場合に、受信者装置300−iが時刻トークンを記憶可能な記憶部を持っているとすると、受信者装置300−iは、時間(b1≦T≦e1)に時刻トークンを正しく受信し、ユーザが意図しない時間(e1≦T≦b2)に当該時刻トークンを用いて正しく復号するということができてしまう。そこで受信者装置300−iに耐タンパー機能を持つ記憶部、つまり時刻トークンを記憶不能な記憶部を持たせることによって、送信者装置200を扱うユーザが意図した時間帯∨i∈{1,2,…,n}(bi≦T≦ei)のみで復号可能とすることができる。
【0058】
[[実施例6]]
実施例6は、実施例1から実施例5までのそれぞれの変形例に対応する。実施例6では、送信者装置200の暗号文生成部201が暗号文を正しく生成したことを証明する非対話零知識証明用の情報σが暗号文に添付される。これによって、受信者装置300−iの検証部(図示しない)は、非対話零知識証明用の情報σを利用して、送信者装置200から受信した暗号文が正しく生成されたものであるか否かを検証することができる。なお、非対話零知識証明用の情報σは関数暗号に応じてその実体アルゴリズムが決定され、例えばペアリングを用いて関数暗号が実装される場合、上記参考文献2に従って非対話零知識証明アルゴリズムを定めることができる。
【0059】
以下、関数暗号について概説する。説明に先立ち記号等を定義する。
〔定義〕
行列:「行列」とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも「行列」と表現する。
(・)T:(・)Tは・の転置行列を表す。
(・)-1:(・)-1は・の逆行列を表す。
∧:∧は論理積(AND)を表す論理記号である。
∨:∨は論理和(OR)を表す論理記号である。
¬:¬は否定(NOT)を表す論理記号である。
命題変数:命題変数は命題の「真」,「偽」("false","true")を要素とする集合{真,偽}上の変数である。命題変数及び命題変数の否定を総称してリテラル(literal)と呼ぶ。
論理式:論理式とは数理論理学における命題を表す形式的文法を有する式を意味する。具体的には「真」及び「偽」は論理式であり、命題変数は論理式であり、論理式の否定は論理式であり、論理式と論理式との論理積は論理式であり、論理式と論理式との論理和は論理式である。
Z:Zは整数集合を表す。
sec:secはセキュリティパラメータ(sec∈Z, sec>0)を表す。
0*:0*は*個の0からなる列を表す。
1*:1*は*個の1からなる列を表す。
Fq:Fqは位数qの有限体を表す。位数qは1以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fqの例は素体やそれを基礎体とした拡大体である。なお、有限体Fqが素体である場合の演算は、例えば、位数qを法とする剰余演算によって容易に構成できる。また、有限体Fqが拡大体である場合の演算は、例えば、既約多項式を法とする剰余演算によって容易に構成できる。有限体Fqの具体的な構成方法は、例えば、参考文献1「ISO/IEC 18033-2: Information technology - Security techniques - Encryption algorithms - Part 2: Asymmetric ciphers」に開示されている。
0F:0Fは有限体Fqの加法単位元を表す。
1F:1Fは有限体Fqの乗法単位元を表す。
δ(i,j):δ(i,j)はクロネッカーのデルタ関数を表す。i=jの場合にδ(i,j)=1Fを満たし、i≠jの場合にδ(i,j)=0 Fを満たす。
E:Eは有限体Fq上で定義された楕円曲線を表す。Eはアフィン(affine)座標版のWeierstrass方程式
y2+a1・x・y+a3・y=x3+a2・x2+a4・x+a6
(ただし、a1,a2,a3,a4,a6∈Fq)を満たすx,y∈Fqからなる点(x,y)の集合に無限遠点と呼ばれる特別な点Oを付加したもので定義される。楕円曲線E上の任意の2点に対して楕円加算と呼ばれる二項演算+及び楕円曲線E上の任意の1点に対して楕円逆元と呼ばれる単項演算−がそれぞれ定義できる。また、楕円曲線E上の有理点からなる有限集合が楕円加算に関して群をなすこと、楕円加算を用いて楕円スカラー倍算と呼ばれる演算が定義できること、及びコンピュータ上での楕円加算などの楕円演算の具体的な演算方法はよく知られている(例えば、参考文献1、参考文献2「RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems」、参考文献3「イアン・F・ブラケ、ガディエル・セロッシ、ナイジェル・P・スマート=著、「楕円曲線暗号」、出版=ピアソン・エデュケーション、ISBN4-89471-431-0」等参照)。
また、楕円曲線E上の有理点からなる有限集合は位数p(p≧1)の部分群を持つ。例えば、楕円曲線E上の有理点からなる有限集合の要素数を#Eとし、pを#Eを割り切る大きい素数とした場合、楕円曲線Eのp等分点からなる有限集合E[p]は、楕円曲線E上の有理点からなる有限集合の部分群を構成する。なお、楕円曲線Eのp等分点とは、楕円曲線E上の点Aのうち、楕円曲線E上での楕円スカラー倍算値p・Aがp・A=Oを満たす点を意味する。
G1, G2, GT:G1, G2,GTは位数qの巡回群を表す。巡回群G1, G2の具体例は、楕円曲線Eのp等分点からなる有限集合E[p]やその部分群である。G1=G2であってもよいしG1≠G2であってもよい。また、巡回群GTの具体例は、有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における1のp乗根からなる有限集合である。巡回群G1, G2,GTの位数と有限体Fqの位数とを同一とすることで安全性が向上する。
なお、本形態では、巡回群G1, G2上で定義された演算を加法的に表現し、巡回群GT上で定義された演算を乗法的に表現する。すなわち、χ∈Fq及びΩ∈G1に対するχ・Ω∈G1は、Ω∈G1に対して巡回群G1で定義された演算をχ回施すことを意味し、Ω1, Ω2∈G1に対するΩ12∈G1は、Ω1∈G1とΩ2∈G1とを被演算子として巡回群G1で定義された演算を行うことを意味する。同様に、χ∈Fq及びΩ∈G2に対するχ・Ω∈G2は、Ω∈G2に対して巡回群G2で定義された演算をχ回施すことを意味し、Ω1, Ω2∈G2に対するΩ12∈G2は、Ω1∈G2とΩ2∈G2とを被演算子として巡回群G2で定義された演算を行うことを意味する。一方、χ∈Fq及びΩ∈GTに対するΩχ∈GTは、Ω∈GTに対して巡回群GTで定義された演算をχ回施すことを意味し、Ω12∈GTに対するΩ1・Ω2∈GTは、Ω1∈GTとΩ2∈GTとを被演算子として巡回群GTで定義された演算を行うことを意味する。
Ψ:Ψは1以上の整数を表す。
ψ:ψは0以上Ψ以下の整数ψ=0,...,Ψを表す。
λ:λは1以上Ψ以下の整数λ=1,...,Ψを表す。
n(ψ):n(ψ)は1以上の整数を表す。
ζ(ψ):ζ(ψ)は0以上の整数を表す。
G1n(ψ)+ζ(ψ):G1n(ψ)+ζ(ψ)はn(ψ)+ζ(ψ)個の巡回群G1の直積を表す。
G2n(ψ)+ζ(ψ):G2n(ψ)+ζ(ψ)はn(ψ)+ζ(ψ)個の巡回群G2の直積を表す。
g1, g2,gT:g1, g2, gTは巡回群G, G1, G2, GTの生成元を表す。
V(ψ):V(ψ)はn(ψ)+ζ(ψ)個の巡回群G1の直積からなるn(ψ)+ζ(ψ)次元のベクトル空間を表す。
V*(ψ):V*(ψ)はn(ψ)+ζ(ψ)個の巡回群G2の直積からなるn(ψ)+ζ(ψ)次元のベクトル空間を表す。
eψ:eψは直積G1n(ψ)+ζ(ψ)と直積G2n(ψ)+ζ(ψ)との直積G1n(ψ)+ζ(ψ)×G2n(ψ)+ζ(ψ)を巡回群GTに写す非退化な双線形写像(bilinear map)を表す。双線形写像eψは、巡回群G1のn(ψ)+ζ(ψ)個の元γβ(β=1,...,n(ψ)+ζ(ψ))と巡回群G2のn(ψ)+ζ(ψ)個の元γβ*(β=1,...,n(ψ)+ζ(ψ))とを入力とし、巡回群GTの1個の元を出力する。
eψ:G1n(ψ)+ζ(ψ)×G2n(ψ)+ζ(ψ)→GT …(1)
双線形写像eψは以下の性質を満たす。
[双線形性]すべてのΓ1∈G1n(ψ)+ζ(ψ),Γ2∈G2n(ψ)+ζ(ψ)及びν,κ∈Fqについて以下の関係を満たす。
eψ(ν・Γ1,κ・Γ2)=eψ12)ν・κ …(2)
[非退化性]すべてのΓ1∈G1n(ψ)+ζ(ψ),Γ2∈G2n(ψ)+ζ(ψ)を巡回群GTの単位元に写す写像ではない。
[計算可能性]あらゆる
Γ1∈G1n(ψ)+ζ(ψ),Γ2∈G2n(ψ)+ζ(ψ) …(3)
についてeψ12)を効率的に計算するアルゴリズムが存在する。
本形態では、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像
Pair:G1×G2→GT …(4)
を用いて双線形写像eψを構成する。本形態の双線形写像eψは、巡回群G1のn(ψ)+ζ(ψ)個の元γβ (β=1,...,n(ψ)+ζ(ψ))からなるn(ψ)+ζ(ψ)次元ベクトル(γ1,...,γn(ψ)+ζ(ψ))と、巡回群G2のn(ψ)+ζ(ψ)個の元γβ*(β=1,...,n(ψ)+ζ(ψ))からなるn(ψ)+ζ(ψ)次元ベクトル(γ1*,...,γn(ψ)+ζ(ψ)*)との入力に対し、巡回群GTの1個の元を出力する。
eψ:Πβ=1n(ψ)+ζ(ψ)Pair(γβ, γβ*) …(5)
なお、双線形写像Pairは、巡回群G1の1個の元と巡回群G2の1個の元との組を入力とし、巡回群GTの1個の元を出力する。双線形写像Pairは、以下の性質を満たす。
[双線形性]すべてのΩ1∈G1,Ω2∈G2及びν,κ∈Fqについて以下の関係を満たす。
Pair(ν・Ω1,κ・Ω2)=Pair(Ω12)ν・κ …(6)
[非退化性]すべての
Ω1∈G1,Ω2∈G2 …(7)
を巡回群GTの単位元に写す写像ではない。
[計算可能性]あらゆるΩ1∈G1,Ω2∈G2についてPair(Ω12)を効率的に計算するアルゴリズムが存在する。
双線形写像Pairの具体例は、WeilペアリングやTateペアリングなどのペアリング演算を行うための関数である(例えば、参考文献4「Alfred. J. Menezes,ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS, KLUWER ACADEMIC PUBLISHERS,ISBN0-7923-9368-6,pp. 61-81」等参照)。また、楕円曲線Eの種類に応じ、Tateペアリングなどのペアリング演算を行うための関数と所定の関数phiを組み合わせた変更ペアリング関数e(Ω1,phi(Ω2))(Ω1∈G1,Ω2∈G2)を双線形写像Pairとして用いてもよい(例えば、参考文献2等参照)。また、ペアリング演算をコンピュータ上で行うためのアルゴリズムとしては、周知のMiller のアルゴリズム(参考文献5「V. S. Miller, “Short Programs for functions on Curves,”1986,インターネット<http://crypto.stanford.edu/miller/miller.pdf>」などが存在する。また、ペアリング演算を効率的に行うための楕円曲線や巡回群の構成方法はよく知られている(例えば、参考文献2、参考文献6「A. Miyaji, M. Nakabayashi, S.Takano, "New explicit conditions of elliptic curve Traces for FR-Reduction," IEICE Trans. Fundamentals, vol. E84-A, no05, pp. 1234-1243, May 2001」、参考文献7「P.S.L.M. Barreto, B. Lynn, M. Scott, "Constructing elliptic curves with prescribed embedding degrees," Proc. SCN '2002, LNCS 2576, pp.257-267, Springer-Verlag. 2003」、参考文献8「R. Dupont, A. Enge, F. Morain, "Building curves with arbitrary small MOV degree over finite prime fields," http://eprint.iacr.org/2002/094/」等参照)。
ai(ψ)(i=1,...,n(ψ)+ζ(ψ)):ai(ψ)は巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。基底ベクトルai(ψ)の一例は、κ1・g1∈G1をi次元目の要素とし、残りのn(ψ)+ζ(ψ)-1個の要素を巡回群G1の単位元(加法的に「0」と表現)とするn(ψ)+ζ(ψ)次元の基底ベクトルである。この場合、n(ψ)+ζ(ψ)次元の基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1(ψ)=(κ1・g1,0,0,...,0)
a2(ψ)=(0,κ1・g1,0,...,0) …(8)
...
an(ψ)+ζ(ψ)(ψ)=(0,0,0,...,κ1・g1)
ここで、κ1は加法単位元0F以外の有限体Fqの元からなる定数であり、κ1∈Fqの具体例はκ1=1Fである。基底ベクトルai(ψ)は直交基底であり、巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルai(ψ)は前述のベクトル空間V(ψ)を張る。
ai*(ψ)(i=1,...,n(ψ)+ζ(ψ)):巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。基底ベクトルai*(ψ)の一例は、κ2・g2∈G2をi次元目の要素とし、残りのn(ψ)+ζ(ψ)-1個の要素を巡回群G2の単位元(加法的に「0」と表現)とするn(ψ)+ζ(ψ)次元の基底ベクトルである。この場合、基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1*(ψ)=(κ2・g2,0,0,...,0)
a2*(ψ)=(0,κ2・g2,0,...,0) …(9)
...
an(ψ)+ζ(ψ)*(ψ)=(0,0,0,...,κ2・g2)
ここで、κ2は加法単位元0F以外の有限体Fqの元からなる定数であり、κ2∈Fqの具体例はκ2=1Fである。基底ベクトルai*(ψ)は直交基底であり、巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルai*(ψ)は前述のベクトル空間V*(ψ)を張る。
なお、基底ベクトルai(ψ)と基底ベクトルai*(ψ)とは、0Fを除く有限体Fqの元τ=κ1・κ2について
eψ(ai(ψ), aj*(ψ))=gTτ・δ(i,j) …(10)
を満たす。すなわち、i=jの場合には、式(5)(6)の関係から、
eψ(ai(ψ), aj*(ψ))= Pair(κ1・g12・g2)・Pair(0, 0)・...・Pair(0, 0)
= Pair(g1, g2)κ1・κ2・Pair(g1, g2)0・0・...・Pair(g1, g2)0・0
= Pair(g1, g2)κ1・κ2=gTτ
を満たす。なお、上付き添え字κ1,κ2はそれぞれκ1,κ2を表す。一方、i≠jの場合には、eψ(ai(ψ), aj*(ψ))=Πi=1n(ψ)+ζ(ψ) Pair(ai(ψ), aj*(ψ))の右辺は、Pair(κ1・g12・g2)を含まず、Pair(κ1・g1,0)と Pair(0,κ2・g2)とPair(0,0)との積になる。さらに、式(6)の関係からPair(g1, 0)=Pair(0, g2)=Pair(g1, g2)0を満たす。そのため、i≠jの場合には、
eψ(ai(ψ), aj*(ψ))=eψ(g1, g2)0=gT0
を満たす。
特に、τ=κ1・κ2=1Fである場合(例えば、κ12=1Fの場合)、
e(ai(ψ), aj*(ψ))=gTδ(i,j) …(11)
を満たす。ここで、gT0=1は巡回群GTの単位元であり、gT1=gTは巡回群GTの生成元である。この場合、基底ベクトルai(ψ)と基底ベクトルai*(ψ)とは双対正規直交基底であり、ベクトル空間V(ψ)とベクトル空間V*(ψ)とは、双線形写像を構成可能な双対ベクトル空間〔双対ペアリングベクトル空間(DPVS:Dual Paring Vector space)〕である。
A(ψ):基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。例えば、基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))が式(8)によって表現される場合、行列A(ψ)は、
【数8】


となる。
A*(ψ):基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。例えば、基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))が式(9)によって表現される場合、行列A*(ψ)は、
【数9】


となる。
X(ψ):X(ψ)は有限体Fqの元を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。行列X(ψ)は基底ベクトルai(ψ)の座標変換に用いられる。行列X(ψ)のi行j列(i=1,...,n(ψ)+ζ(ψ),j=1,...,n(ψ)+ζ(ψ))の要素をχi,j(ψ)∈Fqとすると、行列X(ψ)は、
【数10】


となる。なお、行列X(ψ)の各要素χi,j(ψ)を変換係数と呼ぶ。
X *(ψ):X *(ψ)と行列X(ψ)とはX*(ψ)=τ'・(X(ψ)-1)Tの関係を満たす。ただし、τ'∈Fqは有限体Fqに属する任意の定数であり、例えば、τ'=1Fである。X*(ψ)は基底ベクトルai*(ψ)の座標変換に用いられる。行列X*(ψ)のi行j列の要素をχi,j*(ψ)∈Fqとすると、行列X*(ψ)は、
【数11】


となる。なお、行列X*(ψ)の各要素χi,j*(ψ)を変換係数と呼ぶ。
この場合、n(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の単位行列をI(ψ)とするとX(ψ)・(X*(ψ))T=τ'・I(ψ)を満たす。すなわち、単位行列
【数12】


に対し、
【数13】


を満たす。ここで、n(ψ)+ζ(ψ)次元ベクトル
χi(ψ)=(χi,1(ψ),...,χi,n(ψ)+ζ(ψ)(ψ)) …(18)
χj→*(ψ)=(χj,1*(ψ),...,χj,n(ψ)+ζ(ψ)*(ψ)) …(19)
を定義する。すると、式(17)の関係から、n(ψ)+ζ(ψ)次元ベクトルχi(ψ)とχj→*(ψ)との内積は、
χi(ψ)・χj→*(ψ)=τ'・δ(i,j) …(20)
となる。
bi(ψ):bi(ψ)は巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。bi(ψ)は行列X(ψ)を用いて基底ベクトルai(ψ) (i=1,...,n(ψ)+ζ(ψ))を座標変換することで得られる。具体的には、基底ベクトルbi(ψ)は、
bi(ψ)=Σj=1n(ψ)+ζ(ψ)χi,j(ψ)・aj(ψ) …(21)
の演算によって得られる。例えば、基底ベクトルaj(ψ)(j=1,...,n(ψ)+ζ(ψ))が式(8)によって表現される場合、基底ベクトルbi(ψ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
bi(ψ)=(χi,1(ψ)・κ1・g1i,2(ψ)・κ1・g1,
...,χi,n(ψ)+ζ(ψ)(ψ)・κ1・g1) …(22)
巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルbi(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルbi(ψ)は前述のベクトル空間V(ψ)を張る。
bi*(ψ):bi*(ψ)は巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。bi*(ψ)は行列X*(ψ)を用いて基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))を座標変換することで得られる。具体的には、基底ベクトルbi*(ψ)は、
bi*(ψ)=Σj=1n(ψ)+ζ(ψ)χi,j*(ψ)・aj*(ψ) …(23)
の演算によって得られる。例えば、基底ベクトルaj*(ψ) (j=1,...,n(ψ)+ζ(ψ))が式(9)によって表現される場合、基底ベクトルbi*(ψ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
bi*(ψ)=(χi,1*(ψ)・κ2・g2i,2*(ψ)・κ2・g2,
...,χi,n(ψ)+ζ(ψ)*(ψ)・κ2・g2) …(24)
となる。巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルbi*(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルbi*(ψ)は前述のベクトル空間V*(ψ)を張る。
なお、基底ベクトルbi(ψ)と基底ベクトルbi*(ψ)とは、0Fを除く有限体Fqの元τ=κ1・κ2について
eψ(bi(ψ), bj*(ψ))=gTτ・τ'・δ(i,j) …(25)
を満たす。すなわち、式(5)(20)(22)(24)の関係から、
【数14】


を満たす。特にτ=κ1・κ2=1F(例えば、κ12=1F)及びτ'=1Fである場合、
eψ(bi(ψ), bj*(ψ))=gTδ(i,j) …(26)
を満たす。この場合、基底ベクトルbi(ψ)と基底ベクトルbi*(ψ)とは、双対ペアリングベクトル空間(ベクトル空間V(ψ)とベクトル空間V*(ψ))の双対正規直交基底である。
なお、式(25)の関係を満たすのであれば、式(8)(9)で例示したもの以外の基底ベクトルai(ψ)及びai*(ψ)や、式(21)(23)で例示したもの以外の基底ベクトルbi(ψ)及びbi*(ψ)を用いてもよい。
B(ψ):B(ψ)は基底ベクトルbi(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列である。B(ψ)=X(ψ)・A(ψ)を満たす。例えば、基底ベクトルbi(ψ)が式(22)によって表現される場合、行列B(ψ)は、
【数15】


となる。
B*(ψ):B*(ψ)は基底ベクトルbi*(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。B*(ψ)=X*(ψ)・A*(ψ)を満たす。例えば、基底ベクトルbi*(ψ) (i=1,...,n(ψ)+ζ(ψ))が式(24)によって表現される場合、行列B*(ψ)は、
【数16】


となる。
v(λ):v(λ)は有限体Fqの元を要素とするn(λ)次元ベクトルを表す。
v(λ)=(v1(λ),...,vn(λ)(λ))∈Fqn(λ) …(29)
vμ(λ):vμ(λ)はn(λ)次元ベクトルv(λ)のμ(μ=1,...,n(λ))番目の要素を表す。
w(λ):w(λ)は有限体Fqの元を要素とするn(λ)次元ベクトルを表す。
w(λ)=(w1(λ),...,wn(λ)(λ))∈Fqn(λ) …(30)
wμ(λ):wμ(λ)はn(λ)次元ベクトルw(λ)のμ(μ=1,...,n(λ))番目の要素を表す。
Enc:Encは共通鍵暗号方式の暗号化処理を示す共通鍵暗号関数を表す。
EncK(M):EncK(M)は、共通鍵Kを用い、共通鍵暗号関数Encに従って平文Mを暗号化して得られた暗号文を表す。
Dec:Decは、共通鍵暗号方式の復号処理を示す共通鍵復号関数を表す。
DecK(C):DecK(C)は、共通鍵Kを用い、共通鍵復号関数Decに従って暗号文Cを復号して得られた復号結果を表す。
【0060】
〔関数暗号方式〕
次に、関数暗号方式の基本的な構成について説明する。
関数暗号方式とは、第1情報と第2情報との組み合わせによって定まる論理式の真理値が「真」となる場合に暗号文が復号される方式である。「第1情報」と「第2情報」の一方が暗号文に埋め込まれ、他方が鍵情報に埋め込まれる。例えば、「"Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products," with Amit Sahai and Brent Waters One of 4 papers from Eurocrypt 2008 invited to the Journal of Cryptology」(参考文献9)に開示された述語暗号方式は関数暗号方式の一種である。
これ以外にも様々な公知の関数暗号方式が存在するが、以下では未公開の新たな関数暗号方式を説明する。以下に説明する新たな関数暗号方式では秘密情報に応じた値が所定の論理式に応じた態様で階層的に秘密分散される。所定の論理式は、第1情報と第2情報との組み合わせによって真理値が定まる命題変数を含み、必要に応じてさらに論理記号∧,∨,¬の何れか又はすべてを含む。そして、各命題変数の真理値が特定されることで定まる当該所定の論理式の真理値が「真」となる場合に秘密情報に応じた値が復元され、それに基づいて暗号文が復号される。
【0061】
<論理式と階層的な秘密分散との関係>
上述した所定の論理式と階層的な秘密分散との関係を説明する。
秘密分散とは、しきい値Kt(Kt≧1)個以上のシェア情報が得られた場合にのみ秘密情報が復元されるように、秘密情報をN(N≧2)個のシェア情報に分散することである。Kt=Nを満たす秘密分散の方式(SSS: Secret Sharing Scheme)をN-out-of-N分散方式(或いは「N-out-of-Nしきい値分散方式」)といい、Kt<Nを満たす秘密分散の方式をKt-out-of-N分散方式(或いは「Kt-out-of-Nしきい値分散方式」)という(例えば、参考文献10「黒沢馨、尾形わかは、“現代暗号の基礎数理 (電子情報通信レクチャーシリーズ)”、コロナ社 、2004年3月、p.116-119」、参考文献11「A. Shamir, "How to Share a Secret", Communications of the ACM, November 1979, Volume 22, Number 11, pp.612-613.」等参照)。
N-out-of-N分散方式は、すべてのシェア情報share(1),...,share(N)が与えられれば秘密情報SEを復元できるが、任意のN-1個のシェア情報share(φ1),...,share(φN-1)が与えられても秘密情報SEの情報はまったく得られない方式である。以下に、その一例を示す。
・SH1,...,SHN-1をランダムに選択する。
・SHN=SE-(SH1+...+SHN-1)の計算を行う。
・SH1,...,SHNを各シェア情報share(1),...,share(N)とする。
・すべてのシェア情報share(1),...,share(N)が与えられれば、
SE=share(1)+...+share(N) …(31)
の復元処理によって秘密情報SEの復元が可能である。
Kt-out-of-N分散方式は、任意の相違なるKt個のシェア情報share(φ1),...,share(φKt)が与えられれば秘密情報SEを復元できるが、任意のKt-1個のシェア情報share(φ1),...,share(φKt-1)が与えられても秘密情報SEの情報はまったく得られない方式である。なお、添え字のKtはKtを表す。以下にKt-out-of-N分散方式の一例を示す。
・f(0)=SEを満たすKt-1次の多項式f(x)=ξ01・x+ξ2・x2+...+ξKt-1・xKt-1をランダムに選ぶ。すなわち、ξ0=SEとし、ξ1,..., ξKt-1をランダムに選ぶ。シェア情報をshare(ρ)=(ρ, f(ρ))(ρ=1,...,N)とする。なお、(ρ, f(ρ))はρ及びf(ρ)の値をそれぞれ抽出可能な情報であり、例えばρとf(ρ)とのビット結合値である。
・任意の相違なるKt個のシェア情報share(φ1),...,share(φKt)((φ1,...,φKt)⊂(1,...,N))が得られた場合、例えば、ラグランジェ(Lagrange)の補間公式を用い、以下のような復元処理によって秘密情報SEの復元が可能である。
SE=f(0)=LA1・f(φ1)+...+ LAKt・f(φKt) …(32)
【数17】

は先頭からρ番目の被演算子〔分母の要素(φρ-φρ)、分子の要素(x-φρ)〕が存在しないことを意味する。すなわち、式(33)の分母は、
ρ1)・...・(φρρ-1)・(φρρ+1)・...・(φρKt)
であり、式(33)の分子は、
(x-φ1)・...・(x-φρ-1)・(x-φρ+1)・...・(x-φKt)
である。
上述した各秘密分散は体上でも実行可能である。また、これらを拡張して秘密情報SEに応じた値をシェア情報shareに秘密分散することもできる。秘密情報SEに応じた値とは秘密情報SEそのものや秘密情報SEの関数値であり、シェア情報shareに応じた値とはシェア情報shareそのものやシェア情報の関数値である。例えば、有限体Fqの元である秘密情報SE∈Fqに応じた巡回群GTの元gTSE∈GTを秘密情報SEの各シェア情報share(1),share(2)に応じた巡回群GTの元gTshare(1),gTshare(2)∈GTに秘密分散することもできる。また、上述した秘密情報SEはシェア情報shareの線形結合となる(式(31)(32))。このように秘密情報SEがシェア情報shareの線形結合となる秘密分散方式を線形秘密分散方式と呼ぶ。
上述した所定の論理式は、秘密情報を階層的に秘密分散して得られる木構造データによって表現できる。すなわち、ド・モルガンの法則により、上述した所定の論理式はリテラルからなる論理式、又は、論理記号∧,∨の少なくとも一部とリテラルとからなる論理式(これらを「標準形論理式」と呼ぶことにする)によって表現でき、この標準形論理式は秘密情報を階層的に秘密分散して得られる木構造データによって表現できる。
標準形論理式を表現する木構造データは複数のノードを含み、少なくとも一部のノードは1個以上の子ノードの親ノードとされ、親ノードの1つはルートノードとされ、子ノードの少なくとも一部は葉ノードとされる。ルートノードの親ノードや、葉ノードの子ノードは存在しない。ルートノードには秘密情報に応じた値が対応し、各親ノードの子ノードには当該親ノードに対応する値を秘密分散したシェア情報に応じた値が対応する。各ノードでの秘密分散形態(秘密分散方式やしきい値)は標準形論理式に応じて定まる。また、各葉ノードには標準形論理式を構成する各リテラルが対応し、当該各リテラルの真理値は第1情報と第2情報との組み合わせによって定まる。
ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られないものとする。また、上述した秘密分散の性質により、親ノードに対応するシェア情報に応じた値(その親ノードがルートノードであれば秘密情報に応じた値)は、その子ノードに対応するシェア情報に応じた値が当該親ノードに対応するしきい値以上の個数だけ得られた場合にのみ復元される。そのため、どの葉ノードに対応するリテラルの真理値が真になったのかと木構造データの構成(各ノードでの秘密分散の形態を含む)とに応じ、最終的にルートノードに対応する秘密情報に応じた値が復元できるか否かが定まる。そして、各葉ノードに対応する各リテラルの真理値が標準形論理式の真理値を真にする場合にのみ最終的にルートノードに対応する秘密情報に応じた値が復元できるように木構造データが構成されている場合、このような木構造データは標準形論理式を表現する。このような標準形論理式を表現する木構造データは容易に設定できる。以下に具体例を示す。
図6は、命題変数PRO(1),PRO(2)と命題変数PRO(3)の否定¬PRO(3)と論理記号∧,∨とを含む標準形論理式PRO(1)∧PRO(2)∨¬PRO(3)を表現する木構造データを例示する図である。図6に例示する木構造データは複数のノードN1,...,N5を含む。ノードN1はノードN2,N5の親ノードとされ、ノードN2はノードN3,N4の親ノードとされ、親ノードの1つノードN1がルートノードとされ、子ノードの一部であるノードN3,N4,N5が葉ノードとされる。ノードN1には秘密情報SEに応じた値が対応し、ノードN1の子ノードN2,N5には、秘密情報SEに応じた値が1-out-of-2分散方式で秘密分散された各シェア情報SE,SEに応じた値がそれぞれ対応する。ノードN2の子ノードN3,N4には、シェア情報SEに応じた値が2-out-of-2分散方式で秘密分散された各シェア情報SE-SH1,SH1に応じた値がそれぞれ対応する。すなわち、葉ノードN3にはシェア情報share(1)=SE-SH1に応じた値が対応し、葉ノードN4にはシェア情報share(2)=SH1に応じた値が対応し、葉ノードN5にはシェア情報share(3)=SEに応じた値が対応する。また、葉ノードN3,N4,N5には標準形論理式PRO(1)∧PRO(2)∨¬PRO(3)を構成する各リテラルPRO(1),PRO(2),¬PRO(3)がそれぞれ対応し、当該各リテラルPRO(1),PRO(2),¬PRO(3)の真理値は第1情報と第2情報との組み合わせによって定まる。ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られない。この場合、第1情報と第2情報との組み合わせが標準形論理式PRO(1)∧PRO(2)∨¬PRO(3)の真理値を真にする場合にのみ秘密情報SEに応じた値が復元される。
図7は、命題変数PRO(1),PRO(2),PRO(3),PRO(6),PRO(7)と命題変数PRO(4),PRO(5)の否定¬PRO(4),¬PRO(5)と論理記号∧,∨とを含む標準形論理式PRO(1)∧PRO(2)∨PRO(2)∧PRO(3)∨PRO(1)∧PRO(3)∨¬PRO(4)∨(¬PRO(5)∧PRO(6))∧PRO(7)を表現する木構造データを例示する図である。
図7に例示する木構造データは複数のノードN1,...,N11を含む。ノードN1はノードN2,N6,N7の親ノードとされ、ノードN2はノードN3,N4,N5の親ノードとされ、ノードN7はノードN8,N11の親ノードとされ、ノードN8はノードN9,N10の親ノードとされ、親ノードの1つであるノードN1がルートノードとされ、ノードN3,N4,N5,N6,N9,N10,N11が葉ノードとされる。ノードN1には秘密情報SEに応じた値が対応し、ノードN1の子ノードN2,N6,N7には、秘密情報SEに応じた値が1-out-of-3分散方式で秘密分散された各シェア情報SE,SE,SEに応じた値がそれぞれ対応する。ノードN2の子ノードN3,N4,N5には、シェア情報SEに応じた値が2-out-of-3分散方式で秘密分散された各シェア情報(1,f(1)),(2,f(2)),(3,f(3))に応じた値がそれぞれ対応する。ノードN7の子ノードN8,N11には、シェア情報SEに応じた値が2-out-of-2分散方式で秘密分散された各シェア情報SH4,SE-SH4に応じた値がそれぞれ対応する。ノードN8の子ノードN9,N10には、シェア情報SH4に応じた値が1-out-of-2分散方式で秘密分散された各シェア情報SH4,SH4に応じた値がそれぞれ対応する。すなわち、葉ノードN3にはシェア情報share(1)=(1,f(1))に応じた値が対応し、葉ノードN4にはシェア情報share(2)=(2,f(2))に応じた値が対応し、葉ノードN5にはシェア情報share(3)=(3,f(3))に応じた値が対応し、葉ノードN6にはシェア情報share(4)=SEに応じた値が対応し、葉ノードN9にはシェア情報share(5)=SH4に応じた値が対応し、葉ノードN10にはシェア情報share(6)=SH4に応じた値が対応し、葉ノードN11にはシェア情報share(7)=SE-SH4に応じた値が対応する。また、葉ノードであるノードN3,N4,N5,N6,N9,N10,N11には標準形論理式PRO(1)∧PRO(2)∨PRO(2)∧PRO(3)∨PRO(1)∧PRO(3)∨¬PRO(4)∨(¬PRO(5)∧PRO(6))∧PRO(7)を構成する各リテラルPRO(1),PRO(2),PRO(2),PRO(3),PRO(1),PRO(3),¬PRO(4),¬PRO(5),PRO(6),PRO(7)がそれぞれ対応し、各リテラルPRO(1),PRO(2),PRO(2),PRO(3),PRO(1),PRO(3),¬PRO(4),¬PRO(5),PRO(6),PRO(7)の真理値は第1情報と第2情報との組み合わせによって定まる。ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られない。この場合、第1情報と第2情報との組み合わせが標準形論理式PRO(1)∧PRO(2)∨PRO(2)∧PRO(3)∨PRO(1)∧PRO(3)∨¬PRO(4)∨(¬PRO(5)∧PRO(6))∧PRO(7)の真理値を真にする場合にのみ秘密情報SEに応じた値が復元される。
【0062】
<アクセス構造>
上述のように秘密情報を階層的に秘密分散して得られる木構造データによって所定の論理式を表現した場合、第1情報と第2情報との組み合わせに対して得られる葉ノードでのシェア情報に応じた値から秘密情報に応じた値を復元できるか否かによって、第1情報と第2情報との組み合わせによって定まる論理式の真理値が「真」となるか「偽」となるかを判定できる。以下、第1情報と第2情報との組み合わせによって定まる論理式の真理値が「真」となる場合に第1情報と第2情報との組み合わせを受け入れ、「偽」となる場合に第1情報と第2情報との組み合わせを拒絶する仕組みをアクセス構造と呼ぶ。
上述のように所定の論理式を表現した木構造データの葉ノードの総数をΨとし、各葉ノードに対応する識別子をλ=1,...,Ψとする。各葉ノードに対応するn(λ)次元ベクトルv(λ)の集合{v(λ)}λ=1,...,Ψを第1情報とし、n(λ)次元ベクトルw(λ)の集合{w(λ)}λ=1,...,Ψを第2情報とする。また、上述した木構造データをラベル付き行列LMT(MT,LAB)として実装する。
ラベル付き行列LMT(MT,LAB)は、Ψ行COL列(COL≧1)の行列
【数18】


と、行列MTの各行λ=1,...,Ψに対応付けられたラベルLAB(λ)とを含む。
行列MTの各要素mtλ,col(col=1,...,COL)は次の2つの要件を満たす。第1に、上述のように所定の論理式を表現した木構造データのルートノードに秘密情報SE∈Fqに応じた値が対応する場合、予め定められた有限体Fqの元を要素とするCOL次元ベクトル
GV=(gv1,...,gvCOL)∈FqCOL …(35)
と、秘密情報SEに応じた有限体Fqの元を要素とするCOL次元ベクトル
CV=(cv1,...,cvCOL)∈FqCOL …(36)
とに対して
SE=GV・(CV)T …(37)
が成立する。COL次元ベクトルGVの具体例は、
GV=(1F,...,1F)∈FqCOL …(38)
であるが、GV=(1F,0F,...,0F)∈FqCOLなどのその他のCOL次元ベクトルであってもよい。第2に、識別子λに対応する葉ノードにシェア情報share(λ)∈Fqに応じた値が対応する場合、
(share(1),...,share(Ψ))T=MT・(CV)T …(39)
が成立する。上述のように所定の論理式を表現した木構造データが定まれば、これら2つの要件を満たす行列MTを選択することは容易である。また、秘密情報SEやシェア情報share(λ)が変数であったとしても、これら2つの要件を満たす行列MTを選択することは容易である。すなわち、行列MTを定めた後で秘密情報SEやシェア情報share(λ)の値が定められてもよい。
また、行列MTの各行λ=1,...,Ψに対応付けられたラベルLAB(λ)は、識別子λに対応する葉ノードに対応するリテラル(PRO(λ)又は¬PRO(λ))に対応する。ここで、命題変数PRO(λ)の真理値が「真」であることと第1情報VSET1={λ,v(λ)|λ=1,...,Ψ}が含むv(λ)と第2情報VSET2={λ,w(λ)|λ=1,...,Ψ}が含むw(λ)との内積v(λ)・w(λ)が0となることとが等価であると扱い、命題変数PRO(λ)の真理値が「偽」であることと内積v(λ)・w(λ)が0とならないこととが等価であると扱う。そして、PRO(λ)に対応するラベルLAB(λ)がv(λ)を表し、¬PRO(λ)に対応するラベルLAB(λ)が¬v(λ)を表すものとする。なお、¬v(λ)はv(λ)の否定を表す論理式であり、¬v(λ)からv(λ)の特定が可能である。また、LAB(λ)がv(λ)を表すことを「LAB(λ)=v(λ)」と表記し、LAB(λ)が¬v(λ)を表すことを「LAB(λ)=¬v(λ)」と表記する。また、LAB(λ)(λ=1,...,Ψ)の集合{LAB(λ)}λ=1,...,ΨをLABと表記する。
さらに、Ψ次元ベクトル
TFV=(tfv(1),...,tfv(Ψ)) …(40)
を定義する。要素tfv(λ)は、内積v(λ)・w(λ)が0のときにtfv(λ)=1となり、0以外のときにtfv(λ)=0となる。
tfv(λ)=1 (PRO(λ)が真) if v(λ)・w(λ)=0 …(41)
tfv(λ)=0 (PRO(λ)が偽) if v(λ)・w(λ)≠0 …(42)
さらに、論理式
{(LAB(λ)=v(λ))∧(tfv(λ)=1)}∨{(LAB(λ)=¬v(λ))∧(tfv(λ)=0)} …(43)
の真理値が「真」になるときLIT(λ)=1と表記し「偽」になるときLIT(λ)=0と表記する。すなわち、識別子λに対応する葉ノードに対応するリテラルの真理値が「真」になるときLIT(λ)=1と表記し「偽」になるときLIT(λ)=0と表記する。すると、行列MTが含む行ベクトルのうちLIT(λ)=1となる行ベクトルmtλ=(mtλ,1,...,mtλ,COL)のみからなる部分行列MTTFVは以下のように表記できる。
MTTFV=(MT)LIT(λ)=1 …(44)
上述した秘密分散方式が線形秘密分散方式である場合、識別子λに対応するシェア情報share(λ)に応じた値から秘密情報SEに応じた値が復元できることと、識別子λに対応する行ベクトルmtλで張られるベクトル空間にCOL次元ベクトルGVが属することとは等価である。すなわち、識別子λに対応する行ベクトルmtλで張られるベクトル空間にCOL次元ベクトルGVが属するか否かを判定することで、識別子λに対応するシェア情報share(λ)に応じた値から秘密情報SEに応じた値が復元できるか否かが判定できる。なお、行ベクトルmtλで張られるベクトル空間とは、行ベクトルmtλの線形結合で表すことができるベクトル空間を意味する。
ここで、上述の部分行列MTTFVの各行ベクトルmtλで張られるベクトル空間span<MTTFV>にCOL次元ベクトルGVが属する場合に第1情報と第2情報との組み合わせが受け入れられ、そうでない場合に第1情報と第2情報との組み合わせが拒絶されることにする。これにより、上述のアクセス構造が具体化される。なお、上述したようにラベル付き行列LMT(MT,LAB)が第1情報に対応する場合、アクセス構造が第1情報と第2情報との組み合わせを受け入れることを「アクセス構造が第2情報を受け入れる」といい、アクセス構造が第1情報と第2情報との組み合わせを受け入れないことを「アクセス構造が第2情報を拒絶する」という。
受け入れ if GV∈span<MTTFV>
拒絶 if ¬(GV∈span<MTTFV>)
また、GV∈span<MTTFV>の場合、
SE=Σμ∈SETconst(μ)・share(μ) …(45)
{const(μ)∈Fq|μ∈SET},SET⊆{1,...,λ|LIT(λ)=1}
を満たす係数const(μ)が存在し、このような係数const(μ)は行列MTのサイズの多項式時間で求めることができる。
【0063】
<アクセス構造を用いた関数暗号方式の基本構成>
以下では、アクセス構造を用いた関数暗号方式によって鍵カプセル化メカニズムKEM (Key Encapsulation Mechanisms)を構成する場合の基本構成を例示する。この構成はSetup(1sec,(Ψ;n(1),...,n(Ψ))),GenKey(PK,MSK,LMT(MT,LAB)),Enc(PK,M,{λ,v(λ)|λ=1,...,Ψ})(v1(λ)=1F),Dec(PK,SKS,C)を含む。また、第2情報VSET2={λ,w(λ)|λ=1,...,Ψ}の1番目の要素w1(λ)が1Fとされる。
[Setup(1sec,(Ψ;n(1),...,n(Ψ))):セットアップ]
−入力:1sec,(Ψ;n(1),...,n(Ψ))
−出力:マスター鍵情報MSK,公開パラメータPK
Setupでは各ψ=0,...,Ψについて以下の処理が実行される。
(Setup-1) 1secを入力としてセキュリティパラメータsecでの位数q、楕円曲線E、巡回群G1, G2, GT、双線形写像eψ(ψ=0,...,Ψ)が生成される(param=(q, E, G1, G2, GT, eψ))。
(Setup-2) τ'∈Fqが選択され、X*(ψ)=τ'・(X(ψ)-1)Tを満たす行列X(ψ),X*(ψ)が選択される。
(Setup-3) 基底ベクトルai(ψ) (i=1,...,n(ψ)+ζ(ψ))が式(21)に従って座標変換され、n(ψ)+ζ(ψ)次元の基底ベクトルbi(ψ) (i=1,...,n(ψ)+ζ(ψ))が生成される。基底ベクトルbi(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列B(ψ)が生成される。
(Setup-4) 基底ベクトルai*(ψ) (i=1,...,n(ψ)+ζ(ψ))が式(23)に従って座標変換され、n(ψ)+ζ(ψ)次元の基底ベクトルbi*(ψ)(i=1,...,n(ψ)+ζ(ψ))が生成される。基底ベクトルbi*(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列B*(ψ)が生成される。
(Setup-5) B*(ψ)^の集合{B*(ψ)^}ψ=0,...,Ψをマスター鍵情報MSK={B*(ψ)^}ψ=0,...,Ψとする。また、B(ψ)^の集合{B(ψ)^}ψ=0,...,Ψと1secとparamとを公開パラメータPKとする。ただし、B*(ψ)^は行列B*(ψ)又はその部分行列であり、B(ψ)^は行列B(ψ)又はその部分行列である。また、集合{B*(ψ)^}ψ=0,...,Ψは、少なくとも、b1*(0),b1*(λ) …,bn(λ)*(λ)(λ=1,...,Ψ)を含む。また、集合{B(ψ)^}ψ=0,...,Ψは、少なくとも、b1(0),b1(λ),…,bn(λ)(λ)(λ=1,...,Ψ)を含む。以下に一例を示す。
・n(0)+ζ(0)≧5, ζ(λ)=3・n(λ)
・B(0)^=(b1(0) b3(0) b5(0))T
・B(λ)^=(b1(λ) …bn(λ)(λ) b3・n(λ)+1(λ) … b4・n(λ)(λ))T(λ=1,...,Ψ)
・B*(0)^=(b1*(0) b3*(0) b4*(0))T
・B*(λ)^=(b1*(λ) … bn(λ)*(λ) b2・n(λ)+1*(λ) … b3・n(λ)*(λ))T(λ=1,...,Ψ)
[GenKey(PK,MSK,LMT(MT,LAB)):鍵情報生成]
−入力:公開パラメータPK,マスター鍵情報MSK,第1情報VSET1={λ,v(λ)|λ=1,...,Ψ}に対応するラベル付き行列LMT(MT,LAB)
−出力:鍵情報SKS
(GenKey-1) 式(35)-(39)を満たす秘密情報SEに対して以下の処理が実行される。
D*(0)=-SE・b1*(0)+Σι=2Icoefι(0)・bι*(0) …(46)
ただし、Iは2以上n(0)+ζ(0)以下の定数である。coefι(0)∈Fqは定数又は乱数である。「乱数」とは真性乱数や擬似乱数を意味する。以下にD*(0)の一例を示す。なお、式(47)のcoef4(0)は乱数である。
D*(0)=-SE・b1*(0)+b3*(0)+coef4(0)・b4*(0) …(47)
(GenKey-2) 式(35)-(39)を満たすshare(λ)(λ=1,...,Ψ)に対して以下の処理が実行される。
LAB(λ)=v(λ)となるλに対して
D*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)
ι=2n(λ)coef(λ)・vι(λ)・bι*(λ)
ι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ) …(48)
が生成され、
LAB(λ)=¬v(λ)となるλに対して
D*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)
ι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ) …(49)
が生成される。ただしcoef(λ),coefι(λ)∈Fqは定数又は乱数である。以下に一例を示す。
LAB(λ)=v(λ)となるλに対して
D*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)
ι=2n(λ)coef(λ)・vι(λ)・bι*(λ)
ι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ) …(50)
が生成され、
LAB(λ)=¬v(λ)となるλに対して
D*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)
ι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ) …(51)
が生成される。なお、式(50)(51)のcoef(λ)及びcoefι(λ)は乱数である。
(GenKey-3) 鍵情報
SKS=(LMT(MT,LAB),D*(0),D*(1),...,D(Ψ)) …(52)
生成される。
[Enc(PK,M,VSET2):暗号化]
−入力:公開パラメータPK,平文M,第2情報VSET2={λ,w(λ)|λ=1,...,Ψ}(w1(λ)=1F)
−出力:暗号文C
(Enc-1) 以下の処理によって共通鍵Kの暗号文C(ψ)(ψ=0,...,Ψ)が生成される。
C(0)=υ・b1(0)+Σι=2Iυι(0)・bι(0) …(53)
C(λ)=υ・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι(λ)・bι(λ) …(54)
ただし、υ,υι(ψ)∈Fq(ψ=0,...,Ψ)は定数又は乱数であり、
(coef2(0),...,coefI(0))・(υ2(0),...,υI(0))=υ' …(55)
coefι(λ)・υι(λ)=0F (ι=n(λ)+1,...,n(λ)+ζ(λ)) …(56)
を満たす。υ'の例はυ2(0),...,υI(0)の何れか1個である。例えば、υ,υ3(0),υ5(0),υ3・n(λ)+1(λ),...,υ4・n(λ)(λ)が乱数であり、ζ(λ)=3・n(λ)、I=5であり、
2(0),...,υI(0))=(0F3(0),0F5(0))
υ'=υ3(0)
n(λ)+1(λ),...,υ3・n(λ)(λ))=(0F,...,0F)
である。
(Enc-2) 共通鍵
K=gTτ・τ'・υ'∈GT …(57)
が生成される。例えば、τ=τ'=1Fの場合、
K=gTυ'∈GT …(58)
である。
(Enc-3) 共通鍵Kを用いて平文Mの暗号文
C(Ψ+1)=EncK(M) …(59)
が生成される。なお、共通鍵暗号方式Encは、例えば共通鍵Kを用いて暗号化可能に構成されたカメリア(Camellia)(登録商標)やAESや共通鍵と平文との排他的論理和などでよいが、その他の簡単な例として以下のようにEncK(M)を生成してもよい。ただし、式(60)の例ではM∈GTとされる。
C(Ψ+1)=gTυ'・M …(60)
(Enc-4) 暗号文
C=(VSET2,C(0),{C(λ)}(λ,w(λ)→)∈VSET2,C(Ψ+1)) …(61)
が生成される。ただし、下付き添え字の「w(λ)→」は「w(λ)」を表す。
[Dec(PK,SKS,C):復号]
−入力:公開パラメータPK,鍵情報SKS,暗号文C
−出力:平文M'
(Dec-1) λ=1,...,Ψについて、鍵情報SKSが含むラベル付き行列LMT(MT,LAB)の各ラベルLAB(λ)であるn(λ)次元ベクトルv(λ)と暗号文CのVSET2が含むn(λ)次元ベクトルw(λ)との内積v(λ)・w(λ)が0となるか否かが判定され、これとLMT(MT,LAB)の各ラベルLAB(λ)とによってGV∈span<MTTFV>であるか否かが判定される(式(40)-(45))。GV∈span<MTTFV>でなければ暗号文Cが拒絶され、GV∈span<MTTFV>であれば暗号文Cが受け入れられる。
(Dec-2) 暗号文Cが受け入れられると、SET⊆{1,...,λ|LIT(λ)=1}と式(45)を満たす係数const(μ)(μ∈SET)とが計算される。
(Dec-3) 共通鍵
【数19】


が生成される。ここで、式(6)(25)(55)から、
【数20】


を満たす。また、式(6)(25)(41)(48)(54)(56)及びw1(λ)=1Fから
【数21】


を満たす。また、式(6)(25)(42)(49)(54)(56)から
【数22】


を満たす。よって、式(45)(63)-(65)から
【数23】

を満たす。例えば、τ=τ'=1Fの場合、
K=gTυ'∈GT …(67)
を満たす。
(Dec-4) 共通鍵Kを用いて平文
M'=DecK(C(Ψ+1))=DecK(C(Ψ+1)) …(68)
が生成される。例えば、式(60)に例示した共通鍵暗号方式の場合、
M'=C(Ψ+1)/K …(69)
によって平文M'が生成される。
なお、gTをGTの生成元とする代わりにgTτやgTτ'やgTτ・τ'をGTの生成元と扱ってもよい。また、鍵情報SKSのλと暗号文のλとを対応関係を特定する写像を用いてC(λ)とD*(λ)との組み合わせを特定し、[Dec(PK,SKS,C):復号]の処理が実行されてもよい。また、第2情報VSET2={λ,w(λ)|λ=1,...,Ψ}の1番目の要素w1(λ)が1Fとされるだけではなく、第1情報VSET1={λ,v(λ)|λ=1,...,Ψ}のn(λ)番目の要素vn(λ)(λ)が1Fとされてもよい。また、要素w1(λ)が1Fでない場合にはw(λ)の代わりにw(λ)/w1(λ)を用いてもよく、要素vn(λ)(λ)が1Fでない場合にはv(λ)の代わりにv(λ)/vn(λ)(λ)を用いてもよい。また、第1情報VSET1={λ,v(λ)|λ=1,...,Ψ}の代わりに第2情報VSET2={λ,w(λ)|λ=1,...,Ψ}が用いられ、第2情報VSET2={λ,w(λ)|λ=1,...,Ψ}の代わりに第1情報VSET1={λ,v(λ)|λ=1,...,Ψ}が用いられてもよい。この場合には第1情報VSET1={λ,v(λ)|λ=1,...,Ψ}の1番目の要素v1(λ)が1Fとされる。
【0064】
次に、関数暗号の一形態である述語暗号の一例として内積を用いた述語暗号について説明する。なお、数式の番号は本節で改めて付け直している。また、説明の都合、上述の説明で用いた文言や記号と同じ文言や記号であっても意味が異なる場合があるので注意されたい。述語暗号は1-out-of-1分散方式を用いた関数暗号に相当する。
【0065】
〔定義〕
次に、以下の各実施形態で使用される用語や記号を定義する。
行列:「行列」とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも「行列」と表現する。
(・)T:(・)Tは・の転置行列を表す。
(・)-1:(・)-1は・の逆行列を表す。
∧:∧は論理積を表す。
∨:∨は論理和を表す。
Z:Zは整数集合を表す。
sec:secはセキュリティパラメータ(sec∈Z, sec>0)を表す。
Fq:Fqは位数qの有限体を表す。位数qは1以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fqの例は素体やそれを基礎体とした拡大体である。
0F:0Fは有限体Fqの加法単位元(零元)を表す。一般化した加法単位元を0と表す。
1F:1Fは有限体Fqの乗法単位元を表す。一般化した乗法単位元を1と表す。
δ(i,j):δ(i,j)はクロネッカーのデルタ関数を表す。i=jの場合にδ(i,j)=1Fを満たし、i≠jの場合にδ(i,j)=0Fを満たす。
E:Eは有限体Fq上で定義された楕円曲線を表す。
G1, G2,GT:G1, G2, GTは位数qの巡回群を表す。巡回群G1, G2の具体例は、楕円曲線Eのp等分点からなる有限集合E[p]やその部分群である。G1=G2であってもよいしG1≠G2であってもよい。また、巡回群GTの具体例は、有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における1のp乗根からなる有限集合である。
なお、本形態では、巡回群G1, G2上で定義された演算を加法的に表現し、巡回群GT上で定義された演算を乗法的に表現する。すなわち、χ∈Fq及びΩ∈G1に対するχ・Ω∈G1は、Ω∈G1に対して巡回群G1で定義された演算をχ回施すことを意味し、Ω1, Ω2∈G1に対するΩ12∈G1は、Ω1∈G1とΩ2∈G1とを被演算子として巡回群G1で定義された演算を行うことを意味する。同様に、χ∈Fq及びΩ∈G2に対するχ・Ω∈G2は、Ω∈G2に対して巡回群G2で定義された演算をχ回施すことを意味し、Ω1, Ω2∈G2に対するΩ12∈G2は、Ω1∈G2とΩ2∈G2とを被演算子として巡回群G2で定義された演算を行うことを意味する。一方、χ∈Fq及びΩ∈GTに対するΩχ∈GTは、Ω∈GTに対して巡回群GTで定義された演算をχ回施すことを意味し、Ω12∈GTに対するΩ1・Ω2∈GTは、Ω1∈GTとΩ2∈GTとを被演算子として巡回群GTで定義された演算を行うことを意味する。
n:nは1以上の整数を表す。
ζ:ζは1以上の整数を表す。ζの一例は2又は3である。
G1n+ζ:G1n+ζはn+ζ個の巡回群G1の直積を表す。
G2n+ζ:G2n+ζはn+ζ個の巡回群G2の直積を表す。
g1, g2,gT:g1, g2, gTは巡回群G, G1, G2, GTの生成元を表す。
V:Vはn+ζ個の巡回群G1の直積からなるn+ζ次元のベクトル空間を表す。
V*:V*はn+ζ個の巡回群G2の直積からなるn+ζ次元のベクトル空間を表す。
e:eは直積G1n+ζと直積G2n+ζとの直積G1n+ζ×G2n+ζを巡回群GTに写す非退化な双線形写像(bilinear map)を表す。双線形写像eは、巡回群G1のn+ζ個の元γβ(β=1,...,n+ζ)と巡回群G2のn+ζ個の元γβ*(β=1,...,n+ζ)とを入力とし、巡回群GTの1個の元を出力する。
e:G1n+ζ×G2n+ζ→GT …(1)
双線形写像eは以下の性質を満たす。
[双線形性]すべてのΓ1∈G1n+ζ,Γ2∈G2n+ζ及びν,κ∈Fqについて以下の関係を満たす。
e(ν・Γ1,κ・Γ2)=e(Γ12)ν・κ …(2)
[非退化性]すべてのΓ1∈G1n+ζ,Γ2∈G2n+ζを巡回群GTの単位元に写すものではない。
[計算可能性]あらゆる
Γ1∈G1n+ζ,Γ2∈G2n+ζ …(3)
についてe(Γ12)を効率的に計算するアルゴリズムが存在する。
本形態では、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像を計算するための関数
Pair:G1×G2→GT …(4)
を用いて双線形写像eを構成する。本形態の双線形写像eは、巡回群G1のn+ζ個の元γβ (β=1,...,n+ζ)からなるn+ζ次元ベクトル(γ1,...,γn+ζ)と、巡回群G2のn+ζ個の元γβ*(β=1,...,n+ζ)からなるn+ζ次元ベクトル(γ1*,...,γn+ζ*)との入力に対し、巡回群GTの1個の元
e=Πβ=1n+ζPair(γβ, γβ*) …(5)
を出力する。
なお、双線形写像Pairは、巡回群G1の1個の元と巡回群G2の1個の元との組を入力とし、巡回群GTの1個の元を出力するものであり、以下の性質を満たす。
[双線形性]すべてのΩ1∈G1,Ω2∈G2及びν,κ∈Fqについて以下の関係を満たす。
Pair(ν・Ω1,κ・Ω2)=Pair(Ω12)ν・κ …(6)
[非退化性]すべての
Ω1∈G1,Ω2∈G2 …(7)
を巡回群GTの単位元に写すものではない。
[計算可能性]あらゆるΩ1∈G1,Ω2∈G2についてPair(Ω12)を効率的に計算するアルゴリズムが存在する。
なお、双線形写像Pairの具体例は、WeilペアリングやTateペアリングなどのペアリングである(例えば、参考文献1「Alfred. J. Menezes,ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS, KLUWER ACADEMIC PUBLISHERS, ISBN0-7923-9368-6,pp. 61-81」、参考文献2「RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems」等参照)。
ai(i=1,...,n+ζ):aiは巡回群G1のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ1・g1∈G1をi次元目の要素とし、残りのn個の要素を巡回群G1の単位元(加法的に「0」と表現)とするn+ζ次元の基底ベクトルである。この場合、n+ζ次元の基底ベクトルai(i=1,...,n+ζ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1=(κ1・g1,0,0,...,0)
a2=(0,κ1・g1,0,...,0) …(8)
...
an+ζ=(0,0,0,...,κ1・g1)
ここで、κ1は加法単位元0F以外の有限体Fqの元からなる定数であり、κ1∈Fqの具体例はκ1=1Fである。基底ベクトルaiは直交基底であり、巡回群G1のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルai(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルaiはベクトル空間Vを張る。
ai*(i=1,...,n+ζ):巡回群G2のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。基底ベクトルai*の一例は、κ2・g2∈G2をi次元目の要素とし、残りのn個の要素を巡回群G2の単位元(加法的に「0」と表現)とするn+ζ次元の基底ベクトルである。この場合、基底ベクトルai*(i=1,...,n+ζ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1*=(κ2・g2,0,0,...,0)
a2*=(0,κ2・g2,0,...,0) …(9)
...
an+ζ*=(0,0,0,...,κ2・g2)
ここで、κ2は加法単位元0F以外の有限体Fqの元からなる定数であり、κ2∈Fqの具体例はκ2=1Fである。基底ベクトルai*は直交基底であり、巡回群G2のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルai*(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルai*はベクトル空間V*を張る。
なお、基底ベクトルaiと基底ベクトルai*とは、0Fを除く有限体Fqの元τ=κ1・κ2について
e(ai, aj*)=gTτ・δ(i,j) …(10)
を満たす。すなわち、i=jの場合には、式(5)(6)の関係から、
e(ai, aj*)= Pair(κ1・g12・g2)・Pair(0, 0)・...・Pair(0, 0)
= Pair(g1, g2)κ1・κ2・Pair(g1, g2)0・0・...・Pair(g1, g2)0・0
= Pair(g1, g2)κ1・κ2=gTτ
を満たす。一方、i≠jの場合には、e(ai, aj*)=Πi=1n+ζ Pair(ai, aj*)の右辺は、Pair(κ1・g12・g2)を含まず、Pair(κ1・g1,0)と Pair(0,κ2・g2)とPair(0,0)との積になる。さらに、式(6)の関係からPair(g1, 0)=Pair(0, g2)=Pair(g1, g2)0を満たす。そのため、i≠jの場合には、
e(ai, aj*)=e(g1, g2)0=gT0
を満たす。
特に、τ=κ1・κ2=1Fである場合(例えば、κ12=1Fの場合)、
e(ai, aj*)=gTδ(i,j) …(11)
を満たす。ここで、gT0=1は巡回群GTの単位元であり、gT1=gTは巡回群GTの生成元である。この場合、基底ベクトルaiと基底ベクトルai*とは双対正規直交基底であり、ベクトル空間Vとベクトル空間V*とは、双線形写像を構成可能な双対ベクトル空間〔双対ペアリングベクトル空間(DPVS:Dual Paring Vector space)〕である。
A:基底ベクトルai(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。例えば、基底ベクトルai(i=1,...,n+ζ)が式(8)によって表現される場合、行列Aは、
【数24】


となる。
A*:基底ベクトルai*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。例えば、基底ベクトルai*(i=1,...,n+ζ)が式(9)によって表現される場合、行列A*は、
【数25】


となる。
X:有限体Fqの元を要素とするn+ζ行n+ζ列の行列を表す。基底ベクトルaiの座標変換に用いられる。行列Xのi行j列(i=1,...,n+ζ,j=1,...,n+ζ)の要素をχi,j∈Fqとすると、行列Xは、
【数26】


となる。なお、行列Xの各要素χi,jを変換係数と呼ぶ。
X *:X *は行列Xの逆行列の転置行列X*=(X-1)Tを表す。基底ベクトルai*の座標変換に用いられる。行列X*のi行j列の要素をχi,j*∈Fqとすると、行列X*は、
【数27】


となる。なお、行列X*の各要素χi,j*を変換係数と呼ぶ。
この場合、n+ζ行n+ζ列の単位行列をIとするとX・(X*)T=Iを満たす。すなわち、単位行列
【数28】


に対し、
【数29】


を満たす。ここで、n+ζ次元ベクトル
χi=(χi,1,...,χi,n+ζ) …(18)
χj→*=(χj,1*,...,χj,n+ζ*) …(19)
を定義する。すると、式(17)の関係から、n+ζ次元ベクトルχiとχj→*との内積は、
χi・χj→*=δ(i,j) …(20)
となる。
bi:biは巡回群G1のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。行列Xを用いて基底ベクトルai(i=1,...,n+ζ)を座標変換することで得られる。具体的には、基底ベクトルbiは、
bij=1n+ζχi,j・aj …(21)
の演算によって得られる。例えば、基底ベクトルaj(j=1,...,n+ζ)が式(8)によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。
bi=(χi,1・κ1・g1i,2・κ1・g1 ,...,χi,n+ζ・κ1・g1) …(22)
巡回群G1のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルbi(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルbiは前述のベクトル空間Vを張る。
bi*:bi*は巡回群G2のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。行列X*を用いて基底ベクトルai*(i=1,...,n+ζ)を座標変換することで得られる。具体的には、基底ベクトルbi*は、
bi*j=1n+ζχi,j*・aj* …(23)
の演算によって得られる。例えば、基底ベクトルaj*(j=1,...,n+ζ)が式(9)によって表現される場合、基底ベクトルbi*の各要素をそれぞれ列挙して表現すると、以下のようになる。
bi*=(χi,1*・κ2・g2i,2*・κ2・g2 ,...,χi,n+ζ*・κ2・g2) …(24)
となる。巡回群G2のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルbi*(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルbi*は前述のベクトル空間V*を張る。
なお、基底ベクトルbiと基底ベクトルbi*とは、0Fを除く有限体Fqの元τ=κ1・κ2について
e(bi, bj*)=gTτ・δ(i,j) …(25)
を満たす。すなわち、式(5)(20)(22)(24)の関係から、
【数30】

を満たす。特に、τ=κ1・κ2=1Fである場合(例えば、κ12=1Fの場合)、
e(bi, bj*)=gTδ(i,j) …(26)
を満たす。この場合、基底ベクトルbiと基底ベクトルbi*とは、双対ペアリングベクトル空間(ベクトル空間Vとベクトル空間V*)の双対正規直交基底である。
なお、式(25)の関係を満たすのであれば、式(8)(9)で例示したもの以外の基底ベクトルai及びai*や、式(21)(23)で例示したもの以外の基底ベクトルbi及びbi*を用いてもよい。
B:Bは基底ベクトルbi(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列。B=X・Aを満たす。例えば、基底ベクトルbiが式(22)によって表現される場合、行列Bは、
【数31】


となる。
B*:B*は基底ベクトルbi*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。B*=X*・A*を満たす。例えば、基底ベクトルbi*(i=1,...,n+ζ)が式(24)によって表現される場合、行列B*は、
【数32】


となる。
【0066】
〔内積述語暗号方式〕
次に、内積述語暗号方式について説明する。内積述語暗号方式とは、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる暗号方式である。内積述語暗号方式では、内積が0となることと論理式の真理値が真となることとが等価である。
【0067】
[内積と論理式の真理値との関係]
内積述語暗号では、論理和や論理積からなる論理式を多項式で表現する。
まず、「x1がη1である」という命題1と「x2がη2である」という命題2との論理和 (x11)∨(x22)を
(x11)・(x22) …(29)
という多項式で表現する。すると、各真理値と式(29)の関数値との関係は以下のようになる。
【表1】

[表1]から分かるように、論理和(x11)∨(x22)が真である場合、式(29)の関数値は0になり、論理和(x11)∨(x22)が偽である場合、式(29)の関数値は0以外の値となる。すなわち、論理和(x11)∨(x22)が真であることと、式(29)の関数値が0となることとは等価である。よって、論理和は式(29)で表現できる。
また、「x1がη1である」という命題1と「x2がη2である」という命題2との論理積 (x11)∧(x22)を
ι1・(x11)+ι2・(x22) …(30)
という多項式で表現する。ただし、ι1及びι2は乱数である。すると、真理値と式(30)の関数値とは以下の関係となる。
【表2】

[表2]から分かるように、論理積 (x11)∧(x22)が真である場合、式(30)の関数値は0になり、論理積 (x11)∧(x22)が偽である場合、式(30)の関数値は0以外の値となる。すなわち、論理積 (x11)∧(x22)が真であることと、式(30)の関数値が0となることとは等価である。よって、論理積は式(30)で表現できる。
以上から、論理和や論理積からなる任意の論理式を多項式で表現できることが分かる。例えば、論理式{(x11)∨(x22)}∧(x33)∧(x44)は、多項式
ι1・{(x11)・(x22)}+ι2・(x33)+ι3・(x44) …(31)
で表現できる。以下、このように論理式を表現する多項式のことを述語多項式と呼ぶ。
述語多項式は2つのベクトルの内積で表現できる。すなわち、述語多項式は、各項の不定元成分と1とを各要素とするベクトルと、各項の係数成分を各要素とするベクトルとの内積に等しい。例えば、式(31)の述語多項式は、各項の不定元成分と1を各要素とするベクトル(x1・x2, x1, x2, x3, x4, 1)と、各項の係数成分を各要素とするベクトル(ι1, -ι1・η2, -ι1・η1, ι2, -ι2・η33, ι1・η1・η23・η4)との内積に等しい。
そのため、述語多項式の値が0であるか否かと、述語多項式の各項の不定元成分と1とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。言い換えると、論理式の真理値が真であるか否かと、当該論理式を示す述語多項式の各項の不定元成分と1とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。
内積述語暗号方式では、上述の各項の不定元成分と1を各要素とするベクトル及び各項の係数成分を各要素とするベクトルの何れか一方のベクトルが暗号文に埋め込まれ、他方のベクトルが復号鍵に埋め込まれる。以下では、暗号文に埋め込まれるベクトルをw=(w1,...,wn)とし、復号鍵に埋め込まれるベクトルをv=(v1,...,vn)とする。
【0068】
[内積述語暗号方式の基本構成]
内積述語暗号方式で鍵カプセル化メカニズムKEM (Key Encapsulation Mechanisms)を構成する例を示す。この構成はSetup,GenKey,Enc,Decを含む。
《Setup:セットアップ》
−入力:セキュリティパラメータsec
−出力:マスター鍵情報MSK,公開パラメータPK
Setupの一例では、まず、セキュリティパラメータsecをnとして、n+ζ次元の基底ベクトルai(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列Aと、基底ベクトルai*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列A*と、座標変換のためのn+ζ行n+ζ列の行列X,X*とが選択される。次に、式(21)に従って座標変換されたn+ζ次元の基底ベクトルbi(i=1,...,n+ζ)が算出され、式(23)に従って座標変換されたn+ζ次元の基底ベクトルbi*(i=1,...,n+ζ)が算出される。そして、基底ベクトルbi*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列B*がマスター鍵情報MSKとして出力され、ベクトル空間V, V*、基底ベクトルbi(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列B、セキュリティパラメータsec、有限体Fq、楕円曲線E、巡回群G1, G2, GT、生成元g1, g2, gT、双線形写像eなどが公開パラメータPKとして出力される。
《GenKey:復号鍵生成》
−入力:マスター鍵情報MSK,ベクトルv
−出力:ベクトルvに対応する復号鍵D*
GenKeyの一例では、まず、有限体Fqから元σ,σι-n∈Fqが選択される。そして、マスター鍵情報MSKである行列B*を用い、ベクトルvに対応する復号鍵
D*=σ・(Σμ=1nvμ・bμ*)+Σι=n+1n+ζ'σι-n・bι*∈G2n+ζ' …(32)
が生成され、出力される。ただし、σ,σι-nは乱数などの変数や定数などであり、ζ'≦ζである(例えばζ=3, ζ'=2)。またΣι=n+1n+ζ'σι-nはシステムで共有される定数値とされる。以下では
Σι=n+1n+ζ'σι-n=1F …(33)
とされた例を説明する。これは本発明を限定しない。
《Enc:暗号化》
−入力:公開パラメータPK,ベクトルw,平文mes
−出力:暗号文(C1,C2)
Encの一例では、行列Bなどの公開パラメータPKと、有限体Fqの元である乱数υ01,...,υζと、ベクトルwとを用い、暗号文
C10・(Σμ=1nwμ・bμ)+Σμ=n+1n+ζυμ-n・bμ∈G1n+ζ …(34)
が生成される。ただし、
υ1=...=υζ' …(35)
を満たす(例えばζ'=2のときにはυ12)。また、gTτ・υ1を共通鍵Kとし、所定の共通鍵暗号方式(第2暗号方式)に則って平文mesの暗号文C2が生成される。暗号文C2の一例は、
C2=gTτ・υ1・mes …(36)
である。添え字のυ1はυ1を意味する。前述のように定数τの一例はτ=1Fである。生成された暗号文(C1,C2)は出力される。
《Dec:復号》
−入力:ベクトルvに対応する復号鍵D*,暗号文(C1,C2)
−出力:復号値mes'
Decの一例では、まず、暗号文C1と復号鍵D*とが式(1)の双線形写像eに入力され、その演算結果を共通鍵K=e(C1,D*)とし、以下のように復号値mes'が求められる。
mes'=C2/e(C1,D*)∈GT …(37)
ここで、式(2)(25)(33)(35)の性質から、
【数33】


を満たす。
内積w・v=0であれば、式(38)は、
【数34】


を満たす。式(36)(37)(39)から、内積w・v=0であればmes'=mesとなり、正しく復号されることがわかる。
【0069】
[階層的内積述語暗号方式の基本構成]
階層的内積述語暗号方式は内積述語暗号方式の一種であり、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる。さらに階層的内積述語暗号方式では階層的な処理によって復号鍵を生成できる。すなわち、階層的内積述語暗号方式では属性が階層化され、各階層までの属性に対応する鍵情報が存在するとともに、上位の階層に対応する鍵情報を用いて下位の階層に対応する鍵情報を生成できる。そして、このような階層的な処理によって生成された最終的な鍵情報が復号鍵となる。以下に階層的内積述語暗号方式の基本構成を例示する。以下では、階層的内積述語暗号方式を用いて鍵カプセル化メカニズムKEMを構成する場合の基本構成を例示する。ただし、これは本発明を限定するものではない。
《前提》
深さdの属性空間の階層フォーマットを以下の式によって定義する。ただし、dは1以上n以下の整数である。
ξ=(n,d;ξ1,...,ξd) (0=ξ01<...<ξd=n) …(40)
有限体Fqの元を要素とするξωω-1(ω=1,...,d)次元のベクトル(零ベクトルを除く)を階層ωに対応するベクトル
【数35】


とし、階層1から階層m(m≦d)までに対応するベクトルを(w1,...,wm)とする。有限体Fqの元を要素とするξωω-1次元(ω=1,...,d)のベクトル(零ベクトルを除く)を階層ωに対応するベクトル
【数36】


とし、階層1から階層mまでに対応するベクトルを(v1,...,vm)とする。
《Setup:セットアップ》
−入力:セキュリティパラメータsec
−出力:階層フォーマットξ,マスター秘密鍵MSK,公開パラメータmpk
Setupの一例では、セキュリティパラメータsecの単調増加関数値をnとし、階層フォーマットξ=(n,d;ξ1,...,ξd)が定められる。また、この例ではζ=3とし、n+3次元の基底ベクトルai(i=1,...,n+3)を要素とするn+3行n+3列の行列Aと、基底ベクトルai*(i=1,...,n+3)を要素とするn+3行n+3列の行列A*と、座標変換のためのn+3行n+3列の行列X,X*とが選択される。次に、式(21)に従って座標変換されたn+3次元の基底ベクトルbi(i=1,...,n+3)が算出され、式(23)に従って座標変換されたn+3次元の基底ベクトルbi*(i=1,...,n+3)が算出される。
この例では、基底ベクトル(b1*,...,bn*,bn+1*,bn+2*,bn+3*)と行列Xとがマスター秘密鍵MSKとして出力され、基底ベクトル(b1,...,bn,bn+1+bn+2,bn+3)、ベクトル空間V, V*、セキュリティパラメータsec、有限体Fq、楕円曲線E、巡回群G1, G2,GT、生成元g1, g2, gT、双線形写像eなどが公開パラメータmpkとして出力される。
《GenKey:鍵情報生成》
−入力:マスター秘密鍵MSK,公開パラメータmpk,ベクトル(v1,...,vm)
−出力:ベクトル(v1,...,vm)に対応する鍵情報km*
GenKeyの一例では、まず、有限体Fqから元σα,ω,Ψ,Φα∈Fq (α=0,...,m+1,ξm+1,...,n; ω=1,...,m)が任意に選択される。この例では、これらとマスター秘密鍵MSKである基底ベクトル(b1*,...,bn*,bn+1*,bn+2*,bn+3*)とベクトル(v1,...,vm)とを用い、ベクトル(v1,...,vm)に対応する鍵情報
【数37】


が生成されて出力される。ただし、
【数38】


である。
《Delegate(m'):鍵情報生成委譲》
−入力:公開パラメータmpk,鍵情報km'*,ベクトルvm'+1
−出力:ベクトル(v1,...,vm'+1)に対応する鍵情報km'+1*
階層的内積述語暗号方式では、マスター秘密鍵MSKを用いることなく、公開パラメータmpk,鍵情報km'*,ベクトルvm'+1からベクトル(v1,...,vm'+1)に対応する鍵情報km'+1*を生成できる。ただし、m'=1,...,d-1である。
Delegate(m')の一例では、有限体Fqから元σ'α,ω,Ψ',Φ'α∈Fq (α=0,...,m'+2,ξm'+1+1,...,n; ω=1,...,m'+1)が任意に選択される。この例では、これらと鍵情報km'*とベクトルvm'+1と用い、ベクトル(v1,...,vm'+1)に対応する鍵情報
【数39】


が生成されて出力される。ただし、
【数40】


である。
《Enc:暗号化》
−入力:公開パラメータmpk,ベクトル(w1,...,wm),平文mes
−出力:暗号文(C1,C2)
Encの一例では、まず、有限体Fqから任意の元υ1,...,υdn+3,υが選択される。そして、これらと公開パラメータmpkとベクトル(w1,...,wm)とを用い、暗号文
【数41】


が生成される。また、gTτ・υを共通鍵Kとし、所定の共通鍵暗号方式(第2暗号方式)に則って平文mesの暗号文C2が生成される。暗号文C2の一例は、
C2=gTτ・υ・mes …(52)
である。なお、前述のように定数τの一例はτ=1Fである。その後、以上のように生成された暗号文(C1,C2)が出力される。
《Dec:復号》
−入力:公開パラメータmpk,ベクトル(v1,...,vm)に対応する鍵情報km*,暗号文(C1,C2)
−出力:復号値mes'
Decの一例では、
mes'=C2/e(C1,km,0*) …(53)
によって復号値mes'を計算する。
暗号文C1と鍵情報km*のkm,0*とが式(1)の双線形写像e(この例ではζ=3)に入力されると、式(2)(25)の性質から、
【数42】


を満たす。なお、σω及びσは有限体Fqの元である。Delegate(m')がなされることなく鍵情報km*が生成された場合にはσω0,ωである。Delegate(m')が1回以上なされた場合には、GenKeyに使用された有限体Fqの元σα,ωやDelegate(m')時に使用された有限体Fqの元σ'α,ωやΦ'αに応じてσωの値が定まる。ここで、すべてのω=1,...,mについて内積vω・wω=0Fであれば、式(54)は、
e(C1,km,0*)=gTτ・υ …(55)
と変形できる。式(52)(53)(55)より、すべてのω=1,...,mについて内積vω・wω=0Fである場合にmes'=mesとなり、正しく復号がなされることがわかる。
【0070】
<補記>
時限暗号システムに含まれるハードウェアエンティティ(時刻サーバ装置、送信者装置、受信者装置)は、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置(例えば通信ケーブル)が接続可能な通信部、CPU(Central Processing Unit)〔キャッシュメモリやレジスタなどを備えていてもよい。〕、メモリであるRAMやROM、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、CPU、RAM、ROM、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、CD−ROMなどの記録媒体を読み書きできる装置(ドライブ)などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【0071】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている(外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるROMに記憶させておくなどでもよい。)。また、これらのプログラムの処理によって得られるデータなどは、RAMや外部記憶装置などに適宜に記憶される。上述の説明では、演算結果やその格納領域のアドレスなどを記憶するRAMやレジスタなどの記憶装置を単に「記憶部」とした。
【0072】
ハードウェアエンティティでは、外部記憶装置〔あるいはROMなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にCPUで解釈実行・処理される。その結果、CPUが所定の機能(例えば、初期設定部、時刻トークン生成部、暗号文生成部、復号部など)を実現する。
【0073】
各実施形態で説明したハードウェアエンティティの細部においては、数論における数値計算処理が必要となる場合があるが、数論における数値計算処理自体は、周知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略した(この点の技術水準を示す数論における数値計算処理が可能なソフトウェアとしては、例えばPARI/GP、KANT/KASHなどが挙げられる。PARI/GPについては、例えばインターネット〈URL: http://pari.math.u-bordeaux.fr/〉[平成23年1月13日検索]を参照のこと。KANT/KASHについては、例えばインターネット〈URL: http://www.math.tu-berlin.de/algebra/やhttp://www.math.tu-berlin.de/~kant/kash.html〉[平成23年1月13日検索]を参照のこと。)。
また、この点に関する文献として、参考文献Aを挙げることができる。
(参考文献A)H. Cohen, "A Course in Computational Algebraic Number Theory", GTM 138, Springer-Verlag, 1993.
【0074】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【0075】
また、上記実施形態において説明したハードウェアエンティティにおける処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【0076】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、DVD(Digital Versatile Disc)、DVD−RAM(Random Access Memory)、CD−ROM(Compact Disc Read Only Memory)、CD−R(Recordable)/RW(ReWritable)等を、光磁気記録媒体として、MO(Magneto-Optical disc)等を、半導体メモリとしてEEP−ROM(Electronically Erasable and Programmable-Read Only Memory)等を用いることができる。
【0077】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【0078】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの(コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等)を含むものとする。
【0079】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

【特許請求の範囲】
【請求項1】
時刻サーバ装置と、送信者装置と、受信者装置とを含み、予め定められた時間において暗号文の復号が可能となる時限暗号システムであって、
公開パラメータpkとマスター秘密鍵skが定められた暗号(KeyGen,Enc,Dec)が、
KeyGen(sk,i)→ski:鍵生成アルゴリズム(マスター秘密鍵skと情報iを入力とし、当該情報iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズム)と、
Enc(pk,j,x)→cj:暗号化アルゴリズム(公開パラメータpkと情報jと暗号化対象の情報(以下、平文という)xを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズム)と、
Dec(pk,ski,cj)→y:復号アルゴリズム(公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、情報yを出力する確率的多項式時間アルゴリズム)と
を含み、上記情報iと上記情報jが予め定められた関係Rを満たすときに上記情報yとして上記平文xが得られるように構成されており、
上記時刻サーバ装置は、
定期あるいは不定期に、上記情報iを時刻tを含む情報として、上記暗号の鍵生成アルゴリズムKeyGen(sk,i)を実行して時刻トークンskt←KeyGen(sk,i)を生成する時刻トークン生成部を含み、
上記送信者成装置は、
上記情報jを上記復号アルゴリズムの実行の時的制限に係る予め定められた時間に関する情報t'(以下、時的制限情報t'という)を含む情報とし、上記平文xを平文mとして、上記暗号の暗号化アルゴリズムEnc(pk,j,m)を実行して暗号文ct'←Enc(pk,j,m)を生成する暗号文生成部を含み、
上記受信者装置は、
上記秘密鍵skiを上記時刻トークンsktとし、上記暗号文cjを上記暗号文ct'として、上記暗号の復号アルゴリズムDec(pk,skt,ct')を実行する復号部を含む
時限暗号システム。
【請求項2】
請求項1に記載の時限暗号システムにおいて、
上記時的制限情報t'を時刻とし、
上記関係Rは、上記時刻tに対してTを述語変数とするt≧Tなる述語と当該述語変数Tに代入されうる上記時的制限情報t'との関係であり、
上記時刻トークン生成部は、上記情報iを上記述語t≧Tとして、上記鍵生成アルゴリズムKeyGen(sk,i)を実行して時刻トークンskt←KeyGen(sk,i)を生成する
ことを特徴とする時限暗号システム。
【請求項3】
請求項1に記載の時限暗号システムにおいて、
上記時的制限情報t'を時刻とし、
上記関係Rは、上記時的制限情報t'に対してTを述語変数とするT≧t'なる述語と当該述語変数Tに代入されうる上記時刻tとの関係であり、
上記暗号文生成部は、上記情報jを上記述語T≧t'として、上記暗号化アルゴリズムEnc(pk,j,m)を実行して暗号文ct'←Enc(pk,j,m)を生成する
ことを特徴とする時限暗号システム。
【請求項4】
請求項1に記載の時限暗号システムにおいて、
上記時的制限情報t'を時刻とし、
上記関係Rは、Tを上記時的制限情報t'が代入されうる述語変数として、上記時刻tが経過するn個の時間区間[bi,ei](i=1,2,…,n)と述語変数Tとによる論理和(b1≦T≦e1)∨(b2≦T≦e2)∨・・・∨(bn≦T≦en)で表される述語と上記時的制限情報t'との関係であり、
上記時刻トークン生成部は、上記情報iを上記述語(b1≦T≦e1)∨(b2≦T≦e2)∨・・・∨(bn≦T≦en)として、上記鍵生成アルゴリズムKeyGen(sk,i)を実行して時刻トークンskt←KeyGen(sk,i)を生成する
ことを特徴とする時限暗号システム。
【請求項5】
請求項1に記載の時限暗号システムにおいて、
上記時的制限情報t'を時間とし、
上記関係Rは、Tを上記時刻tが代入されうる述語変数として、上記時的制限情報t'としてのn個の時間区間[bi,ei](i=1,2,…,n)と述語変数Tとによる論理和(b1≦T≦e1)∨(b2≦T≦e2)∨・・・∨(bn≦T≦en)で表される述語と上記時刻tとの関係であり、
上記暗号文生成部は、上記情報jを上記述語(b1≦T≦e1)∨(b2≦T≦e2)∨・・・∨(bn≦T≦en)として、上記暗号化アルゴリズムEnc(pk,j,m)を実行して暗号文ct'←Enc(pk,j,m)を生成する
ことを特徴とする時限暗号システム。
【請求項6】
請求項1から請求項5のいずれかに記載の時限暗号システムにおいて、
上記暗号文生成部は、上記暗号文ct'が正しく生成されたことを証明可能な非対話零知識証明を上記暗号文ct'に添付し、
上記受信者装置は、上記非対話零知識証明によって上記暗号文ct'が正しく生成されたものであるか否かを検証する検証部を含む
ことを特徴とする時限暗号システム。
【請求項7】
時刻サーバ装置と、送信者装置と、受信者装置とを含み、予め定められた時間において暗号文の復号が可能となる時限暗号システムにおける時限暗号方法であって、
公開パラメータpkとマスター秘密鍵skが定められた暗号(KeyGen,Enc,Dec)が、
KeyGen(sk,i)→ski:鍵生成アルゴリズム(マスター秘密鍵skと情報iを入力とし、当該情報iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズム)と、
Enc(pk,j,x)→cj:暗号化アルゴリズム(公開パラメータpkと情報jと暗号化対象の情報(以下、平文という)xを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズム)と、
Dec(pk,ski,cj)→y:復号アルゴリズム(公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、情報yを出力する確率的多項式時間アルゴリズム)と
を含み、上記情報iと上記情報jが予め定められた関係Rを満たすときに上記情報yとして上記平文xが得られるように構成されており、
上記時刻サーバ装置の時刻トークン生成部が、定期あるいは不定期に、上記情報iを時刻tを含む情報として、上記暗号の鍵生成アルゴリズムKeyGen(sk,i)を実行して時刻トークンskt←KeyGen(sk,i)を生成する時刻トークン生成ステップと、
上記送信者成装置の暗号文生成部が、上記情報jを上記復号アルゴリズムの実行の時的制限に係る予め定められた時間に関する情報t'を含む情報とし、上記平文xを平文mとして、上記暗号の暗号化アルゴリズムEnc(pk,j,m)を実行して暗号文ct'←Enc(pk,j,m)を生成する暗号文生成ステップと、
上記受信者装置の復号部が、上記秘密鍵skiを上記時刻トークンsktとし、上記暗号文cjを上記暗号文ct'として、上記暗号の復号アルゴリズムDec(pk,skt,ct')を実行する復号ステップとを有する
時限暗号方法。
【請求項8】
請求項1から請求項6のいずれかに記載の時限暗号システムにおいて用いられる上記時刻サーバ装置。
【請求項9】
請求項1から請求項6のいずれかに記載の時限暗号システムにおいて用いられる上記送信者装置。
【請求項10】
請求項1から請求項6のいずれかに記載の時限暗号システムにおいて用いられる上記受信者装置。
【請求項11】
請求項8に記載の時刻サーバ装置、請求項9に記載の送信者装置、請求項10に記載の受信者装置のいずれかとしてコンピュータを機能させるプログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate