(57)【特許請求の範囲】
【請求項１】
平文μが設定された暗号要素Ｃと、属性ｘが設定された暗号要素Ｃｘと、前記平文μが設定され、前記属性ｘが満たすポリシーｆに対応する復号鍵ｓｋｆによって復号されない暗号要素Ｆとを含む暗号文ｃｔを取得する暗号文取得部と、
ポリシーの集合であるポリシー集合Ｆを取得するポリシー取得部と、
前記暗号文取得部によって取得された前記暗号文ｃｔに含まれる前記暗号要素Ｃを、前記暗号要素Ｆにより、前記ポリシー取得部によって取得された前記ポリシー集合Ｆに対応する復号鍵ｓｋＦによって復号可能な暗号要素Ｃ〜に変換することにより、前記暗号文ｃｔを暗号文ｃｔ〜に変換する暗号文変換部と、
前記暗号文変換部によって変換された前記暗号文ｃｔ〜に対して準同型演算ｇを行い暗号文ｃｔ＊を生成する準同型演算部と
を備える準同型演算装置。
【請求項２】
前記暗号要素Ｆには、乱数Ｒが設定され、
前記暗号文ｃｔには、前記乱数Ｒが暗号化された暗号要素Ｄが含まれ、
前記暗号文変換部は、前記暗号要素Ｃを、前記暗号要素Ｆ及び前記暗号要素Ｄにより、前記暗号要素Ｃ〜に変換する
請求項１に記載の準同型演算装置。
【請求項３】
前記暗号文ｃｔは、数１に示す前記暗号要素Ｃと、数２に示す前記暗号要素Ｃｘと、数３に示す前記暗号要素Ｆと、数４に示す暗号要素Ｄとを含む
請求項２に記載の準同型演算装置。
【数１】
0006522263.tif 000059
【数２】
0006522263.tif 000060
【数３】
0006522263.tif 000061
【数４】
0006522263.tif 000062
【請求項４】
前記暗号変換部は、数５に示すように前記暗号要素Ｃを暗号要素Ｃ＾ｆに変換し、数６に示すように前記暗号要素Ｃ＾ｆを前記暗号要素Ｃ〜に変換する
請求項３に記載の準同型演算装置。
【数５】
0006522263.tif 000063
【数６】
0006522263.tif 000064
【請求項５】
前記準同型演算部は、前記暗号要素Ｃ〜に対して前記準同型演算ｇを行い暗号要素Ｃ＊を生成し、前記暗号要素Ｆに対して前記準同型演算ｇを行い暗号要素Ｆ＊を生成し、前記暗号要素Ｄを変換した暗号要素Ｄ〜に対して前記準同型演算ｇを行い暗号要素Ｄ＊を生成し、前記暗号要素Ｃ＊と前記暗号要素Ｆ＊と前記暗号要素Ｄ＊とを含む前記暗号文ｃｔ＊を生成する
請求項３又は４に記載の準同型演算装置。
【請求項６】
前記暗号変換部は、数７に示すように前記暗号要素Ｄを前記暗号要素Ｄ〜に変換する
請求項５に記載の準同型演算装置。
【数７】
0006522263.tif 000065
【請求項７】
前記準同型演算部は、前記暗号要素Ｃ〜に対して準同型演算ｇを行い生成された暗号要素Ｃ＊を含む前記暗号文ｃｔ＊を生成し、
前記暗号文取得部は、前記準同型演算部によって生成された前記暗号文ｃｔ＊を取得し、
前記暗号文変換部は、前記暗号文ｃｔ＊に含まれる前記暗号要素Ｃ＊を、前記暗号要素Ｆにより、前記復号鍵ｓｋＦとは異なる復号鍵ｓｋＦ’によって復号可能な暗号要素Ｃ〜に変換することにより、暗号文ｃｔ＊を暗号文ｃｔ〜に変換する
請求項１に記載の準同型演算装置。
【請求項８】
平文μが設定された暗号要素Ｃと、属性ｘが設定された暗号要素Ｃｘと、前記平文μが設定され、前記属性ｘが満たすポリシーｆに対応する復号鍵ｓｋｆによって復号されない暗号要素Ｆとを含む暗号文ｃｔを生成する暗号化装置と、
前記暗号化装置によって生成された前記暗号文ｃｔに含まれる前記暗号要素Ｃを、前記暗号要素Ｆにより、ポリシーの集合であるポリシー集合Ｆに対応する復号鍵ｓｋＦによって復号可能な暗号要素Ｃ〜に変換することにより、前記暗号文ｃｔを暗号文ｃｔ〜に変換し、変換された前記暗号文ｃｔ〜に対して準同型演算ｇを行い暗号文ｃｔ＊を生成する準同型演算装置と
を備える暗号システム。
【請求項９】
平文μが設定された暗号要素Ｃと、属性ｘが設定された暗号要素Ｃｘと、前記平文μが設定され、前記属性ｘが満たすポリシーｆに対応する復号鍵ｓｋｆによって復号されない暗号要素Ｆとを含む暗号文ｃｔを取得する暗号文取得処理と、
ポリシーの集合であるポリシー集合Ｆを取得するポリシー取得処理と、
前記暗号文取得処理によって取得された前記暗号文ｃｔに含まれる前記暗号要素Ｃを、前記暗号要素Ｆにより、前記ポリシー取得処理によって取得された前記ポリシー集合Ｆに対応する復号鍵ｓｋＦによって復号可能な暗号要素Ｃ〜に変換することにより、前記暗号文ｃｔを暗号文ｃｔ〜に変換する暗号文変換処理と、
前記暗号文変換処理によって変換された前記暗号文ｃｔ〜に対して準同型演算ｇを行い暗号文ｃｔ＊を生成する準同型演算処理と
をコンピュータに実行させる準同型演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データを暗号化したまま演算する技術に関する。
【背景技術】
【０００２】
準同型暗号とは、データを暗号化したまま演算できる暗号技術である。昨今、クラウドサービスの利用が広まりつつあるが、クラッキングとクラウドの信頼性の懸念とから、クラウドにはデータを暗号化した上で保管することが考えられる。準同型暗号は、暗号化されているデータに対して、復号することなく演算を施すことができるため、安全性を損なうことなくクラウドサービスの利用を可能とする技術である。【０００３】
準同型暗号の利便性を向上するために、指定された条件に従って復号者を柔軟に制御可能にした暗号技術が属性ベース準同型暗号である。属性ベース準同型暗号では、暗号文がある属性に関連するとともに、復号鍵がある復号許可条件に関連しており、属性が復号許可条件を満たすような鍵で暗号文を復号したときにだけ、正しい平文を得ることができる。【０００４】
非特許文献１には、属性ベース準同型暗号の初めての方式が記載されている。非特許文献１に記載された方式では、同一の属性に関する暗号文同士でしか準同型演算できないという課題がある。【０００５】
非特許文献２には、非特許文献１の課題を解決した属性ベース準同型暗号の方式が記載されている。
非特許文献２には、単一ターゲット属性ベース準同型暗号と複数ターゲット属性ベース準同型暗号と呼ばれる２つの暗号技術の構成が示されている。単一ターゲット属性ベース準同型暗号は、ある１つの復号許可条件に対して、その条件を満たす属性に関する暗号文同士であれば準同型演算を行える暗号方式である。複数ターゲット属性ベース準同型暗号は、複数の復号許可条件に対して、いずれかの条件を満たす属性に関する暗号文同士であれば準同型演算可能な暗号方式である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｃ．Ｇｅｎｔｒｙ，Ａ．Ｓａｈａｉ，ａｎｄ  Ｂ．Ｗａｔｅｒｓ．“Ｈｏｍｏｍｏｒｐｈｉｃ  Ｅｎｃｒｙｐｔｉｏｎ  ｆｒｏｍ  Ｌｅａｒｎｉｎｇ  ｗｉｔｈ  Ｅｒｒｏｒｓ：  Ｃｏｎｃｅｐｔｕａｌｌｙ−Ｓｉｍｐｌｅｒ，Ａｓｙｍｐｔｏｔｉｃａｌｌｙ−Ｆａｓｔｅｒ，Ａｔｔｒｉｂｕｔｅ−Ｂａｓｅｄ”．Ｉｎ  ＣＲＹＰＴＯ  ２０１３，ｐａｇｅｓ  ７５−９２，２０１３．
【非特許文献２】Ｚ．Ｂｒａｋｅｒｓｋｉ，Ｄ．Ｃａｓｈ，Ｒ．Ｔｓａｂａｒｙ，ａｎｄ  Ｈ．Ｗｅｅ．“Ｔａｒｇｅｔｅｄ  Ｈｏｍｏｍｏｒｐｈｉｃ  Ａｔｔｒｉｂｕｔｅ  Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ”．Ｉｎ  ＴＣＣ  ２０１６−Ｂ，ｐａｇｅｓ  ３３０−３６０，２０１６．
【非特許文献３】Ｃ．Ｐｅｉｋｅｒｔ，ａｎｄ  Ｓ．Ｓｈｉｅｈｉａｎ“Ｍｕｌｔｉ−Ｋｅｙ  ＦＨＥ  ｆｒｏｍ  ＬＷＥ，  Ｒｅｖｉｓｉｔｅｄ”  ２０１６
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献２に示されている複数ターゲット属性ベース準同型暗号では、演算対象の暗号文Ｘに対して準同型演算を行って得られる暗号文Ｙは、演算対象の暗号文Ｘを復号可能な復号許可条件の集合Ｆに関連付けられる。暗号文Ｙを用いて、再び別の準同型演算前の暗号文Ｚと準同型演算を行う際には、暗号文Ｚの復号許可条件が、暗号文Ｙが関連付けられた復号許可条件の集合Ｆに含まれていない限り、準同型演算を行うことができない。
そのため、暗号文Ｘ，Ｙ，Ｚの復号許可条件によっては、暗号文Ｘ，Ｙ，Ｚを全て事前に収集し、一度に準同型演算を行う必要がある。したがって、例えば、暗号化された時系列データについて準同型演算を行う際には、事前に演算に用いられる時系列データをすべて収集し、保持しておくための膨大な記憶容量が必要となる。
この発明は、柔軟な準同型演算を可能にすることを目的とする。
【課題を解決するための手段】
【０００８】
この発明に係る準同型演算装置は、
平文μが設定された暗号要素Ｃと、属性ｘが設定された暗号要素Ｃｘと、前記平文μが設定され、前記属性ｘが満たすポリシーｆに対応する復号鍵ｓｋｆによって復号されない暗号要素Ｆとを含む暗号文ｃｔを取得する暗号文取得部と、
ポリシーの集合であるポリシー集合Ｆを取得するポリシー取得部と、
前記暗号文取得部によって取得された前記暗号文ｃｔに含まれる前記暗号要素Ｃを、前記暗号要素Ｆにより、前記ポリシー取得部によって取得された前記ポリシー集合Ｆに対応する復号鍵ｓｋＦによって復号可能な暗号要素Ｃ〜に変換することにより、前記暗号文ｃｔを暗号文ｃｔ〜に変換する暗号文変換部と、
前記暗号文変換部によって変換された前記暗号文ｃｔ〜に対して準同型演算ｇを行い暗号文ｃｔ＊を生成する準同型演算部と
を備える。
【発明の効果】
【０００９】
この発明では、暗号要素Ｆを用いて、暗号要素Ｃを暗号要素Ｃ〜に変換する。これにより、暗号要素Ｃ内の要素をポリシー集合Ｆに関連付けてしまうことなく、準同型演算を行うことが可能になる。そのため、暗号文ｃｔ＊を入力として再び柔軟な準同型演算を行うことが可能になる。
【図面の簡単な説明】
【００１０】
【図１】実施の形態１に係る暗号システム１０の構成図。
【図２】実施の形態１に係る鍵生成装置２０の構成図。
【図３】実施の形態１に係る暗号化装置３０の構成図。
【図４】実施の形態１に係る準同型演算装置４０の構成図。
【図５】実施の形態１に係る復号装置５０の構成図。
【図６】実施の形態１に係るＳｅｔｕｐ処理のフローチャート。
【図７】実施の形態１に係るＫｅｙＧｅｎ処理のフローチャート。
【図８】実施の形態１に係るＥｎｃ処理のフローチャート。
【図９】実施の形態１に係るＥｖａｌ処理のフローチャート。
【図１０】実施の形態１に係るＤｅｃ処理のフローチャート。
【図１１】変形例１に係る鍵生成装置２０の構成図。
【図１２】変形例１に係る暗号化装置３０の構成図。
【図１３】変形例１に係る準同型演算装置４０の構成図。
【図１４】変形例１に係る復号装置５０の構成図。
【発明を実施するための形態】
【００１１】
実施の形態１．
＊＊＊構成の説明＊＊＊
図１を参照して、実施の形態１に係る暗号システム１０の構成を説明する。
暗号システム１０は、鍵生成装置２０と、暗号化装置３０と、準同型演算装置４０と、復号装置５０とを備える。
鍵生成装置２０と、暗号化装置３０と、準同型演算装置４０と、復号装置５０とは、ネットワーク６０を介して接続される。ネットワーク６０は、具体例としては、インターネットである。ネットワーク６０は、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）といった他の種類のネットワークであってもよい。
【００１２】
図２を参照して、実施の形態１に係る鍵生成装置２０の構成を説明する。
鍵生成装置２０は、コンピュータである。
鍵生成装置２０は、プロセッサ２１と、メモリ２２と、ストレージ２３と、通信インタフェース２４とのハードウェアを備える。プロセッサ２１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００１３】
鍵生成装置２０は、機能構成要素として、取得部２１１と、マスタ鍵生成部２１２と、復号鍵生成部２１３と、出力部２１４とを備える。取得部２１１と、マスタ鍵生成部２１２と、復号鍵生成部２１３と、出力部２１４との機能はソフトウェアにより実現される。
ストレージ２３には、取得部２１１と、マスタ鍵生成部２１２と、復号鍵生成部２１３と、出力部２１４との機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ２１によりメモリ２２に読み込まれ、プロセッサ２１によって実行される。これにより、取得部２１１と、マスタ鍵生成部２１２と、復号鍵生成部２１３と、出力部２１４との機能が実現される。
また、ストレージ２３は、マスタ鍵記憶部２３１の機能を実現する。
【００１４】
図３を参照して、実施の形態１に係る暗号化装置３０の構成を説明する。
暗号化装置３０は、コンピュータである。
暗号化装置３０は、プロセッサ３１と、メモリ３２と、ストレージ３３と、通信インタフェース３４とのハードウェアを備える。プロセッサ３１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００１５】
暗号化装置３０は、機能構成要素として、取得部３１１と、暗号化部３１２と、出力部３１３とを備える。取得部３１１と、暗号化部３１２と、出力部３１３との機能はソフトウェアにより実現される。
ストレージ３３には、取得部３１１と、暗号化部３１２と、出力部３１３との機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ３１によりメモリ３２に読み込まれ、プロセッサ３１によって実行される。これにより、取得部３１１と、暗号化部３１２と、出力部３１３との機能が実現される。
また、ストレージ３３は、公開パラメータ記憶部３３１の機能を実現する。
【００１６】
図４を参照して、実施の形態１に係る準同型演算装置４０の構成を説明する。
準同型演算装置４０は、コンピュータである。
準同型演算装置４０は、プロセッサ４１と、メモリ４２と、ストレージ４３と、通信インタフェース４４とのハードウェアを備える。プロセッサ４１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００１７】
準同型演算装置４０は、機能構成要素として、取得部４１１と、暗号文変換部４１２と、準同型演算部４１３と、出力部４１４とを備える。取得部４１１は、公開パラメータ取得部４１５と、暗号文取得部４１６と、ポリシー取得部４１７と、演算取得部４１８とを備える。取得部４１１と、暗号文変換部４１２と、準同型演算部４１３と、出力部４１４と、公開パラメータ取得部４１５と、暗号文取得部４１６と、ポリシー取得部４１７と、演算取得部４１８との機能はソフトウェアにより実現される。
ストレージ４３には、取得部４１１と、暗号文変換部４１２と、準同型演算部４１３と、出力部４１４と、公開パラメータ取得部４１５と、暗号文取得部４１６と、ポリシー取得部４１７と、演算取得部４１８との機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ４１によりメモリ４２に読み込まれ、プロセッサ４１によって実行される。これにより、取得部４１１と、暗号文変換部４１２と、準同型演算部４１３と、出力部４１４と、公開パラメータ取得部４１５と、暗号文取得部４１６と、ポリシー取得部４１７と、演算取得部４１８との機能が実現される。
また、ストレージ４３は、公開パラメータ記憶部４３１と、暗号文記憶部４３２との機能を実現する。
【００１８】
図５を参照して、実施の形態１に係る復号装置５０の構成を説明する。
復号装置５０は、コンピュータである。
復号装置５０は、プロセッサ５１と、メモリ５２と、ストレージ５３と、通信インタフェース５４とのハードウェアを備える。プロセッサ５１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００１９】
復号装置５０は、機能構成要素として、取得部５１１と、復号部５１２と、出力部５１３とを備える。取得部５１１と、復号部５１２と、出力部５１３との機能はソフトウェアにより実現される。
ストレージ５３には、取得部５１１と、復号部５１２と、出力部５１３との機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ５１によりメモリ５２に読み込まれ、プロセッサ５１によって実行される。これにより、取得部５１１と、復号部５１２と、出力部５１３との機能が実現される。
また、ストレージ５３は、鍵記憶部５３１と、条件記憶部５３２と、結果記憶部５３３との機能を実現する。
【００２０】
プロセッサ２１，３１，４１，５１は、演算処理を行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。プロセッサ２１，３１，４１，５１は、具体例としては、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
【００２１】
メモリ２２，３２，４２，５２は、データを一時的に記憶する記憶装置である。メモリ２２，３２，４２，５２は、具体例としては、ＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。
【００２２】
ストレージ２３，３３，４３，５３は、データを保管する記憶装置である。ストレージ２３，３３，４３，５３は、具体例としては、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。また、ストレージ２３，３３，４３，５３は、ＳＤ（登録商標，Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ）メモリカード、ＣＦ（ＣｏｍｐａｃｔＦｌａｓｈ）、ＮＡＮＤフラッシュ、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）といった可搬記憶媒体であってもよい。
【００２３】
通信インタフェース２４，３４，４４，５４は、外部の装置と通信するためのインタフェースである。通信インタフェース２４，３４，４４，５４は、具体例としては、Ｅｔｈｅｒｎｅｔ（登録商標）、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）、ＨＤＭＩ（登録商標，Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）のポートである。
【００２４】
図２では、プロセッサ２１は、１つだけ示されている。しかし、鍵生成装置２０は、プロセッサ２１を代替する複数のプロセッサを備えていてもよい。同様に、暗号化装置３０は、プロセッサ３１を代替する複数のプロセッサを備え、準同型演算装置４０は、プロセッサ４１を代替する複数のプロセッサを備え、復号装置５０は、プロセッサ５１を代替する複数のプロセッサを備えていてもよい。これら複数のプロセッサは、各機能構成要素の機能を実現するプログラムの実行を分担する。それぞれのプロセッサは、プロセッサ２１，３１，４１，５１と同じように、演算処理を行うＩＣである。
【００２５】
＊＊＊動作の説明＊＊＊
図６から図１０を参照して、実施の形態１に係る暗号システム１０の動作を説明する。
実施の形態１に係る暗号システム１０の動作は、実施の形態１に係る暗号方法に相当する。また、実施の形態１に係る暗号プログラムの処理に相当する。
暗号システム１０の動作は、Ｓｅｔｕｐ処理と、ＫｅｙＧｅｎ処理と、Ｅｎｃ処理と、Ｅｖａｌ処理と、Ｄｅｃ処理とに分けられる。
【００２６】
以下の説明では、非特許文献２に記載された内容と異なる部分を中心に説明し、非特許文献２に記載された内容と同一の部分について既に公知の内容であるため、一部説明を省略する。
【００２７】
以下の説明における符号について説明する。
ｎ，ｑ，χは、ＬＷＥ（Ｌｅａｒｎｉｎｇ  Ｗｉｔｈ  Ｅｒｒｏｒｓ）問題におけるパラメータである。ＬＷＥ問題は公知の問題である。Ｄｅｃｉｓｉｏｎａｌ  ＬＷＥ問題（ＤＬＷＥ問題）は、次のように定義される。
＜ＤＬＷＥ問題＞
λはセキュリティパラメータであり、ｎ＝ｎ（λ）とｑ＝ｑ（λ）とは整数であり、χ＝χ（λ）は整数Ｚ上の確率分布であるとする。ＤＬＷＥｎ，ｑ，χ問題は、全てのｍ＝ｐｏｌｙ（ｎ）に対して、数１１とする場合に、（Ａ，ｓＴＡ＋ｅＴ）と（Ａ，ｕＴ）とが計算的に見分けがつかないというものである。
【数１１】
0006522263.tif 000002
【００２８】
ｍ、Ｎ，Ｍ．ｇＴは、数１２に示す通りである。
【数１２】
0006522263.tif 000003
任意のｘ∈Ｚｑに対して、数１３に示すｙは、数１４を満たすベクトルである。
【数１３】
0006522263.tif 000004
【数１４】
0006522263.tif 000005
任意の自然数ｎ，ｍに対して、Ｉｎはｎ行ｎ列の単位行列であり、０ｎ×ｍは要素が全て０のｎ行ｍ列の行列である。任意のｉ∈［ｎ］に対して、ｅｉ∈｛０，１｝ｎは、ｎ要素目が１でその他が０の標準基底ベクトルである。なお、ｉ∈［ｎ］は、ｉ＝１，．．．，ｎを意味する。
Ｆ⊆｛０，１｝Ｌ→｛０，１｝は、深さｄＦのブーリアンサーキットで計算できるポリシーのクラスである。Ｇ⊆｛０，１｝＊→｛０，１｝は、深さｄＧのブーリアンサーキットで計算できる演算のクラスである。
【００２９】
図６を参照して、実施の形態１に係るＳｅｔｕｐ処理を説明する。
Ｓｅｔｕｐ処理は、暗号システム１０の初期設定時等に、主に鍵生成装置２０によって実行される。実施の形態１に係るＳｅｔｕｐ処理は、実施の形態１に係るマスタ鍵生成方法とマスタ鍵生成プログラムの処理とに相当する。
【００３０】
（ステップＳ１１：取得処理）
鍵生成装置２０の取得部２１１は、パラメータλ，Ｌ，ｄＦ，ｄＧを取得する。
具体的には、取得部２１１は、通信インタフェース２４を介して、暗号システム１０の管理者等によって入力されたパラメータλ，Ｌ，ｄＦ，ｄＧを受け付ける。取得部２１１は、受け付けられたパラメータλ，Ｌ，ｄＦ，ｄＧをメモリ２２に書き込む。
【００３１】
（ステップＳ１２：マスタ鍵生成処理）
鍵生成装置２０のマスタ鍵生成部２１２は、公開パラメータｐｐとマスタ秘密鍵ｍｓｋとのペアを生成する。
具体的には、マスタ鍵生成部２１２は、数１５に示すように、行列ＡとトラップドアＡτ０−１とのペア（Ａ，Ａτ０−１）を生成する。
【数１５】
0006522263.tif 000006
ＴｒａｐＧｅｎアルゴリズムは非特許文献２に記載されている。ここで、行列Ａは数１６に示す行列であり、トラップドアＡτ０−１は数１７に示すアルゴリズムである。
【数１６】
0006522263.tif 000007
【数１７】
0006522263.tif 000008
【００３２】
マスタ鍵生成部２１２は、数１８に示すように、行列Ｂ，Ｂ０，Ｂ１，．．．，ＢＬを生成し、Ｂ→ｘを定義する。
【数１８】
0006522263.tif 000009
【００３３】
マスタ鍵生成部２１２は、数１９に示すように、ベクトルｖとＰＲＦ（ＰｓｅｕｄｏＲａｎｄｏｍ  Ｆｕｎｃｔｉｏｎ）のシードσとを生成する。
【数１９】
0006522263.tif 000010
ＰＲＦ．Ｇｅｎアルゴリズムは非特許文献２に記載されている。
【００３４】
マスタ鍵生成部２１２は、（Ａ，Ｂ０，Ｂ→ｘ，Ｂ，ｖ）を公開パラメータｐｐとし、（Ａτ０−１，σ）をマスタ秘密鍵ｍｓｋとする。マスタ鍵生成部２１２は、公開パラメータｐｐをメモリ２２に書き込むとともに、公開パラメータｐｐ及びマスタ秘密鍵ｍｓｋをマスタ鍵記憶部２３１に書き込む。
【００３５】
（ステップＳ１３：出力処理）
鍵生成装置２０の出力部２１４は、公開パラメータｐｐを出力する。
具体的には、出力部２１４は、メモリ２２から公開パラメータｐｐを読み出す。そして、出力部２１４は、通信インタフェース２４を介して、公開パラメータｐｐを暗号化装置３０と準同型演算装置４０と復号装置５０とに送信する。
【００３６】
（ステップＳ１４：公開パラメータ取得処理）
暗号化装置３０の取得部３１１と、準同型演算装置４０の公開パラメータ取得部４１５と、復号装置５０の取得部５１１とは、公開パラメータｐｐを取得する。
具体的には、取得部３１１は、通信インタフェース３４を介して、出力部２１４によって送信された公開パラメータｐｐを受信する。取得部３１１は、受信された公開パラメータｐｐを公開パラメータ記憶部３３１に書き込む。
また、準同型演算装置４０の公開パラメータ取得部４１５は、通信インタフェース４４を介して、出力部２１４によって送信された公開パラメータｐｐを受信する。公開パラメータ取得部４１５は、受信された公開パラメータｐｐを公開パラメータ記憶部４３１に書き込む。
また、復号装置５０の取得部５１１は、通信インタフェース５４を介して、出力部２１４によって送信された公開パラメータｐｐを受信する。取得部５１１は、受信された公開パラメータｐｐを鍵記憶部５３１に書き込む。
【００３７】
つまり、鍵生成装置２０は、数２０に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｐとマスタ秘密鍵ｍｓｋとを生成する。
【数２０】
0006522263.tif 000011
【００３８】
図７を参照して、実施の形態１に係るＫｅｙＧｅｎ処理を説明する。
ＫｅｙＧｅｎ処理は、新たな復号鍵ｓｋｆを生成する際に、主に鍵生成装置２０によって実行される。実施の形態１に係るＫｅｙＧｅｎ処理は、実施の形態１に係る復号鍵生成方法と復号鍵生成プログラムの処理とに相当する。
【００３９】
（ステップＳ２１：復号鍵依頼処理）
復号装置５０の取得部５１１は、復号鍵ｓｋｆの生成を鍵生成装置２０に依頼する。
具体的には、取得部５１１は、復号装置５０の利用者等によって入力された復号許可条件を示すポリシーｆを受け付ける。ポリシーｆは、例えば、利用者の属性が設定される。そして、取得部５１１は、入力されたポリシーｆを鍵生成装置２０に送信して、ポリシーｆに関連付けられた復号鍵ｓｋｆの生成を要求する。
取得部５１１は、復号鍵ｓｋｆの生成を要求した際に送信されたポリシーｆを条件記憶部５３２に書き込む。
【００４０】
（ステップＳ２２：取得処理）
鍵生成装置２０の取得部２１１は、ポリシーｆを取得する。
具体的には、取得部２１１は、通信インタフェース２４を介して、復号装置５０から送信されたポリシーｆを受信する。取得部２１１は、受信されたポリシーｆをメモリ２２に書き込む。
【００４１】
（ステップＳ２３：復号鍵生成処理）
鍵生成装置２０の復号鍵生成部２１３は、ポリシーｆに関連付けられた復号鍵ｓｋｆを生成する。
具体的には、復号鍵生成部２１３は、メモリ２２からポリシーｆを読み出し、マスタ鍵記憶部２３１から公開パラメータｐｐ及びマスタ秘密鍵ｍｓｋを読み出す。復号鍵生成部２１３は、数２１に示すように、行列Ｂｆを計算する。
【数２１】
0006522263.tif 000012
Ｅｖａｌアルゴリズムは非特許文献２に記載されている。
【００４２】
復号鍵生成部２１３は、ランダムオラクルにクエリして行列ｒ’ｆ＝Ｏ（Ａ，ｆ）∈｛０，１｝Ｎを得る。つまり、復号鍵生成部２１３は、ランダムな行列ｒ’ｆを生成する。復号鍵生成部２１３は、数２２に示すように、行列ｒｆを生成する。
【数２２】
0006522263.tif 000013
ここで、τは数２３に示す通りである。
【数２３】
0006522263.tif 000014
このとき、トラップドアＡτ０−１は数１７に示すアルゴリズムであるから、数２４が成立する。
【数２４】
0006522263.tif 000015
復号鍵生成部２１３は、行列ｒｆを復号鍵ｓｋｆとしてメモリ２２に書き込む。
【００４３】
（ステップＳ２４：出力処理）
鍵生成装置２０の出力部２１４は、復号鍵ｓｋｆを出力する。
具体的には、出力部２１４は、メモリ２２から復号鍵ｓｋｆを読み出す。そして、出力部２１４は、通信インタフェース２４を介して、復号鍵ｓｋｆを復号装置５０に送信する。
【００４４】
（ステップＳ２５：復号鍵取得処理）
復号装置５０の取得部５１１は、復号鍵ｓｋｆを取得する。
具体的には、取得部５１１は、通信インタフェース５４を介して、出力部２１４によって送信された復号鍵ｓｋｆを受信する。取得部５１１は、受信された復号鍵ｓｋｆを鍵記憶部５３１に書き込む。
【００４５】
つまり、鍵生成装置２０は、数２５に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋｆを生成する。
【数２５】
0006522263.tif 000016
【００４６】
図８を参照して、実施の形態１に係るＥｎｃ処理を説明する。
Ｅｎｃ処理は、暗号文ｃｔを生成する際に、主に暗号化装置３０によって実行される。実施の形態１に係るＥｎｃ処理は、実施の形態１に係る暗号化方法と暗号化プログラムの処理とに相当する。
【００４７】
（ステップＳ３１：取得処理）
暗号化装置３０の取得部３１１は、平文μと、属性ｘとを取得する。
具体的には、取得部３１１は、通信インタフェース３４を介して、暗号化装置３０の利用者等によって入力された平文μと属性ｘとを受け付ける。平文μは、暗号化した上で送信するメッセージであり、平文μ∈｛０，１｝である。属性ｘは、暗号文に関連付けられる属性であり、属性ｘ∈｛０，１｝Ｌである。取得部３１１は、平文μと属性ｘとをメモリ３２に書き込む。
【００４８】
（ステップＳ３２：暗号化処理）
暗号化装置３０の暗号化部３１２は、属性ｘを設定して平文μを暗号化した暗号文ｃｔを生成する。
具体的には、暗号化部３１２は、公開パラメータ記憶部３３１から公開パラメータｐｐを読み出すとともに、メモリ３２から平文μと属性ｘとを読み出す。暗号化部３１２は、数２６に示すように、行列Ｓと行列ＥＡとエラーベクトルｅｖとを生成する。
【数２６】
0006522263.tif 000017
【００４９】
暗号化部３１２は、数２７に示すように、ｉ∈｛０，１，．．．，Ｌ｝の各整数ｉと、ｊ∈［Ｍ］の各整数ｊとについて、行列Ｒｉ，ｊを生成する。
【数２７】
0006522263.tif 000018
暗号化部３１２は、数２８に示すように、ｉ∈｛０，１，．．．，Ｌ｝の各整数ｉと、ｊ∈［Ｍ］の各整数ｊとについて、行列Ｅｉ［ｊ］を生成する。ここで、Ｅｉ［ｊ］及びＥＡ［ｊ］は、それぞれ行列Ｅｉ及び行列ＥＡのｊ列目を示す。
【数２８】
0006522263.tif 000019
【００５０】
暗号化部３１２は、数２９に示すように行列Ｃを生成し、数３０に示すように行列Ｃｘを生成する。
【数２９】
0006522263.tif 000020
【数３０】
0006522263.tif 000021
行列Ｃには、平文μが設定されており、属性ｘが満たすポリシーｆに対応する復号鍵ｓｋｆによって復号可能な構成になっている。
ここで、数３１は、テンソル積を示す。
【数３１】
0006522263.tif 000022
また、数３２である。
【数３２】
0006522263.tif 000023
【００５１】
暗号化部３１２は、数３３に示すように、行列Ｒと行列ＥＦとを生成する。
【数３３】
0006522263.tif 000024
暗号化部３１２は、数３４に示すように、行列Ｆを生成する。
【数３４】
0006522263.tif 000025
数３４に示すように、行列Ｆには、平文μと乱数である行列Ｒとが設定されている。行列Ｆは、行列に含まれる行列Ｂ０に代えて行列Ｂが含まれており、属性ｘが満たすポリシーｆに対応する復号鍵ｓｋｆによって復号されない構成になっている。
【００５２】
暗号化部３１２は、数３５に示すように、ｉ∈｛０，１，．．．，Ｌ｝の各整数ｉと、ｊ∈［Ｍ］の各整数ｊと、ｋ∈［Ｎ］の各整数ｋとについて、行列Ｅ（ｋ）Ａと、ベクトルｅ（ｋ）ｖと、行列Ｒ（ｋ）ｉ，ｊとを生成する。
【数３５】
0006522263.tif 000026
暗号化部３１２は、数３６に示すように、ベクトルＥ（ｋ）ｉと行列Ｅ（ｋ）とを生成する。ここで、Ｅ（ｋ）ｉ［ｊ］及び行列Ｅ（ｋ）Ａ［ｊ］は、それぞれ行列Ｅ（ｋ）ｉ及び行列Ｅ（ｋ）Ａのｊ列目を示す。
【数３６】
0006522263.tif 000027
暗号化部３１２は、数３７に示すように、行列Ｓ（１），．．．，Ｓ（Ｎ）を生成する。
【数３７】
0006522263.tif 000028
暗号化部３１２は、数３８に示すように行列Ｄを生成し、数３９に示すように行列Ｄ（ｋ）ｘを生成する。
【数３８】
0006522263.tif 000029
【数３９】
0006522263.tif 000030
つまり、行列Ｄは、行列Ｆに含まれる乱数である行列Ｒが暗号化されている。
【００５３】
暗号化部３１２は、属性ｘと、行列Ｃと、行列Ｃｘと、行列Ｆと、行列Ｄと、ｋ∈［Ｎ］の各整数ｋについての行列Ｄ（ｋ）ｘとを暗号要素とする暗号文ｃｔを、メモリ３２に書き込む。つまり、暗号文ｃｔには、平文μが設定された暗号要素である行列Ｃと、属性ｘが設定された暗号要素である行列Ｃｘと、平文μと乱数である行列Ｒとが設定され、属性ｘが満たすポリシーｆに対応する復号鍵ｓｋｆによって復号されない暗号要素である行列Ｆと、乱数である行列Ｒが暗号化された暗号要素である行列Ｄとが含まれる。
【００５４】
（ステップＳ３３：出力処理）
暗号化装置３０の出力部３１３は、暗号文ｃｔを出力する。
具体的には、出力部３１３は、メモリ３２から暗号文ｃｔを読み出す。そして、出力部３１３は、通信インタフェース３４を介して、暗号文ｃｔを準同型演算装置４０に送信する。
【００５５】
（ステップＳ３４：暗号文取得処理）
準同型演算装置４０の暗号文取得部４１６は、通信インタフェース４４を介して、出力部３１３によって送信された暗号文ｃｔを受信する。暗号文取得部４１６は、受信された暗号文ｃｔを暗号文記憶部４３２に書き込む。
【００５６】
つまり、暗号化装置３０は、数４０から数４１に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔを生成する。
【数４０】
0006522263.tif 000031
【数４１】
0006522263.tif 000032
【００５７】
図９を参照して、実施の形態１に係るＥｖａｌ処理を説明する。
Ｅｖａｌ処理は、暗号文ｃｔに対して準同型演算を行う際に、準同型演算装置４０によって実行される。実施の形態１に係るＥｖａｌ処理は、実施の形態１に係る準同型演算方法と準同型演算プログラムの処理とに相当する。
【００５８】
（ステップＳ４１：暗号文取得処理）
暗号文取得部４１６は、演算対象の暗号文ｃｔ（１），．．．，ｃｔ（ｋ）を取得する。ここで、ｋは１以上の整数である。
具体的には、暗号文取得部４１６は、通信インタフェース４４を介して、準同型演算装置４０の利用者等によって指定された暗号文ｃｔ（１），．．．，ｃｔ（ｋ）を暗号文記憶部４３２から読み出す。暗号文取得部４１６は、読み出された暗号文ｃｔ（１），．．．，ｃｔ（ｋ）をメモリ４２に書き込む。
【００５９】
（ステップＳ４２：ポリシー取得処理）
準同型演算装置４０のポリシー取得部４１７は、ポリシーの集合であるポリシー集合Ｆ：＝｛ｆ１，．．．，ｆｄ｝を取得する。ここで、ｄは、１以上の整数である。
具体的には、ポリシー取得部４１７は、通信インタフェース４４を介して、準同型演算装置４０の利用者等によって入力されたポリシー集合Ｆを受け付ける。ポリシー取得部４１７は、受け付けられたポリシー集合Ｆをメモリ４２に書き込む。
なお、準同型演算を行うためには、ステップＳ４１で読み出されたｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ（ｉ）が、ポリシー集合Ｆに含まれるいずれかのｆ１，．．．，ｆｄを満たす必要がある。言い換えると、ｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ（ｉ）が、いずれかのｆ１，．．．，ｆｄに関連付けられた復号鍵ｓｋｆで復号可能である必要がある。つまり、ｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ（ｉ）に設定された属性を属性ｘｉとすると、ｉ＝１，．．．，ｋの各整数ｉについて、あるｊ∈［ｄ］に対して、ｆｊ（ｘｉ）＝０を満たす必要がある。
【００６０】
（ステップＳ４３：演算取得処理）
準同型演算装置４０の演算取得部４１８は、実行する準同型演算ｇを取得する。
具体的には、演算取得部４１８は、通信インタフェース４４を介して、準同型演算装置４０の利用者等によって入力された準同型演算ｇを受け付ける。演算取得部４１８は、受け付けられた準同型演算ｇをメモリ４２に書き込む。
【００６１】
（ステップＳ４４：暗号文変換処理）
準同型演算装置４０の暗号文変換部４１２は、ｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ（ｉ）を暗号文ｃｔ（ｉ）〜：＝（Ｃ〜，Ｆ〜，Ｄ〜）に変換する。
具体的には、暗号文変換部４１２は、ｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ（ｉ）を対象として、まずＡｐｐｌｙアルゴリズムを実行し、その後Ｅｘｐａｎｓｉｏｎアルゴリズムを実行する。但し、Ａｐｐｌｙアルゴリズムは、１度も準同型演算が行われていない暗号文ｃｔ（ｉ）についてのみ実行される。つまり、暗号文ｃｔ（ｉ）が暗号化装置３０によって生成され、図８のステップＳ３３で出力された暗号文ｃｔである場合には、Ａｐｐｌｙアルゴリズムは実行され、暗号文ｃｔ（ｉ）が後述するステップＳ４６で出力された暗号文ｃｔ＊である場合には、Ａｐｐｌｙアルゴリズムは実行されない。暗号文ｃｔ（ｉ）が後述するステップＳ４６で出力された暗号文ｃｔ＊である場合には、Ｅｘｐａｎｓｉｏｎアルゴリズムだけが実行される。
ここでは、表記の簡略化のため、対象とする暗号文ｃｔ（ｉ）を暗号文ｃｔと書き、暗号文ｃｔ（ｉ）が変換された暗号文ｃｔ（ｉ）〜を暗号文ｃｔ〜と書く。また、対象とする暗号文ｃｔ（ｉ）が満たすポリシーｆｊをポリシーｆと書く。
【００６２】
Ａｐｐｌｙアルゴリズムについて説明する。
暗号文変換部４１２は、数４２に示すように、行列Ｈを計算する。
【数４２】
0006522263.tif 000033
ＥｖＲｅｌａｔｉｏｎアルゴリズムは非特許文献２に記載されている。
【００６３】
暗号文変換部４１２は、行列Ｃｆ：＝ＨＴＣｘを生成する。暗号文変換部４１２は、数４３に示すように、行列Ｃ＾ｆを生成する。
【数４３】
0006522263.tif 000034
【００６４】
暗号文変換部４１２は、ｉ∈［ｋ］の各整数ｉについて、数４４に示すように、行列Ｄ（ｉ）ｆを生成する。
【数４４】
0006522263.tif 000035
暗号文変換部４１２は、数４５に示すように、行列Ｄｆを生成する。
【数４５】
0006522263.tif 000036
暗号文変換部４１２は、行列Ｄ＾ｆ：＝Ｄｆ＋Ｄを生成する。
【００６５】
つまり、暗号文変換部４１２は、数４６に示すＡｐｐｌｙアルゴリズムを実行する。
【数４６】
0006522263.tif 000037
【００６６】
Ｅｘｐａｎｓｉｏｎアルゴリズムについて説明する。
ここで、対象とする暗号文ｃｔ（ｉ）が後述するステップＳ４６で出力された暗号文ｃｔ＊：＝（Ｃ＊，Ｆ＊，Ｄ＊）である場合には、Ｃ＾ｆ：＝Ｃ＊，Ｆ：＝Ｆ＊，Ｄ＾ｆ：＝Ｄ＊とする。
【００６７】
暗号文変換部４１２は、行列Ｆをそのまま行列Ｆ〜とする。
【００６８】
暗号文変換部４１２は、数４７に示すように、行列Ｄ〜を生成する。
【数４７】
0006522263.tif 000038
【００６９】
暗号文変換部４１２は、数４８に示すように、行列Ｃ〜を生成する。
【数４８】
0006522263.tif 000039
ここで、行列Ｘは、数４９に示す通りである。
【数４９】
0006522263.tif 000040
また、行列ｓは、数５０に示す通りである。
【数５０】
0006522263.tif 000041
なお、ベクトルｒ’ｆ∈｛０，１｝Ｎは、ｆをランダムオラクルにクエリすることによって得られるベクトルである。つまり、ベクトルｒ’ｆは、ランダムなベクトルである。また、Ｂｆは、数２１に示す通りである。
【００７０】
暗号文変換部４１２は、暗号文ｃｔ〜：＝（Ｃ〜，Ｆ〜，Ｄ〜）をメモリ４２に書き込む。
【００７１】
つまり、暗号文変換部４１２は、数５１に示すＥｘｐａｎｓｉｏｎアルゴリズムを実行する。
【数５１】
0006522263.tif 000042
【００７２】
（ステップＳ４５：準同型演算処理）
準同型演算装置４０の準同型演算部４１３は、ｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ（ｉ）〜に対して、準同型演算ｇを実行して、暗号文ｃｔ＊：＝（Ｃ＊，Ｆ＊，Ｄ＊）を生成する。
具体的には、準同型演算部４１３は、ｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ（ｉ）〜を読み出す。そして、準同型演算部４１３は、ｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ（ｉ）〜を入力として、非特許文献３の“３．２  Ｈｏｍｏｍｏｒｐｈｉｃ  Ｏｐｅｒａｔｉｏｎｓ”に記載された準同型演算の演算方法に従い、準同型演算ｇを実行して、暗号文ｃｔ＊を生成する。準同型演算部４１３は、生成された暗号文ｃｔ＊をメモリ４２に書き込む。
【００７３】
具体例として、２つの暗号文ｃｔ（１）〜：＝（Ｃ１，Ｆ１，Ｄ１）とｃｔ（２）〜：＝（Ｃ２，Ｆ２，Ｄ２）とについて、準同型加算する場合を説明する。この場合、準同型演算部４１３は、Ｃ＊：＝Ｃ１＋Ｃ２，Ｆ＊：＝Ｆ１＋Ｆ２，Ｄ＊：＝Ｄ１＋Ｄ２のように、各暗号要素を計算する。
【００７４】
また、具体例として、２つの暗号文ｃｔ（１）〜：＝（Ｃ１，Ｆ１，Ｄ１）とｃｔ（２）〜：＝（Ｃ２，Ｆ２，Ｄ２）とについて、準同型乗算する場合を説明する。この場合、準同型演算部４１３は、数５２に示すように、各暗号要素を計算する。
【数５２】
0006522263.tif 000043
【００７５】
（ステップＳ４６：出力処理）
準同型演算装置４０の出力部４１４は、暗号文ｃｔ＊を出力する。
具体的には、出力部４１４は、メモリ４２から暗号文ｃｔ＊を読み出す。そして、出力部４１４は、暗号文ｃｔ＊を暗号文記憶部４３２に書き込む。
【００７６】
つまり、準同型演算装置４０は、数５３に示すＥｖａｌｕａｔｉｏｎアルゴリズムを実行して、暗号文ｃｔ＊を生成する。
【数５３】
0006522263.tif 000044
なお、Ｈ．Ｏｐアルゴリズムは、非特許文献３に記載された準同型演算の演算アルゴリズムのことである。
【００７７】
図１０を参照して、実施の形態１に係るＤｅｃ処理を説明する。
Ｄｅｃ処理は、暗号文ｃｔを復号する際に、主に復号装置５０によって実行される。実施の形態１に係るＤｅｃ処理は、実施の形態１に係る復号方法と復号プログラムの処理とに相当する。
【００７８】
（ステップＳ５１：取得処理）
復号装置５０の取得部５１１は、復号の対象とする暗号文ｃｔ（Ｆ）：＝（Ｃ＾Ｆ，Ｆ，Ｄ＾Ｆ）を取得する。
具体的には、取得部５１１は、通信インタフェース５４を介して、準同型演算装置４０に暗号文ｃｔ（Ｆ）の取得要求を送信する。準同型演算装置４０の出力部４１４は、取得要求を受信すると、要求された暗号文ｃｔ（Ｆ）を暗号文記憶部４３２から読み出す。この際、準同型演算装置４０の暗号文変換部４１２は、暗号文ｃｔ（Ｆ）が図８のステップＳ３３で出力された暗号文ｃｔである場合には、上述したＡｐｐｌｙアルゴリズムを実行して、暗号文ｃｔを暗号文ｃｔ（Ｆ）：＝（Ｃ＾Ｆ，Ｆ，Ｄ＾Ｆ）に変換する。また、準同型演算装置４０の暗号文変換部４１２は、暗号文ｃｔ（Ｆ）が図９のステップＳ４６で出力された暗号文ｃｔ＊：＝（Ｃ＊，Ｆ＊，Ｄ＊）である場合には、暗号文ｃｔ（Ｆ）：＝（Ｃ＾ｆ：＝Ｃ＊，Ｆ：＝Ｆ＊，Ｄ＾ｆ：＝Ｄ＊）に変換する。そして、出力部４１４は、変換された暗号文ｃｔ（Ｆ）を、通信インタフェース４４を介して復号装置５０に送信する。取得部５１１は、準同型演算装置４０から送信された暗号文ｃｔ（Ｆ）を受信する。取得部５１１は、受信された暗号文ｃｔ（Ｆ）をメモリ５２に書き込む。
暗号文ｃｔ（Ｆ）は、ポリシー集合Ｆ：＝｛ｆ１，．．．，ｆｄ｝に関連付けられた復号鍵ｓｋｆ１，．．．，ｓｋｆｄによって復号可能な暗号文であることを意味する。
【００７９】
（ステップＳ５２：復号処理）
復号装置５０の復号部５１２は、暗号文ｃｔ（Ｆ）を復号鍵ｓｋｆ１：＝ｒｆ１，．．．，ｓｋｆｄ：＝ｒｆｄにより復号して、値μ〜を計算する。
具体的には、復号部５１２は、ｊ∈［ｄ］の各整数ｊについて、ランダムオラクルにクエリして行列ｒ’ｆｊ：＝Ｏ（Ａ，ｆｊ）を取得する。復号部５１２は、数５４に示すように、ｊ∈［ｄ］の各整数ｊについての復号鍵ｓｋｆｊを連結して、復号鍵ｒＦＴを生成する。
【数５４】
0006522263.tif 000045
【００８０】
復号部５１２は、数５５に示すように、ベクトルｃを計算する。
【数５５】
0006522263.tif 000046
復号部５１２は、数５６に示すように、値μ〜を計算する。
【数５６】
0006522263.tif 000047
ここで、ベクトルｕは、数５７に示す通りである。
【数５７】
0006522263.tif 000048
【００８１】
（ステップＳ５３：出力処理）
復号装置５０の出力部５１３は、値μ〜の絶対値がｑ／４未満であれば０を出力し、そうでなければ１を出力する。
【００８２】
つまり、復号装置５０は、数５８に示すＤｅｃアルゴリズムを実行して、暗号文ｃｔ（Ｆ）を復号する。
【数５８】
0006522263.tif 000049
【００８３】
＊＊＊実施の形態１の効果＊＊＊
以上のように、実施の形態１に係る暗号システム１０では、暗号要素Ｆを用いて、暗号要素である行列Ｃを暗号要素である行列Ｃ〜に変換する。これにより、暗号要素Ｃ内の要素をポリシー集合Ｆに関連付けてしまうことなく、準同型演算を行うことが可能になる。そのため、暗号文ｃｔ＊を入力として再び柔軟な準同型演算を行うことが可能になる。
【００８４】
暗号文ｃｔ＊を入力として再び柔軟な準同型演算を行うことが可能になるという効果が得られる理由を説明する。
暗号化装置３０により生成された暗号文ｃｔ：＝（ｘ，Ｃ，Ｃｘ，Ｆ，Ｄ，｛Ｄ（ｋ）ｘ｝ｋ）を入力として、図９のステップＳ４４で説明したＡｐｐｌｙアルゴリズムが実行された結果、暗号文ｃｔ（ｆ）：＝（Ｃ＾ｆ，Ｆ，Ｄ＾ｆ）が得られたとする。
このとき、暗号文ｃｔ（ｆ）は、復号鍵ｔ∈Ｚｑｍ＋Ｎ＋１と、小さなランダム行列Ｒ∈Ｚｑｎ×Ｍとに対して数５９に示す（１）から（３）の関係を満たしている。
【数５９】
0006522263.tif 000050
【００８５】
暗号文ｃｔ（ｆ）を入力として、図９のステップＳ４４で説明したＥｘｐａｎｓｉｏｎアルゴリズムが実行された結果、暗号文ｃｔ〜：＝（Ｃ〜，Ｆ〜，Ｄ〜）が得られたとする。このとき、暗号文ｃｔ〜は、復号鍵ｔに、復号鍵ｔｆを連結してできる復号鍵ｔ〜：＝［ｔ｜｜ｔｆ］と、ランダム行列Ｒ〜とに対して、以下に説明するように、数５９に示す（１）から（３）の関係を満たす状態が保持されている。
【００８６】
行列Ｆがそのまま行列Ｆ〜になる。そのため、ランダム行列Ｒがそのままランダム行列Ｒ〜になる。したがって、数５９の（２）に示す関係は満たされる。
【００８７】
行列Ｄ〜は、数４７に示すように生成される。このとき、数６０に示す関係が成立する。
【数６０】
0006522263.tif 000051
したがって、数５９の（３）の関係は満たされる。
【００８８】
行列Ｃ〜は、数４８に示すように生成される。このとき、行列Ｘの構成により、数６１の関係が成立する。
【数６１】
0006522263.tif 000052
したがって、数６２の関係が成立する。
【数６２】
0006522263.tif 000053
その結果、数６３の関係が成立しており、数５９の（１）の関係は満たされる。
【数６３】
0006522263.tif 000054
【００８９】
暗号文ｃｔ〜を入力として、図９のステップＳ４５で説明した準同型演算ｇが実行された結果、暗号文ｃｔ＊：＝（Ｃ＊，Ｆ＊，Ｄ＊）が得られたとする。このとき、非特許文献３で説明されているように、暗号文ｃｔ＊についても、数５９に示す（１）から（３）の関係を満たす状態が保持されている。
つまり、暗号化装置３０により生成された暗号文ｃｔを入力としてＡｐｐｌｙアルゴリズムが実行された結果得られた暗号文ｃｔ（ｆ）が満たす関係を、準同型演算ｇが実行された結果得られた暗号文ｃｔ＊が保持している。そのため、暗号化装置３０により生成された暗号文ｃｔに代えて、準同型演算ｇが実行された結果得られた暗号文ｃｔ＊を入力としてＥｘｐａｎｓｉｏｎアルゴリズムが実行された場合にも、この関係を満たす状態とすることができる。その結果、準同型演算ｇが実行された結果得られた暗号文ｃｔ＊についても、暗号化装置３０により生成された暗号文ｃｔと同様に、柔軟な準同型演算を行うことが可能である。
【００９０】
つまり、図９のステップＳ４４では、暗号文変換部４１２は、暗号文取得部４１６によって取得された暗号文ｃｔに含まれる暗号要素である行列Ｃ及び行列Ｃｘを、暗号要素である行列Ｆ及び暗号要素である行列Ｄにより、ポリシー取得部４１７によって取得されたポリシー集合Ｆに対応する復号鍵ｓｋＦによって復号可能な暗号要素である行列Ｃ〜に変換する。また、暗号文変換部４１２は、行列Ｄについても、合わせて行列Ｄ〜に変換する。これにより、暗号文変換部４１２は、暗号文ｃｔを暗号文ｃｔ〜に変換する。
すなわち、暗号文変換部４１２は、平文μが設定された暗号要素である行列Ｃと、属性ｘが設定された暗号要素である行列Ｃｘとを、平文μと乱数である行列Ｒとが設定され、属性ｘが満たすポリシーｆに対応する復号鍵ｓｋｆによって復号されない暗号要素である行列Ｆと、乱数である行列Ｒが暗号化された暗号要素である行列Ｄとを用いて変換する。このように、暗号文変換部４１２は、行列Ｆ及び行列Ｄを用いることにより、暗号文と復号鍵及び乱数Ｒとの間に成立する関係性を保持したまま、準同型演算を実行可能にしている。
【００９１】
＊＊＊他の構成＊＊＊
＜変形例１＞
実施の形態１では、鍵生成装置２０と暗号化装置３０と準同型演算装置４０と復号装置５０との機能構成要素がソフトウェアで実現された。しかし、変形例１として、機能構成要素はハードウェアで実現されてもよい。この変形例１について、実施の形態１と異なる点を説明する。
【００９２】
図１１を参照して、変形例１に係る鍵生成装置２０の構成を説明する。
機能がハードウェアで実現される場合、鍵生成装置２０は、プロセッサ２１とメモリ２２とストレージ２３とに代えて、処理回路２５を備える。処理回路２５は、鍵生成装置２０の機能構成要素と、メモリ２２とストレージ２３との機能とを実現する専用の電子回路である。
【００９３】
図１２を参照して、変形例１に係る暗号化装置３０の構成を説明する。
機能がハードウェアで実現される場合、暗号化装置３０は、プロセッサ３１とメモリ３２とストレージ３３とに代えて、処理回路３５を備える。処理回路３５は、暗号化装置３０の機能構成要素と、メモリ３２とストレージ３３との機能とを実現する専用の電子回路である。
【００９４】
図１３を参照して、変形例１に係る準同型演算装置４０の構成を説明する。
機能がハードウェアで実現される場合、準同型演算装置４０は、プロセッサ４１とメモリ４２とストレージ４３とに代えて、処理回路４５を備える。処理回路４５は、準同型演算装置４０の機能構成要素と、メモリ４２とストレージ４３との機能とを実現する専用の電子回路である。
【００９５】
図１４を参照して、変形例１に係る復号装置５０の構成を説明する。
機能がハードウェアで実現される場合、復号装置５０は、プロセッサ５１とメモリ５２とストレージ５３とに代えて、処理回路５５を備える。処理回路５５は、復号装置５０の機能構成要素と、メモリ５２とストレージ５３との機能とを実現する専用の電子回路である。
【００９６】
処理回路２５，３５，４５，５５は、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ（Ｇａｔｅ  Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）が想定される。
鍵生成装置２０の各機能構成要素の機能を１つの処理回路２５で実現してもよいし、各機能構成要素の機能を複数の処理回路２５に分散させて実現してもよい。同様に、暗号化装置３０と準同型演算装置４０と復号装置５０とのそれぞれについて、各機能構成要素の機能を１つの処理回路３５，４５，５５で実現してもよいし、各機能構成要素の機能を複数の処理回路３５，４５，５５に分散させて実現してもよい。
【００９７】
＜変形例２＞
変形例２として、一部の機能がハードウェアで実現され、他の機能がソフトウェアで実現されてもよい。つまり、各機能構成要素のうち、一部の機能がハードウェアで実現され、他の機能がソフトウェアで実現されてもよい。
【００９８】
プロセッサ２１，３１，４１，５１とメモリ２２，３２，４２，５２とストレージ２３，３３，４３，５３と処理回路２５，３５，４５，５５とを、総称して「プロセッシングサーキットリー」という。つまり、各機能構成要素の機能は、プロセッシングサーキットリーにより実現される。
【００９９】
＊＊＊記法の説明＊＊＊
Ａがランダムな変数または分布であるとき、数６４は、Ａの分布に従いＡからｙをランダムに選択することを表す。つまり、数６４において、ｙは乱数である。
【数６４】
0006522263.tif 000055
Ａが集合であるとき、数６５は、Ａからｙを一様に選択することを表す。つまり、数６５において、ｙは一様乱数である。
【数６５】
0006522263.tif 000056
【０１００】
数６６は、ｙがｚにより定義された集合であること、又はｙがｚを代入された集合であることを表す。
【数６６】
0006522263.tif 000057
【０１０１】
ａが定数であるとき、数６７は、機械（アルゴリズム）Ａが入力ｘに対しａを出力することを表す。
【数６７】
0006522263.tif 000058
【０１０２】
Ｚｑは、位数ｑの整数の群を示す。また、ｙ∈Ｚｑｖは、ｙはＺｑ上のｖ個の要素を有するベクトルであることを示す。また、ｙ∈Ｚｑｖ×ｗは、ｙはＺｑ上の要素を持つ、ｖ行ｗ列の行列であることを示す。
【符号の説明】
【０１０３】
１０  暗号システム、２０  鍵生成装置、２１  プロセッサ、２２  メモリ、２３  ストレージ、２４  通信インタフェース、２５  処理回路、２１１  取得部、２１２  マスタ鍵生成部、２１３  復号鍵生成部、２１４  出力部、２３１  マスタ鍵記憶部、３０  暗号化装置、３１  プロセッサ、３２  メモリ、３３  ストレージ、３４  通信インタフェース、３５  処理回路、３１１  取得部、３１２  暗号化部、３１３  出力部、３３１  公開パラメータ記憶部、４０  準同型演算装置、４１  プロセッサ、４２  メモリ、４３  ストレージ、４４  通信インタフェース、４５  処理回路、４１１  取得部、４１２  暗号文変換部、４１３  準同型演算部、４１４  出力部、４１５  公開パラメータ取得部、４１６  暗号文取得部、４１７  ポリシー取得部、４１８  演算取得部、４３１  公開パラメータ記憶部、４３２  暗号文記憶部、５０  復号装置、５１  プロセッサ、５２  メモリ、５３  ストレージ、５４  通信インタフェース、５５  処理回路、５１１  取得部、５１２  復号部、５１３  出力部、５３１  鍵記憶部、５３２  条件記憶部、５３３  結果記憶部、λ  セキュリティパラメータ、ｐｐ  公開パラメータ、ｍｓｋ  マスタ秘密鍵、ｓｋｆ  復号鍵、μ  平文、ｘ  属性、ｃｔ，ｃｔ（Ｆ），ｃｔ〜，ｃｔ＊  暗号文、Ｆ  ポリシー集合、ｇ  準同型演算。
【図１】
0006522263.tif 000066
【図２】
0006522263.tif 000067
【図３】
0006522263.tif 000068
【図４】
0006522263.tif 000069
【図５】
0006522263.tif 000070
【図６】
0006522263.tif 000071
【図７】
0006522263.tif 000072
【図８】
0006522263.tif 000073
【図９】
0006522263.tif 000074
【図１０】
0006522263.tif 000075
【図１１】
0006522263.tif 000076
【図１２】
0006522263.tif 000077
【図１３】
0006522263.tif 000078
【図１４】
0006522263.tif 000079