特許ウォッチ

公開番号2024175753
公報種別公開特許公報(A)
公開日2024-12-19
出願番号2023093724
出願日2023-06-07
発明の名称スパンプログラム調整装置、暗号化装置、復号装置、鍵生成装置、スパンプログラム調整方法及びスパンプログラム調整プログラム
出願人三菱電機株式会社
代理人弁理士法人クロスボーダー特許事務所
主分類G09C 1/00 20060101AFI20241212BHJP(教育;暗号方法;表示;広告;シール)
要約【課題】ガウスの消去法により、非0成分がより少ないαを計算可能にする。
【解決手段】スパンプログラム取得部22は、暗号文の復号条件を構成するための複数の属性それぞれに行が対応付けられた行列Mを有するスパンプログラムを取得する。スパンプログラム調整部23は、復号条件を満たすために必要な属性の個数が少なくなる属性に対応付けられた行ほど、ガウスの消去法においてピボットとして選択され易くなるように、スパンプログラム取得部22によって生成されたスパンプログラムが有する行列Mの行を置換して行列M’を生成する。
【選択図】図1
特許請求の範囲【請求項１】
暗号文の復号条件を構成するための複数の属性それぞれに行が対応付けられた行列Ｍを有するスパンプログラムを取得するスパンプログラム取得部と、
前記復号条件を満たすために必要な属性の個数が少なくなる属性に対応付けられた行ほど、ガウスの消去法においてピボットとして選択され易くなるように、前記スパンプログラム取得部によって生成された前記スパンプログラムが有する前記行列Ｍの行を置換して行列Ｍ’を生成するスパンプログラム調整部と
を備えるスパンプログラム調整装置。
続きを表示（約 1,300 文字）【請求項２】
前記復号条件は、前記複数の属性を１つ以上のａｎｄ演算子と１つ以上のｏｒ演算子とを用いて結合した論理条件により表され、
前記スパンプログラム調整部は、
前記複数の属性それぞれと前記１つ以上のａｎｄ演算子それぞれと前記１つ以上のｏｒ演算子それぞれとをノードとした多分木であって、前記複数の属性それぞれをリーフとし、前記１つ以上のａｎｄ演算子それぞれと前記１つ以上のｏｒ演算子それぞれとをリーフ以外のノードとした多分木によって、前記復号条件を表す木構造化部と、
前記木構造化部によって表された前記多分木における前記１つ以上のｏｒ演算子のノードそれぞれに対して、紐づくリーフの数が少ない順に子のノードを整列する整列部と、
前記整列部によって整列された前記多分木を根から辿って先に到達するリーフが示す属性に対応する行ほど、前記ガウスの消去法において前記ピボットとして選択され易い位置になるように、前記行列Ｍの行を置換して行列Ｍ’を生成する置換部と
を備える請求項１に記載のスパンプログラム調整装置。
【請求項３】
請求項１に記載のスパンプログラム調整装置と、
前記スパンプログラム調整部によって生成された前記行列Ｍ’を含む暗号文を生成する暗号化部と
を備える暗号化装置。
【請求項４】
請求項１に記載のスパンプログラム調整装置と、
前記スパンプログラム調整部によって生成された前記行列Ｍ’を用いて前記暗号文を復号する復号部と
を備える復号装置。
【請求項５】
前記スパンプログラム調整部は、前記行列Ｍのうち、属性の集合Γに含まれる属性に対応する行が抽出された行列Ｍ
δ
を、前記行列Ｍとして用いる
請求項４に記載の復号装置。
【請求項６】
請求項１に記載のスパンプログラム調整装置と、
前記スパンプログラム調整部によって生成された前記行列Ｍ’を用いて復号鍵を生成する鍵生成部
を備える鍵生成装置。
【請求項７】
コンピュータが、暗号文の復号条件を構成するための複数の属性それぞれに行が対応付けられた行列Ｍを有するスパンプログラムを取得し、
コンピュータが、前記復号条件を満たすために必要な属性の個数が少なくなる属性に対応付けられた行ほど、ガウスの消去法においてピボットとして選択され易くなるように、前記スパンプログラムが有する前記行列Ｍの行を置換して行列Ｍ’を生成するスパンプログラム調整方法。
【請求項８】
暗号文の復号条件を構成するための複数の属性それぞれに行が対応付けられた行列Ｍを有するスパンプログラムを取得するスパンプログラム取得処理と、
前記復号条件を満たすために必要な属性の個数が少なくなる属性に対応付けられた行ほど、ガウスの消去法においてピボットとして選択され易くなるように、前記スパンプログラム取得処理によって生成された前記スパンプログラムが有する前記行列Ｍの行を置換して行列Ｍ’を生成するスパンプログラム調整処理と
を行うスパンプログラム調整装置としてコンピュータを機能させるスパンプログラム調整プログラム。

発明の詳細な説明【技術分野】
【０００１】
本開示は、スパンプログラムを用いた関数型暗号方式における復号処理の高速化技術に関する。
続きを表示（約 2,500 文字）【背景技術】
【０００２】
関数型暗号方式は、暗号文を復号可能な条件を設定できる暗号である。関数型暗号方式には、復号可能な条件を暗号文に設定する暗号文ポリシー関数型暗号と、秘密鍵に設定する鍵ポリシー関数型暗号とがある。暗号文ポリシー関数型暗号は、例えばクラウドサーバ上の機密情報管理システムに適用できる。暗号文ポリシー関数型暗号は、暗号化の際に復号可能なユーザを、所属及び役職といった属性のブール式で設定できるため、機密性の高いデータの安全な保管に適している。
例えば、復号条件として「人事部ａｎｄ課長ｏｒ部長」を設定した暗号文を生成とする。この場合には、人事部の課長は「人事部」と「課長」との属性を持つ自らの秘密鍵で暗号文を復号できる。一方で、総務部の課長は復号条件を満たす秘密鍵を所持していないため暗号文を復号できない。
【０００３】
関数型暗号方式を実現する具体的な方式として、特許文献１及び非特許文献１には、スパンプログラムを用いて復号可否を制御する方式が記載されている。スパンプログラムは、Ｌ行×ｒ列の行列Ｍとラベルρとで構成される。行列Ｍの各行は復号可能なユーザの条件式に含まれる各属性に対応付けされており、どの行がどの属性に対応付けられているかはラベルρによって示される。以降は簡単のため、モノトーンなスパンプログラムとそれを用いた復号手順について説明する。
【０００４】
スパンプログラムは、暗号文を復号可能な条件である復号条件を表している。ある属性の集合Γが与えられたとき、属性の集合Γが復号条件を満足するか否かがスパンプログラムを用いて判定される。対応する属性が属性の集合Γに含まれている行列Ｍの行を抜き出した行列をＭ
δ
とする。このとき、属性の集合Γに対し、復号条件は１
→
∈ｓｐａｎ＜Ｍ
δ
＞であれば受理し、さもなければ拒絶することを表す。ここで、ｓｐａｎ＜Ｍ
δ
＞はＭ
δ
の各行の線形結合全体である。１
→
は成分が全て１のｒ次元行ベクトルである。
【０００５】
復号処理では、暗号文（又は秘密鍵）に含まれるスパンプログラム（Ｍ，ρ）と、秘密鍵（又は暗号文）に含まれる属性の集合Γとに対して、１
→
＝αＭを満たすＬ次元行ベクトルαが、もし存在すれば計算される。そのようなαが存在する場合、すなわち復号条件を満たす場合、０でないαの成分α
ｉ
に対応する暗号文のベクトルと秘密鍵のベクトルとに対して、ペアリング演算とα
ｉ
乗とが実行され、掛け合わされて平文が得られる。一方、そのようなαが存在しない場合は復号条件を満たしていないと分かる。
【０００６】
特許文献２には、行列Ｍの成分が０又は１となるようにスパンプログラムを生成する手法が記載されている。特許文献２に記載された方法により生成されたスパンプログラムを使用すると、αの成分α
ｉ
が０又は１となるものが存在する。言い換えると、各成分α
ｉ
は対応する属性が復号条件を真にするために必要（α
ｉ
＝１）か不要（α
ｉ
＝０）かを表す。よって、復号処理の実行時間の多くはペアリング演算が占める。ペアリング演算は０でないαの成分α
ｉ
の個数に比例する回数実行されるため、αに０でない成分が少ないほど復号は高速に実行できる。
【先行技術文献】
【特許文献】
【０００７】
特開２０１１－２３２４７５号公報
国際公開第２０１６／００２０２０号
【非特許文献】
【０００８】
Ｔ．Ｏｋａｍｏｔｏ，Ｋ．Ｔａｋａｓｈｉｍａ， “ＦｕｌｌｙＳｅｃｕｒｅＦｕｎｃｔｉｏｎａｌＥｎｃｒｙｐｔｉｏｎｗｉｔｈＧｅｎｅｒａｌＲｅｌａｔｉｏｎｓｆｒｏｍｔｈｅＤｅｃｉｓｉｏｎａｌＬｉｎｅａｒＡｓｓｕｍｐｔｉｏｎ，” ＣＲＹＰＴＯ２０１０，１９１－２０８．
【発明の概要】
【発明が解決しようとする課題】
【０００９】
行列Ｍ
δ
に対してαを計算する方法として、ガウスの消去法がある。しかし、ガウスの消去法によるαの計算では、αが複数存在する場合、非０成分がより少ないαが必ず得られるとは限らない。また特許文献１及び特許文献２では、非０成分がより少ないαの計算方法については言及されていない。
例えば、復号条件ｐｒｄ＝（（ＡａｎｄＢ）ｏｒＣ）ｏｒＤに対して、属性の集合はΓ＝｛Ａ，Ｂ，Ｃ，Ｅ｝であるとする。この場合、行列Ｍ
δ
は３×２の行列であり、各行は属性Ａ，Ｂ，Ｃに対応する。このとき、成分が０又は１のαは（１，１，０）と（０，０，１）との２通りが存在し、復号条件を満たす属性の組み合わせを示している。すなわち、前者は属性Ａ，Ｂ∈Γによって復号条件が真になることを意味しており、後者は属性Ｃ∈Γによって復号条件が真になることを意味している。ここで、復号をより高速に実行するためには、α＝（１，１，０）よりも０でない成分が少ないα＝（０，０，１）を採用すべきである。α＝（１，１，０）が得られた場合でも、行列Ｍ
δ
の核の基底（－１，－１，１）を加算することでα＝（０，０，１）を得ることができるが、基底の個数が増えるほど０でない成分の少ないαの探索は困難となる。
【００１０】
本開示は、ガウスの消去法により、非０成分がより少ないαを計算可能にすることを目的とする。
【課題を解決するための手段】
（【００１１】以降は省略されています）

関連特許