(57)【要約】  暗号システム（１０）は、格子理論に基づく関数型暗号方式を実現する。暗号システム（１０）において、鍵生成装置（１００）は、入力パラメータＹである述語ベクトルｖによって定まる行列ＡＹと、行列ｅとの積が、公開パラメータＰＰから得られる複数の行列ｕのうちの行列ｕｊであって、複数の値を含む集合［Ｎ］のうちの値ｊについての行列ｕｊになる行列ｅを鍵要素として含む秘密鍵ｓｋｖを、述語ベクトルｖについての秘密鍵ｓｋｖとして生成する。
2016162941.tif 000002
【特許請求の範囲】
【請求項１】
入力パラメータＹによって定まる行列ＡＹと、行列ｅとの積が、公開パラメータＰＰから得られる複数の行列ｕのうちの行列ｕｊであって、複数の値を含む集合［Ｎ］のうちの値ｊについての行列ｕｊになる前記行列ｅを鍵要素として含む秘密鍵を、前記入力パラメータＹについての秘密鍵として生成する鍵生成装置と、
前記集合［Ｎ］に含まれる各値についての暗号要素を含む暗号文を生成する暗号化装置と、
前記暗号文に含まれる暗号要素のうちの前記値ｊについての暗号要素と、前記秘密鍵とを用いて、前記暗号文を復号する復号装置と
を備える暗号システム。
【請求項２】
前記行列ｅは、前記行列ＡＹ及び行列ｕｊよりもノルムが短い
請求項１に記載の暗号システム。
【請求項３】
前記各値についての暗号要素は、その値についての行列ｕを用いて生成された
請求項１又は２に記載の暗号システム。
【請求項４】
前記行列ＡＹは、前記入力パラメータＹである述語ベクトルｖが設定された行列Ａｖであり、
前記暗号化装置は、前記各値についての暗号要素に加えて、属性ベクトルｗを設定した暗号要素を含む暗号文を生成する
請求項１から３までのいずれか１項に記載の暗号システム。
【請求項５】
前記鍵生成装置は、数１に示す行列ｅを前記鍵要素として生成し、
前記暗号化装置は、数２に示すｃ０と、数３に示すｃｉ，γと、数４に示すｃ’ｊとを前記暗号要素として生成し、
前記復号装置は、数５に示す計算をして、前記暗号文を復号する
請求項４に記載の暗号システム。
【数１】
2016162941.tif 000007
【数２】
2016162941.tif 000008
【数３】
2016162941.tif 000009
【数４】
2016162941.tif 000010
【数５】
2016162941.tif 000011
【請求項６】
入力パラメータＹと公開パラメータＰＰとを取得するパラメータ取得部と、
前記パラメータ取得部が取得した入力パラメータＹによって定まる行列ＡＹと、行列ｅとの積が、公開パラメータＰＰから得られる複数の行列ｕのうちの行列ｕｊであって、複数の値を含む集合［Ｎ］のうちの値ｊについての行列ｕｊになる前記行列ｅを秘密鍵の鍵要素として生成する秘密鍵生成部と
を備える鍵生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、格子理論に基づく関数型暗号方式に関する。
【背景技術】
【０００２】
非特許文献１〜３には、格子理論に基づく関数型暗号方式について記載されている。非特許文献１〜３に記載された関数型暗号方式は、格子理論に基づくことにより、量子計算機にも耐性を有している。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｓｈｗｅｔａ  Ａｇｒａｗａｌ，  Ｄａｖｉｄ  Ｍａｎｄｅｌｌ  Ｆｒｅｅｍａｎ，  ａｎｄ  Ｖｉｎｏｄ  Ｖａｉｋｕｎｔａｎａｔｈａｎ．  Ｆｕｎｃｔｉｏｎａｌ  ｅｎｃｒｙｐｔｉｏｎ  ｆｏｒ  ｉｎｎｅｒ  ｐｒｏｄｕｃｔ  ｐｒｅｄｉｃａｔｅｓ  ｆｒｏｍ  ｌｅａｒｎｉｎｇ  ｗｉｔｈ  ｅｒｒｏｒｓ．  Ｉｎ  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＡＳＩＡＣＲＹＰＴ  ２０１１  −  １７ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  ｔｈｅ  Ｔｈｅｏｒｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎ  ｏｆ  Ｃｒｙｐｔｏｌｏｇｙ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ，  Ｓｅｏｕｌ，  Ｓｏｕｔｈ  Ｋｏｒｅａ，  Ｄｅｃｅｍｂｅｒ  ４−８，２０１１．  Ｐｒｏｃｅｅｄｉｎｇｓ，  ｐａｇｅｓ  ２１−４０，  ２０１１．
【非特許文献２】Ｍｉｃｈｅｌ  Ａｂｄａｌｌａ，  Ａｎｇｅｌｏ  Ｄｅ  Ｃａｒｏ，  ａｎｄ  Ｋａｒｉｎａ  Ｍｏｃｈｅｔｔｉ．  Ｌａｔｔｉｃｅ−ｂａｓｅｄ  ｈｉｅｒａｒｃｈｉｃａｌ  ｉｎｎｅｒ  ｐｒｏｄｕｃｔ  ｅｎｃｒｙｐｔｉｏｎ．Ｉｎ  Ｐｒｏｇｒｅｓｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＬＡＴＩＮＣＲＹＰＴ  ２０１２  −  ２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｒｙｐｔｏｌｏｇｙ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ  ｉｎ  Ｌａｔｉｎ  Ａｍｅｒｉｃａ，  Ｓａｎｔｉａｇｏ，  Ｃｈｉｌｅ，  Ｏｃｔｏｂｅｒ  ７−１０，  ２０１２．  Ｐｒｏｃｅｅｄｉｎｇｓ，  ｐａｇｅｓ  １２１−１３８，  ２０１２．
【非特許文献３】Ｋｅｉｔａ  Ｘａｇａｗａ．  Ｉｍｐｒｏｖｅｄ  （ｈｉｅｒａｒｃｈｉｃａｌ）  ｉｎｎｅｒ−ｐｒｏｄｕｃｔ  ｅｎｃｒｙｐｔｉｏｎ  ｆｒｏｍ  ｌａｔｔｉｃｅｓ．  Ｉｎ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ  −  ＰＫＣ  ２０１３  −  １６ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｐｒａｃｔｉｃｅ  ａｎｄ  Ｔｈｅｏｒｙ  ｉｎ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ，  Ｎａｒａ，  Ｊａｐａｎ，  Ｆｅｂｒｕａｒｙ  ２６  −  Ｍａｒｃｈ  １，  ２０１３．  Ｐｒｏｃｅｅｄｉｎｇｓ，  ｐａｇｅｓ  ２３５−２５２，  ２０１３．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１〜３に記載された関数型暗号方式は、弱属性秘匿である。つまり、非特許文献１〜３に記載された関数型暗号方式は、秘密鍵の条件が満たされるような属性をもつ暗号文からは余計な情報が漏れる恐れがある。
この発明は、秘密鍵の条件が満たされるような属性をもつ暗号文から余計な情報が漏れないようにすることを目的とする。
【課題を解決するための手段】
【０００５】
この発明に係る暗号システムは、
入力パラメータＹによって定まる行列ＡＹと、行列ｅとの積が、公開パラメータＰＰから得られる複数の行列ｕのうちの行列ｕｊであって、複数の値を含む集合［Ｎ］のうちの値ｊについての行列ｕｊになる前記行列ｅを鍵要素として含む秘密鍵を、前記入力パラメータＹについての秘密鍵として生成する鍵生成装置と、
前記集合［Ｎ］に含まれる各値についての暗号要素を含む暗号文を生成する暗号化装置と、
前記暗号文に含まれる暗号要素のうちの前記値ｊについての暗号要素と、前記秘密鍵とを用いて、前記暗号文を復号する復号装置と
を備える。
【発明の効果】
【０００６】
この発明では、行列ＡＹと行列ｅとの積が、集合Ｎに含まれる値ｊについての行列ｕｊになる行列ｅを鍵要素として含む秘密鍵を生成する。これにより、秘密鍵の条件が満たされるような属性をもつ暗号文から余計な情報が漏れないようにすることが可能である。
【図面の簡単な説明】
【０００７】
【図１】実施の形態１に係る暗号システム１０の構成図。
【図２】実施の形態１に係る鍵生成装置１００の構成図。
【図３】実施の形態１に係る暗号化装置２００の構成図。
【図４】実施の形態１に係る復号装置３００の構成図。
【図５】実施の形態１に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図６】実施の形態１に係るＫｅｙＧｅｎアルゴリズムの処理を示すフローチャート。
【図７】実施の形態１に係るＥｎｃアルゴリズムの処理を示すフローチャート。
【図８】実施の形態１に係るＤｅｃアルゴリズムの処理を示すフローチャート。
【図９】実施の形態１に係る鍵生成装置１００と暗号化装置２００と復号装置３００とのハードウェア構成例を示す図。
【発明を実施するための形態】
【０００８】
実施の形態１．
実施の形態１では、まず、秘密鍵の条件が満たされるような属性をもつ暗号文から余計な情報が漏れない強属性秘匿にするためのキーテクニックを説明する。その上で、キーテクニックを適用した暗号方式を説明する。
実施の形態１では、非特許文献１に記載された関数型暗号方式に対して、キーテクニックを適用した方式について説明する。しかし、非特許文献２，３等に記載された関数型暗号方式にもキーテクニックを適用することができる。
【０００９】
＊＊＊キーテクニック＊＊＊
格子理論に基づく関数型暗号では、入力パラメータＹに関する秘密鍵生成において、入力パラメータＹによって定まる行列ＡＹと、公開パラメータＰＰから得られる行列ｕと、行列ＡＹ及び行列ｕよりもノルムが短い行列ｅとについて、行列ターゲット等式“ＡＹ・ｅ＝ｕ”を満たす行列ｅを鍵要素とする秘密鍵が生成される。
【００１０】
実施の形態１では、公開パラメータＰＰから得られる行列ｕのうち、複数の値を含む集合Ｎから選択された値ｊについての行列ｕｊを用いて、行列ターゲット等式“ＡＹ・ｅ＝ｕｊ”を満たす行列ｅを鍵要素とする秘密鍵が生成される。
暗号化する場合には、集合Ｎのうちのどの値が値ｊとして選択されたか特定できないため、集合Ｎに含まれる各値について暗号要素を含む暗号文が生成される。そして、復号する場合には、値ｊについての暗号要素と、秘密鍵とを用いて、暗号文が復号される。
【００１１】
＊＊＊構成の説明＊＊＊
図１に基づき、実施の形態１に係る暗号システム１０の構成を説明する。
暗号システム１０は、鍵生成装置１００と、暗号化装置２００と、復号装置３００とを備える。
【００１２】
鍵生成装置１００は、パラメータである１ｎと１Ｌと１Ｎとを入力として、Ｓｅｔｕｐアルゴリズムを実行して、公開パラメータＰＰと、マスター鍵ＭＫとを生成する。また、鍵生成装置１００は、公開パラメータＰＰと、マスター鍵ＭＫと、入力パラメータＹである述語ベクトルｖとを入力として、ＫｅｙＧｅｎアルゴリズムを実行して、述語ベクトルｖについての秘密鍵ｓｋｖを生成する。
なお、Ｓｅｔｕｐアルゴリズムは、システムセットアップ時等に１度実行され、ＫｅｙＧｅｎアルゴリズムは、秘密鍵ｓｋｖを生成する度に実行される。また、Ｓｅｔｕｐアルゴリズムを実行する装置と、ＫｅｙＧｅｎアルゴリズムを実行する装置とを別の装置としてもよい。
【００１３】
暗号化装置２００は、鍵生成装置１００によって生成された公開パラメータＰＰと、属性ベクトルｗと、０又は１を示す１ビットのメッセージＭとを入力として、Ｅｎｃアルゴリズムを実行して、暗号文ＣＴを生成する。
【００１４】
復号装置３００は、鍵生成装置１００によって生成された公開パラメータＰＰ及び秘密鍵ｓｋｖと、暗号化装置２００によって生成された暗号文ＣＴとを入力として、Ｄｅｃアルゴリズムを実行して、０又は１を出力する。
【００１５】
図２に基づき、実施の形態１に係る鍵生成装置１００の構成を説明する。
鍵生成装置１００は、パラメータ取得部１１０と、マスター鍵生成部１２０と、秘密鍵生成部１３０と、パラメータ公開部１４０と、秘密鍵出力部１５０とを備える。
【００１６】
パラメータ取得部１１０は、暗号システム１０の管理者によって入力された、パラメータである１ｎと１Ｌと１Ｎとを取得する。
パラメータ取得部１１０は、暗号システム１０の管理者によって入力された、述語ベクトルｖを取得する。ここでは、述語ベクトルｖは、秘密鍵ｓｋｖのユーザの属性を示す。
【００１７】
マスター鍵生成部１２０は、パラメータ取得部１１０によって取得された１ｎと１Ｌと１Ｎとを入力として、Ｓｅｔｕｐアルゴリズムを実行して、公開パラメータＰＰと、マスター鍵ＭＫとを生成する。
マスター鍵生成部１２０は、基本行列選択部１２１と、ランダム行列選択部１２２と、ランダムベクトル選択部１２３とを備える。
【００１８】
秘密鍵生成部１３０は、マスター鍵生成部１２０によって生成された公開パラメータＰＰ及びマスター鍵ＭＫと、パラメータ取得部１１０によって取得された述語ベクトルｖとを入力として、ＫｅｙＧｅｎアルゴリズムを実行して、述語ベクトルｖについての秘密鍵ｓｋｖを生成する。
秘密鍵生成部１３０は、ベクトル分解部１３１と、述語行列生成部１３２と、鍵要素生成部１３３とを備える。
【００１９】
パラメータ公開部１４０は、マスター鍵生成部１２０によって生成された公開パラメータＰＰを公開する。
ここでは、パラメータ公開部１４０は、公開パラメータＰＰを公開用のサーバに送信し、インターネット又はイントラネットでアクセス可能にすることにより、公開パラメータＰＰを公開する。公開パラメータＰＰは、暗号化装置２００及び復号装置３００に送信されるといった他の方法により公開されてもよい。
【００２０】
秘密鍵出力部１５０は、秘密鍵生成部１３０によって生成された秘密鍵ｓｋｖを秘密裡に復号装置３００に出力する。
ここでは、秘密鍵出力部１５０は、秘密鍵ｓｋｖを何らかの暗号方式で暗号化した上でネットワークを介して送信することにより、秘密鍵ｓｋｖを秘密裡に出力する。秘密鍵ｓｋｖは、記憶媒体に記憶した上で記憶媒体を復号装置３００に配送するといった他の方法により、秘密裡に復号装置３００に出力されてもよい。
【００２１】
図３に基づき、実施の形態１に係る暗号化装置２００の構成を説明する。
暗号化装置２００は、パラメータ取得部２１０と、暗号文生成部２２０と、暗号文出力部２３０とを備える。
【００２２】
パラメータ取得部２１０は、鍵生成装置１００によって生成された公開パラメータＰＰを取得する。
パラメータ取得部２１０は、暗号化装置２００のユーザによって入力された、属性ベクトルｗと、メッセージＭとを取得する。ここでは、属性ベクトルｗは、暗号文ＣＴを復号可能なユーザの属性を示す。また、ここでは、メッセージＭは、０又は１を示す１ビットの値である。
【００２３】
暗号文生成部２２０は、パラメータ取得部２１０によって取得された公開パラメータＰＰ及び属性ベクトルｗ及びメッセージＭを入力として、Ｅｎｃアルゴリズムを実行して、暗号文ＣＴを生成する。
暗号文生成部２２０は、ランダム行列選択部２２１と、乱数選択部２２２と、ノイズ選択部２２３と、暗号要素生成部２２４とを備える。
【００２４】
暗号文出力部２３０は、暗号文生成部２２０によって生成された暗号文ＣＴを復号装置３００に出力する。
ここでは、暗号文出力部２３０は、暗号文ＣＴをネットワークを介して復号装置３００に送信することにより、暗号文ＣＴを復号装置３００に出力する。暗号文ＣＴは、記憶媒体に記憶した上で記憶媒体を復号装置３００に配送するといった他の方法により、復号装置３００に出力されてもよい。
【００２５】
図４に基づき、実施の形態１に係る復号装置３００の構成を説明する。
復号装置３００は、パラメータ取得部３１０と、復号部３２０とを備える。
【００２６】
パラメータ取得部３１０は、鍵生成装置１００によって生成された公開パラメータＰＰ及び秘密鍵ｓｋｖを取得する。
パラメータ取得部３１０は、暗号化装置２００によって生成された暗号文ＣＴを取得する。
【００２７】
復号部３２０は、パラメータ取得部３１０によって取得された公開パラメータＰＰ及び秘密鍵ｓｋｖ及び暗号文ＣＴを入力として、Ｄｅｃアルゴリズムを実行して、０又は１を出力する。つまり、復号部３２０は、暗号文ＣＴを秘密鍵ｓｋｖによって復号した結果を出力する。
復号部３２０は、行列計算部３２１と、値計算部３２２と、結果出力部３２３とを備える。
【００２８】
＊＊＊動作の説明＊＊＊
図５から図８に基づき、実施の形態１に係る暗号システム１０の動作を説明する。
実施の形態１に係る暗号システム１０の動作は、実施の形態１に係る暗号方法に相当する。また、実施の形態１に係る暗号システム１０の動作は、実施の形態１に係る暗号プログラムの処理に相当する。
【００２９】
図５に基づき、実施の形態１に係るＳｅｔｕｐアルゴリズムの処理を説明する。
上述した通り、Ｓｅｔｕｐアルゴリズムは鍵生成装置１００によって実行される。
【００３０】
Ｓ１０１のパラメータ取得処理では、パラメータ取得部１１０は、Ｓｅｔｕｐアルゴリズムの入力となるパラメータ１ｎと１Ｌと１Ｎとを取得する。
ここで、ｎはセキュリティパラメータであり、１以上の整数である。Ｌは、述語ベクトルｖと属性ベクトルｗとの長さを示す１以上の整数である。Ｎは、２以上の整数である。
【００３１】
以下の説明では、ｑは２より大きい整数であり、ｍはｎより大きい整数であるとする。また、σ及びαは、正の実数ガウスパラメータであるとする。
【００３２】
Ｓ１０２の基本行列選択処理では、基本行列選択部１２１は、行列Ａ∈Ｚｑｎ×ｍを、数１１に示すようなベクトルの最大階数集合ＴＡとともに選択する。基本行列選択部１２１は、非特許文献１に記載されているＴｒａｐＧｅｎアルゴリズムを用いることにより、行列Ａとベクトルの最大階数集合ＴＡとを選択することが可能である。
【数１１】
2016162941.tif 000003
ここで、Ｔ〜Ａは、ＴＡをグラムシュミット直交化したものである。ωは、漸近的な下界を示す記号であり、ω（√ｌｏｇｍ）は、√ｌｏｇｍと同じか少し大きいという意味である。
【００３３】
Ｓ１０３のランダム行列選択処理では、ランダム行列選択部１２２は、ｉ＝１，．．．，Ｌの各整数ｉと、γ＝０，．．．，ｋの各整数γとについてのＬ・（ｋ＋１）個の一様にランダムな行列Ａｉ，γ∈Ｚｑｎ×ｍを選択する。
なお、Ｚｑとは、ｑを法とする整数空間を意味する。また、Ｚｑａにおけるａは要素数を表している。そのため、行列Ａｉ，γ∈Ｚｑｎ×ｍは、ｑを法とする整数空間におけるｎ行ｍ列の行列を意味する。
【００３４】
Ｓ１０４のランダムベクトル選択処理では、ランダムベクトル選択部１２３は、ｊ＝１，．．．，Ｎの各整数ｊについてのｊ個の一様にランダムなベクトルｕｊ∈Ｚｑｎを選択する。
【００３５】
Ｓ１０５の鍵生成処理では、マスター鍵生成部１２０は、Ｓ１０２からＳ１０４で生成された行列Ａと、Ｌ・（ｋ＋１）個の行列Ａｉ，γと、ｊ個のベクトルｕｊとを公開パラメータＰＰとする。また、マスター鍵生成部１２０は、Ｓ１０２で生成されたベクトルの集合ＴＡをマスター鍵ＭＫとする。
【００３６】
Ｓ１０６のパラメータ公開処理では、パラメータ公開部１４０は、Ｓ１０５で生成された公開パラメータＰＰを公開する。
【００３７】
図６に基づき、実施の形態１に係るＫｅｙＧｅｎアルゴリズムの処理を説明する。
上述した通り、ＫｅｙＧｅｎアルゴリズムは鍵生成装置１００によって実行される。
【００３８】
Ｓ２０１のパラメータ取得処理では、パラメータ取得部１１０は、述語ベクトルｖ：＝（ｖ１，．．．，ｖＬ）∈ＺｑＬを取得する。また、秘密鍵生成部１３０は、マスター鍵生成部１２０によって生成された公開パラメータＰＰ及びマスター鍵ＭＫを取得する。
【００３９】
Ｓ２０２のベクトル分解処理では、ベクトル分解部１３１は、ｉ＝１，．．．，Ｌの各整数ｉについての述語ベクトルｖの要素ｖｉを数１２に示すように２進分解する。
【数１２】
2016162941.tif 000004
ここで、ｖｉ，γは、０又は１である。
【００４０】
Ｓ２０３の述語行列生成処理では、述語行列生成部１３２は、Ｓ２０２で分解され生成された値ｖｉ，γと、Ｓ２０１で取得された公開パラメータＰＰに含まれる行列Ａｉ，γとを用いて、数１３に示すように行列Ｃｖと、行列Ａｖとを生成する。
【数１３】
2016162941.tif 000005
ここでは、入力パラメータＹが述語ベクトルｖであるため、行列Ａｖはキーテクニックで説明した行列ＡＹに相当する。
【００４１】
Ｓ２０４のインデックス選択処理では、鍵要素生成部１３３は、集合［Ｎ］：＝１，．．．，Ｎに含まれる値からランダムに値ｊを選択する。
【００４２】
Ｓ２０５の鍵要素生成処理では、鍵要素生成部１３３は、Ｓ２０４で選択された値ｊについて、行列Ａｖとベクトルｅとの積がベクトルｕｊとなる、つまりＡｖ・ｅ＝ｕｊ  ｍｏｄ  ｑとなるベクトルｅを計算する。
ここでは、鍵要素生成部１３３は、Ｓ２０１で取得された公開パラメータＰＰに含まれる行列Ａと、Ｓ２０３で生成された行列Ｃｖと、マスター鍵ＭＫである集合ＴＡと、公開パラメータＰＰに含まれるベクトルｕｊと、ガウスパラメータσとを入力として、ＳａｍｐｌｅＬｅｆｔアルゴリズムを実行して、ランダムにベクトルｅを計算する。なお、ＳａｍｐｌｅＬｅｆｔアルゴリズムについては、非特許文献１に記載されている。ベクトルｅが計算できるのであれば、ＳａｍｐｌｅＬｅｆｔアルゴリズム以外の方法であってもよい。
【００４３】
Ｓ２０６の秘密鍵出力処理では、秘密鍵出力部１５０は、Ｓ２０１で取得された述語ベクトルｖと、Ｓ２０４で選択された値ｊと、Ｓ２０５で計算されたベクトルｅとを鍵要素とする秘密鍵ｓｋｖを出力する。
【００４４】
図７に基づき、実施の形態１に係るＥｎｃアルゴリズムの処理を説明する。
上述した通り、Ｅｎｃアルゴリズムは暗号化装置２００によって実行される。
【００４５】
Ｓ３０１のパラメータ取得処理では、パラメータ取得部２１０は、パラメータ公開部１４０によって公開された公開パラメータＰＰを取得する。また、パラメータ取得部２１０は、属性ベクトルｗ：＝（ｗ１，．．．，ｗＬ）と、メッセージＭ∈｛０，１｝とを取得する。
【００４６】
Ｓ３０２のランダム行列選択処理では、ランダム行列選択部２２１は、一様にランダムな行列Ｂ∈Ｚｑｎ×ｍを選択する。
【００４７】
Ｓ３０３の乱数選択処理では、乱数選択部２２２は、ベクトルｓ∈Ｚｑｎをランダムに選択する。
【００４８】
Ｓ３０４のノイズ選択処理では、ノイズ選択部２２３は、確率分布φαからｍ個の要素を有するノイズベクトルＸをランダムに選択するとともに、確率分布φαからノイズ項ｘをランダムに選択する。
ここで、確率分布φαは、α∈（０，１）と，２より大きい整数ｑとに対して、平均０であり、標準偏差α／√（２π）の正規分布（ガウス分布）から実数ｘを生成し、ｑｘに最も近い整数を出力することにより得られたＺｑ：＝Ｚ／ｑＺ上の確率分布である。
【００４９】
Ｓ３０５のｃ０生成処理では、暗号要素生成部２２４は、Ｓ３０１で取得された公開パラメータＰＰに含まれる行列Ａと、Ｓ３０３で選択されたベクトルｓと、Ｓ３０４で生成されたノイズベクトルＸとを用いて、ｃ０：＝ＡＴｓ＋Ｘのように、行列ｃ０を計算する。
【００５０】
Ｓ３０６のｃｉ，γ生成処理では、暗号要素生成部２２４は、ｉ＝１，．．．，Ｌの各整数ｉと、γ＝０，．．．，ｋの各整数γとについて、以下の（ａ）（ｂ）を実行する。
（ａ）暗号要素生成部２２４は、ランダムな行列Ｒｉ，γ∈｛０，１｝ｍ×ｍを選択する。（ｂ）暗号要素生成部２２４は、Ｓ３０１で取得された公開パラメータＰＰに含まれる行列Ａｉ，γと、Ｓ３０１で取得された属性ベクトルｗと、Ｓ３０２で選択された行列Ｂと、Ｓ３０３で選択されたベクトルｓと、Ｓ３０４で生成されたノイズベクトルＸとを用いて、ｃｉ，γ：＝（Ａｉ，γ＋２γｗｉＢ）Ｔｓ＋Ｒｉ，γＴＸのように、行列ｃｉ，γを計算する。
【００５１】
Ｓ３０７のｃ’ｊ生成処理では、暗号要素生成部２２４は、ｊ＝１，．．．，Ｎの各整数ｊについて、Ｓ３０１で取得された公開パラメータＰＰに含まれるベクトルｕｊと、Ｓ３０３で選択されたベクトルｓと、Ｓ３０４で選択されたノイズ項ｘと、Ｓ３０１で取得されたメッセージＭとを用いて、ｃ’ｊ：＝ｕｊＴｓ＋ｘ＋Ｍ・“２／ｑ”∈Ｚｑのように、行列ｃ’ｊを計算する。つまり、暗号要素生成部２２４は、集合［Ｎ］に含まれる各値について、行列ｃ’ｊを計算する。
ここで、“２／ｑ”は、２／ｑに最も近い整数を意味する。
【００５２】
Ｓ３０８の暗号文出力処理では、暗号文出力部２３０は、Ｓ３０５で計算された行列ｃ０と、Ｓ３０６で計算された行列ｃｉ，γと、Ｓ３０７で計算された行列ｃ’ｊとを暗号要素とする暗号文ＣＴを出力する。
【００５３】
図８に基づき、実施の形態１に係るＤｅｃアルゴリズムの処理を説明する。
上述した通り、Ｄｅｃアルゴリズムは復号装置３００によって実行される。
【００５４】
Ｓ４０１のパラメータ取得処理では、パラメータ取得部３１０は、パラメータ公開部１４０によって公開された公開パラメータＰＰを取得する。また、パラメータ取得部３１０は、秘密鍵出力部１５０によって出力された秘密鍵ｓｋｖを取得する。また、パラメータ取得部３１０は、暗号文出力部２３０によって出力された暗号文ＣＴを取得する。
【００５５】
Ｓ４０２の行列計算処理では、行列計算部３２１は、Ｓ４０１で取得された秘密鍵ｓｋｖに含まれる述語ベクトルｖと、Ｓ４０１で取得された暗号文ＣＴに含まれる行列ｃｉ，γとを用いて、数１４に示すように、行列ｃｖを計算する。
【数１４】
2016162941.tif 000006
【００５６】
Ｓ４０３の値計算処理では、値計算部３２２は、暗号文ＣＴに含まれる行列ｃ０と、Ｓ４０２で計算された行列ｃｖとを連接して行列ｃを計算する。つまり、値計算部３２２は、ｃ：＝［ｃ０｜｜ｃｖ］とする。
そして、値計算部３２２は、暗号文ＣＴに含まれる行列ｃ’ｊと、秘密鍵ｓｋｖに含まれるベクトルｅと、行列ｃとを用いて、ｚ：＝ｃ’ｊ−ｅＴｃ  ｍｏｄ  ｑのように、値ｚを計算する。
【００５７】
Ｓ４０４の結果出力処理では、結果出力部３２３は、Ｓ４０３で計算された値ｚの絶対値｜ｚ｜が、ｑ／４よりも小さいなら０を出力し、そうでないなら、１を出力する。
【００５８】
ノイズベクトルＸとノイズ項ｘとを“ｎｏｉｓｅ”と表記する。すると、述語ベクトルｖと属性ベクトルｗとの内積が０（ｖ・ｗ＝０）なら、ｃｖ：＝Σｉ＝１ＬΣγ＝０ｋｖｉ，γｃｉ，γ＝ＣｖＴｓ＋ｎｏｉｓｅである。そのため、ｃ：＝［ｃ０｜｜ｃｖ］＝［Ａ｜｜Ｃｖ］Ｔｓ＋ｎｏｉｓｅ＝ＡｖＴｓ＋ｎｏｉｓｅである。Ａｖ・ｅ＝ｕｊなので、ｅＴｃ＝ｅＴＡｖＴｓ＋ｎｏｉｓｅ＝ｕＴｓ＋ｎｏｉｓｅである。したがって、ｚ＝Ｍ・“ｑ／２”＋ｎｏｉｓｅである。ここで、“２／ｑ”は、２／ｑに最も近い整数である。
メッセージＭは０又は１であり、ｎｏｉｓｅはφαから選択されたものであり、小さい値である。そのため、絶対値｜ｚ｜が、ｑ／４よりも小さいなら、メッセージＭは０であり、そうでないなら、メッセージＭは１であるということができる。
【００５９】
＊＊＊効果の説明＊＊＊
以上のように、実施の形態１に係る暗号システム１０は、格子理論に基づく関数型暗号方式を実現する。特に、実施の形態１に係る暗号システム１０は、複数の値を含む集合Ｎから選択された値ｊについての行列ｕｊを用いて、行列ターゲット等式“Ａｖ・ｅ＝ｕｊ”を満たすベクトルｅを鍵要素とする秘密鍵ｓｋｖ生成する。
これにより、秘密鍵の条件が満たされるような属性をもつ暗号文から余計な情報が漏れないようにすることが可能である。
【００６０】
なお、上記関数型暗号方式では、ｅ及びｕｊがベクトルであった。しかし、キーテクニックを適用するアルゴリズムによっては、ｅ及びｕｊは行列になる。
【００６１】
また、上記説明では、行列ＡＹと行列ｅと行列ｕｊとについて、行列ターゲット等式ＡＹ・ｅ＝ｕｊを満たす行列ｅを鍵要素とする秘密鍵を生成するとした。しかし、行列ＡＹと行列ｅと行列ｕｊとは、関数空間の要素と読み替えてもよい。また、行列ＡＹと行列ｅと行列ｕｊとは、無限次元ベクトルと読み替えてもよい。
【００６２】
また、上記説明では、行列ｅは、行列ＡＹに比べてノルムが短いとした。
行列ｅは、ＳａｍｐｌｅＬｅｆｔアルゴリズムによって計算される。ＳａｍｐｌｅＬｅｆｔアルゴリズムでは、行列ｅは、ガウス分布ＤΛ，σからサンプリングして選択される。そのため、行列ｅは、ほぼガウス分布ＤΛ，σに従って分布している。
この場合、標準偏差値σが実質的な分布の幅を２σ√（ｍ＋ｍ１）に定めている。標準偏差値σは、大体、Ｏ（√（ｎ・（ｍ＋ｍ１））・ｌｏｇｑ・ｌｏｇ（ｍ＋ｍ１））と同じくらいである。そのため、行列ｅの長さも、適当な定数ｃを使って、ほぼｃ√（ｎ・（ｍ＋ｍ１））・ｌｏｇｑ・ｌｏｇ（ｍ＋ｍ１）である。なお、ｍ１は、正の整数である。
【００６３】
図９は、実施の形態１に係る鍵生成装置１００と暗号化装置２００と復号装置３００とのハードウェア構成例を示す図である。
鍵生成装置１００と暗号化装置２００と復号装置３００とはコンピュータである。
鍵生成装置１００と暗号化装置２００と復号装置３００とは、プロセッサ９０１、補助記憶装置９０２、メモリ９０３、通信装置９０４、入力インタフェース９０５、ディスプレイインタフェース９０６といったハードウェアを備える。
プロセッサ９０１は、信号線９１０を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
入力インタフェース９０５は、ケーブル９１１により入力装置９０７に接続されている。
ディスプレイインタフェース９０６は、ケーブル９１２によりディスプレイ９０８に接続されている。
【００６４】
プロセッサ９０１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。プロセッサ９０１は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
補助記憶装置９０２は、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、フラッシュメモリ、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。
メモリ９０３は、例えば、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。
通信装置９０４は、データを受信するレシーバー９０４１及びデータを送信するトランスミッター９０４２を含む。通信装置９０４は、例えば、通信チップ又はＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）である。
入力インタフェース９０５は、入力装置９０７のケーブル９１１が接続されるポートである。入力インタフェース９０５は、例えば、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）端子である。
ディスプレイインタフェース９０６は、ディスプレイ９０８のケーブル９１２が接続されるポートである。ディスプレイインタフェース９０６は、例えば、ＵＳＢ端子又はＨＤＭＩ（登録商標）（Ｈｉｇｈ  Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）端子である。
入力装置９０７は、例えば、マウス、キーボード又はタッチパネルである。
ディスプレイ９０８は、例えば、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）である。
【００６５】
パラメータ取得部１１０と、パラメータ公開部１４０と、秘密鍵出力部１５０と、パラメータ取得部２１０と、暗号文出力部２３０と、パラメータ取得部３１０とは、通信装置９０４によって実現される。パラメータ取得部１１０と、パラメータ取得部２１０と、パラメータ取得部３１０とは、入力インタフェース９０５によって実現されてもよい。
結果出力部３２３は、ディスプレイインタフェース９０６によって実現される。
【００６６】
補助記憶装置９０２には、上述したマスター鍵生成部１２０と、基本行列選択部１２１と、ランダム行列選択部１２２と、ランダムベクトル選択部１２３と、秘密鍵生成部１３０と、ベクトル分解部１３１と、述語行列生成部１３２と、鍵要素生成部１３３と、暗号文生成部２２０と、ランダム行列選択部２２１と、乱数選択部２２２と、ノイズ選択部２２３と、暗号要素生成部２２４と、復号部３２０と、行列計算部３２１と、値計算部３２２と（以下、マスター鍵生成部１２０と、基本行列選択部１２１と、ランダム行列選択部１２２と、ランダムベクトル選択部１２３と、秘密鍵生成部１３０と、ベクトル分解部１３１と、述語行列生成部１３２と、鍵要素生成部１３３と、暗号文生成部２２０と、ランダム行列選択部２２１と、乱数選択部２２２と、ノイズ選択部２２３と、暗号要素生成部２２４と、復号部３２０と、行列計算部３２１と、値計算部３２２とをまとめて「部」と表記する）の機能を実現するプログラムが記憶されている。
このプログラムは、メモリ９０３にロードされ、プロセッサ９０１に読み込まれ、プロセッサ９０１によって実行される。
更に、補助記憶装置９０２には、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）も記憶されている。
そして、ＯＳの少なくとも一部がメモリ９０３にロードされ、プロセッサ９０１はＯＳを実行しながら、「部」の機能を実現するプログラムを実行する。
図９では、１つのプロセッサ９０１が図示されているが、鍵生成装置１００と暗号化装置２００と復号装置３００とが複数のプロセッサ９０１を備えていてもよい。そして、複数のプロセッサ９０１が「部」の機能を実現するプログラムを連携して実行してもよい。
また、「部」の処理の結果を示す情報やデータや信号値や変数値が、メモリ９０３、補助記憶装置９０２、又は、プロセッサ９０１内のレジスタ又はキャッシュメモリにファイルとして記憶される。
【００６７】
「部」を「サーキットリー」で提供してもよい。また、「部」を「回路」又は「工程」又は「手順」又は「処理」に読み替えてもよい。「回路」及び「サーキットリー」は、プロセッサ９０１だけでなく、ロジックＩＣ又はＧＡ（Ｇａｔｅ  Ａｒｒａｙ）又はＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）又はＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）といった他の種類の処理回路をも包含する概念である。
【符号の説明】
【００６８】
１０  暗号システム、１００  鍵生成装置、１１０  パラメータ取得部、１２０  マスター鍵生成部、１２１  基本行列選択部、１２２  ランダム行列選択部、１２３  ランダムベクトル選択部、１３０  秘密鍵生成部、１３１  ベクトル分解部、１３２  述語行列生成部、１３３  鍵要素生成部、１４０  パラメータ公開部、１５０  秘密鍵出力部、２００  暗号化装置、２１０  パラメータ取得部、２２０  暗号文生成部、２２１  ランダム行列選択部、２２２  乱数選択部、２２３  ノイズ選択部、２２４  暗号要素生成部、２３０  暗号文出力部、３００  復号装置、３１０  パラメータ取得部、３２０  復号部、３２１  行列計算部、３２２  値計算部、３２３  結果出力部。
【図１】
2016162941.tif 000012
【図２】
2016162941.tif 000013
【図３】
2016162941.tif 000014
【図４】
2016162941.tif 000015
【図５】
2016162941.tif 000016
【図６】
2016162941.tif 000017
【図７】
2016162941.tif 000018
【図８】
2016162941.tif 000019
【図９】
2016162941.tif 000020
【手続補正書】
【提出日】平成29年2月15日(2017.2.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力パラメータＹによって定まる行列ＡＹと、行列ｅとの積が、公開パラメータＰＰから得られる複数の行列ｕのうちの行列ｕｊであって、複数の値を含む集合［Ｎ］のうちの値ｊについての行列ｕｊになる前記行列ｅを鍵要素として含む秘密鍵を、前記入力パラメータＹについての秘密鍵として生成する鍵生成装置と、
前記集合［Ｎ］に含まれる各値についての暗号要素を含む暗号文を生成する暗号化装置と、
前記暗号文に含まれる暗号要素のうちの前記値ｊについての暗号要素と、前記秘密鍵とを用いて、前記暗号文を復号する復号装置と
を備える暗号システム。
【請求項２】
前記行列ｅは、前記行列ＡＹ及び行列ｕｊよりもノルムが短い
請求項１に記載の暗号システム。
【請求項３】
前記各値についての暗号要素は、その値についての行列ｕを用いて生成された
請求項１又は２に記載の暗号システム。
【請求項４】
前記行列ＡＹは、前記入力パラメータＹである述語ベクトルｖが設定された行列Ａｖであり、
前記暗号化装置は、前記各値についての暗号要素に加えて、属性ベクトルｗを設定した暗号要素を含む暗号文を生成する
請求項１から３までのいずれか１項に記載の暗号システム。
【請求項５】
前記鍵生成装置は、数１に示す行列ｅを前記鍵要素として生成し、
前記暗号化装置は、数２に示すｃ０と、数３に示すｃｉ，γと、数４に示すｃ’ｊとを前記暗号要素として生成し、
前記復号装置は、数５に示す計算をして、前記暗号文を復号する
請求項４に記載の暗号システム。
【数１】
2016162941.tif 000021
【数２】
2016162941.tif 000022
【数３】
2016162941.tif 000023
【数４】
2016162941.tif 000024
【数５】
2016162941.tif 000025
【請求項６】
入力パラメータＹと公開パラメータＰＰとを取得するパラメータ取得部と、
前記パラメータ取得部が取得した入力パラメータＹによって定まる行列ＡＹと、行列ｅとの積が、公開パラメータＰＰから得られる複数の行列ｕのうちの行列ｕｊであって、複数の値を含む集合［Ｎ］のうちの値ｊについての行列ｕｊになる前記行列ｅを秘密鍵の鍵要素として生成する秘密鍵生成部と
を備える鍵生成装置。
【国際調査報告】
2016162941.tif 000026
2016162941.tif 000027