WO2018134922A1

WO2018134922A1 - 準同型演算装置、暗号システム及び準同型演算プログラム

Info

Publication number: WO2018134922A1
Application number: PCT/JP2017/001589
Authority: WO
Inventors: 良廣政; 豊川合
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 2017-01-18
Filing date: 2017-01-18
Publication date: 2018-07-26
Anticipated expiration: 2019-07-18
Also published as: JPWO2018134922A1; CN110169010B; US20200127810A1; JP6522263B2; US11139952B2; CN110169010A

Abstract

暗号化装置（３０）は、平文μが設定された暗号要素Ｃと、属性ｘが設定された暗号要素Ｃ_ｘと、平文μが設定され、属性ｘが満たすポリシーｆに対応する復号鍵ｓｋ_ｆによって復号されない暗号要素Ｆとを含む暗号文ｃｔを生成する。準同型演算装置（４０）は、暗号文ｃｔに含まれる暗号要素Ｃを、暗号要素Ｆにより、ポリシー取得部によって取得されたポリシー集合Ｆに対応する復号鍵ｓｋ_Ｆによって復号可能な暗号要素Ｃ^～に変換することにより、暗号文ｃｔを暗号文ｃｔ^～に変換する。準同型演算装置（４０）は、暗号文ｃｔ^～に対して準同型演算ｇを行い暗号文ｃｔ^＊を生成する。

Description

準同型演算装置、暗号システム及び準同型演算プログラム

　この発明は、データを暗号化したまま演算する技術に関する。

　準同型暗号とは、データを暗号化したまま演算できる暗号技術である。昨今、クラウドサービスの利用が広まりつつあるが、クラッキングとクラウドの信頼性の懸念とから、クラウドにはデータを暗号化した上で保管することが考えられる。準同型暗号は、暗号化されているデータに対して、復号することなく演算を施すことができるため、安全性を損なうことなくクラウドサービスの利用を可能とする技術である。

　準同型暗号の利便性を向上するために、指定された条件に従って復号者を柔軟に制御可能にした暗号技術が属性ベース準同型暗号である。属性ベース準同型暗号では、暗号文がある属性に関連するとともに、復号鍵がある復号許可条件に関連しており、属性が復号許可条件を満たすような鍵で暗号文を復号したときにだけ、正しい平文を得ることができる。

　非特許文献１には、属性ベース準同型暗号の初めての方式が記載されている。非特許文献１に記載された方式では、同一の属性に関する暗号文同士でしか準同型演算できないという課題がある。

　非特許文献２には、非特許文献１の課題を解決した属性ベース準同型暗号の方式が記載されている。
　非特許文献２には、単一ターゲット属性ベース準同型暗号と複数ターゲット属性ベース準同型暗号と呼ばれる２つの暗号技術の構成が示されている。単一ターゲット属性ベース準同型暗号は、ある１つの復号許可条件に対して、その条件を満たす属性に関する暗号文同士であれば準同型演算を行える暗号方式である。複数ターゲット属性ベース準同型暗号は、複数の復号許可条件に対して、いずれかの条件を満たす属性に関する暗号文同士であれば準同型演算可能な暗号方式である。

Ｃ．Ｇｅｎｔｒｙ，Ａ．Ｓａｈａｉ，ａｎｄ　Ｂ．Ｗａｔｅｒｓ．"Ｈｏｍｏｍｏｒｐｈｉｃ　Ｅｎｃｒｙｐｔｉｏｎ　ｆｒｏｍ　Ｌｅａｒｎｉｎｇ　ｗｉｔｈ　Ｅｒｒｏｒｓ：　Ｃｏｎｃｅｐｔｕａｌｌｙ－Ｓｉｍｐｌｅｒ，Ａｓｙｍｐｔｏｔｉｃａｌｌｙ－Ｆａｓｔｅｒ，Ａｔｔｒｉｂｕｔｅ－Ｂａｓｅｄ"．Ｉｎ　ＣＲＹＰＴＯ　２０１３，ｐａｇｅｓ　７５－９２，２０１３．Ｚ．Ｂｒａｋｅｒｓｋｉ，Ｄ．Ｃａｓｈ，Ｒ．Ｔｓａｂａｒｙ，ａｎｄ　Ｈ．Ｗｅｅ．"Ｔａｒｇｅｔｅｄ　Ｈｏｍｏｍｏｒｐｈｉｃ　Ａｔｔｒｉｂｕｔｅ　Ｂａｓｅｄ　Ｅｎｃｒｙｐｔｉｏｎ"．Ｉｎ　ＴＣＣ　２０１６－Ｂ，ｐａｇｅｓ　３３０－３６０，２０１６．Ｃ．Ｐｅｉｋｅｒｔ，ａｎｄ　Ｓ．Ｓｈｉｅｈｉａｎ"Ｍｕｌｔｉ－Ｋｅｙ　ＦＨＥ　ｆｒｏｍ　ＬＷＥ，　Ｒｅｖｉｓｉｔｅｄ"　２０１６

　非特許文献２に示されている複数ターゲット属性ベース準同型暗号では、演算対象の暗号文Ｘに対して準同型演算を行って得られる暗号文Ｙは、演算対象の暗号文Ｘを復号可能な復号許可条件の集合Ｆに関連付けられる。暗号文Ｙを用いて、再び別の準同型演算前の暗号文Ｚと準同型演算を行う際には、暗号文Ｚの復号許可条件が、暗号文Ｙが関連付けられた復号許可条件の集合Ｆに含まれていない限り、準同型演算を行うことができない。
　そのため、暗号文Ｘ，Ｙ，Ｚの復号許可条件によっては、暗号文Ｘ，Ｙ，Ｚを全て事前に収集し、一度に準同型演算を行う必要がある。したがって、例えば、暗号化された時系列データについて準同型演算を行う際には、事前に演算に用いられる時系列データをすべて収集し、保持しておくための膨大な記憶容量が必要となる。
　この発明は、柔軟な準同型演算を可能にすることを目的とする。

　この発明に係る準同型演算装置は、
　平文μが設定された暗号要素Ｃと、属性ｘが設定された暗号要素Ｃ_ｘと、前記平文μが設定され、前記属性ｘが満たすポリシーｆに対応する復号鍵ｓｋ_ｆによって復号されない暗号要素Ｆとを含む暗号文ｃｔを取得する暗号文取得部と、
　ポリシーの集合であるポリシー集合Ｆを取得するポリシー取得部と、
　前記暗号文取得部によって取得された前記暗号文ｃｔに含まれる前記暗号要素Ｃを、前記暗号要素Ｆにより、前記ポリシー取得部によって取得された前記ポリシー集合Ｆに対応する復号鍵ｓｋ_Ｆによって復号可能な暗号要素Ｃ^～に変換することにより、前記暗号文ｃｔを暗号文ｃｔ^～に変換する暗号文変換部と、
　前記暗号文変換部によって変換された前記暗号文ｃｔ^～に対して準同型演算ｇを行い暗号文ｃｔ^＊を生成する準同型演算部と
を備える。

　この発明では、暗号要素Ｆを用いて、暗号要素Ｃを暗号要素Ｃ^～に変換する。これにより、暗号要素Ｃ内の要素をポリシー集合Ｆに関連付けてしまうことなく、準同型演算を行うことが可能になる。そのため、暗号文ｃｔ^＊を入力として再び柔軟な準同型演算を行うことが可能になる。

実施の形態１に係る暗号システム１０の構成図。実施の形態１に係る鍵生成装置２０の構成図。実施の形態１に係る暗号化装置３０の構成図。実施の形態１に係る準同型演算装置４０の構成図。実施の形態１に係る復号装置５０の構成図。実施の形態１に係るＳｅｔｕｐ処理のフローチャート。実施の形態１に係るＫｅｙＧｅｎ処理のフローチャート。実施の形態１に係るＥｎｃ処理のフローチャート。実施の形態１に係るＥｖａｌ処理のフローチャート。実施の形態１に係るＤｅｃ処理のフローチャート。変形例１に係る鍵生成装置２０の構成図。変形例１に係る暗号化装置３０の構成図。変形例１に係る準同型演算装置４０の構成図。変形例１に係る復号装置５０の構成図。

　実施の形態１．
　＊＊＊構成の説明＊＊＊
　図１を参照して、実施の形態１に係る暗号システム１０の構成を説明する。
　暗号システム１０は、鍵生成装置２０と、暗号化装置３０と、準同型演算装置４０と、復号装置５０とを備える。
　鍵生成装置２０と、暗号化装置３０と、準同型演算装置４０と、復号装置５０とは、ネットワーク６０を介して接続される。ネットワーク６０は、具体例としては、インターネットである。ネットワーク６０は、ＬＡＮ（Ｌｏｃａｌ　Ａｒｅａ　Ｎｅｔｗｏｒｋ）といった他の種類のネットワークであってもよい。

　図２を参照して、実施の形態１に係る鍵生成装置２０の構成を説明する。
　鍵生成装置２０は、コンピュータである。
　鍵生成装置２０は、プロセッサ２１と、メモリ２２と、ストレージ２３と、通信インタフェース２４とのハードウェアを備える。プロセッサ２１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。

　鍵生成装置２０は、機能構成要素として、取得部２１１と、マスタ鍵生成部２１２と、復号鍵生成部２１３と、出力部２１４とを備える。取得部２１１と、マスタ鍵生成部２１２と、復号鍵生成部２１３と、出力部２１４との機能はソフトウェアにより実現される。
　ストレージ２３には、取得部２１１と、マスタ鍵生成部２１２と、復号鍵生成部２１３と、出力部２１４との機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ２１によりメモリ２２に読み込まれ、プロセッサ２１によって実行される。これにより、取得部２１１と、マスタ鍵生成部２１２と、復号鍵生成部２１３と、出力部２１４との機能が実現される。
　また、ストレージ２３は、マスタ鍵記憶部２３１の機能を実現する。

　図３を参照して、実施の形態１に係る暗号化装置３０の構成を説明する。
　暗号化装置３０は、コンピュータである。
　暗号化装置３０は、プロセッサ３１と、メモリ３２と、ストレージ３３と、通信インタフェース３４とのハードウェアを備える。プロセッサ３１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。

　暗号化装置３０は、機能構成要素として、取得部３１１と、暗号化部３１２と、出力部３１３とを備える。取得部３１１と、暗号化部３１２と、出力部３１３との機能はソフトウェアにより実現される。
　ストレージ３３には、取得部３１１と、暗号化部３１２と、出力部３１３との機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ３１によりメモリ３２に読み込まれ、プロセッサ３１によって実行される。これにより、取得部３１１と、暗号化部３１２と、出力部３１３との機能が実現される。
　また、ストレージ３３は、公開パラメータ記憶部３３１の機能を実現する。

　図４を参照して、実施の形態１に係る準同型演算装置４０の構成を説明する。
　準同型演算装置４０は、コンピュータである。
　準同型演算装置４０は、プロセッサ４１と、メモリ４２と、ストレージ４３と、通信インタフェース４４とのハードウェアを備える。プロセッサ４１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。

　準同型演算装置４０は、機能構成要素として、取得部４１１と、暗号文変換部４１２と、準同型演算部４１３と、出力部４１４とを備える。取得部４１１は、公開パラメータ取得部４１５と、暗号文取得部４１６と、ポリシー取得部４１７と、演算取得部４１８とを備える。取得部４１１と、暗号文変換部４１２と、準同型演算部４１３と、出力部４１４と、公開パラメータ取得部４１５と、暗号文取得部４１６と、ポリシー取得部４１７と、演算取得部４１８との機能はソフトウェアにより実現される。
　ストレージ４３には、取得部４１１と、暗号文変換部４１２と、準同型演算部４１３と、出力部４１４と、公開パラメータ取得部４１５と、暗号文取得部４１６と、ポリシー取得部４１７と、演算取得部４１８との機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ４１によりメモリ４２に読み込まれ、プロセッサ４１によって実行される。これにより、取得部４１１と、暗号文変換部４１２と、準同型演算部４１３と、出力部４１４と、公開パラメータ取得部４１５と、暗号文取得部４１６と、ポリシー取得部４１７と、演算取得部４１８との機能が実現される。
　また、ストレージ４３は、公開パラメータ記憶部４３１と、暗号文記憶部４３２との機能を実現する。

　図５を参照して、実施の形態１に係る復号装置５０の構成を説明する。
　復号装置５０は、コンピュータである。
　復号装置５０は、プロセッサ５１と、メモリ５２と、ストレージ５３と、通信インタフェース５４とのハードウェアを備える。プロセッサ５１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。

　復号装置５０は、機能構成要素として、取得部５１１と、復号部５１２と、出力部５１３とを備える。取得部５１１と、復号部５１２と、出力部５１３との機能はソフトウェアにより実現される。
　ストレージ５３には、取得部５１１と、復号部５１２と、出力部５１３との機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ５１によりメモリ５２に読み込まれ、プロセッサ５１によって実行される。これにより、取得部５１１と、復号部５１２と、出力部５１３との機能が実現される。
　また、ストレージ５３は、鍵記憶部５３１と、条件記憶部５３２と、結果記憶部５３３との機能を実現する。

　プロセッサ２１，３１，４１，５１は、演算処理を行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ　Ｃｉｒｃｕｉｔ）である。プロセッサ２１，３１，４１，５１は、具体例としては、ＣＰＵ（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ　Ｓｉｇｎａｌ　Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）である。

　メモリ２２，３２，４２，５２は、データを一時的に記憶する記憶装置である。メモリ２２，３２，４２，５２は、具体例としては、ＳＲＡＭ（Ｓｔａｔｉｃ　Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）、ＤＲＡＭ（Ｄｙｎａｍｉｃ　Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）である。

　ストレージ２３，３３，４３，５３は、データを保管する記憶装置である。ストレージ２３，３３，４３，５３は、具体例としては、ＨＤＤ（Ｈａｒｄ　Ｄｉｓｋ　Ｄｒｉｖｅ）である。また、ストレージ２３，３３，４３，５３は、ＳＤ（登録商標，Ｓｅｃｕｒｅ　Ｄｉｇｉｔａｌ）メモリカード、ＣＦ（ＣｏｍｐａｃｔＦｌａｓｈ）、ＮＡＮＤフラッシュ、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ　Ｖｅｒｓａｔｉｌｅ　Ｄｉｓｋ）といった可搬記憶媒体であってもよい。

　通信インタフェース２４，３４，４４，５４は、外部の装置と通信するためのインタフェースである。通信インタフェース２４，３４，４４，５４は、具体例としては、Ｅｔｈｅｒｎｅｔ（登録商標）、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ　Ｓｅｒｉａｌ　Ｂｕｓ）、ＨＤＭＩ（登録商標，Ｈｉｇｈ－Ｄｅｆｉｎｉｔｉｏｎ　Ｍｕｌｔｉｍｅｄｉａ　Ｉｎｔｅｒｆａｃｅ）のポートである。

　図２では、プロセッサ２１は、１つだけ示されている。しかし、鍵生成装置２０は、プロセッサ２１を代替する複数のプロセッサを備えていてもよい。同様に、暗号化装置３０は、プロセッサ３１を代替する複数のプロセッサを備え、準同型演算装置４０は、プロセッサ４１を代替する複数のプロセッサを備え、復号装置５０は、プロセッサ５１を代替する複数のプロセッサを備えていてもよい。これら複数のプロセッサは、各機能構成要素の機能を実現するプログラムの実行を分担する。それぞれのプロセッサは、プロセッサ２１，３１，４１，５１と同じように、演算処理を行うＩＣである。

　＊＊＊動作の説明＊＊＊
　図６から図１０を参照して、実施の形態１に係る暗号システム１０の動作を説明する。
　実施の形態１に係る暗号システム１０の動作は、実施の形態１に係る暗号方法に相当する。また、実施の形態１に係る暗号プログラムの処理に相当する。
　暗号システム１０の動作は、Ｓｅｔｕｐ処理と、ＫｅｙＧｅｎ処理と、Ｅｎｃ処理と、Ｅｖａｌ処理と、Ｄｅｃ処理とに分けられる。

　以下の説明では、非特許文献２に記載された内容と異なる部分を中心に説明し、非特許文献２に記載された内容と同一の部分について既に公知の内容であるため、一部説明を省略する。

　以下の説明における符号について説明する。
　ｎ，ｑ，χは、ＬＷＥ（Ｌｅａｒｎｉｎｇ　Ｗｉｔｈ　Ｅｒｒｏｒｓ）問題におけるパラメータである。ＬＷＥ問題は公知の問題である。Ｄｅｃｉｓｉｏｎａｌ　ＬＷＥ問題（ＤＬＷＥ問題）は、次のように定義される。
　＜ＤＬＷＥ問題＞
　λはセキュリティパラメータであり、ｎ＝ｎ（λ）とｑ＝ｑ（λ）とは整数であり、χ＝χ（λ）は整数Ｚ上の確率分布であるとする。ＤＬＷＥ_{ｎ，ｑ，χ}問題は、全てのｍ＝ｐｏｌｙ（ｎ）に対して、数１１とする場合に、（Ａ，ｓ^ＴＡ＋ｅ^Ｔ）と（Ａ，ｕ^Ｔ）とが計算的に見分けがつかないというものである。

　ｍ、Ｎ，Ｍ．ｇ^Ｔは、数１２に示す通りである。

　任意のｘ∈Ｚ_ｑに対して、数１３に示すｙは、数１４を満たすベクトルである。

　任意の自然数ｎ，ｍに対して、Ｉ_ｎはｎ行ｎ列の単位行列であり、０_ｎ×ｍは要素が全て０のｎ行ｍ列の行列である。任意のｉ∈［ｎ］に対して、ｅ_ｉ∈｛０，１｝^ｎは、ｎ要素目が１でその他が０の標準基底ベクトルである。なお、ｉ∈［ｎ］は、ｉ＝１，．．．，ｎを意味する。
　Ｆ⊆｛０，１｝^Ｌ→｛０，１｝は、深さｄ_Ｆのブーリアンサーキットで計算できるポリシーのクラスである。Ｇ⊆｛０，１｝^＊→｛０，１｝は、深さｄ_Ｇのブーリアンサーキットで計算できる演算のクラスである。

　図６を参照して、実施の形態１に係るＳｅｔｕｐ処理を説明する。
　Ｓｅｔｕｐ処理は、暗号システム１０の初期設定時等に、主に鍵生成装置２０によって実行される。実施の形態１に係るＳｅｔｕｐ処理は、実施の形態１に係るマスタ鍵生成方法とマスタ鍵生成プログラムの処理とに相当する。

　（ステップＳ１１：取得処理）
　鍵生成装置２０の取得部２１１は、パラメータλ，Ｌ，ｄ_Ｆ，ｄ_Ｇを取得する。
　具体的には、取得部２１１は、通信インタフェース２４を介して、暗号システム１０の管理者等によって入力されたパラメータλ，Ｌ，ｄ_Ｆ，ｄ_Ｇを受け付ける。取得部２１１は、受け付けられたパラメータλ，Ｌ，ｄ_Ｆ，ｄ_Ｇをメモリ２２に書き込む。

　（ステップＳ１２：マスタ鍵生成処理）
　鍵生成装置２０のマスタ鍵生成部２１２は、公開パラメータｐｐとマスタ秘密鍵ｍｓｋとのペアを生成する。
　具体的には、マスタ鍵生成部２１２は、数１５に示すように、行列ＡとトラップドアＡ_τ０ ^－１とのペア（Ａ，Ａ_τ０ ^－１）を生成する。

　ＴｒａｐＧｅｎアルゴリズムは非特許文献２に記載されている。ここで、行列Ａは数１６に示す行列であり、トラップドアＡ_τ０ ^－１は数１７に示すアルゴリズムである。

　マスタ鍵生成部２１２は、数１８に示すように、行列Ｂ，Ｂ_０，Ｂ_１，．．．，Ｂ_Ｌを生成し、Ｂ^→ _ｘを定義する。

　マスタ鍵生成部２１２は、数１９に示すように、ベクトルｖとＰＲＦ（ＰｓｅｕｄｏＲａｎｄｏｍ　Ｆｕｎｃｔｉｏｎ）のシードσとを生成する。

　ＰＲＦ．Ｇｅｎアルゴリズムは非特許文献２に記載されている。

　マスタ鍵生成部２１２は、（Ａ，Ｂ_０，Ｂ^→ _ｘ，Ｂ，ｖ）を公開パラメータｐｐとし、（Ａ_τ０ ^－１，σ）をマスタ秘密鍵ｍｓｋとする。マスタ鍵生成部２１２は、公開パラメータｐｐをメモリ２２に書き込むとともに、公開パラメータｐｐ及びマスタ秘密鍵ｍｓｋをマスタ鍵記憶部２３１に書き込む。

　（ステップＳ１３：出力処理）
　鍵生成装置２０の出力部２１４は、公開パラメータｐｐを出力する。
　具体的には、出力部２１４は、メモリ２２から公開パラメータｐｐを読み出す。そして、出力部２１４は、通信インタフェース２４を介して、公開パラメータｐｐを暗号化装置３０と準同型演算装置４０と復号装置５０とに送信する。

　（ステップＳ１４：公開パラメータ取得処理）
　暗号化装置３０の取得部３１１と、準同型演算装置４０の公開パラメータ取得部４１５と、復号装置５０の取得部５１１とは、公開パラメータｐｐを取得する。
　具体的には、取得部３１１は、通信インタフェース３４を介して、出力部２１４によって送信された公開パラメータｐｐを受信する。取得部３１１は、受信された公開パラメータｐｐを公開パラメータ記憶部３３１に書き込む。
　また、準同型演算装置４０の公開パラメータ取得部４１５は、通信インタフェース４４を介して、出力部２１４によって送信された公開パラメータｐｐを受信する。公開パラメータ取得部４１５は、受信された公開パラメータｐｐを公開パラメータ記憶部４３１に書き込む。
　また、復号装置５０の取得部５１１は、通信インタフェース５４を介して、出力部２１４によって送信された公開パラメータｐｐを受信する。取得部５１１は、受信された公開パラメータｐｐを鍵記憶部５３１に書き込む。

　つまり、鍵生成装置２０は、数２０に示すＳｅｔｕｐアルゴリズムを実行して、公開パラメータｐｐとマスタ秘密鍵ｍｓｋとを生成する。

　図７を参照して、実施の形態１に係るＫｅｙＧｅｎ処理を説明する。
　ＫｅｙＧｅｎ処理は、新たな復号鍵ｓｋ_ｆを生成する際に、主に鍵生成装置２０によって実行される。実施の形態１に係るＫｅｙＧｅｎ処理は、実施の形態１に係る復号鍵生成方法と復号鍵生成プログラムの処理とに相当する。

　（ステップＳ２１：復号鍵依頼処理）
　復号装置５０の取得部５１１は、復号鍵ｓｋ_ｆの生成を鍵生成装置２０に依頼する。
　具体的には、取得部５１１は、復号装置５０の利用者等によって入力された復号許可条件を示すポリシーｆを受け付ける。ポリシーｆは、例えば、利用者の属性が設定される。そして、取得部５１１は、入力されたポリシーｆを鍵生成装置２０に送信して、ポリシーｆに関連付けられた復号鍵ｓｋ_ｆの生成を要求する。
　取得部５１１は、復号鍵ｓｋ_ｆの生成を要求した際に送信されたポリシーｆを条件記憶部５３２に書き込む。

　（ステップＳ２２：取得処理）
　鍵生成装置２０の取得部２１１は、ポリシーｆを取得する。
　具体的には、取得部２１１は、通信インタフェース２４を介して、復号装置５０から送信されたポリシーｆを受信する。取得部２１１は、受信されたポリシーｆをメモリ２２に書き込む。

　（ステップＳ２３：復号鍵生成処理）
　鍵生成装置２０の復号鍵生成部２１３は、ポリシーｆに関連付けられた復号鍵ｓｋ_ｆを生成する。
　具体的には、復号鍵生成部２１３は、メモリ２２からポリシーｆを読み出し、マスタ鍵記憶部２３１から公開パラメータｐｐ及びマスタ秘密鍵ｍｓｋを読み出す。復号鍵生成部２１３は、数２１に示すように、行列Ｂ_ｆを計算する。

　Ｅｖａｌアルゴリズムは非特許文献２に記載されている。

　復号鍵生成部２１３は、ランダムオラクルにクエリして行列ｒ’_ｆ＝Ｏ（Ａ，ｆ）∈｛０，１｝^Ｎを得る。つまり、復号鍵生成部２１３は、ランダムな行列ｒ’_ｆを生成する。復号鍵生成部２１３は、数２２に示すように、行列ｒ_ｆを生成する。

　ここで、τは数２３に示す通りである。

　このとき、トラップドアＡ_τ０ ^－１は数１７に示すアルゴリズムであるから、数２４が成立する。

　復号鍵生成部２１３は、行列ｒ_ｆを復号鍵ｓｋ_ｆとしてメモリ２２に書き込む。

　（ステップＳ２４：出力処理）
　鍵生成装置２０の出力部２１４は、復号鍵ｓｋ_ｆを出力する。
　具体的には、出力部２１４は、メモリ２２から復号鍵ｓｋ_ｆを読み出す。そして、出力部２１４は、通信インタフェース２４を介して、復号鍵ｓｋ_ｆを復号装置５０に送信する。

　（ステップＳ２５：復号鍵取得処理）
　復号装置５０の取得部５１１は、復号鍵ｓｋ_ｆを取得する。
　具体的には、取得部５１１は、通信インタフェース５４を介して、出力部２１４によって送信された復号鍵ｓｋ_ｆを受信する。取得部５１１は、受信された復号鍵ｓｋ_ｆを鍵記憶部５３１に書き込む。

　つまり、鍵生成装置２０は、数２５に示すＫｅｙＧｅｎアルゴリズムを実行して、復号鍵ｓｋ_ｆを生成する。

　図８を参照して、実施の形態１に係るＥｎｃ処理を説明する。
　Ｅｎｃ処理は、暗号文ｃｔを生成する際に、主に暗号化装置３０によって実行される。実施の形態１に係るＥｎｃ処理は、実施の形態１に係る暗号化方法と暗号化プログラムの処理とに相当する。

　（ステップＳ３１：取得処理）
　暗号化装置３０の取得部３１１は、平文μと、属性ｘとを取得する。
　具体的には、取得部３１１は、通信インタフェース３４を介して、暗号化装置３０の利用者等によって入力された平文μと属性ｘとを受け付ける。平文μは、暗号化した上で送信するメッセージであり、平文μ∈｛０，１｝である。属性ｘは、暗号文に関連付けられる属性であり、属性ｘ∈｛０，１｝^Ｌである。取得部３１１は、平文μと属性ｘとをメモリ３２に書き込む。

　（ステップＳ３２：暗号化処理）
　暗号化装置３０の暗号化部３１２は、属性ｘを設定して平文μを暗号化した暗号文ｃｔを生成する。
　具体的には、暗号化部３１２は、公開パラメータ記憶部３３１から公開パラメータｐｐを読み出すとともに、メモリ３２から平文μと属性ｘとを読み出す。暗号化部３１２は、数２６に示すように、行列Ｓと行列Ｅ_Ａとエラーベクトルｅ_ｖとを生成する。

　暗号化部３１２は、数２７に示すように、ｉ∈｛０，１，．．．，Ｌ｝の各整数ｉと、ｊ∈［Ｍ］の各整数ｊとについて、行列Ｒ_ｉ，ｊを生成する。

　暗号化部３１２は、数２８に示すように、ｉ∈｛０，１，．．．，Ｌ｝の各整数ｉと、ｊ∈［Ｍ］の各整数ｊとについて、行列Ｅ_ｉ［ｊ］を生成する。ここで、Ｅ_ｉ［ｊ］及びＥ_Ａ［ｊ］は、それぞれ行列Ｅ_ｉ及び行列Ｅ_Ａのｊ列目を示す。

　暗号化部３１２は、数２９に示すように行列Ｃを生成し、数３０に示すように行列Ｃ_ｘを生成する。

　行列Ｃには、平文μが設定されており、属性ｘが満たすポリシーｆに対応する復号鍵ｓｋ_ｆによって復号可能な構成になっている。
　ここで、数３１は、テンソル積を示す。

　また、数３２である。

　暗号化部３１２は、数３３に示すように、行列Ｒと行列Ｅ_Ｆとを生成する。

　暗号化部３１２は、数３４に示すように、行列Ｆを生成する。

　数３４に示すように、行列Ｆには、平文μと乱数である行列Ｒとが設定されている。行列Ｆは、行列に含まれる行列Ｂ_０に代えて行列Ｂが含まれており、属性ｘが満たすポリシーｆに対応する復号鍵ｓｋ_ｆによって復号されない構成になっている。

　暗号化部３１２は、数３５に示すように、ｉ∈｛０，１，．．．，Ｌ｝の各整数ｉと、ｊ∈［Ｍ］の各整数ｊと、ｋ∈［Ｎ］の各整数ｋとについて、行列Ｅ^（ｋ） _Ａと、ベクトルｅ^（ｋ） _ｖと、行列Ｒ^（ｋ） _ｉ，ｊとを生成する。

　暗号化部３１２は、数３６に示すように、ベクトルＥ^（ｋ） _ｉと行列Ｅ^（ｋ）とを生成する。ここで、Ｅ^（ｋ） _ｉ［ｊ］及び行列Ｅ^（ｋ） _Ａ［ｊ］は、それぞれ行列Ｅ^（ｋ） _ｉ及び行列Ｅ^（ｋ） _Ａのｊ列目を示す。

　暗号化部３１２は、数３７に示すように、行列Ｓ^（１），．．．，Ｓ^（Ｎ）を生成する。

　暗号化部３１２は、数３８に示すように行列Ｄを生成し、数３９に示すように行列Ｄ^（ｋ） _ｘを生成する。

　つまり、行列Ｄは、行列Ｆに含まれる乱数である行列Ｒが暗号化されている。

　暗号化部３１２は、属性ｘと、行列Ｃと、行列Ｃ_ｘと、行列Ｆと、行列Ｄと、ｋ∈［Ｎ］の各整数ｋについての行列Ｄ^（ｋ） _ｘとを暗号要素とする暗号文ｃｔを、メモリ３２に書き込む。つまり、暗号文ｃｔには、平文μが設定された暗号要素である行列Ｃと、属性ｘが設定された暗号要素である行列Ｃ_ｘと、平文μと乱数である行列Ｒとが設定され、属性ｘが満たすポリシーｆに対応する復号鍵ｓｋ_ｆによって復号されない暗号要素である行列Ｆと、乱数である行列Ｒが暗号化された暗号要素である行列Ｄとが含まれる。

　（ステップＳ３３：出力処理）
　暗号化装置３０の出力部３１３は、暗号文ｃｔを出力する。
　具体的には、出力部３１３は、メモリ３２から暗号文ｃｔを読み出す。そして、出力部３１３は、通信インタフェース３４を介して、暗号文ｃｔを準同型演算装置４０に送信する。

　（ステップＳ３４：暗号文取得処理）
　準同型演算装置４０の暗号文取得部４１６は、通信インタフェース４４を介して、出力部３１３によって送信された暗号文ｃｔを受信する。暗号文取得部４１６は、受信された暗号文ｃｔを暗号文記憶部４３２に書き込む。

　つまり、暗号化装置３０は、数４０から数４１に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔを生成する。

　図９を参照して、実施の形態１に係るＥｖａｌ処理を説明する。
　Ｅｖａｌ処理は、暗号文ｃｔに対して準同型演算を行う際に、準同型演算装置４０によって実行される。実施の形態１に係るＥｖａｌ処理は、実施の形態１に係る準同型演算方法と準同型演算プログラムの処理とに相当する。

　（ステップＳ４１：暗号文取得処理）
　暗号文取得部４１６は、演算対象の暗号文ｃｔ^（１），．．．，ｃｔ^（ｋ）を取得する。ここで、ｋは１以上の整数である。
　具体的には、暗号文取得部４１６は、通信インタフェース４４を介して、準同型演算装置４０の利用者等によって指定された暗号文ｃｔ^（１），．．．，ｃｔ^（ｋ）を暗号文記憶部４３２から読み出す。暗号文取得部４１６は、読み出された暗号文ｃｔ^（１），．．．，ｃｔ^（ｋ）をメモリ４２に書き込む。

　（ステップＳ４２：ポリシー取得処理）
　準同型演算装置４０のポリシー取得部４１７は、ポリシーの集合であるポリシー集合Ｆ：＝｛ｆ_１，．．．，ｆ_ｄ｝を取得する。ここで、ｄは、１以上の整数である。
　具体的には、ポリシー取得部４１７は、通信インタフェース４４を介して、準同型演算装置４０の利用者等によって入力されたポリシー集合Ｆを受け付ける。ポリシー取得部４１７は、受け付けられたポリシー集合Ｆをメモリ４２に書き込む。
　なお、準同型演算を行うためには、ステップＳ４１で読み出されたｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ^（ｉ）が、ポリシー集合Ｆに含まれるいずれかのｆ_１，．．．，ｆ_ｄを満たす必要がある。言い換えると、ｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ^（ｉ）が、いずれかのｆ_１，．．．，ｆ_ｄに関連付けられた復号鍵ｓｋ_ｆで復号可能である必要がある。つまり、ｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ^（ｉ）に設定された属性を属性ｘ_ｉとすると、ｉ＝１，．．．，ｋの各整数ｉについて、あるｊ∈［ｄ］に対して、ｆ_ｊ（ｘ_ｉ）＝０を満たす必要がある。

　（ステップＳ４３：演算取得処理）
　準同型演算装置４０の演算取得部４１８は、実行する準同型演算ｇを取得する。
　具体的には、演算取得部４１８は、通信インタフェース４４を介して、準同型演算装置４０の利用者等によって入力された準同型演算ｇを受け付ける。演算取得部４１８は、受け付けられた準同型演算ｇをメモリ４２に書き込む。

　（ステップＳ４４：暗号文変換処理）
　準同型演算装置４０の暗号文変換部４１２は、ｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ^（ｉ）を暗号文ｃｔ^（ｉ）～：＝（Ｃ^～，Ｆ^～，Ｄ^～）に変換する。
　具体的には、暗号文変換部４１２は、ｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ^（ｉ）を対象として、まずＡｐｐｌｙアルゴリズムを実行し、その後Ｅｘｐａｎｓｉｏｎアルゴリズムを実行する。但し、Ａｐｐｌｙアルゴリズムは、１度も準同型演算が行われていない暗号文ｃｔ^（ｉ）についてのみ実行される。つまり、暗号文ｃｔ^（ｉ）が暗号化装置３０によって生成され、図８のステップＳ３３で出力された暗号文ｃｔである場合には、Ａｐｐｌｙアルゴリズムは実行され、暗号文ｃｔ^（ｉ）が後述するステップＳ４６で出力された暗号文ｃｔ^＊である場合には、Ａｐｐｌｙアルゴリズムは実行されない。暗号文ｃｔ^（ｉ）が後述するステップＳ４６で出力された暗号文ｃｔ^＊である場合には、Ｅｘｐａｎｓｉｏｎアルゴリズムだけが実行される。
　ここでは、表記の簡略化のため、対象とする暗号文ｃｔ^（ｉ）を暗号文ｃｔと書き、暗号文ｃｔ^（ｉ）が変換された暗号文ｃｔ^（ｉ）～を暗号文ｃｔ^～と書く。また、対象とする暗号文ｃｔ^（ｉ）が満たすポリシーｆ_ｊをポリシーｆと書く。

　Ａｐｐｌｙアルゴリズムについて説明する。
　暗号文変換部４１２は、数４２に示すように、行列Ｈを計算する。

　ＥｖＲｅｌａｔｉｏｎアルゴリズムは非特許文献２に記載されている。

　暗号文変換部４１２は、行列Ｃ_ｆ：＝Ｈ^ＴＣ_ｘを生成する。暗号文変換部４１２は、数４３に示すように、行列Ｃ＾ｆを生成する。

　暗号文変換部４１２は、ｉ∈［ｋ］の各整数ｉについて、数４４に示すように、行列Ｄ^（ｉ） _ｆを生成する。

　暗号文変換部４１２は、数４５に示すように、行列Ｄ_ｆを生成する。

　暗号文変換部４１２は、行列Ｄ＾_ｆ：＝Ｄ_ｆ＋Ｄを生成する。

　つまり、暗号文変換部４１２は、数４６に示すＡｐｐｌｙアルゴリズムを実行する。

　Ｅｘｐａｎｓｉｏｎアルゴリズムについて説明する。
　ここで、対象とする暗号文ｃｔ^（ｉ）が後述するステップＳ４６で出力された暗号文ｃｔ^＊：＝（Ｃ^＊，Ｆ^＊，Ｄ^＊）である場合には、Ｃ＾_ｆ：＝Ｃ^＊，Ｆ：＝Ｆ^＊，Ｄ＾_ｆ：＝Ｄ^＊とする。

　暗号文変換部４１２は、行列Ｆをそのまま行列Ｆ^～とする。

　暗号文変換部４１２は、数４７に示すように、行列Ｄ^～を生成する。

　暗号文変換部４１２は、数４８に示すように、行列Ｃ^～を生成する。

　ここで、行列Ｘは、数４９に示す通りである。

　また、行列ｓは、数５０に示す通りである。

　なお、ベクトルｒ’_ｆ∈｛０，１｝^Ｎは、ｆをランダムオラクルにクエリすることによって得られるベクトルである。つまり、ベクトルｒ’_ｆは、ランダムなベクトルである。また、Ｂ_ｆは、数２１に示す通りである。

　暗号文変換部４１２は、暗号文ｃｔ^～：＝（Ｃ^～，Ｆ^～，Ｄ^～）をメモリ４２に書き込む。

　つまり、暗号文変換部４１２は、数５１に示すＥｘｐａｎｓｉｏｎアルゴリズムを実行する。

　（ステップＳ４５：準同型演算処理）
　準同型演算装置４０の準同型演算部４１３は、ｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ^（ｉ）～に対して、準同型演算ｇを実行して、暗号文ｃｔ^＊：＝（Ｃ^＊，Ｆ^＊，Ｄ^＊）を生成する。
　具体的には、準同型演算部４１３は、ｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ^（ｉ）～を読み出す。そして、準同型演算部４１３は、ｉ＝１，．．．，ｋの各整数ｉについての暗号文ｃｔ^（ｉ）～を入力として、非特許文献３の“３．２　Ｈｏｍｏｍｏｒｐｈｉｃ　Ｏｐｅｒａｔｉｏｎｓ”に記載された準同型演算の演算方法に従い、準同型演算ｇを実行して、暗号文ｃｔ^＊を生成する。準同型演算部４１３は、生成された暗号文ｃｔ^＊をメモリ４２に書き込む。

　具体例として、２つの暗号文ｃｔ^（１）～：＝（Ｃ_１，Ｆ_１，Ｄ_１）とｃｔ^（２）～：＝（Ｃ_２，Ｆ_２，Ｄ_２）とについて、準同型加算する場合を説明する。この場合、準同型演算部４１３は、Ｃ^＊：＝Ｃ_１＋Ｃ_２，Ｆ^＊：＝Ｆ_１＋Ｆ_２，Ｄ^＊：＝Ｄ_１＋Ｄ_２のように、各暗号要素を計算する。

　また、具体例として、２つの暗号文ｃｔ^（１）～：＝（Ｃ_１，Ｆ_１，Ｄ_１）とｃｔ^（２）～：＝（Ｃ_２，Ｆ_２，Ｄ_２）とについて、準同型乗算する場合を説明する。この場合、準同型演算部４１３は、数５２に示すように、各暗号要素を計算する。

　（ステップＳ４６：出力処理）
　準同型演算装置４０の出力部４１４は、暗号文ｃｔ^＊を出力する。
　具体的には、出力部４１４は、メモリ４２から暗号文ｃｔ^＊を読み出す。そして、出力部４１４は、暗号文ｃｔ^＊を暗号文記憶部４３２に書き込む。

　つまり、準同型演算装置４０は、数５３に示すＥｖａｌｕａｔｉｏｎアルゴリズムを実行して、暗号文ｃｔ^＊を生成する。

　なお、Ｈ．Ｏｐアルゴリズムは、非特許文献３に記載された準同型演算の演算アルゴリズムのことである。

　図１０を参照して、実施の形態１に係るＤｅｃ処理を説明する。
　Ｄｅｃ処理は、暗号文ｃｔを復号する際に、主に復号装置５０によって実行される。実施の形態１に係るＤｅｃ処理は、実施の形態１に係る復号方法と復号プログラムの処理とに相当する。

　（ステップＳ５１：取得処理）
　復号装置５０の取得部５１１は、復号の対象とする暗号文ｃｔ^（Ｆ）：＝（Ｃ＾_Ｆ，Ｆ，Ｄ＾_Ｆ）を取得する。
　具体的には、取得部５１１は、通信インタフェース５４を介して、準同型演算装置４０に暗号文ｃｔ^（Ｆ）の取得要求を送信する。準同型演算装置４０の出力部４１４は、取得要求を受信すると、要求された暗号文ｃｔ^（Ｆ）を暗号文記憶部４３２から読み出す。この際、準同型演算装置４０の暗号文変換部４１２は、暗号文ｃｔ^（Ｆ）が図８のステップＳ３３で出力された暗号文ｃｔである場合には、上述したＡｐｐｌｙアルゴリズムを実行して、暗号文ｃｔを暗号文ｃｔ^（Ｆ）：＝（Ｃ＾_Ｆ，Ｆ，Ｄ＾_Ｆ）に変換する。また、準同型演算装置４０の暗号文変換部４１２は、暗号文ｃｔ^（Ｆ）が図９のステップＳ４６で出力された暗号文ｃｔ^＊：＝（Ｃ^＊，Ｆ^＊，Ｄ^＊）である場合には、暗号文ｃｔ^（Ｆ）：＝（Ｃ＾_ｆ：＝Ｃ^＊，Ｆ：＝Ｆ^＊，Ｄ＾_ｆ：＝Ｄ^＊）に変換する。そして、出力部４１４は、変換された暗号文ｃｔ^（Ｆ）を、通信インタフェース４４を介して復号装置５０に送信する。取得部５１１は、準同型演算装置４０から送信された暗号文ｃｔ^（Ｆ）を受信する。取得部５１１は、受信された暗号文ｃｔ^（Ｆ）をメモリ５２に書き込む。
　暗号文ｃｔ^（Ｆ）は、ポリシー集合Ｆ：＝｛ｆ_１，．．．，ｆ_ｄ｝に関連付けられた復号鍵ｓｋ_ｆ１，．．．，ｓｋ_ｆｄによって復号可能な暗号文であることを意味する。

　（ステップＳ５２：復号処理）
　復号装置５０の復号部５１２は、暗号文ｃｔ^（Ｆ）を復号鍵ｓｋ_ｆ１：＝ｒ_ｆ１，．．．，ｓｋ_ｆｄ：＝ｒ_ｆｄにより復号して、値μ^～を計算する。
　具体的には、復号部５１２は、ｊ∈［ｄ］の各整数ｊについて、ランダムオラクルにクエリして行列ｒ’_ｆｊ：＝Ｏ（Ａ，ｆ_ｊ）を取得する。復号部５１２は、数５４に示すように、ｊ∈［ｄ］の各整数ｊについての復号鍵ｓｋ_ｆｊを連結して、復号鍵ｒ_Ｆ ^Ｔを生成する。

　復号部５１２は、数５５に示すように、ベクトルｃを計算する。

　復号部５１２は、数５６に示すように、値μ^～を計算する。

　ここで、ベクトルｕは、数５７に示す通りである。

　（ステップＳ５３：出力処理）
　復号装置５０の出力部５１３は、値μ^～の絶対値がｑ／４未満であれば０を出力し、そうでなければ１を出力する。

　つまり、復号装置５０は、数５８に示すＤｅｃアルゴリズムを実行して、暗号文ｃｔ^（Ｆ）を復号する。

　＊＊＊実施の形態１の効果＊＊＊
　以上のように、実施の形態１に係る暗号システム１０では、暗号要素Ｆを用いて、暗号要素である行列Ｃを暗号要素である行列Ｃ^～に変換する。これにより、暗号要素Ｃ内の要素をポリシー集合Ｆに関連付けてしまうことなく、準同型演算を行うことが可能になる。そのため、暗号文ｃｔ^＊を入力として再び柔軟な準同型演算を行うことが可能になる。

　暗号文ｃｔ^＊を入力として再び柔軟な準同型演算を行うことが可能になるという効果が得られる理由を説明する。
　暗号化装置３０により生成された暗号文ｃｔ：＝（ｘ，Ｃ，Ｃ_ｘ，Ｆ，Ｄ，｛Ｄ^（ｋ） _ｘ｝_ｋ）を入力として、図９のステップＳ４４で説明したＡｐｐｌｙアルゴリズムが実行された結果、暗号文ｃｔ^（ｆ）：＝（Ｃ＾_ｆ，Ｆ，Ｄ＾_ｆ）が得られたとする。
　このとき、暗号文ｃｔ^（ｆ）は、復号鍵ｔ∈Ｚ_ｑ ^{ｍ＋Ｎ＋１}と、小さなランダム行列Ｒ∈Ｚ_ｑ ^ｎ×Ｍとに対して数５９に示す（１）から（３）の関係を満たしている。

　暗号文ｃｔ^（ｆ）を入力として、図９のステップＳ４４で説明したＥｘｐａｎｓｉｏｎアルゴリズムが実行された結果、暗号文ｃｔ^～：＝（Ｃ^～，Ｆ^～，Ｄ^～）が得られたとする。このとき、暗号文ｃｔ^～は、復号鍵ｔに、復号鍵ｔ_ｆを連結してできる復号鍵ｔ^～：＝［ｔ｜｜ｔ_ｆ］と、ランダム行列Ｒ^～とに対して、以下に説明するように、数５９に示す（１）から（３）の関係を満たす状態が保持されている。

　行列Ｆがそのまま行列Ｆ^～になる。そのため、ランダム行列Ｒがそのままランダム行列Ｒ^～になる。したがって、数５９の（２）に示す関係は満たされる。

　行列Ｄ^～は、数４７に示すように生成される。このとき、数６０に示す関係が成立する。

　したがって、数５９の（３）の関係は満たされる。

　行列Ｃ^～は、数４８に示すように生成される。このとき、行列Ｘの構成により、数６１の関係が成立する。

　したがって、数６２の関係が成立する。

　その結果、数６３の関係が成立しており、数５９の（１）の関係は満たされる。

　暗号文ｃｔ^～を入力として、図９のステップＳ４５で説明した準同型演算ｇが実行された結果、暗号文ｃｔ^＊：＝（Ｃ^＊，Ｆ^＊，Ｄ^＊）が得られたとする。このとき、非特許文献３で説明されているように、暗号文ｃｔ^＊についても、数５９に示す（１）から（３）の関係を満たす状態が保持されている。
　つまり、暗号化装置３０により生成された暗号文ｃｔを入力としてＡｐｐｌｙアルゴリズムが実行された結果得られた暗号文ｃｔ^（ｆ）が満たす関係を、準同型演算ｇが実行された結果得られた暗号文ｃｔ^＊が保持している。そのため、暗号化装置３０により生成された暗号文ｃｔに代えて、準同型演算ｇが実行された結果得られた暗号文ｃｔ^＊を入力としてＥｘｐａｎｓｉｏｎアルゴリズムが実行された場合にも、この関係を満たす状態とすることができる。その結果、準同型演算ｇが実行された結果得られた暗号文ｃｔ^＊についても、暗号化装置３０により生成された暗号文ｃｔと同様に、柔軟な準同型演算を行うことが可能である。

　つまり、図９のステップＳ４４では、暗号文変換部４１２は、暗号文取得部４１６によって取得された暗号文ｃｔに含まれる暗号要素である行列Ｃ及び行列Ｃ_ｘを、暗号要素である行列Ｆ及び暗号要素である行列Ｄにより、ポリシー取得部４１７によって取得されたポリシー集合Ｆに対応する復号鍵ｓｋ_Ｆによって復号可能な暗号要素である行列Ｃ^～に変換する。また、暗号文変換部４１２は、行列Ｄについても、合わせて行列Ｄ^～に変換する。これにより、暗号文変換部４１２は、暗号文ｃｔを暗号文ｃｔ^～に変換する。
　すなわち、暗号文変換部４１２は、平文μが設定された暗号要素である行列Ｃと、属性ｘが設定された暗号要素である行列Ｃ_ｘとを、平文μと乱数である行列Ｒとが設定され、属性ｘが満たすポリシーｆに対応する復号鍵ｓｋ_ｆによって復号されない暗号要素である行列Ｆと、乱数である行列Ｒが暗号化された暗号要素である行列Ｄとを用いて変換する。このように、暗号文変換部４１２は、行列Ｆ及び行列Ｄを用いることにより、暗号文と復号鍵及び乱数Ｒとの間に成立する関係性を保持したまま、準同型演算を実行可能にしている。

　＊＊＊他の構成＊＊＊
　＜変形例１＞
　実施の形態１では、鍵生成装置２０と暗号化装置３０と準同型演算装置４０と復号装置５０との機能構成要素がソフトウェアで実現された。しかし、変形例１として、機能構成要素はハードウェアで実現されてもよい。この変形例１について、実施の形態１と異なる点を説明する。

　図１１を参照して、変形例１に係る鍵生成装置２０の構成を説明する。
　機能がハードウェアで実現される場合、鍵生成装置２０は、プロセッサ２１とメモリ２２とストレージ２３とに代えて、処理回路２５を備える。処理回路２５は、鍵生成装置２０の機能構成要素と、メモリ２２とストレージ２３との機能とを実現する専用の電子回路である。

　図１２を参照して、変形例１に係る暗号化装置３０の構成を説明する。
　機能がハードウェアで実現される場合、暗号化装置３０は、プロセッサ３１とメモリ３２とストレージ３３とに代えて、処理回路３５を備える。処理回路３５は、暗号化装置３０の機能構成要素と、メモリ３２とストレージ３３との機能とを実現する専用の電子回路である。

　図１３を参照して、変形例１に係る準同型演算装置４０の構成を説明する。
　機能がハードウェアで実現される場合、準同型演算装置４０は、プロセッサ４１とメモリ４２とストレージ４３とに代えて、処理回路４５を備える。処理回路４５は、準同型演算装置４０の機能構成要素と、メモリ４２とストレージ４３との機能とを実現する専用の電子回路である。

　図１４を参照して、変形例１に係る復号装置５０の構成を説明する。
　機能がハードウェアで実現される場合、復号装置５０は、プロセッサ５１とメモリ５２とストレージ５３とに代えて、処理回路５５を備える。処理回路５５は、復号装置５０の機能構成要素と、メモリ５２とストレージ５３との機能とを実現する専用の電子回路である。

　処理回路２５，３５，４５，５５は、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ（Ｇａｔｅ　Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ　Ｓｐｅｃｉｆｉｃ　Ｉｎｔｅｇｒａｔｅｄ　Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ－Ｐｒｏｇｒａｍｍａｂｌｅ　Ｇａｔｅ　Ａｒｒａｙ）が想定される。
　鍵生成装置２０の各機能構成要素の機能を１つの処理回路２５で実現してもよいし、各機能構成要素の機能を複数の処理回路２５に分散させて実現してもよい。同様に、暗号化装置３０と準同型演算装置４０と復号装置５０とのそれぞれについて、各機能構成要素の機能を１つの処理回路３５，４５，５５で実現してもよいし、各機能構成要素の機能を複数の処理回路３５，４５，５５に分散させて実現してもよい。

　＜変形例２＞
　変形例２として、一部の機能がハードウェアで実現され、他の機能がソフトウェアで実現されてもよい。つまり、各機能構成要素のうち、一部の機能がハードウェアで実現され、他の機能がソフトウェアで実現されてもよい。

　プロセッサ２１，３１，４１，５１とメモリ２２，３２，４２，５２とストレージ２３，３３，４３，５３と処理回路２５，３５，４５，５５とを、総称して「プロセッシングサーキットリー」という。つまり、各機能構成要素の機能は、プロセッシングサーキットリーにより実現される。

　＊＊＊記法の説明＊＊＊
　Ａがランダムな変数または分布であるとき、数６４は、Ａの分布に従いＡからｙをランダムに選択することを表す。つまり、数６４において、ｙは乱数である。

　Ａが集合であるとき、数６５は、Ａからｙを一様に選択することを表す。つまり、数６５において、ｙは一様乱数である。

　数６６は、ｙがｚにより定義された集合であること、又はｙがｚを代入された集合であることを表す。

　ａが定数であるとき、数６７は、機械（アルゴリズム）Ａが入力ｘに対しａを出力することを表す。

　Ｚ_ｑは、位数ｑの整数の群を示す。また、ｙ∈Ｚ_ｑ ^ｖは、ｙはＺ_ｑ上のｖ個の要素を有するベクトルであることを示す。また、ｙ∈Ｚ_ｑ ^ｖ×ｗは、ｙはＺ_ｑ上の要素を持つ、ｖ行ｗ列の行列であることを示す。

　１０　暗号システム、２０　鍵生成装置、２１　プロセッサ、２２　メモリ、２３　ストレージ、２４　通信インタフェース、２５　処理回路、２１１　取得部、２１２　マスタ鍵生成部、２１３　復号鍵生成部、２１４　出力部、２３１　マスタ鍵記憶部、３０　暗号化装置、３１　プロセッサ、３２　メモリ、３３　ストレージ、３４　通信インタフェース、３５　処理回路、３１１　取得部、３１２　暗号化部、３１３　出力部、３３１　公開パラメータ記憶部、４０　準同型演算装置、４１　プロセッサ、４２　メモリ、４３　ストレージ、４４　通信インタフェース、４５　処理回路、４１１　取得部、４１２　暗号文変換部、４１３　準同型演算部、４１４　出力部、４１５　公開パラメータ取得部、４１６　暗号文取得部、４１７　ポリシー取得部、４１８　演算取得部、４３１　公開パラメータ記憶部、４３２　暗号文記憶部、５０　復号装置、５１　プロセッサ、５２　メモリ、５３　ストレージ、５４　通信インタフェース、５５　処理回路、５１１　取得部、５１２　復号部、５１３　出力部、５３１　鍵記憶部、５３２　条件記憶部、５３３　結果記憶部、λ　セキュリティパラメータ、ｐｐ　公開パラメータ、ｍｓｋ　マスタ秘密鍵、ｓｋ_ｆ　復号鍵、μ　平文、ｘ　属性、ｃｔ，ｃｔ^（Ｆ），ｃｔ^～，ｃｔ^＊　暗号文、Ｆ　ポリシー集合、ｇ　準同型演算。

Claims

　平文μが設定された暗号要素Ｃと、属性ｘが設定された暗号要素Ｃ_ｘと、前記平文μが設定され、前記属性ｘが満たすポリシーｆに対応する復号鍵ｓｋ_ｆによって復号されない暗号要素Ｆとを含む暗号文ｃｔを取得する暗号文取得部と、
　ポリシーの集合であるポリシー集合Ｆを取得するポリシー取得部と、
　前記暗号文取得部によって取得された前記暗号文ｃｔに含まれる前記暗号要素Ｃを、前記暗号要素Ｆにより、前記ポリシー取得部によって取得された前記ポリシー集合Ｆに対応する復号鍵ｓｋ_Ｆによって復号可能な暗号要素Ｃ^～に変換することにより、前記暗号文ｃｔを暗号文ｃｔ^～に変換する暗号文変換部と、
　前記暗号文変換部によって変換された前記暗号文ｃｔ^～に対して準同型演算ｇを行い暗号文ｃｔ^＊を生成する準同型演算部と
を備える準同型演算装置。
　前記暗号要素Ｆには、乱数Ｒが設定され、
　前記暗号文ｃｔには、前記乱数Ｒが暗号化された暗号要素Ｄが含まれ、
　前記暗号文変換部は、前記暗号要素Ｃを、前記暗号要素Ｆ及び前記暗号要素Ｄにより、前記暗号要素Ｃ^～に変換する
請求項１に記載の準同型演算装置。
　前記暗号文ｃｔは、数１に示す前記暗号要素Ｃと、数２に示す前記暗号要素Ｃ_ｘと、数３に示す前記暗号要素Ｆと、数４に示す暗号要素Ｄとを含む
請求項２に記載の準同型演算装置。
　前記暗号変換部は、数５に示すように前記暗号要素Ｃを暗号要素Ｃ＾_ｆに変換し、数６に示すように前記暗号要素Ｃ＾_ｆを前記暗号要素Ｃ^～に変換する
請求項３に記載の準同型演算装置。
　前記準同型演算部は、前記暗号要素Ｃ^～に対して前記準同型演算ｇを行い暗号要素Ｃ^＊を生成し、前記暗号要素Ｆに対して前記準同型演算ｇを行い暗号要素Ｆ^＊を生成し、前記暗号要素Ｄを変換した暗号要素Ｄ^～に対して前記準同型演算ｇを行い暗号要素Ｄ^＊を生成し、前記暗号要素Ｃ^＊と前記暗号要素Ｆ^＊と前記暗号要素Ｄ^＊とを含む前記暗号文ｃｔ^＊を生成する
請求項３又は４に記載の準同型演算装置。
　前記暗号変換部は、数７に示すように前記暗号要素Ｄを前記暗号要素Ｄ^～に変換する
請求項５に記載の準同型演算装置。
　前記準同型演算部は、前記暗号要素Ｃ^～に対して準同型演算ｇを行い生成された暗号要素Ｃ^＊を含む前記暗号文ｃｔ^＊を生成し、
　前記暗号文取得部は、前記準同型演算部によって生成された前記暗号文ｃｔ^＊を取得し、
　前記暗号文変換部は、前記暗号文ｃｔ^＊に含まれる前記暗号要素Ｃ^＊を、前記暗号要素Ｆにより、前記復号鍵ｓｋ_Ｆとは異なる復号鍵ｓｋ_Ｆ’によって復号可能な暗号要素Ｃ^～に変換することにより、暗号文ｃｔ^＊を暗号文ｃｔ^～に変換する
請求項１に記載の準同型演算装置。
　平文μが設定された暗号要素Ｃと、属性ｘが設定された暗号要素Ｃ_ｘと、前記平文μが設定され、前記属性ｘが満たすポリシーｆに対応する復号鍵ｓｋ_ｆによって復号されない暗号要素Ｆとを含む暗号文ｃｔを生成する暗号化装置と、
　前記暗号化装置によって生成された前記暗号文ｃｔに含まれる前記暗号要素Ｃを、前記暗号要素Ｆにより、ポリシーの集合であるポリシー集合Ｆに対応する復号鍵ｓｋ_Ｆによって復号可能な暗号要素Ｃ^～に変換することにより、前記暗号文ｃｔを暗号文ｃｔ^～に変換し、変換された前記暗号文ｃｔ^～に対して準同型演算ｇを行い暗号文ｃｔ^＊を生成する準同型演算装置と
を備える暗号システム。
　平文μが設定された暗号要素Ｃと、属性ｘが設定された暗号要素Ｃ_ｘと、前記平文μが設定され、前記属性ｘが満たすポリシーｆに対応する復号鍵ｓｋ_ｆによって復号されない暗号要素Ｆとを含む暗号文ｃｔを取得する暗号文取得処理と、
　ポリシーの集合であるポリシー集合Ｆを取得するポリシー取得処理と、
　前記暗号文取得処理によって取得された前記暗号文ｃｔに含まれる前記暗号要素Ｃを、前記暗号要素Ｆにより、前記ポリシー取得処理によって取得された前記ポリシー集合Ｆに対応する復号鍵ｓｋ_Ｆによって復号可能な暗号要素Ｃ^～に変換することにより、前記暗号文ｃｔを暗号文ｃｔ^～に変換する暗号文変換処理と、
　前記暗号文変換処理によって変換された前記暗号文ｃｔ^～に対して準同型演算ｇを行い暗号文ｃｔ^＊を生成する準同型演算処理と
をコンピュータに実行させる準同型演算プログラム。