(57)【特許請求の範囲】
【請求項１】
複数の述語ベクトルが設定された１つのユーザ秘密鍵と、前記複数の述語ベクトルのうちの１つの述語ベクトルに対応する１つの属性ベクトルがそれぞれに設定された複数の暗号文と、を入力にして内積述語暗号の判定アルゴリズムを実行する判定装置を備え、
前記複数の暗号文は、設定された属性ベクトルに対応する述語ベクトルが互いに異なり、
前記判定装置は、前記判定アルゴリズムを実行することによって、前記複数の暗号文の全てで、設定された属性ベクトルが前記複数の述語ベクトルのうちの対応する述語ベクトルと直交するか判定する
暗号システム。
【請求項２】
前記判定装置は、数１に示す値ζをユーザ秘密鍵ｕｓｋの要素（σ１，…，σｍ）と暗号文の組（ｃ１，…，ｃｍ）とを用いて算出し、値ζに基づいて判定結果を生成する
請求項１に記載の暗号システム。
【数１】
0006980155.tif 000033
【請求項３】
ユーザ秘密鍵ｕｓｋの要素σｉが数２で定義される請求項２に記載の暗号システム。
【数２】
0006980155.tif 000034
【請求項４】
識別子ｉｄと属性ベクトルｘｉとを用いて、暗号文ｃｉが数３で定義される請求項２または請求項３に記載の暗号システム。
【数３】
0006980155.tif 000035
【請求項５】
前記暗号システムは、
１つのマスタ秘密鍵と複数の述語ベクトルとを受け付け、受け付けたマスタ秘密鍵と受け付けた複数の述語ベクトルとを用いて前記ユーザ秘密鍵を生成するユーザ鍵生成装置と、
前記複数の暗号文を生成する複数の暗号文生成装置と、を備え、
前記複数の暗号文生成装置のそれぞれは、１つの暗号鍵と１つの述語ベクトルとを受け付け、受け付けた暗号鍵と受け付けた述語ベクトルとを用いて１つの暗号文を生成する
請求項１から請求項４のいずれか１項に記載の暗号システム。
【請求項６】
前記暗号システムは、１つのマスタ秘密鍵と複数の暗号化鍵とを生成するマスタ鍵生成装置を備え、
前記ユーザ鍵生成装置は、前記マスタ鍵生成装置によって生成されたマスタ秘密鍵を受け付け、
前記複数の暗号文生成装置のそれぞれは、前記マスタ鍵生成装置によって生成された複数の暗号化鍵のうちの１つの暗号化鍵を受け付ける
請求項５に記載の暗号システム。
【請求項７】
ユーザ秘密鍵受付部と暗号文受付部と判定部を備える判定装置によって実行される暗号方法であって、
前記ユーザ秘密鍵受付部が、複数の述語ベクトルが設定された１つのユーザ秘密鍵を受け付け、
前記暗号文受付部が、前記複数の述語ベクトルのうちの１つの述語ベクトルに対応する１つの属性ベクトルがそれぞれに設定された複数の暗号文を受け付け、
前記判定部が、前記１つのユーザ秘密鍵と前記複数の暗号文とを入力にして内積述語暗号の判定アルゴリズムを実行し、
前記複数の暗号文は、設定された属性ベクトルに対応する述語ベクトルが互いに異なり、
前記判定部は、前記判定アルゴリズムを実行することによって、前記複数の暗号文の全てで、設定された属性ベクトルが前記複数の述語ベクトルのうちの対応する述語ベクトルと直交するか判定する
暗号方法。
【請求項８】
複数の述語ベクトルが設定された１つのユーザ秘密鍵を受け付けるユーザ秘密鍵受付部と、
前記複数の述語ベクトルのうちの１つの述語ベクトルに対応する１つの属性ベクトルがそれぞれに設定された複数の暗号文を受け付ける暗号文受付部と、
前記１つのユーザ秘密鍵と前記複数の暗号文とを入力にして内積述語暗号の判定アルゴリズムを実行する判定部として
コンピュータを機能させるための暗号プログラムであって、
前記複数の暗号文は、設定された属性ベクトルに対応する述語ベクトルが互いに異なり、
前記判定部は、前記判定アルゴリズムを実行することによって、前記複数の暗号文の全てで、設定された属性ベクトルが前記複数の述語ベクトルのうちの対応する述語ベクトルと直交するか判定する
暗号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチクライアント型内積述語暗号に関するものである。
【背景技術】
【０００２】
内積述語暗号とは、ベクトルの直交性を、ベクトルの値を秘匿したまま判定することが可能な暗号技術である。
内積述語暗号では、まずマスタ秘密鍵と暗号化鍵の２つが生成される。そして、マスタ秘密鍵を使ってユーザ秘密鍵が生成され、暗号化鍵を使って暗号文が生成される。ユーザ秘密鍵と暗号文とのそれぞれには、入力されるベクトルが割り当てられる。ユーザ秘密鍵と暗号文を判定アルゴリズムに入力すると、割り当てられたベクトル同士が直交するか否かを表す真偽値が出力される。この時、ユーザ秘密鍵と暗号文を見ても、それぞれに割り当てられたベクトルの値についての情報を得ることはできない。そのため、判定アルゴリズムを用いて直交性を判定することしかできない。【０００３】
上記の通り、内積述語暗号では、具体的な値を秘匿したまま特定の関係性を満たすことを判定することが可能である。
そのため、内積述語暗号は、暗号化したまま検索を行う技術である検索可能暗号に応用される。【０００４】
特許文献１には、暗号文に設定された属性ベクトルと、復号鍵に設定された述語ベクトルと、を共に秘匿可能な内積述語暗号について記載されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第５９５１１２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来の内積述語暗号では、ユーザ秘密鍵と暗号文とのそれぞれに１つのベクトルが割り当てられ、１つのユーザ秘密鍵と１つの暗号文との間でベクトルが直交することを判定する。
そのため、複数のクライアントによって作成された複数の暗号文を判定する場合には、判定アルゴリズムを実行するユーザに複数のクライアントに対応する複数のユーザ秘密鍵を渡さなければならない。また、個別の鍵と暗号文をそれぞれ用いることで、暗号文とユーザ秘密鍵の全ての組み合わせにおける直交性が分かってしまう。【０００７】
本発明は、内積述語暗号において複数のクライアントに対応する複数のユーザ秘密鍵を用いずに複数の暗号文を判定できるようにすることを目的とする。
【課題を解決するための手段】
【０００８】
本発明の暗号システムは、
複数の述語ベクトルが設定された１つのユーザ秘密鍵と、前記複数の述語ベクトルのうちの１つの述語ベクトルに対応する１つの属性ベクトルがそれぞれに設定された複数の暗号文と、を入力にして内積述語暗号の判定アルゴリズムを実行する判定装置を備え、
前記複数の暗号文は、設定された属性ベクトルに対応する述語ベクトルが互いに異なり、
前記判定装置は、前記判定アルゴリズムを実行することによって、前記複数の暗号文の全てで、設定された属性ベクトルが前記複数の述語ベクトルのうちの対応する述語ベクトルと直交するか判定する。
【発明の効果】
【０００９】
本発明によれば、内積述語暗号において１つのユーザ秘密鍵を用いて複数の暗号文の全ての直交性を判定することができる。
【図面の簡単な説明】
【００１０】
【図１】実施の形態１における暗号システム１００の構成図。
【図２】実施の形態１におけるマスタ鍵生成装置１１０の機能構成図。
【図３】実施の形態１におけるユーザ鍵生成装置１２０の機能構成図。
【図４】実施の形態１における暗号文生成装置１３０の機能構成図。
【図５】実施の形態１における判定装置１４０の機能構成図。
【図６】実施の形態１における各装置（１１０、１２０、１３０、１４０）のハードウェア構成図。
【図７】実施の形態１におけるマスタ鍵生成アルゴリズム（Ｓ１２０）のフローチャート。
【図８】実施の形態１におけるユーザ鍵生成アルゴリズム（Ｓ２３０）のフローチャート。
【図９】実施の形態１における暗号文生成アルゴリズム（Ｓ３３０）のフローチャート。
【図１０】実施の形態１における判定アルゴリズム（Ｓ４３０）のフローチャート。
【図１１】実施の形態１における各装置（１１０、１２０、１３０、１４０）のハードウェア構成の補足図。
【発明を実施するための形態】
【００１１】
実施の形態および図面において、同じ要素または対応する要素には同じ符号を付している。説明した要素と同じ符号が付された要素の説明は適宜に省略または簡略化する。図中の矢印はデータの流れ又は処理の流れを主に示している。
【００１２】
実施の形態で使用する記法について説明する。
［数１０１］は、「Ａ」がランダムな変数またはランダムな分布である時、「Ａ」の分布に従い「Ａ」から「ｙ」を一様ランダムに選択したことを表す。つまり、［数１０１］は、「ｙ」が「Ａ」上の一様乱数であることを表す。
【００１３】
【数１０１】
0006980155.tif 000002
【００１４】
［数１０２］は、「ｙ」が「ｚ」により定義された値であること、または、「ｚ」が変数ｙに代入されたことを表す。
【００１５】
【数１０２】
0006980155.tif 000003
【００１６】
［数１０３］は、位数ｑの有限体Ｆを示す。位数ｑの有限体Ｆを有限体Ｆｑと記す。
【００１７】
【数１０３】
0006980155.tif 000004
【００１８】
［数１０４］は、有限体Ｆｑにおけるベクトル（ｘ１，…，ｘｎ）を表す。
【００１９】
【数１０４】
0006980155.tif 000005
【００２０】
［数１０５］は、行列Ｘの転置行列を表す。行列Ｘの転置行列を行列ＸＴと記す。
【００２１】
【数１０５】
0006980155.tif 000006
【００２２】
［数１０６］は、ベクトル（ｂ１，…，ｂＮ）から成る基底Ｂ、および、ベクトル（ｂ１＊，…，ｂＮ＊）からなる基底Ｂ＊を表す。
【００２３】
【数１０６】
0006980155.tif 000007
【００２４】
［数１０７］は、基底Ｂ上の元の係数ベクトル（ｘ１，…，ｘＮ）Ｂ、および、基底Ｂ＊上の元の係数ベクトル（ｙ１，…，ｙＮ）Ｂを表す。
【００２５】
【数１０７】
0006980155.tif 000008
【００２６】
実施の形態で使用する数学的概念について説明する。
まず、対称双線型ペアリング群について説明する。
対称双線型ペアリング群（ｑ，Ｇ，ＧＴ，ｇ、ｅ）は、素数ｑと、位数ｑの加法巡回群Ｇと、位数ｑの乗法巡回群ＧＴと、ペアリングｅとの組である。
ペアリングｅは、ｇ≠０∈Ｇと多項式時間で計算可能な非退化双線型ペアリングであり、「ｅ：Ｇ×Ｇ→ＧＴ」で表される。そして、ｅ（ｓｇ、ｔｇ）＝ｅ（ｇ，ｇ）ｓｔとｅ（ｇ，ｇ）≠１が成り立つ。
【００２７】
次に、双対ペアリングベクトル空間について説明する。
双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は、対称双線型ペアリング群（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の直積によって構成することができる。
双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は、素数ｑと、空間Ｖ、位数ｑの乗法巡回群ＧＴ、空間Ｖの標準基底Ａと、ペアリングｅとの組である。
空間Ｖは、有限体Ｆｑ上のＮ次元ベクトル空間であり、［数１０８］で定義される。
空間Ｖの標準基底Ａは、「Ａ：＝（ａ１，…，ａＮ）」で定義される。「ａｉ」は、［数１０９］で定義される。
空間Ｖにおけるペアリングは、［数１１０］によって定義される。この定義は、非退化双線型である。
つまり、ｅ（ｓｘ，ｔｙ）＝ｅ（ｘ，ｙ）ｓｔであり、全ての整数ｙ∈Ｖに対してｅ（ｘ，ｙ）＝１である場合、ｘ＝０である。
また、全ての整数ｉ＜Ｎと全ての整数ｊ＜Ｎに対して、ｅ（ａｉ，ａｊ）＝ｅ（ｇ，ｇ）δｉ，ｊである。但し、ｉ＝ｊであれば、δｉ，ｊ＝１であり、ｉ≠ｊであれば、δｉ，ｊ＝０である。また、ｅ（ｇ，ｇ）≠１∈ＧＴである。
【００２８】
【数１０８】
0006980155.tif 000009
【００２９】
【数１０９】
0006980155.tif 000010
【００３０】
【数１１０】
0006980155.tif 000011
【００３１】
実施の形態１．
暗号システム１００について、図１から図１１に基づいて説明する。
【００３２】
暗号システム１００は、内積述語暗号を実施するシステムである。特に、暗号システム１００は、マルチクライアント型内積述語暗号の実施に有用である。
マルチクライアント型内積述語暗号は、マルチクライアントに対して適用することが可能な内積述語暗号である。
【００３３】
＊＊＊構成の説明＊＊＊
図１に基づいて、暗号システム１００の構成を説明する。
暗号システム１００は、マスタ鍵生成装置１１０と、ユーザ鍵生成装置１２０と、複数の暗号文生成装置１３０と、判定装置１４０とを備える。
【００３４】
暗号文生成装置１３０の数は「ｍ」である。「ｍ」は２以上の整数である。
ｉ番目の暗号文生成装置１３０を第ｉ暗号文生成装置１３０と称する。「ｉ」は１以上ｍ以下の整数である。
【００３５】
マスタ鍵生成装置１１０は、マスタ鍵生成パラメータ（λ，ｎ，ｍ）を用いて、マスタ秘密鍵ｍｓｋと暗号化鍵の組（ｅｋ１，…，ｅｋｍ）を生成する。
ユーザ鍵生成装置１２０は、マスタ秘密鍵ｍｓｋと述語ベクトルの組（ｙ１，…，ｙｍ）とを用いて、ユーザ秘密鍵ｕｓｋを生成する。
第ｉ暗号文生成装置１３０は、暗号化鍵ｅｋｉと属性ベクトルｘｉと識別子ｉｄとを用いて、暗号文ｃｉを生成する。
判定装置１４０は、ユーザ秘密鍵ｕｓｋと暗号文の組（ｃ１，…，ｃｍ）とを用いて、判定結果（０または１）を求める。
【００３６】
判定結果は、全ての「ｉ」について、述語ベクトルｙｉと属性ベクトルｘｉとの直交性を示す。
判定結果「１」は、全ての「ｉ」について、述語ベクトルｙｉと属性ベクトルｘｉとが直交することを意味する。
判定結果「０」は、少なくともいずれかの「ｉ」について、述語ベクトルｙｉと属性ベクトルｘｉとが直交しないことを意味する。
【００３７】
図２に基づいて、マスタ鍵生成装置１１０の機能構成を説明する。
マスタ鍵生成装置１１０は、パラメータ受付部１１１と、マスタ鍵生成部１１２と、マスタ鍵出力部１１３とを備える。
パラメータ受付部１１１は、マスタ鍵生成パラメータ（λ，ｎ，ｍ）を受け付ける。
マスタ鍵生成部１１２は、マスタ鍵生成パラメータ（λ，ｎ，ｍ）を用いて、マスタ秘密鍵ｍｓｋと、暗号化鍵の組（ｅｋ１，…，ｅｋｍ）を生成する。
マスタ鍵出力部１１３は、マスタ秘密鍵ｍｓｋと、暗号化鍵の組（ｅｋ１，…，ｅｋｍ）を出力する。
【００３８】
図３に基づいて、ユーザ鍵生成装置１２０の機能構成を説明する。
ユーザ鍵生成装置１２０は、マスタ秘密鍵受付部１２１と、述語ベクトル受付部１２２と、ユーザ秘密鍵生成部１２３と、ユーザ秘密鍵出力部１２４とを備える。
マスタ秘密鍵受付部１２１は、マスタ秘密鍵ｍｓｋを受け付ける。
述語ベクトル受付部１２２は、述語ベクトルの組（ｙ１，…，ｙｍ）を受け付ける。
ユーザ秘密鍵生成部１２３は、マスタ秘密鍵ｍｓｋと述語ベクトルの組（ｙ１，…，ｙｍ）とを用いて、ユーザ秘密鍵ｕｓｋを生成する。
ユーザ秘密鍵出力部１２４は、ユーザ秘密鍵ｕｓｋを出力する。
【００３９】
図４に基づいて、第ｉ暗号文生成装置１３０の機能構成を説明する。
第ｉ暗号文生成装置１３０は、暗号化鍵受付部１３１と、属性ベクトル受付部１３２と、暗号文生成部１３３と、暗号文出力部１３４とを備える。
暗号化鍵受付部１３１は、暗号化鍵ｅｋｉを受け付ける。
属性ベクトル受付部１３２は、属性ベクトルｘｉと識別子ｉｄとを受け付ける。
暗号文生成部１３３は、暗号化鍵ｅｋｉと属性ベクトルｘｉと識別子ｉｄとを用いて、暗号文ｃｉを生成する。
暗号文出力部１３４は、暗号文ｃｉを出力する。
【００４０】
図５に基づいて、判定装置１４０の機能構成を説明する。
判定装置１４０は、ユーザ秘密鍵受付部１４１と、暗号文受付部１４２と、判定部１４３と、判定結果出力部１４４とを備える。
ユーザ秘密鍵受付部１４１は、ユーザ秘密鍵ｕｓｋを受け付ける。
暗号文受付部１４２は、暗号文の組（ｃ１，…，ｃｍ）を受け付ける。
判定部１４３は、ユーザ秘密鍵ｕｓｋと暗号文の組（ｃ１，…，ｃｍ）とを用いて、判定結果（０または１）を求める。
判定結果出力部１４４は、判定結果（０または１）を出力する。
【００４１】
図６に基づいて、暗号システム１００の各装置のハードウェア構成を説明する。
マスタ鍵生成装置１１０とユーザ鍵生成装置１２０と暗号文生成装置１３０と判定装置１４０とのそれぞれは、コンピュータである。
各コンピュータは、プロセッサ１９１とメモリ１９２と補助記憶装置１９３と通信装置１９４と入出力インタフェース１９５といったハードウェアを備える。これらのハードウェアは、信号線を介して互いに接続されている。
【００４２】
プロセッサ１９１は、演算処理を行うＩＣであり、他のハードウェアを制御する。例えば、プロセッサ１９１はＣＰＵである。
ＩＣは、Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔの略称である。
ＣＰＵは、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔの略称である。
【００４３】
メモリ１９２は揮発性の記憶装置である。メモリ１９２は、主記憶装置またはメインメモリとも呼ばれる。例えば、メモリ１９２はＲＡＭである。メモリ１９２に記憶されたデータは必要に応じて補助記憶装置１９３に保存される。
ＲＡＭは、Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙの略称である。
【００４４】
補助記憶装置１９３は不揮発性の記憶装置である。例えば、補助記憶装置１９３は、ＲＯＭ、ＨＤＤまたはフラッシュメモリである。補助記憶装置１９３に記憶されたデータは必要に応じてメモリ１９２にロードされる。
ＲＯＭは、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙの略称である。
ＨＤＤは、Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅの略称である。
【００４５】
通信装置１９４はレシーバ及びトランスミッタである。例えば、通信装置１９４は通信チップまたはＮＩＣである。
ＮＩＣは、Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄの略称である。
【００４６】
入出力インタフェース１９５は、入力装置および出力装置が接続されるポートである。例えば、入出力インタフェース１９５はＵＳＢ端子であり、入力装置はキーボード、マウスまたはＵＳＢメモリであり、出力装置はディスプレイまたはＵＳＢメモリである。ＵＳＢメモリは記憶媒体の一例である。
ＵＳＢは、Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓの略称である。
【００４７】
マスタ鍵生成装置１１０の補助記憶装置１９３には、パラメータ受付部１１１とマスタ鍵生成部１１２とマスタ鍵出力部１１３としてコンピュータを機能させるためのマスタ鍵生成プログラムが記憶されている。
ユーザ鍵生成装置１２０の補助記憶装置１９３には、マスタ秘密鍵受付部１２１と述語ベクトル受付部１２２とユーザ秘密鍵生成部１２３とユーザ秘密鍵出力部１２４としてコンピュータを機能させるためのユーザ鍵生成プログラムが記憶されている。
暗号文生成装置１３０の補助記憶装置１９３には、暗号化鍵受付部１３１と属性ベクトル受付部１３２と暗号文生成部１３３と暗号文出力部１３４としてコンピュータを機能させるための暗号文生成プログラムが記憶されている。
判定装置１４０の補助記憶装置１９３には、ユーザ秘密鍵受付部１４１と暗号文受付部１４２と判定部１４３と判定結果出力部１４４としてコンピュータを機能させるための判定プログラムが記憶されている。
各プログラムは、メモリ１９２にロードされて、プロセッサ１９１によって実行される。
【００４８】
補助記憶装置１９３には、さらに、ＯＳが記憶されている。ＯＳの少なくとも一部は、メモリ１９２にロードされて、プロセッサ１９１によって実行される。
プロセッサ１９１は、ＯＳを実行しながら、各プログラムを実行する。
ＯＳは、Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍの略称である。
【００４９】
各プログラムの入出力データは記憶部１９６に記憶される。
メモリ１９２は記憶部１９６として機能する。但し、補助記憶装置１９３、プロセッサ１９１内のレジスタおよびプロセッサ１９１内のキャッシュメモリなどの記憶装置が、メモリ１９２の代わりに、又は、メモリ１９２と共に、記憶部１９６として機能してもよい。
【００５０】
各装置は、プロセッサ１９１を代替する複数のプロセッサを備えてもよい。複数のプロセッサは、プロセッサ１９１の役割を分担する。
【００５１】
各プログラムは、光ディスクまたはフラッシュメモリ等の不揮発性の記録媒体にコンピュータ読み取り可能に記録（格納）することができる。
【００５２】
＊＊＊動作の説明＊＊＊
暗号システム１００の動作の手順は暗号方法に相当する。また、暗号システム１００の動作の手順は暗号プログラムによる処理の手順に相当する。
暗号方法は、マスタ鍵生成方法と、ユーザ鍵生成方法と、暗号文生成方法と、判定方法とで構成される。
暗号プログラムは、マスタ鍵生成プログラムと、ユーザ鍵生成プログラムと、暗号文生成プログラムと、判定プログラムとで構成される。
【００５３】
図２に基づいて、マスタ鍵生成方法を説明する。
ステップＳ１１０において、パラメータ受付部１１１は、マスタ鍵生成パラメータ（λ，ｎ，ｍ）を受け付ける。
具体的には、マスタ鍵生成装置１１０のユーザが、入力装置を操作して、マスタ鍵生成パラメータ（λ，ｎ，ｍ）をマスタ鍵生成装置１１０に入力する。そして、パラメータ受付部１１１は、入力されたマスタ鍵生成パラメータ（λ，ｎ，ｍ）を受け付ける。但し、パラメータ受付部１１１は、通信装置１９４を用いて、マスタ鍵生成パラメータ（λ，ｎ，ｍ）を受信してもよい。
【００５４】
マスタ鍵生成パラメータ（λ，ｎ，ｍ）は、セキュリティパラメータλと、ベクトル次元数ｎとベクトル個数ｍとから成る。
セキュリティパラメータλは、生成される鍵の強度を指定する。
ベクトル次元数ｎは、述語ベクトルｙｉと属性ベクトルｘｉとのそれぞれの次元数である。
ベクトル個数ｍは、述語ベクトルｙｉと属性ベクトルｘｉとのそれぞれの数であり、暗号文生成装置１３０の数、すなわち、クライアントの数に相当する。
【００５５】
ステップＳ１２０において、マスタ鍵生成部１１２は、マスタ鍵生成パラメータ（λ，ｎ，ｍ）を入力にして、鍵生成アルゴリズムを実行する。これにより、マスタ秘密鍵ｍｓｋと、暗号化鍵の組（ｅｋ１，…，ｅｋｍ）が生成される。
鍵生成アルゴリズムについて後述する。
【００５６】
ステップＳ１３０において、マスタ鍵出力部１１３は、マスタ秘密鍵ｍｓｋと、暗号化鍵の組（ｅｋ１，…，ｅｋｍ）を出力する。
具体的には、マスタ鍵出力部１１３は、通信装置１９４を用いて、マスタ秘密鍵ｍｓｋをユーザ鍵生成装置１２０へ送信する。また、マスタ鍵出力部１１３は、通信装置１９４を用いて、暗号化鍵ｅｋｉを第ｉ暗号文生成装置１３０へ送信する。但し、マスタ鍵出力部１１３は、入出力インタフェース１９５に接続された記憶媒体へ、マスタ秘密鍵ｍｓｋを書き出してもよい。また、マスタ鍵出力部１１３は、入出力インタフェース１９５に接続された別の記憶媒体へ、暗号化鍵の組（ｅｋ１，…，ｅｋｍ）を書き出してもよい。
【００５７】
図３に基づいて、ユーザ鍵生成方法を説明する。
ステップＳ２１０において、マスタ秘密鍵受付部１２１は、マスタ秘密鍵ｍｓｋを受け付ける。
具体的には、マスタ秘密鍵受付部１２１は、通信装置１９４を用いて、マスタ鍵生成装置１１０から送信されたマスタ秘密鍵ｍｓｋを受信する。但し、マスタ秘密鍵受付部１２１は、入出力インタフェース１９５に接続された記憶媒体から、マスタ秘密鍵ｍｓｋを読み出してもよい。
【００５８】
ステップＳ２２０において、述語ベクトル受付部１２２は、述語ベクトルの組（ｙ１，…，ｙｍ）を受け付ける。
具体的には、ユーザ鍵生成装置１２０のユーザが、入力装置を操作して、述語ベクトルの組（ｙ１，…，ｙｍ）をユーザ鍵生成装置１２０に入力する。そして、述語ベクトル受付部１２２は、入力された述語ベクトルの組（ｙ１，…，ｙｍ）を受け付ける。但し、述語ベクトル受付部１２２は、通信装置１９４を用いて、述語ベクトルの組（ｙ１，…，ｙｍ）を受信してもよい。
【００５９】
ステップＳ２３０において、ユーザ秘密鍵生成部１２３は、マスタ秘密鍵ｍｓｋと述語ベクトルの組（ｙ１，…，ｙｍ）とを入力にして、ユーザ鍵生成アルゴリズムを実行する。これにより、ユーザ秘密鍵ｕｓｋが生成される。
ユーザ鍵生成アルゴリズムについて後述する。
【００６０】
ステップＳ２４０において、ユーザ秘密鍵出力部１２４は、ユーザ秘密鍵ｕｓｋを出力する。
具体的には、ユーザ秘密鍵出力部１２４は、通信装置１９４を用いて、ユーザ秘密鍵ｕｓｋを判定装置１４０へ送信する。但し、ユーザ秘密鍵出力部１２４は、入出力インタフェース１９５に接続された記憶媒体へ、ユーザ秘密鍵ｕｓｋを書き出してもよい。
【００６１】
図４に基づいて、第ｉ暗号文生成装置１３０による暗号文生成方法を説明する。
ステップＳ３１０において、暗号化鍵受付部１３１は、暗号化鍵ｅｋｉを受け付ける。
具体的には、マスタ秘密鍵受付部１２１は、通信装置１９４を用いて、マスタ鍵生成装置１１０から送信された暗号化鍵ｅｋｉを受信する。但し、マスタ秘密鍵受付部１２１は、入出力インタフェース１９５に接続された記憶媒体から、暗号化鍵ｅｋｉを読み出してもよい。
【００６２】
ステップＳ３２０において、属性ベクトル受付部１３２は、属性ベクトルｘｉと識別子ｉｄとを受け付ける。
具体的には、暗号文生成装置１３０のユーザが、入力装置を操作して、属性ベクトルｘｉと識別子ｉｄとを暗号文生成装置１３０に入力する。そして、属性ベクトル受付部１３２は、入力された属性ベクトルｘｉと入力された識別子ｉｄとを受け付ける。但し、属性ベクトル受付部１３２は、通信装置１９４を用いて、属性ベクトルｘｉと識別子ｉｄとを受信してもよい。
【００６３】
ステップＳ３３０において、暗号文生成部１３３は、暗号化鍵ｅｋｉと属性ベクトルｘｉと識別子ｉｄとを入力にして、暗号文生成アルゴリズムを実行する。これにより、暗号文ｃｉが生成される。
暗号文生成アルゴリズムについて後述する。
【００６４】
ステップＳ３４０において、暗号文出力部１３４は、暗号文ｃｉを出力する。
具体的には、暗号文出力部１３４は、通信装置１９４を用いて、暗号文ｃｉを判定装置１４０へ送信する。但し、暗号文出力部１３４は、入出力インタフェース１９５に接続された記憶媒体へ、暗号文ｃｉを書き出してもよい。
【００６５】
図５に基づいて、判定方法を説明する。
ステップＳ４１０において、ユーザ秘密鍵受付部１４１は、ユーザ秘密鍵ｕｓｋを受け付ける。
具体的には、ユーザ秘密鍵受付部１４１は、通信装置１９４を用いて、ユーザ鍵生成装置１２０から送信されたユーザ秘密鍵ｕｓｋを受信する。但し、ユーザ秘密鍵受付部１４１は、入出力インタフェース１９５に接続された記憶媒体から、ユーザ秘密鍵ｕｓｋを読み出してもよい。
【００６６】
ステップＳ４２０において、暗号文受付部１４２は、暗号文の組（ｃ１，…，ｃｍ）を受け付ける。
具体的には、暗号文受付部１４２は、通信装置１９４を用いて、第ｉ暗号文生成装置１３０から送信された暗号文ｃｉを受信する。但し、暗号文受付部１４２は、入出力インタフェース１９５に接続された記憶媒体から、暗号文ｃｉを読み出してもよい。
【００６７】
ステップＳ４３０において、判定部１４３は、ユーザ秘密鍵ｕｓｋと暗号文の組（ｃ１，…，ｃｍ）とを入力にして、判定アルゴリズムを実行する。これにより、判定結果（０または１）が得られる。
判定アルゴリズムについて後述する。
【００６８】
ステップＳ４４０において、判定結果出力部１４４は、判定結果（０または１）を出力する。
具体的には、判定結果出力部１４４は、入出力インタフェース１９５に接続されたディスプレイに、判定結果（０または１）を表示する。但し、判定結果出力部１４４は、通信装置１９４を用いて、判定結果（０または１）を送信してもよい。
【００６９】
図７に基づいて、マスタ鍵生成アルゴリズム（Ｓ１２０）を説明する。
ステップＳ１２１において、マスタ鍵生成部１１２は、セキュリティパラメータλに基づいて、対称双線型ペアリング群のパラメータＰ０を決定する。
対称双線型ペアリング群のパラメータＰ０は［数１１１］で定義される。
【００７０】
【数１１１】
0006980155.tif 000012
【００７１】
対称双線型ペアリング群のパラメータＰ０は、位数ｑと、位数ｑの加法巡回群Ｇと、乗法巡回群ＧＴと、加法巡回群Ｇの生成元ｇと、ペアリングｅとを含む。
位数ｑと加法巡回群Ｇと乗法巡回群ＧＴと生成元ｇは、ペアリングに適したＢＮ曲線などの楕円曲線を生成する既存のアルゴリズムによって生成される。
ペアリングｅは、ｏｐｔｉｍａｌ  ａｔｅペアリングなどの既存のペアリング演算アルゴリズムから選択されるアルゴリズムによって決定される。
【００７２】
ステップＳ１２２において、マスタ鍵生成部１１２は、対称双線型ペアリング群のパラメータＰ０に基づいて、双対ペアリングベクトル空間のパラメータＰ１を決定する。
双対ペアリングベクトル空間のパラメータＰ１は［数１１２］で定義される。
【００７３】
【数１１２】
0006980155.tif 000013
【００７４】
双対ペアリングベクトル空間のパラメータＰ１は、位数ｑと、空間Ｖと、位数ｑの乗法巡回群ＧＴと、空間Ｖの標準基底Ａとを含む。
位数ｑと空間Ｖと位数ｑの乗法巡回群ＧＴと空間Ｖの標準基底Ａとペアリングｅは、［数１０８］と［数１０９］と［数１１０］に示すように、対称双線型ペアリング群の直積とその上のペアリングとして決定される。
空間Ｖは［数１０８］で定義される。「Ｎ」は、ベクトル次元数ｎを用いて、Ｎ＝６（ｎ＋１）で定義される。
空間Ｖの標準基底Ａは「Ａ：＝（ａ１，…，ａＮ）」で定義される。「ａｉ」は［数１０９］で定義される。
ペアリングｅは［数１１０］で定義される。
【００７５】
ステップＳ１２３において、マスタ鍵生成部１１２は、乱数ψを生成する。
具体的には、マスタ鍵生成部１１２は、有限体Ｆｑから乱数ψを選択する。
乱数ψは［数１１３］で定義される。
【００７６】
【数１１３】
0006980155.tif 000014
【００７７】
ステップＳ１２４において、マスタ鍵生成部１１２は、行列式が０でないランダム行列の組（Ｘ１，…，Ｘｍ）を生成する。
ランダム行列Ｘｋは有限体Ｆｑ上のランダム行列であり、ランダム行列Ｘｋの大きさは（Ｎ×Ｎ）である。「ｋ」は１以上ｍ以下の整数である。
【００７８】
ランダム行列Ｘｋは［数１１４］で定義される。
（Ｘｋｉ，ｊ）は、ランダム行列Ｘｋの要素である。
ここでＧＬ（ｎ，Ｆｑ）は有限体Ｆｑ上のｎ次正則行列全体の集合を表す。
【００７９】
【数１１４】
0006980155.tif 000015
【００８０】
ステップＳ１２５において、マスタ鍵生成部１１２は、ランダム行列Ｘｋに基づいて、要素（γｋｉ，ｊ）を生成する。
要素（γｋｉ，ｊ）は［数１１５］で定義される。
【００８１】
【数１１５】
0006980155.tif 000016
【００８２】
ステップＳ１２６において、マスタ鍵生成部１１２は、標準基底Ａとランダム行列Ｘｋとに基づいて、基底Ｂｋを生成する。
基底Ｂｋは［数１１６］で定義される。
【００８３】
【数１１６】
0006980155.tif 000017
【００８４】
ステップＳ１２７において、マスタ鍵生成部１１２は、要素（γｋｉ，ｊ）と標準基底Ａとに基づいて、基底Ｂｋ＊を生成する。
基底Ｂｋ＊は［数１１７］で定義される。
【００８５】
【数１１７】
0006980155.tif 000018
【００８６】
ステップＳ１２８において、マスタ鍵生成部１１２は、ペアリングｅに基づいて、要素ｇＴを生成する。
要素ｇＴは［数１１８］で定義される。
【００８７】
【数１１８】
0006980155.tif 000019
【００８８】
ステップＳ１２９において、マスタ鍵生成部１１２は、パラメータＰ０とパラメータＰ１と基底の組（Ｂ１＊，…，Ｂｍ＊）とを用いて、マスタ秘密鍵ｍｓｋを生成する。
マスタ秘密鍵ｍｓｋは、パラメータＰ０とパラメータＰ１と基底の組（Ｂ１＊，…，Ｂｍ＊）とを含む。
マスタ秘密鍵ｍｓｋは［数１１９］で定義される。
【００８９】
【数１１９】
0006980155.tif 000020
【００９０】
さらに、マスタ鍵生成部１１２は、パラメータＰ０とパラメータＰ１と基底Ｂｉとを用いて、暗号化鍵ｅｋｉを生成する。「ｉ」は１以上ｍ以下の整数である。
暗号化鍵ｅｋｉは、パラメータＰ０とパラメータＰ１と基底Ｂｉとを含む。
暗号化鍵ｅｋｉは［数１２０］で定義される。
【００９１】
【数１２０】
0006980155.tif 000021
【００９２】
図８に基づいて、ユーザ鍵生成アルゴリズム（Ｓ２３０）を説明する。
ステップＳ２３１において、ユーザ秘密鍵生成部１２３は、有限体Ｆｑに基づいて、乱数の組（ｓ１，…，ｓｍ−１）を生成する。
乱数の組（ｓ１，…，ｓｍ−１）は［数１２１］で定義される。
【００９３】
【数１２１】
0006980155.tif 000022
【００９４】
ユーザ秘密鍵生成部１２３は、乱数の組（ｓ１，…，ｓｍ−１）に基づいて、乱数ｓｍを生成する。乱数ｓｍは、乱数の組（ｓ１，…，ｓｍ−１）の総和の逆元である。
乱数ｓｍは［数１２２］で定義される。
【００９５】
【数１２２】
0006980155.tif 000023
【００９６】
ユーザ秘密鍵生成部１２３は、有限体Ｆｑに基づいて、ランダムなベクトルの組（η１，…，ηｍ）を生成する。
ランダムなベクトルの組（η１，…，ηｍ）は［数１２３］で定義される。
【００９７】
【数１２３】
0006980155.tif 000024
【００９８】
ユーザ秘密鍵生成部１２３は、有限体Ｆｑに基づいて、ランダムなベクトルの組（θ１，…，θｍ）を生成する。
ランダムなベクトルの組（θ１，…，θｍ）は［数１２４］で定義される。
【００９９】
【数１２４】
0006980155.tif 000025
【０１００】
ステップＳ２３２において、ユーザ秘密鍵生成部１２３は、基底の組（Ｂ１＊，…，Ｂｍ＊）を用いて、双対ペアリングベクトル空間上の元の組（σ１，…，σｍ）を生成する。
双対ペアリングベクトル空間上の元σｉは［数１２５］で定義される。「ｉ」は１以上ｍ以下の整数である。
【０１０１】
【数１２５】
0006980155.tif 000026
【０１０２】
ステップＳ２３３において、ユーザ秘密鍵生成部１２３は、双対ペアリングベクトル空間上の元の組（σ１，…，σｍ）を用いて、ユーザ秘密鍵ｕｓｋを生成する。
ユーザ秘密鍵ｕｓｋは双対ペアリングベクトル空間上の元の組（σ１，…，σｍ）を含む。
ユーザ秘密鍵ｕｓｋは［数１２６］で定義される。
【０１０３】
【数１２６】
0006980155.tif 000027
【０１０４】
図９に基づいて、第ｉ暗号文生成装置１３０による暗号文生成アルゴリズム（Ｓ３３０）を説明する。
ステップＳ３３１において、暗号文生成部１３３は、有限体Ｆｑに基づいて、ランダムなベクトルωｉを生成する。
ランダムなベクトルωｉは［数１２７］で定義される。
【０１０５】
【数１２７】
0006980155.tif 000028
【０１０６】
さらに、暗号文生成部１３３は、有限体Ｆｑに基づいて、ランダムなベクトルφｉを生成する。
ランダムなベクトルφｉは［数１２８］で定義される。
【０１０７】
【数１２８】
0006980155.tif 000029
【０１０８】
ステップＳ３３２において、暗号文生成部１３３は、ベクトルωｉとベクトルφｉと基底Ｂｉとに基づいて、双対ペアリングベクトル空間上の元ｃｉを生成する。生成された元ｃｉが暗号文となる。
双対ペアリングベクトル空間上の元ｃｉ（暗号文ｃｉ）は［数１２９］で定義される。
ここでＨ（ｉｄ）はＦｑを値域とするハッシュ関数Ｈにｉｄを入力した際の出力を表す。
【０１０９】
【数１２９】
0006980155.tif 000030
【０１１０】
図１０に基づいて、判定アルゴリズム（Ｓ４３０）を説明する。
ステップＳ４３１において、判定部１４３は、ユーザ秘密鍵ｕｓｋの要素（σ１，…，σｍ）と暗号文の組（ｃ１，…，ｃｍ）とを用いて、判定値ζを算出する。
判定値ζは［数１３０］で定義される。
【０１１１】
【数１３０】
0006980155.tif 000031
【０１１２】
ステップＳ４３２において、判定部１４３は、判定値ζに基づいて、判定結果を生成する。
具体的には、判定値ζが「１」であれば判定結果は「１」であり、判定値ζが「１」でなければ判定結果は「０」である。
判定結果ｏｕｔｐｕｔは［数１３１］で定義される。
【０１１３】
【数１３１】
0006980155.tif 000032
【０１１４】
＊＊＊実施の形態１の特徴＊＊＊
暗号システム１００は、以下のような内積述語暗号方式を実現する。
その内積述語暗号方式は、ベクトルがそれぞれに設定されたユーザ秘密鍵と暗号文を用いて、ベクトルの値を秘匿したまま、直交性の判定が可能である。特に、複数のベクトルが設定された１つのユーザ秘密鍵と、１つのベクトルが設定された複数の暗号文との間で、対応するベクトル同士の直交性が全て成り立つか否かを各ベクトルの値を秘匿したまま判定することが可能である。
複数の暗号文はそれぞれ異なるクライアントの装置によってバラバラに生成することが可能である。また、各暗号文にはベクトルだけではなく識別子ｉｄが設定され、識別子ｉｄが等しい暗号文同士のみが判定アルゴリズムの入力として機能する。そのため、暗号文同士の識別子ｉｄが異なる場合は、常に、判定結果が「０」になる。
【０１１５】
＊＊＊実施の形態１の概要＊＊＊
暗号システム１００は、判定装置１４０を備える。
判定装置１４０は、複数の述語ベクトルが設定された１つのユーザ秘密鍵と、前記複数の述語ベクトルのうちの１つの述語ベクトルに対応する１つの属性ベクトルがそれぞれに設定された複数の暗号文と、を入力にして内積述語暗号の判定アルゴリズムを実行する。
前記複数の暗号文は、設定された属性ベクトルに対応する述語ベクトルが互いに異なる。
そして、判定装置１４０は、前記判定アルゴリズムを実行することによって、前記複数の暗号文の全てで、設定された属性ベクトルが前記複数の述語ベクトルのうちの対応する述語ベクトルと直交するか判定する。
【０１１６】
暗号システム１００は、ユーザ鍵生成装置１２０と複数の暗号文生成装置１３０とを備える。
ユーザ鍵生成装置１２０は、１つのマスタ秘密鍵と複数の述語ベクトルとを受け付け、受け付けたマスタ秘密鍵と受け付けた複数の述語ベクトルとを用いて前記ユーザ秘密鍵を生成する。
複数の暗号文生成装置１３０は、前記複数の暗号文を生成する。
複数の暗号文生成装置１３０のそれぞれは、１つの暗号鍵と１つの述語ベクトルとを受け付け、受け付けた暗号鍵と受け付けた述語ベクトルとを用いて１つの暗号文を生成する。
【０１１７】
暗号システム１００は、マスタ鍵生成装置１１０を備える。
マスタ鍵生成装置１１０は、１つのマスタ秘密鍵と複数の暗号化鍵とを生成する。
ユーザ鍵生成装置１２０は、マスタ鍵生成装置１１０によって生成されたマスタ秘密鍵を受け付ける。
複数の暗号文生成装置１３０のそれぞれは、マスタ鍵生成装置１１０によって生成された複数の暗号化鍵のうちの１つの暗号化鍵を受け付ける。
【０１１８】
＊＊＊実施の形態１の効果＊＊＊
それぞれ１つのベクトルが割り当てられた複数の暗号文に対して複数のベクトルが割り当てられた１つのユーザ秘密鍵を用いることで、対応するベクトル同士のペアの全てが直交するか否かのみを一度に判定することができる。
【０１１９】
＊＊＊実施の形態１の補足＊＊＊
実施の形態１では、対称双線型ペアリング群により双対ペアリングベクトル空間を構成した場合について説明した。
なお、非対称双線型ペアリング群により双対ペアリングベクトル空間を構成することも可能である。
実施の形態１を非対称双線型ペアリング群により双対ペアリングベクトル空間を構成した場合に応用することは容易である。
【０１２０】
図１１に基づいて、暗号システム１００の各装置のハードウェア構成について補足する。
マスタ鍵生成装置１１０とユーザ鍵生成装置１２０と暗号文生成装置１３０と判定装置１４０とのそれぞれは、処理回路１９９を備える。
マスタ鍵生成装置１１０処理回路１９９は、パラメータ受付部１１１とマスタ鍵生成部１１２とマスタ鍵出力部１１３とを実現するハードウェアである。
ユーザ鍵生成装置１２０の処理回路１９９は、マスタ秘密鍵受付部１２１と述語ベクトル受付部１２２とユーザ秘密鍵生成部１２３とユーザ秘密鍵出力部１２４とを実現するハードウェアである。
暗号文生成装置１３０の処理回路１９９は、暗号化鍵受付部１３１と属性ベクトル受付部１３２と暗号文生成部１３３と暗号文出力部１３４とを実現するハードウェアである。
判定装置１４０の処理回路１９９は、ユーザ秘密鍵受付部１４１と暗号文受付部１４２と判定部１４３と判定結果出力部１４４とを実現するハードウェアである。
【０１２１】
処理回路１９９は、専用のハードウェアであってもよいし、メモリ１９２にロードされたプログラムを実行する処理回路１９９であってもよい。
【０１２２】
処理回路１９９が専用のハードウェアである場合、処理回路１９９は、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ、ＦＰＧＡまたはこれらの組み合わせである。
ＡＳＩＣは、Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔの略称である。
ＦＰＧＡは、Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙの略称である。
【０１２３】
各装置は、処理回路１９９を代替する複数の処理回路を備えてもよい。複数の処理回路は、処理回路１９９の役割を分担する。
【０１２４】
各装置において、一部の機能が専用のハードウェアで実現されて、残りの機能がソフトウェアまたはファームウェアで実現されてもよい。
【０１２５】
このように、各装置の機能はハードウェア、ソフトウェア、ファームウェアまたはこれらの組み合わせで実現することができる。
【０１２６】
実施の形態は、好ましい形態の例示であり、本発明の技術的範囲を制限することを意図するものではない。実施の形態は、部分的に実施してもよいし、他の形態と組み合わせて実施してもよい。フローチャート等を用いて説明した手順は、適宜に変更してもよい。
【０１２７】
実施の形態で説明された各装置の要素である「部」は、「処理」または「工程」と読み替えてもよい。
【符号の説明】
【０１２８】
１００  暗号システム、１１０  マスタ鍵生成装置、１１１  パラメータ受付部、１１２  マスタ鍵生成部、１１３  マスタ鍵出力部、１２０  ユーザ鍵生成装置、１２１  マスタ秘密鍵受付部、１２２  述語ベクトル受付部、１２３  ユーザ秘密鍵生成部、１２４  ユーザ秘密鍵出力部、１３０  暗号文生成装置、１３１  暗号化鍵受付部、１３２  属性ベクトル受付部、１３３  暗号文生成部、１３４  暗号文出力部、１４０  判定装置、１４１  ユーザ秘密鍵受付部、１４２  暗号文受付部、１４３  判定部、１４４  判定結果出力部、１９１  プロセッサ、１９２  メモリ、１９３  補助記憶装置、１９４  通信装置、１９５  入出力インタフェース、１９６  記憶部、１９９  処理回路。
【図１】
0006980155.tif 000036
【図２】
0006980155.tif 000037
【図３】
0006980155.tif 000038
【図４】
0006980155.tif 000039
【図５】
0006980155.tif 000040
【図６】
0006980155.tif 000041
【図７】
0006980155.tif 000042
【図８】
0006980155.tif 000043
【図９】
0006980155.tif 000044
【図１０】
0006980155.tif 000045
【図１１】
0006980155.tif 000046