(57)【要約】【課題】計算効率の向上を図ることができる暗号化システムを提供する。【解決手段】多項式の演算が可能な準同型暗号方式を用いた暗号化システムであって、暗号化鍵と、復号鍵とを生成する鍵生成手段Ｓ１１０と、ｍ行ｋ列で示される第１平文から第１要素、及びｋ行ｌ列で示される第２平文から第２要素をそれぞれ導出する導出手段Ｓ１２０と、前記第１要素から第１暗号文、及び前記第２要素から第２暗号文をそれぞれ算出する暗号文算出手段Ｓ１３０と、前記第１暗号文と、前記第２暗号文との内積を演算し、第１内積値、第２内積値、第３内積値、及び第４内積値を取得する内積手段Ｓ１４０と、前記第１内積値、前記第２内積値、前記第３内積値、及び前記第４内積値から復号文を算出する復号文算出手段Ｓ１５０と、を備える。前記復号文は、前記第１平文と前記第２平文との行列乗算の結果を含むことを特徴とする。【選択図】図１
2019101083.tif 000002
【特許請求の範囲】
【請求項１】
多項式の演算が可能な準同型暗号方式を用いた暗号化システムであって、
平文に対応する暗号文の算出に用いる暗号化鍵と、前記暗号文に対応する復号文の算出に用いる復号鍵とを生成する鍵生成手段と、
下記の［数１］に基づき、ｍ行ｋ列で示される第１平文から第１要素、及びｋ行ｌ列で示される第２平文から第２要素をそれぞれ導出する導出手段と、
下記の［数２］に示す暗号化アルゴリズムを用いて、前記第１要素から第１暗号文、及び前記第２要素から第２暗号文をそれぞれ算出する暗号文算出手段と、
前記第１暗号文と、前記第２暗号文との内積を演算し、下記の［数３］に示す第１内積値、第２内積値、第３内積値、及び第４内積値を取得する内積手段と、
下記の［数４］に示す復号アルゴリズムを用いて、前記第１内積値、前記第２内積値、前記第３内積値、及び前記第４内積値から前記復号文を算出する復号文算出手段と、
を備え、
前記復号文は、下記の［数５］に基づく前記第１平文と前記第２平文との行列乗算の結果を含むこと
を特徴とする暗号化システム。
【数１】
2019101083.tif 000036
ここで、左辺Ｍ（ハット）は、前記第１要素又は前記第２要素を示し、Ｍβ(r)は前記第１平文又は前記第２平文のβ行に対応するベクトルを示し、Ｍβ(c)は前記第１平文又は前記第２平文のβ列に対応するベクトルを示し、値βは値ｍ、値ｋ、及び値ｌのうち最大の値と等しく、値ｘは変数を示し、変数ベクトルＸは下記の［数６］で示される。
【数２】
2019101083.tif 000037
ここで、Ｅｎｃは、前記暗号化鍵（ｐｋ）を用いる前記暗号化アルゴリズムを示し、ｃ1及びｃ2は、前記第１暗号文の暗号文要素を示し、ｄ1及びｄ2は、前記第２暗号文の暗号文要素を示し、Ｒqは暗号文空間を示す。
【数３】
2019101083.tif 000038
ここで、Ｗ1は前記第１内積値を示し、Ｗ21は前記第２内積値を示し、Ｗ22は前記第３内積値を示し、ξは前記第４内積値を示し、ｑは素数を示し、Ｚqは暗号文空間の集合を示す。
【数４】
2019101083.tif 000039
ここで、ＤｅｃＩＰ*は前記復号鍵（Ｓ）を用いた前記復号アルゴリズムを示し、Ｓ*＝ＳＳTは内積算出対応復号鍵を示し、ｎは正の整数を示し、ｗk、ｕk、及びｖkはそれぞれ係数を示す。
【数５】
2019101083.tif 000040
ここで、ｍijは前記復号文に含まれる要素を示し、ｐは前記素数ｑよりも小さい素数を示し、Ｖｅｃは下記の［数７］で示される係数ベクトルを示す。
【数６】
2019101083.tif 000041
【数７】
2019101083.tif 000042
ここで、Ｒpは平文空間を示す。
【請求項２】
前記値βは、下記の［数８］で示す条件を満たすこと
を特徴とする請求項１記載の暗号化システム。
【数８】
2019101083.tif 000043
【請求項３】
前記内積手段は、下記の［数９］及び［数１０］に基づき、前記第１内積値、前記第２内積値、前記第３内積値、及び前記第４内積値を取得すること
を特徴とする請求項１又は２記載の暗号化システム。
【数９】
2019101083.tif 000044
【数１０】
2019101083.tif 000045
ここで、Ｗ2は前記第２内積値Ｗ21及び前記第３内積値Ｗ22を含む内積値示す。
【請求項４】
前記復号文算出手段は、下記の［数１１］及び前記［数５］に基づき、前記復号文を算出すること
を特徴とする請求項３記載の暗号化システム。
【数１１】
2019101083.tif 000046
【請求項５】
前記値ｋは、前記値ｍ及び前記値ｌとは異なる値であること
を特徴とする請求項１〜４の何れか１項記載の暗号化システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多項式の演算が可能な準同型暗号方式を用いた暗号化システムに関するものである。
【背景技術】
【０００２】
従来、統計計算や機械学習の分野において、最も基本的で有用な操作の１つとして、行列乗算が挙げられる。行列乗算は、例えばクラウドサーバ等の必ずしも安全ではない環境において、機密情報を含むデータの解析を行う必要がある場合に用いられる。特に、データの解析を委託する際、情報漏洩を防止するために、準同型暗号が注目を集めている。
【０００３】
準同型暗号とは、データを暗号化した状態で計算できる技術である。例えば、加法と乗法とが計算できる公開鍵準同型暗号（Somewhat PHE）であれば、暗号化前の平文に対応する行列の各項目が暗号化されたセキュアな行列乗算の自明な構成ができる。準同型暗号方式を用いた技術として、例えば特許文献１、非特許文献１、及び非特許文献２等が開示されている。
【０００４】
特許文献１では、ｃ1＝ｅ1Ａ＋ｐｅ2、ｃ2＝ｅ1Ｐ＋ｐｅ3＋ｍに従い、クライアントの公開鍵（Ａ，Ｐ，ｎ，ｓ）で暗号化された、ベクトル形式を有する暗号データｃ＝（ｃ1，ｃ2）を複数記憶保持し、クライアントから、複数の暗号データのうちの２つの暗号データｃ、ｃ’に対応する２つの平文データについて内積を求めるべき情報がもたらされたときに該情報を受け付け、この情報に基づいて、ｎ行ｎ列の正方行列Ｗ1＝ｃ1’Tｃ1、ｎ行ｌ列の行列Ｗ2＝ｃ1’Tｃ2＋ｃ1Tｃ2’、およびスカラーξ＝ｃ2ｃ2’ Tを算出し、正方行列Ｗ1、行列Ｗ2、およびスカラーξをクライアントに提供する旨の技術が開示されている。
【０００５】
非特許文献１では、効率の良いセキュアな行列乗算が提案されている。非特許文献１では、既存のセキュアな内積演算のためのパッキング方法（非特許文献３）を拡張し、非特許文献４により提案されたBV-PHEというRing-LWEベース準同型暗号に基づく行列演算が開示されている。
【０００６】
非特許文献２では、行列のトレースの性質を用いて、準同型内積演算の一般的構成法が開示されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１７−９７１０２号公報
【非特許文献】
【０００８】
【非特許文献１】Dung, D. H., Mishra, P. K., Yasuda, M.: Efficient secure matrix multiplication over LWE-based homomorphic encryption. In: Tatra Mt. Math. Publ. vol. 67, pp. 69-83 (2016)
【非特許文献２】林  卓也，青野  良範，レ  チュウ  フォン，王  立華，“効率的な準同型内積演算の一般的構成”SCIS2017, Jan. 2017
【非特許文献３】Yasuda, M., Shimoyama,T., Kogure, J., Yokoyama, K., Koshiba, T.: Secure statistical analysis using RLWE-based homomorphic encryption. In: Foo, E., Stebila, D. (eds.) ACISP 2015. LNCS, vol. 9144, pp. 471-487. Springer, Cham (2015)
【非特許文献４】Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-LWE and security for key dependent messages. In: P. Rogaway (Ed.) CRYPTO 2011.LNCS, vol. 6841, pp. 505-524. Springer, Heidelberg (2011)
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、上述した開示技術では、パッキング法を用いる回数が多い点や、暗号文の復号時における計算量が多い点等に起因する計算効率の悪さが課題として挙げられている。
【００１０】
そこで本発明は、上述した問題点に鑑みて案出されたものであり、その目的とするところは、計算効率の向上を図ることができる暗号化システムを提供することにある。
【課題を解決するための手段】
【００１１】
本発明者らは、上述した問題点を解決するために、多項式の演算が可能な準同型暗号方式を用い、鍵生成手段と、導出手段と、暗号文算出手段と、内積手段と、復号文算出手段とを備える暗号化システムを発明した。鍵生成手段は、平文に対応する暗号文の算出に用いる暗号化鍵と、暗号文に対応する復号文の算出に用いる復号鍵とを生成する。導出手段は、ｍ行ｋ列で示される第１平文から第１要素、及びｋ行ｌ列で示される第２平文から第２要素をそれぞれ導出する。暗号文算出手段は、第１要素から第１暗号文、及び第２要素から第２暗号文をそれぞれ算出する。内積手段は、第１暗号文と、第２暗号文との内積を演算し、第１内積値、第２内積値、第３内積値、及び第４内積値を取得する。復号文算出手段は、第１内積値、第２内積値、第３内積値、及び第４内積値から復号文を算出する。復号文は、第１平文と第２平文との行列乗算の結果を含む。
【００１２】
請求項１に記載の暗号化システムは、多項式の演算が可能な準同型暗号方式を用いた暗号化システムであって、平文に対応する暗号文の算出に用いる暗号化鍵と、前記暗号文に対応する復号文の算出に用いる復号鍵とを生成する鍵生成手段と、下記の［数１］に基づき、ｍ行ｋ列で示される第１平文から第１要素、及びｋ行ｌ列で示される第２平文から第２要素をそれぞれ導出する導出手段と、下記の［数２］に示す暗号化アルゴリズムを用いて、前記第１要素から第１暗号文、及び前記第２要素から第２暗号文をそれぞれ算出する暗号文算出手段と、前記第１暗号文と、前記第２暗号文との内積を演算し、下記の［数３］に示す第１内積値、第２内積値、第３内積値、及び第４内積値を取得する内積手段と、下記の［数４］に示す復号アルゴリズムを用いて、前記第１内積値、前記第２内積値、前記第３内積値、及び前記第４内積値から前記復号文を算出する復号文算出手段と、を備え、前記復号文は、下記の［数５］に基づく前記第１平文と前記第２平文との行列乗算の結果を含むことを特徴とする。
【数１】
2019101083.tif 000003
ここで、左辺Ｍ（ハット）は、前記第１要素又は前記第２要素を示し、Ｍβ(r)は前記第１平文又は前記第２平文のβ行に対応するベクトルを示し、Ｍβ(c)は前記第１平文又は前記第２平文のβ列に対応するベクトルを示し、値βは値ｍ、値ｋ、及び値ｌのうち最大の値と等しく、値ｘは変数を示し、変数ベクトルＸは下記の［数６］で示される。
【数２】
2019101083.tif 000004
ここで、Ｅｎｃは、前記暗号化鍵（ｐｋ）を用いる前記暗号化アルゴリズムを示し、ｃ1及びｃ2は、前記第１暗号文の暗号文要素を示し、ｄ1及びｄ2は、前記第２暗号文の暗号文要素を示し、Ｒqは暗号文空間を示す。
【数３】
2019101083.tif 000005
ここで、Ｗ1は前記第１内積値を示し、Ｗ21は前記第２内積値を示し、Ｗ22は前記第３内積値を示し、ξは前記第４内積値を示し、ｑは素数を示し、Ｚqは暗号文空間の集合を示す。
【数４】
2019101083.tif 000006
ここで、ＤｅｃＩＰ*は前記復号鍵（Ｓ）を用いた前記復号アルゴリズムを示し、Ｓ*＝ＳＳTは内積算出対応復号鍵を示し、ｎは正の整数を示し、ｗk、ｕk、及びｖkはそれぞれ係数を示す。
【数５】
2019101083.tif 000007
ここで、ｍijは前記復号文に含まれる要素を示し、ｐは前記素数ｑよりも小さい素数を示し、Ｖｅｃは下記の［数７］で示される係数ベクトルを示す。
【数６】
2019101083.tif 000008
【数７】
2019101083.tif 000009
ここで、Ｒpは平文空間を示す。
【００１３】
請求項２に記載の暗号化システムは、請求項１記載の暗号化システムにおいて、前記値βは、下記の［数８］で示す条件を満たすことを特徴とする。
【数８】
2019101083.tif 000010
【００１４】
請求項３に記載の暗号化システムは、請求項１又は請求項２記載の暗号化システムにおいて、前記内積手段は、下記の［数９］及び［数１０］に基づき、前記第１内積値、前記第２内積値、前記第３内積値、及び前記第４内積値を取得することを特徴とする。
【数９】
2019101083.tif 000011
【数１０】
2019101083.tif 000012
ここで、Ｗ2は前記第２内積値Ｗ21及び前記第３内積値Ｗ22を含む内積値示す。
【００１５】
請求項４に記載の暗号化システムは、請求項３記載の暗号化システムにおいて、前記復号文算出手段は、下記の［数１１］及び前記［数５］に基づき、前記復号文を算出することを特徴とする。
【数１１】
2019101083.tif 000013
【００１６】
請求項５に記載の暗号化システムは、請求項１〜請求項４の何れか記載の暗号化システムにおいて、前記値ｋは、前記値ｍ及び前記値ｌとは異なる値であることを特徴とする。
【発明の効果】
【００１７】
上述した構成からなる本発明によれば、導出手段は、［数１］に基づき、第１平文から第１要素、及び第２平文から第２要素をそれぞれ導出する。このため、１つの平文に対して導出される要素を１つに抑制することができ、暗号文算出手段における算出回数を最小限に抑えることができる。これにより、計算効率の向上を図ることが可能となる。また、計算量及びデータ通信量を低減させることが可能となる。
【００１８】
また、上述した構成からなる本発明によれば、内積手段は、［数３］に示す第１内積値〜第４内積値を取得し、復号文算出手段は、［数４］に示す復号アルゴリズムを用いて、復号文を算出する。このとき、復号文は、［数５］に基づく第１平文と第２平文との行列乗算の結果を含む。このため、１回の復号計算により第１平文と第２平文との行列乗算の結果を取得することができる。これにより、計算効率の向上を図ることが可能となる。
【００１９】
また、上述した構成からなる本発明によれば、例えば値ｋは、値ｍ及び値ｌとは異なる値である。このため、各平文が長方行列の場合においても、正方行列の場合と同様に処理を実行することができる。これにより、平文の自由度を大幅に拡大することが可能となる。
【図面の簡単な説明】
【００２０】
【図１】本発明が適用される暗号化システムの一例を示す模式図である。
【図２】本発明が適用される暗号化システムの動作の一例を示すフローチャートである。
【図３】本発明が適用される暗号化システムに用いることができるアルゴリズムの一例を示す図である。
【図４】分析者端末等の構成の一例を示す模式図である。
【発明を実施するための形態】
【００２１】
（実施形態：暗号化システム１００の構成）
以下、本発明の実施形態としての暗号化システム１００について詳細に説明する。図１は、本実施形態における暗号化システム１００の一例を示す模式図である。
【００２２】
暗号化システム１００は、多項式の演算が可能な準同型暗号方式を用いており、主に秘匿性の高いデータを扱う場合に用いられる。図１に示すように、暗号化システム１００は、分析者端末１０と、サーバ２０と、プロバイダ端末３０とを備え、それぞれ公衆通信網４０を介して接続される。
【００２３】
暗号化システム１００では、例えばプロバイダ端末３０が平文に対応する暗号文を取得する。その後、サーバ２０が準同型暗号方式を用いて、暗号文に対して統計処理を行う。そして、分析者端末１０が、演算処理の結果から平文に対応する復号文を算出する。
【００２４】
このため、平文が秘匿性の高いデータを含む場合、データの内容を外部に漏らすことなくプロバイダ端末３０から分析者端末１０へと送ることができる。
【００２５】
上記に加え、データの内容を暗号化した状態で統計処理を行うことができる。これにより、統計処理を外部に委託した場合においても、情報漏洩等の発生を防止することが可能となる。
【００２６】
暗号化システム１００では、任意の行列で示される平文から、多項式で示される要素を導出し（パッキング方法）、要素から暗号文が算出される。また、２つの暗号文における内積を演算して取得された内積値から、復号文が算出される。
【００２７】
暗号文は、暗号化アルゴリズムを用いて算出され、復号文は、復号アルゴリズムを用いて算出される。暗号化アルゴリズムに用いられる暗号化鍵、及び復号アルゴリズムに用いられる復号鍵は、分析者端末１０で生成される。暗号化鍵は、生成された後に公開され、プロバイダ端末３０等で用いることができる。復号鍵は、生成された後、公開せず分析者端末１０に記憶される。
【００２８】
このとき、分析者端末１０は、例えば内積準同型方式を用いて演算処理した結果のみから復号文に算出可能となり、プロバイダ端末３０から直接暗号文を取得できない状態で用いられる。例えば図１に示すように、分析者端末１０とプロバイダ端末３０とが異なる公衆通信網４０ａ、４０ｂに接続されてもよい。
【００２９】
＜分析者端末１０＞
分析者端末１０は、例えば暗号化システム１００の管理者等が保有する端末を示す。分析者端末１０は、生成部１１と、復号文算出部１２と、記憶部１３と、通信インターフェース１４とを有する。
【００３０】
生成部１１は、暗号化システム１００に用いられる各種情報を生成する。生成部１１は、例えばパラメータ生成部１１ａと、鍵生成部１１ｂとを有する。パラメータ生成部１１ａは、暗号化鍵及び復号鍵を生成するために必要となるパラメータを生成する。鍵生成部１１ｂは、平文に対応する暗号文の算出に用いられる暗号化鍵と、暗号文から平文に対応する復号文の算出に用いられる復号鍵とを生成する。復号文算出部１２は、復号アルゴリズムを用いて、内積値から復号文を算出する。このとき、復号文は、２つの平文の行列乗算の結果を含む。
【００３１】
記憶部１３は、暗号化鍵や復号鍵等の各種情報を記憶する。通信インターフェース１４は、公衆通信網４０と接続され、外部と各種情報を送受信する。
【００３２】
＜サーバ２０＞
サーバ２０は、例えばクラウドサーバのように、管理者等に代わって各種情報の記憶や統計処理を行う第三者機関（業務委託先等）が保有するサーバを示す。サーバ２０は、内積部２１と、記憶部２２と、通信インターフェース２３とを有する。
【００３３】
内積部２１は、２つの暗号文における内積を演算し、内積値を取得する。記憶部２２は、暗号文や内積等の各種情報を記憶する。通信インターフェース２３は、公衆通信網４０と接続され、外部と各種情報を送受信する。
【００３４】
＜プロバイダ端末３０＞
プロバイダ端末３０は、例えば秘匿性の高いデータを扱うプロバイダが保有する端末を示す。プロバイダ端末３０は、導出部３１と、暗号文算出部３２と、記憶部３３と、通信インターフェース３４とを有する。なお、プロバイダ端末３０は、図１では２つ（３０ａ、３０ｂ）接続されているが、接続される数は任意である。
【００３５】
導出部３１は、平文から要素を導出する。暗号文算出部３２は、暗号化アルゴリズムを用いて、要素から暗号文を算出する。記憶部３３は、平文、要素や暗号文等の各種情報を記憶する。通信インターフェース３４は、公衆通信網４０と接続され、外部と各種情報を送受信する。
【００３６】
（実施形態：暗号化システム１００の動作）
次に、本実施形態における暗号化システム１００の動作について詳細に説明する。図２は、本実施形態における暗号化システム１００の動作の一例を示すフローチャートである。
【００３７】
暗号化システム１００の動作は、鍵生成手段Ｓ１１０と、導出手段Ｓ１２０と、暗号文算出手段Ｓ１３０と、内積手段Ｓ１４０と、復号文算出手段Ｓ１５０とを有する。各手段は、下記の［数１２］〜［数１４］、［数１６］、［数１８］及び図３の３ａ、３ｂに示すアルゴリズム（The Ring-LWE-based LNV scheme）を適宜用いてもよい。
【００３８】
＜鍵生成手段：Ｓ１１０＞
先ず、平文に対応する暗号文の算出に用いる暗号化鍵と、暗号文に対応する復号文の算出に用いる復号鍵とを生成する（鍵生成手段Ｓ１１０）。鍵生成手段Ｓ１１０は、例えば第１ステップＳ１１０ａと、第２ステップＳ１１０ｂとを有する。
【００３９】
第１ステップＳ１１０ａは、暗号化鍵及び復号鍵を生成するために必要となるパラメータを生成する。パラメータ生成部１１ａは、下記の［数１２］に示すパラメータ生成アルゴリズム（ＰａｒａｍＧｅｎ（１λ）→ｐｐ）に基づき、パラメータｐｐ＝（ｑ、ｎ、ｐ）を生成する。パラメータ生成部１１ａは、素数ｑ、素数ｑよりも小さい素数ｐ、及び正の整数ｎを生成する。
【数１２】
2019101083.tif 000014
ここで、Ｚ+は正の整数の集合を示し、λはセキュリティパラメータを示す。
【００４０】
このとき、パラメータ生成部１１ａは、下記の［数１３］に基づきパラメータを設定する。
【数１３】
2019101083.tif 000015
ここで、Ｒは多項式環を示し、Ｒpは平文空間を示し、Ｒqは暗号文空間を示す。
Ｚ(0、s2)は、中心０、分散ｓ2＞０の整数上の離散ガウス分布を示し、Ｒ(0、s2)は多項式環Ｒの各係数を離散ガウス分布Ｚ(0、s2)から独立に抽出した環上の離散ガウス分布を示す。
【００４１】
その後、第２ステップＳ１１０ｂは、暗号化鍵及び復号鍵を生成する。鍵生成部１１ｂは、下記の［数１４］に示す鍵生成アルゴリズム（ＫｅｙＧｅｎ（１λ、ｐｐ）→（ｐｋ、ｓｋ））に基づき、暗号化鍵ｐｋ＝（ａ、Ｐ）、及び復号鍵ｓｋ＝Ｓを生成する。鍵生成部１１ｂは、環上の離散ガウス分布Ｒ(0、s2)から抽出した値ｒ及び値Ｓ、並びに暗号文空間Ｒqから一様ランダム抽出した値ａを生成する。
【数１４】
2019101083.tif 000016
ここで、Ｒ+は正の実数の集合を示す。
【００４２】
その後、例えばプロバイダ端末３０は、例えば各通信インターフェース１４、３４を介して、暗号化鍵ｐｋを取得する。
【００４３】
＜導出手段：Ｓ１２０＞
次に、下記の［数１］に基づき、平文から要素を導出する（導出手段Ｓ１２０）。プロバイダ端末３０の導出部３１は、ｍ行ｋ列で示される第１平文から第１要素、及びｋ行ｌ列で示される第２平文をそれぞれ導出する。なお、第１平文及び第２平文は、それぞれ下記の［数１５］で示す行列として導出部３１によって生成又は取得される。
【数１】
2019101083.tif 000017
ここで、左辺Ｍ（ハット）は、各要素（第１要素、第２要素）を示し、Ｍβ(r)は各平文（第１平文、第２平文）のβ行に対応するベクトルを示し、Ｍβ(c)は各平文のβ列に対応するベクトルを示し、値βは値ｍ、値ｋ、及び値ｌのうち最大の値と等しく、値ｘは変数を示し、変数ベクトルＸは下記の［数６］で示される。すなわち、各要素は、多項式を含むスカラー量で示される。
【数６】
2019101083.tif 000018
【数１５】
2019101083.tif 000019
ここで、Ｚpは平文空間の集合を示す。
【００４４】
このとき、例えば値βは、下記の［数８］に示す条件を満たしてもよい。この場合、第１要素及び第２要素を示す多項式の項数を所定の数に抑えることができる。
【数８】
2019101083.tif 000020
【００４５】
また、値ｋは、値ｍ及び値ｌと同じ値であるほか、例えば値ｍ及び値ｌとは異なる値でもよい。すなわち、各平文が長方行列の場合においても、平行行列の場合と同様に処理を実行することができる。なお、値ｍは、値ｌと同じ値であるほか、例えば値ｌと異なる値でもよい。
【００４６】
＜暗号文算出手段：Ｓ１３０＞
次に、下記の［数２］に示す暗号化アルゴリズムを用いて、要素から暗号文を算出する（暗号文算出手段Ｓ１３０）。暗号文算出部３２は、第１要素から第１暗号文、及び第２要素から第２暗号文をそれぞれ算出する。
【数２】
2019101083.tif 000021
ここで、Ｅｎｃは、暗号化鍵ｐｋを用いる暗号化アルゴリズムを示し、ｃ1及びｃ2は、第１暗号文の暗号文要素を示し、ｄ1及びｄ2は、第２暗号文の暗号文要素を示し、Ｒqは暗号文空間を示す。
【００４７】
なお、例えば下記の［数１６］に示すアルゴリズムに基づき、暗号化アルゴリズムが用いられる。暗号文算出部３２は、環上の離散ガウス分布Ｒ(0、s2)から抽出したノイズｅ1、ｅ2、ｅ3を生成する。
【数１６】
2019101083.tif 000022
ここで、ｍeは平文から算出された各要素（第１要素、第２要素）を示す。
【００４８】
＜内積手段：Ｓ１４０＞
次に、２つの暗号文における内積を演算し、内積値を取得する（内積手段Ｓ１４０）。サーバ２０の内積部２１は、各通信インターフェース２３、３４を介して、第１暗号文及び第２暗号文を取得する。内積部２１は、第１暗号文と、第２暗号文との内積を演算し、下記の［数３］に示す第１内積値〜第４内積値を取得する。
【数３】
2019101083.tif 000023
ここで、Ｗ1は第１内積値を示し、Ｗ21は第２内積値を示し、Ｗ22は第３内積値を示し、ξは第４内積値を示し、Ｚqは暗号文空間の集合を示す。
【００４９】
内積部２１は、例えば下記の［数９］及び［数１０］に基づき、第１内積値〜第４内積値を取得する。
【数９】
2019101083.tif 000024
【数１０】
2019101083.tif 000025
ここで、Ｗ2は第２内積値Ｗ21及び第３内積値Ｗ22を含む内積値示す。
【００５０】
なお、内積部２１は、内積の演算において下記の［数１７］（係数転置変換性質）を用いて第１内積値〜第４内積値を取得する。
【数１７】
2019101083.tif 000026
【００５１】
例えば内積部２１は、第１暗号文と、第２暗号文との内積を演算する前に、図３に示したアルゴリズムを用いて、各暗号文同士の加算等を演算してもよい。
【００５２】
例えば、［数１］及び［数２］を用いて暗号化された同じサイズ（ｍ行ｍ列）の第１暗号文ｃ及び第２暗号文ｃ’に対して、３ａ枠に示す加算アルゴリズムＡｄｄ（ｃ，ｃ’）に基づきｃadd＝ｃ＋ｃ’を計算できる。この場合、分析者端末１０の復号文算出部１２において、３ｂ枠に示す復号アルゴリズムＤｅｃＡ（Ｓ，ｃadd）＝Ｄｅｃ（Ｓ，ｃadd）に基づきｍ＋ｍ’を計算できる。更に、３ａ枠に示す加算アルゴリズムの出力を用いた後、［数３］、並びに後述する［数４］及び［数５］を用いることで、第１平文Ａと第２平文Ｂに対して（Ａ＋Ｂ）2を計算することもできる。
【００５３】
＜復号文算出手段：Ｓ１５０＞
次に、第１内積値〜第４内積値から復号文を算出する（復号文算出手段Ｓ１５０）。分析者端末１０の復号文算出部１２は、各通信インターフェース１４、２３を介して、第１内積値〜第４内積値を取得する。復号文算出部１２は、下記の［数４］に示す復号アルゴリズムを用いて、第１内積値〜第４内積値から復号文を算出する。
【数４】
2019101083.tif 000027
ここで、ＤｅｃＩＰ*は復号鍵Ｓを用いた復号アルゴリズムを示し、Ｓ*＝ＳＳTは内積算出対応復号鍵を示し、値ｗk、値ｕk、及び値ｖkはそれぞれ係数を示す。
【００５４】
復号文算出部１２は、例えば下記の［数１１］に基づき、復号文を算出する。このとき、復号文算出部１２は、［数１７］を用いて復号文を算出する。
【数１１】
2019101083.tif 000028
【００５５】
なお、例えば下記の［数１８］に示すアルゴリズムに基づき、復号アルゴリズムが用いられる。
【数１８】
2019101083.tif 000029
ここで、ｍは復号文を示す。ここで、復号文ｍに含まれる要素ｍijは、下記の［数５］で示すように、第１平文及び第２平文の行列要素を用いて表すことができる。すなわち、［数５］は［数１１］と等しい値を示し、復号文ｍは第１平文と第２平文との行列乗算の結果を含む。なお、復号文ｍとして、例えば要素ｍijを行列要素とした行列が用いられるほか、例えばスカラー量が用いられてもよい。
【数５】
2019101083.tif 000030
ここで、Ｖｅｃは下記の［数７］で示される係数ベクトルを示す。
【数７】
2019101083.tif 000031
【００５６】
上述した動作を実施することで、本実施形態における暗号化システム１００の動作は終了する。なお、上述した導出手段Ｓ１２０では、１つのプロバイダ端末３０を用いて第１要素及び第２要素が導出されるほか、例えば第１プロバイダ端末３０ａを用いて第１要素、及び第２プロバイダ端末３０ｂを用いて第２要素が導出されてもよい。
【００５７】
次に、本実施形態における分析者端末１０の構成の一例を説明する。なお、サーバ２０及びプロバイダ端末３０においても、分析者端末１０と同様の構成を備えることができるため、説明を省略する。
【００５８】
図４は、分析者端末１０の構成の一例を示す模式図である。分析者端末１０として、パーソナルコンピュータ（ＰＣ）等の電子機器が用いられるほか、例えばウェブサーバ等により具現化されてもよい。分析者端末１０は、と、ＣＰＵ１０１と、ＲＯＭ１０２と、ＲＡＭ１０３と、保存部１０４と、Ｉ／Ｆ１０５〜１０７とを備える。各構成１０１〜１０７は、内部バス１１０により接続され、筐体１１１内に格納される。
【００５９】
ＣＰＵ（Central Processing Unit）１０１は、分析者端末１０全体を制御する。ＲＯＭ（Read Only Memory）１０２は、ＣＰＵ１０１の動作コードを格納する。ＲＡＭ（Random Access Memory）１０３は、ＣＰＵ１０１の動作時に使用される作業領域である。保存部１０４は、記憶部１３を介して各種情報が保存される。保存部１０４としてデータ保存装置が用いられ、例えばＨＤＤ（Hard Disk Drive）、ＳＳＤ（solid state drive）等が用いられる。
【００６０】
Ｉ／Ｆ１０５は、公衆通信網４０等と接続するためのインターフェース部品であり、例えばＩ／Ｆ１０５を介してサーバ２０等との各種情報の送受信が行われる。
【００６１】
Ｉ／Ｆ１０６は、入力部分１０８との情報の送受信を行うためのインターフェース部品である。入力部分１０８として、例えばキーボードが用いられ、分析者端末１０の利用者等は、入力部分１０８を介して、各種情報又は分析者端末１０の制御コマンド等を入力できる。Ｉ／Ｆ１０７は、出力部分１０９との各種情報の送受信を行うためのインターフェース部品である。出力部分１０９は、保存部１０４に保存された各種情報、又は分析者端末１０の処理状況等を出力できる。出力部分１０９として、例えばディスプレイが用いられる。なお、生成部１１、復号文算出部１２、記憶部１３、及び通信インターフェース１４は、ＣＰＵ１０１が、ＲＡＭ１０３を作業領域として、保存部１０４等に保存されたプログラム（命令）を実行することにより実現される。
【００６２】
本実施形態によれば、導出手段Ｓ１２０は、［数１］に基づき、第１平文から第１要素、及び第２平文から第２要素をそれぞれ導出する。このため、１つの平文に対して導出される要素を１つに抑制することができ、暗号文算出手段Ｓ１３０における算出回数を最小限に抑えることができる。これにより、計算効率の向上を図ることが可能となる。また、計算量及びデータ通信量を低減させることが可能となる。
【００６３】
また、本実施形態によれば、内積手段Ｓ１４０は、［数３］に示す第１内積値〜第４内積値を取得し、復号文算出手段Ｓ１５０は、［数４］に示す復号アルゴリズムを用いて、復号文を算出する。このとき、復号文は、［数５］に基づく第１平文と第２平文との行列乗算の結果を含む。このため、１回の復号計算により第１平文と第２平文との行列乗算の結果を取得することができる。これにより、計算効率の向上を図ることが可能となる。
【００６４】
また、本実施形態によれば、例えば値ｋは、値ｍ及び値ｌとは異なる値でもよい。このとき、各平文が長方行列の場合においても、正方行列の場合と同様に処理を実行することができる。これにより、平文の自由度（柔軟性）を向上させることが可能となる。
【００６５】
また、本実施形態によれば、例えば第１平文Ａと第２平文Ｂとの乗算ＡＢに加え、乗算ＢＡが必要なときにおいても、第１平文Ａ及び第２平文Ｂに対してそれぞれ１通りのパッキング方法により上述した計算を実現することが可能となる。これにより、乗算ＡＢ及び乗算ＢＡを演算するときのコストを削減することが可能となる。
【００６６】
例えば、下記の［数１９］で示すｍ行ｋ列の第１平文Ａ及びｋ行ｍ列の第２平文Ｂで示される場合、［数１］、［数２］、［数３］、下記の［数２０］、下記の［数２１］を用いて復号文を算出できる。この結果は、下記の［数２２］乗算ＡＢm×m、及び乗算ＢＡk×kに対応するため、乗算ＡＢ及び乗算ＢＡを１回復号で計算できることが示される。
【数１９】
2019101083.tif 000032
【数２０】
2019101083.tif 000033
【数２１】
2019101083.tif 000034
ここで、ηkは係数を示し、第１内積値Ｗ1、第２内積値Ｗ21、第３内積値Ｗ22は［数３］の値が用いられ、第４内積値ξは［数２０］の値が用いられる。
【数２２】
2019101083.tif 000035
【００６７】
上記より、第１平文Ａの列と第２平文Ｂの行、及び第１平文Ｂの行と第２平文の列とが等しいとき、［数３］に示したξを簡易に示すことができ、［数４］よりも係数の少ない［数２１］に示す復号アルゴリズムを用いることができる。
【００６８】
また、本実施形態によれば、例えばｍ行ｋ列の第１平文Ａ、ｋ行ｌ列の第２平文Ｂ、及びｌ行ｍ列の第３平文Ｃを用いた場合、乗算ＡＢと乗算ＣＡとの演算が必要なときにおいても、第１平文Ａに対して１通りのパッキング方法により上述した計算を実現することが可能となる。
【００６９】
また、本実施形態によれば、プライバシー保護、ＰＣＡ（主成分分析）計算、データの次元圧縮等への応用を実現することが可能となる。
【符号の説明】
【００７０】
１０        ：分析者端末
１１        ：生成部
１１ａ      ：パラメータ生成部
１１ｂ      ：鍵生成部
１２        ：復号文算出部
１３        ：記憶部
１４        ：通信インターフェース
２０        ：サーバ
２１        ：内積部
２２        ：記憶部
２３        ：通信インターフェース
３０        ：プロバイダ端末
３１        ：導出部
３２        ：暗号文算出部
３３        ：記憶部
３４        ：通信インターフェース
４０        ：公衆通信網
１００      ：暗号化システム
１０１      ：ＣＰＵ
１０２      ：ＲＯＭ
１０３      ：ＲＡＭ
１０４      ：保存部
１０５      ：Ｉ／Ｆ
１０６      ：Ｉ／Ｆ
１０７      ：Ｉ／Ｆ
１０８      ：入力部分
１０９      ：出力部分
１１０      ：内部バス
１１１      ：筐体
Ｓ１１０    ：鍵生成手段
Ｓ１１０ａ  ：第１ステップ
Ｓ１１０ｂ  ：第２ステップ
Ｓ１２０    ：導出手段
Ｓ１３０    ：暗号文算出手段
Ｓ１４０    ：内積手段
Ｓ１５０    ：復号文算出手段
【図１】
2019101083.tif 000047
【図２】
2019101083.tif 000048
【図３】
2019101083.tif 000049
【図４】
2019101083.tif 000050