JP5657128B2 - 秘匿計算システム、秘匿計算方法、および秘匿計算プログラム - Google Patents

Description

本発明は、秘匿計算システム、秘匿計算方法、および秘匿計算プログラムに関するものであり、具体的には、データ預託先のコンピュータにおいて、良好なセキュリティを維持しつつ、秘匿した状態での預託データに関する効率的な演算を実行可能とする技術に関する。

情報システムの開発の効率化、運用管理費の低減などを目的に、近年、計算リソースを自分で保持せず、外部業者に委託するクラウドと呼ばれる運用管理形態が脚光を浴びている。こうしたクラウドにおいては、効率化やコスト低減を図れる反面、クラウドを実現する情報システムの管理業者と、前記情報システムの利用者とが異なることで、機密情報を外部業者たる前記管理業者に預託することへの不安が前記利用者に生じやすい。そのため、事前に、預託するデータの不正利用の予防策として、暗号技術を活用し、該当データの機密性を確保する必要がある。

しかし、単純な暗号化方式において、暗号化したデータに対する足し算、掛け算などの基本演算やそれらを組み合わせた統計処理、関数値計算などは、データの復号可能な者しか実行できない。従って、データ預託先である、外部の情報システム管理者ではそうした暗号化データに対する各種演算処理はできない。こうした状況に対処するために専用の人員を預託先に配置したり、種々の対策が必要となり、クラウドを採用する当初目的である、コスト低減の目的に反することになる。

こうした状況への対策技術のうち、クライアントが、秘匿化したデータをサーバに預託しながら、任意の関数値計算が可能な暗号方式が提案されている。例えば、計算機上で実現可能な任意の関数計算は、ブール足し算とブール掛け算との組み合わせで表現できる事を利用し、秘匿化したｂｉｔデータに対して、ブール足し算とブール掛け算が実行可能な暗号方式（特許文献１参照）が提案されている。

米国特許公開公報２０１１／０１１０５２５

上述した従来技術などにおいては、平文ｂｉｔデータに、エラーベクトルを加える事で暗号化を行っている。しかし、暗号化データをブール演算する度に、暗号化データ内のエラーベクトルの大きさは増大する。エラーベクトルの大きさが特定の閾値を超えると、復号化アルゴリズムで正しい関数値が算出されない確率が高くなる。

この問題に対し従来技術では、暗号化データ内のエラーベクトルを小さくするために、暗号化済みの復号関数回路に暗号化データと暗号化した復号用秘密鍵を入力し、平文を変えずに、エラーベクトルのより小さい暗号化データに再暗号化する方法が提案されている。 エラーベクトルの小さい暗号文に再暗号化する事によって、エラーベクトルが閾値に達するまで、再びブール演算が実行可能となる。しかし、この方法を実行するには、復号関数回路を計算する際に発生するエラーベクトルの増大量が、閾値以下である必要がある。 始めに平文ｂｉｔを暗号化する際に、加えるエラーベクトルの大きさを十分小さくとる事で、エラーベクトルの増大を閾値以下にする事が出来る。しかし、エラーベクトルを小さく取ると、公開鍵を用いた格子簡約攻撃が可能となり、セキュリティの観点から適切ではない。そこで、従来技術においては、ｓｑｕａｈｉｎｇという方法を用いて復号関数回路計算時に発生するエラーベクトルの増大を抑え、再暗号化を実行する技術が提案されている。ただし、このｓｑｕａｈｉｎｇによって、暗号化データのデータ長や再暗号化に必要な計算量が大幅に増大する問題が挙げられており、現実的な対策とは言い難い。

そこで上記に鑑み本発明は、データ預託先のコンピュータにおいて、良好なセキュリティを維持しつつ、秘匿した状態での預託データに関する効率的な演算を実行可能とする、ことを目的とする。

を目的としている。

上記課題を解決する本発明の秘匿計算システムは、準同型性を持つ暗号方式において秘密鍵を用いたデータ暗号化を実行し、該暗号化データをサーバに送信するクライアントと、クライアントから受信した暗号化データに対して準同型暗号方式に基づく秘匿計算処理を実行し、該演算結果をクライアントに返信するサーバとを含むコンピュータシステムであって、前記クライアントは、ｎ次元のイデアル格子基底を秘密鍵として、平文を、準同型性の暗号方式に対応した所定の暗号化関数を用いて暗号化し、前記データ暗号化を実行する処理と、前記秘密鍵が生成する格子の部分格子基底である抑制情報を前記サーバに送信する処理を実行するものであり、前記サーバは、前記クライアントから前記抑制情報を受信して記憶装置に保持する処理と、前記クライアントから受信した暗号化データに対する準同型暗号方式に基づく秘匿計算処理を、暗号化データ数に応じた回数で実行するに際し、少なくともいずれかの回での秘匿計算処理において、所定暗号化データに関して行った秘匿計算処理の結果であるベクトルについて、ノルムと所定の閾値とを比較した結果、ノルムが所定の閾値を超えている場合、前記抑制情報に基づいて、前記ベクトルの基底表現における実数係数を所定値以下に低減することで、前記ベクトルのノルムを前記閾値以下とする処理を実行するものであることを特徴とする。

本発明によれば、データ預託先のコンピュータにおいて、良好なセキュリティを維持しつつ、秘匿した状態での預託データに関する効率的な演算が実行可能となる。

本実施形態における秘匿計算システムの構成例を示す図である。 本実施形態におけるクライアント端末の構成例を示す図である。 本実施形態における秘匿計算サーバの構成例を示す図である。 本実施形態における秘匿計算方法の処理手順例１を示すフロー図である。 本実施形態における秘匿計算方法の処理手順例２を示すフロー図である。 本実施形態における秘匿計算方法の処理手順例３を示すフロー図である。 本実施形態における秘匿計算方法の処理手順例４を示すフロー図である。 本実施形態における秘匿計算方法の処理手順例５を示すフロー図である。 本実施形態における秘匿計算方法の処理手順例６を示すフロー図である。 本実施形態における秘匿計算方法の処理手順例７を示すフロー図である。 本実施形態における秘匿計算方法の処理手順例８を示すフロー図である。

−−−システム構成−−−
以下に本発明の実施形態について図面を用いて詳細に説明する。図１は、本実施形態の秘匿計算システム１０の構成例を示す図である。図１に示す秘匿計算システム１０（以下、システム１０）は、準同型性を持つ暗号方式において秘密鍵を用いたデータ暗号化を実行し、該暗号化データをサーバに送信するクライアントと、クライアントから受信した暗号化データに対して準同型性を有する演算処理を実行し、該演算結果をクライアントに返信するサーバとを含むコンピュータシステムであって、データ預託先のコンピュータにおいて、良好なセキュリティを維持しつつ、秘匿した状態での預託データに関する効率的な演算を実行可能とするコンピュータシステムである。

図１に示すように、本実施形態における前記システム１０は、本発明で言うところのクライアントたるクライアント端末１００、本発明で言うところのサーバたる秘匿計算サーバ２００、を備え、クライアント端末１００と秘匿計算サーバ２００とは、ネットワーク３００を介して相互にデータ授受可能となっている。

こうした前記システム１０を構成するクライアント端末１００、秘匿計算サーバ２００のハードウェア構成は以下の如くとなる。図２は本実施形態におけるクライアント端末１００の構成例を示す図である。図示するように、クライアント端末１００は、ＣＰＵ１０１、ハードディスクドライブなど適宜な不揮発性記憶装置で構成される補助記憶装置１０２、ＲＡＭなど揮発性記憶装置で構成されるメモリ１０３、耐タンパ記憶装置１０５、処理データの表示を行うディスプレイ等の表示装置１０６、キーボードやマウスなど入出力インターフェイス１０７、および、ネットワーク３００と接続し秘匿計算サーバ２００との通信処理を担う通信装置１０８が、内部信号線１０４で連結し構成される。前記ＣＰＵ１０１は、前記補助記憶装置１０２に保持されるプログラムをメモリ１０３に読み出すなどして実行しクライアント端末１００自体の統括制御を行なうとともに各種判定、演算及び制御処理を行なう演算装置である。また、前記補助記憶装置１０２には、プログラムの他に、暗号化対象となる平文データ、および暗号化に用いる秘密鍵が予め格納されているものとする。

図３は本実施形態における秘匿計算サーバ２００の構成例を示す図である。また、前記秘匿計算サーバ２００は、ＣＰＵ２０１、ハードディスクドライブなど適宜な不揮発性記憶装置で構成される補助記憶装置２０２、ＲＡＭなど揮発性記憶装置で構成されるメモリ２０３、処理データの表示を行うディスプレイ等の表示装置２０６、キーボードやマウスなど入出力インターフェイス２０７、および、ネットワーク３００と接続しクライアント端末１００との通信処理を担う通信装置２０８が、内部信号線２０４で連結し構成される。前記ＣＰＵ２０１は、前記補助記憶装置２０２に保持されるプログラムをメモリ２０３に読み出すなどして実行し、秘匿計算サーバ２００自体の統括制御を行なうとともに各種判定、演算及び制御処理を行なう演算装置である。

続いて、本実施形態の秘匿計算システム１０を構成する、前記クライアント端末１００、および秘匿計算サーバ２００が備える機能について説明する。上述したように、以下に説明する機能は、クライアント端末１００、および秘匿計算サーバ２００らが、それぞれ補助記憶装置にて備えるプログラムを各々実行することで実装される機能と言える。
なお、本実施形態において実行される暗号化は、準同型性を持つ暗号方式において秘密鍵を用いた暗号化であるものとする。

前記システム１０のうち前記クライアント端末１００は、所定基準以下の大きさのエラーベクトルを、補助記憶装置１０２から読み出した平文データに加えて当該平文データの暗号化を実行する機能を備える。暗号化が施されたデータ、すなわち暗号化データは、クライアント端末１００から秘匿計算サーバ２００に対し送信される。クライアント端末１００から秘匿計算サーバ２００に送られる前記暗号化データは、準同型性を有する演算処理の対象となる。

また前記クライアント端末１００は、補助記憶装置１０２から読み出した秘密鍵が生成する格子の部分格子基底からなる暗号文抑制情報（抑制情報）を、前記秘匿計算サーバ２００に送信する機能を備える。

また前記クライアントは、補助記憶装置１０２に保持する秘密鍵行列と、所定の整数係数正則行列との行列積を実行し、該行列積の結果である行列を、前記暗号文抑制情報として、前記秘匿計算サーバ２００に送信する機能を備える、とすれば好適である。

一方、前記秘匿計算サーバ２００は、前記クライアント端末１００から前記暗号文抑制情報を受信して、補助記憶装置１０２ないしメモリ２０３に保持する機能を備える。

また、前記秘匿計算サーバ２００は、前記クライアント端末１００から前記暗号化データを受信し、この暗号化データに対する準同型性を有する演算処理を実行する機能を備える。秘匿計算サーバ２００は、この演算処理に際し、演算処理中ないし演算処理結果の暗号文のビット長が、所定閾値以上である場合、該当暗号文のベクトルを、前記保持する暗号文抑制情報に対応した部分格子基底が成す領域内に平行移動させ、前記暗号文のビット長を所定閾値以下に低減する機能を備える。

また前記秘匿計算サーバ２００は、前記クライアント端末１００から受信した暗号文抑制情報が示す、抑制情報行列の列ベクトルからなる一次結合で、係数の絶対値が１以下のベクトル全体の中で、原点からのユークリッド距離が最も大きいものを特定し、該特定したベクトルと原点との距離を前記所定閾値とする機能を備えるとすれば好適である。

−−−用語の定義−−−
ここではまず、本実施形態において使用する用語について定義しておく。
（１）イデアル格子基底Ｂ＝（ｂ１，ｂ２，・・・，ｂｎ）：非特許文献１と同様の定義とする。つまり、イデアル格子の条件を満足するｎ次元整数係数ベクトル基底である。
（２）暗号文抑制情報：暗号文生成用秘密鍵であるイデアル格子基底Ｂ＝（ｂ１，ｂ２，・・・，ｂｎ）と、ランダムに生成したｎ×ｎ整数係数正則行列Ｕとの行列積をとった格子基底Ｐ＝（ｐ１，ｐ２，・・・，ｐｎ）とする。
（３）秘匿計算プログラム：本実施形態における暗号文（暗号化データ）を入力値とし、ｍ回のブール演算ステップを行う処理とする。
（４）秘匿計算関数用内部変数：秘匿計算プログラムの各ステップの出力値を格納し、それを次のステップに対する入力値として利用する変数の変数名とする。
（５）秘匿計算用引数：秘匿計算プログラムの入力値として、クライアント端末１００が生成する、準同型性の暗号方式の暗号文もしくは、暗号文の組である。
（６）ノルム：ユークリッドノルムを指す。つまり、ｎ次元整数係数ベクトル（ｖ１，ｖ２，・・・，ｖｎ）に対して、Ｓ＝ｖ１×ｖ１＋ｖ２×ｖ２＋・・・＋ｖｎ×ｖｎとし、値Ｓの平方根をｎ次元整数係数ベクトル（ｖ１，ｖ２，・・・，ｖｎ）のノルムとする。
（７）閾値Ｌ：暗号文抑制情報である格子基底Ｐ＝（ｐ１，ｐ２，・・・，ｐｎ）に対して、実係数一次結合ａ１×ｐ１＋ ａ２×ｐ２＋・・・ａｎ×ｐｎ：ただし０＜ａｉ＜＝１とするとき、この一次結合の全体の中で、ノルムが最大であるベクトルのノルムをＬとする。

−−−全体処理フロー−−−
以下、本実施形態における秘匿計算方法の実際手順について図に基づき説明する。以下で説明する秘匿計算方法に対応する各種動作は、前記システム１０を構成するクライアント端末１００や秘匿計算サーバ２００らがそれぞれメモリ等に読み出して実行するプログラムによって実現される。そして、このプログラムは、以下に説明される各種の動作を行うためのコードから構成されている。

図４は本実施形態における秘匿計算方法の処理手順例１を示すフロー図であり、具体的には、クライアント端末１００と秘匿計算サーバ２００との間で、秘匿計算用の各種データ送受信を示すフローである。
この場合、クライアント端末１００は、例えば入出力インターフェイス１０７で受けたユーザ指示に応じ、暗号文生成用秘密鍵生成プログラムを実行し、暗号文生成用秘密鍵を生成する（Ｓ１００）。この暗号文生成用秘密鍵を生成する処理については後に詳述する。

続いてクライアント端末１００は、ユーザ指示を受けて、或いは、前記ステップＳ１００の実行を受けて、暗号文抑制情報生成プログラムを実行し、暗号文抑制情報の生成を行う（Ｓ２００）。またクライアント端末１００は、ここで生成した暗号文抑制情報（Ｄ１００）を、通信装置１０８を用いてネットワーク３００上の秘匿計算サーバ２００に送信する。この暗号文抑制情報生成の処理については後に詳述する。

次にクライアント端末１００は、ユーザ指示を受けて、或いは、前記ステップＳ２００の実行を受けて、秘匿計算用引数生成プログラムを実行し、秘匿計算プログラムに入力するための暗号文を生成し（Ｓ３００）、それを秘匿計算用引数（Ｄ２００）として通信装置１０８を用いて秘匿計算サーバ２００に送信する。この秘匿計算用引数生成の処理については後に詳述する。

一方、秘匿計算サーバ２００は、前記クライアント端末１００より、前記暗号文抑制情報（Ｄ１００）と、秘匿計算用引数（Ｄ２００）を受信し、これらを入力値として、秘匿計算プログラムによる秘匿計算処理を実行する（Ｓ４００）。また、秘匿計算サーバ２００は、前記秘匿計算プログラムの出力値である秘匿計算結果（Ｄ３００）を、通信装置２０３を用いて、ネットワーク３００上のクライアント端末１００に送信する。この秘匿計算の処理については後に詳述する。

他方、前記クライアント端末１００は、前記秘匿計算サーバ２００より秘匿計算結果（Ｄ３００）を受信し、ここで受信した秘匿計算結果（Ｄ３００）を入力値とする復号処理プログラムによる復号処理を実行する（Ｓ５００）。前記クライアント端末１００は、当該復号プログラムの出力値である計算結果を得て本処理を終了する。この復号処理については後に詳述する。

−−−暗号文生成用秘密鍵生成処理−−−
次に、暗号文生成用秘密鍵生成処理について図に基づき説明する。図５は、本実施形態における秘匿計算方法の処理手順例２を示すフロー図であり、具体的には、図４の処理フローにおける暗号文生成用秘密鍵生成プログラムの処理（Ｓ１００）を示す図である。
この場合、前記クライアント端末１００は、所定の秘密鍵用イデアル格子生成アルゴリズムを用いて、ｎ次元のイデアル格子基底Ｂ＝（ｂ１，ｂ２，・・・，ｂｎ）を生成し（Ｓ１１０）、生成したイデアル格子基底を暗号文生成用秘密鍵として耐タンパ記憶装置１０５に格納する。なお、本実施形態で用いる、暗号文生成用秘密鍵生成プログラムにおける秘密鍵用イデアル格子生成アルゴリズム、暗号化関数、復号化関数については、非特許文献１にある従来技術（秘密鍵生成プログラム、暗号化関数プログラム、復号化関数プログラム）を用いてもよい。

−−−暗号文抑制情報生成処理−−−
次に、暗号文抑制情報生成処理について図に基づき説明する。図６は本実施形態における秘匿計算方法の処理手順例３を示すフロー図であり、具体的には、図４の処理フローにおける暗号文抑制情報生成プログラムの処理（Ｓ２００）を示す図である。
この場合、前記クライアント端末１００は、暗号文生成用秘密鍵生成プログラム（図５：Ｓ１００）で生成した暗号文生成用秘密鍵である、ｎ次元のイデアル格子基底Ｂ＝（ｂ１，ｂ２，・・・，ｂｎ）を、例えばメモリ１０３にて計算用に確保した記憶領域に格納する（Ｓ２１０）。
続いて前記クライアント端末１００は、ランダムなｎ×ｎ整数係数正則行列Ｕを、既存技術による所定アルゴリズムにて生成し（Ｓ２２０）、このランダムなｎ×ｎ整数係数正則行列Ｕを、前記メモリ１０３にセッティングしたｎ次元のイデアル格子基底Ｂ＝（ｂ１，ｂ２，・・・，ｂｎ）に対して乗じる（Ｓ２３０）。クライアント端末１００は、前記ステップＳ２３０による行列積の結果を、“Ｐ＝（ｐ１，ｐ２，・・・，ｐｎ）”といった行列たる暗号文抑制情報として出力する。この暗号文抑制情報は、クライアント端末１００から前記秘匿計算サーバ２００に送信されることになる。

−−−秘匿計算用引数生成処理−−−
次に、秘匿計算用引数生成処理について図に基づき説明する。図７は本実施形態における秘匿計算方法の処理手順例４を示すフロー図であり、具体的には、図４の処理フローにおける秘匿計算用引数生成プログラムの処理（Ｓ３００）を示す図である。
この場合、前記クライアント端末１００は、ｋ個の関数引数用の平文ｍ１，ｍ２，・・・，ｍｋ、すなわち、秘匿計算対象となる暗号化データの元となるデータを、入出力インターフェイス１０７で受けたユーザ指示に応じて補助記憶装置１０２から読み出し、例えばメモリ１０３にて計算用に確保した記憶領域に格納する（Ｓ３１０）。
またクライアント端末１００は、前記暗号文生成用秘密鍵生成プログラムの処理（Ｓ１００）で生成している暗号文生成用秘密鍵Ｂを秘密鍵として、前記メモリ１０３にセッティングした各平文ｍ１，ｍ２，・・・，ｍｋを、準同型性の暗号方式に対応した所定の暗号化関数（既存のものでよい）を用いて暗号化し、それらｋ個の各暗号文を、”ｃ１，ｃ２，・・・，ｃｋ”の行列とし（Ｓ３２０）、秘匿計算用引数として秘匿計算サーバ２００に出力する。

−−−秘匿計算処理−−−
次に、秘匿計算処理について図に基づき説明する。図８は本実施形態における秘匿計算方法の処理手順例５を示すフロー図であり、図９は本実施形態における秘匿計算方法の処理手順例６を示すフロー図である。具体的には、図４の処理フローにおける秘匿計算サーバ２００が行う秘匿計算処理フロー（Ｓ４００）を示す図である。
この場合、前記秘匿計算サーバ２００は、前記クライアント端末１００が前記ステップＳ２００で生成した暗号文抑制情報Ｐ＝（ｐ１，ｐ２，・・・，ｐｎ）を、前記クライアント端末１００から受信する（Ｓ４１０）。

また秘匿計算サーバ２００は、前記クライアント端末１００が前記ステップＳ３００で生成した秘匿計算用引数（ｃ１，ｃ２，・・・，ｃｋ）を、前記クライアント端末１００が前記ステップから受信する（Ｓ４２０）。秘匿計算用引数の具体例としては、例えば、秘匿性を維持しつつも、統計処理を必要とする個人情報などが想定できる。本実施形態では、例えば、統計対象の個人がｍ人だけ存在し、各人の個人情報が示す所定値を合算するため、第１〜第ｍの計ｍステップにわたって、秘匿計算を行う例を想定する。

前記秘匿計算サーバ２００は、秘匿計算関数用内部変数Ｚを初期化し（Ｓ４３０）、前記ステップＳ４２０で得た秘匿計算用引数（ｃ１，ｃ２，・・・，ｃｋ）をコマンド引数とする秘匿計算関数の第１ステップを計算し、その出力を秘匿計算関数用内部変数Ｚに格納する（Ｓ４４０）。秘匿計算関数は、暗号文に対して平文や秘密鍵なしで演算可能な準同型暗号方式において、加法や乗法のような二項演算を行う関数である。秘匿計算サーバ２００は当然ながら、こうした秘匿計算関数のプログラムを補助記憶装置１０２等に予め保持している。

次に、前記秘匿計算サーバ２００は、秘匿計算関数用内部変数Ｚのノルムと閾値Ｌとを比較し（Ｓ４５０）、ノルムの値が閾値Ｌ以下であれば（Ｓ４５０：ノルム＜Ｌ）、秘匿計算関数の第２ステップに処理を移行する。一方、前記ノルムが閾値Ｌを超えていれば（Ｓ４５０：ノルム＞Ｌ）、秘匿計算サーバ２００は、暗号文抑制情報Ｐ＝（ｐ１，ｐ２，・・・，ｐｎ）を用いて秘匿計算関数用内部変数ＺのノルムをＬ以下に変形し、その値を秘匿計算関数用内部変数Ｚに格納し、秘匿計算関数の第２ステップに処理を移行する（Ｓ４６０）。

なお、前記閾値Ｌは、秘匿計算サーバ２００が、暗号文抑制情報の行列の列ベクトルからなる一次結合で、係数の絶対値が１以下のベクトル全体の中で、原点からのユークリッド距離が最も大きいものを特定し、該特定したベクトルと原点との距離を閾値Ｌとして採用したものである。
また、暗号文抑制情報Ｐ＝（ｐ１，ｐ２，・・・，ｐｎ）を用いて、秘匿計算関数用内部変数ＺのノルムをＬ以下に変形する処理、すなわち、暗号文抑制処理については図１１に基づき後述する。

次に、秘匿計算サーバ２００は、秘匿計算用引数（ｃ１，ｃ２，・・・，ｃｋ）と秘匿計算関数用内部変数Ｚをコマンド引数とする秘匿計算関数の第２ステップを計算し、その出力を秘匿計算関数用内部変数Ｚに格納する（Ｓ４７０）。ここで秘匿計算サーバ２００は、秘匿計算関数用内部変数Ｚのノルムと閾値Ｌとを比較し（Ｓ４８０）、前記ノルムの値が閾値Ｌ以下であれば（Ｓ４８０：ノルム＜Ｌ）、秘匿計算関数の第３ステップに処理を移行する。他方、ノルムが閾値Ｌを超えていれば（Ｓ４８０：ノルム＞Ｌ）、秘匿計算サーバ２００は、暗号文抑制情報Ｐ＝（ｐ１，ｐ２，・・・，ｐｎ）を用いて秘匿計算関数用内部変数ＺのノルムをＬ以下に変形し、その値を秘匿計算関数用内部変数Ｚに格納し、秘匿計算関数の第３ステップに処理を移行する（Ｓ４９０）。

次に、秘匿計算サーバ２００は、秘匿計算用引数（ｃ１，ｃ２，・・・，ｃｋ）と秘匿計算関数用内部変数Ｚをコマンド引数とする秘匿計算関数の第３ステップを計算し、その出力を秘匿計算関数用内部変数Ｚに格納する（Ｓ４１１）。

次に秘匿計算サーバ２００は、秘匿計算関数用内部変数Ｚのノルムと閾値Ｌとを比較し（Ｓ４２１）、ノルムの値が閾値Ｌ以下であれば（Ｓ４２１：ノルム＜Ｌ）、秘匿計算関数の第４ステップに処理を移行する。他方、ノルムが閾値Ｌを超えていれば（Ｓ４２１：ノルム＞Ｌ）、秘匿計算サーバ２００は、暗号文抑制情報Ｐ＝（ｐ１，ｐ２，・・・，ｐｎ）を用いて秘匿計算関数用内部変数ＺのノルムをＬ以下に変形し、その値を秘匿計算関数用内部変数Ｚに格納し、秘匿計算関数の第４ステップに処理を移行する（Ｓ４３１）。

以下、上述した秘匿計算関数の第１ステップ〜第３ステップまでと同様の手続きで、秘匿計算関数の第４ステップから秘匿計算関数の第ｍ−１ステップまで計算する（Ｓ４４１）。

続いて秘匿計算サーバ２００は、秘匿計算用引数（ｃ１，ｃ２，・・・，ｃｋ）と秘匿計算関数用内部変数Ｚをコマンド引数とする秘匿計算関数の第ｍステップを計算し、その出力を秘匿計算関数用内部変数Ｚに格納する（Ｓ４５１）。

また、秘匿計算サーバ２００は、秘匿計算関数用内部変数Ｚのノルムと閾値Ｌとを比較し（Ｓ４６１）、ノルムの値が閾値Ｌ以下であれば（Ｓ４６１：ノルム＜Ｌ）、秘匿計算用内部変数Ｚを秘匿計算結果Ｒとして出力する。他方、ノルムが閾値Ｌを超えていれば（Ｓ４６１：ノルム＜Ｌ）、秘匿計算サーバ２００は、暗号文抑制情報Ｐ＝（ｐ１，ｐ２，・・・，ｐｎ）を用いて秘匿計算関数用内部変数Ｚの係数ノルムをＬ以下に変形し、その値を秘匿計算関数用内部変数Ｚに格納し、秘匿計算用内部変数Ｚを秘匿計算結果Ｒとして出力する（Ｓ４７１）。この秘匿計算結果Ｒは、秘匿計算サーバ２００から前記クライアント端末１００に返信されるものである。上記例の場合、秘匿計算結果Ｒは、ｍ人の個人情報が示す所定値の合算値に対応したものとなる。

−−−復号処理−−−
次に、復号処理について図に基づき説明する。図１０は本実施形態における秘匿計算方法の処理手順例７を示すフロー図であり、具体的には、図４の処理フローにおける復号処理プログラムによる処理（Ｓ５００）を示す図である。
この場合、前記クライアント端末１００は、前記秘匿計算サーバ２００から、前記秘匿計算結果Ｒ（Ｄ２００）を受信する（Ｓ５１０）。また前記クライアント端末１００は、上述した暗号文生成用秘密鍵生成プログラムの処理（図４、図５：Ｓ１００）で生成してある暗号文生成用秘密鍵Ｂを秘密鍵として、前記秘匿計算結果Ｒを、所定の復号化関数を用いて復号する（Ｓ５２０）。クライアント端末１００は、ここで復号した値を計算結果として表示装置１０５にて出力する。上記例の場合、表示装置１０５にて出力する計算結果は、統計対象であるｍ人の個人に関する、個人情報の合算値となる。

−−−暗号文抑制処理−−−
次に、暗号文抑制処理について図に基づき説明する。図１１は本実施形態における秘匿計算方法の処理手順例８を示すフロー図であり、具体的には、図８と図９の秘匿計算処理フロー（Ｓ４００）における暗号文抑制処理を示す図である。
この場合、前記秘匿計算サーバ２００は、暗号文抑制情報Ｐ＝（ｐ１，ｐ２，・・・，ｐｎ）を用いて、秘匿計算関数用内部変数Ｚをベクトル基底表現する。つまり、実数係数（ａ１，ａ２，・・・，ａｎ）で、Ｚ＝ａ１×ｐ１＋ａ２×ｐ２＋・・・ａｎ×ｐｎとなる表示を求める（Ｓ６１０）。次に、秘匿計算サーバ２００は、前記ステップＳ６１０で求めた各ａｉ（ｉ＝１〜ｎ）に対して、実数ａｉを超えない最大の整数たる［ａｉ］を減算し、各係数ａｉを“ａｉ−［ａｉ］”の値に更新する（Ｓ６２０）。例えば、ａ１が“３．５”である時、実数“３．５”を超えない最大の整数たる“３”で“３．５”を減算し、係数ａ１を“０．５”の値に更新する。

続いて秘匿計算サーバ２００は、前記ステップＳ６２０で求めた、各係数ａｉを用いて、秘匿計算関数用内部変数Ｚを、Ｚ＝ａ１×ｐ１＋ａ２×ｐ２＋・・・ａｎ×ｐｎ、に更新し（Ｓ６３０）、秘匿計算関数用内部変数Ｚを出力する。こうした処理は、すなわち、抑制前の暗号文のベクトル（“ａｉ”が１を越えている）を、前記暗号用抑制情報に対応した部分格子基底が成す領域内に平行移動させ（“ａｉ”を１以下とする）、前記暗号文のビット長を所定値以下に低減する処理となる。

なお、上記実施形態においては、暗号文抑制情報を生成する際に、ランダムなｎ×ｎ整数係数正則行列Ｕを生成しているが、行列式の値がある条件を満足するランダムなｎ×ｎ整数係数正則行列Ｕとしてもよい。また、上記実施形態においては、ベクトルのノルム計算方法として、ユークリッドノルム計算法を利用しているが、その他の従来技術であるノルム計算法を用いてもよい。また、上記実施形態においては、秘匿計算用内部変数を一つの変数Ｚとしているが、秘匿計算用内部変数を複数の変数の組（Ｚ１，Ｚ２，・・・，Ｚｋ）としてもよい。

以上、本発明を実施するための最良の形態などについて具体的に説明したが、本発明はこれに限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能である。

こうした本実施形態においては、従来の課題であった「再暗号化時に発生するエラーベクトルの増大」を抑制するために、平文ｂｉｔを暗号化する際に、クライアント端末１００が加えるエラーベクトルの大きさを十分小さくとり、さらに、エラーベクトルが小さくことにより懸念される格子簡約攻撃を防ぐため、従来公開していた公開鍵は秘匿する方式となっている。また、秘匿計算サーバ２００は、従来の公開鍵とは異なる暗号文抑制情報生成（暗号文のビット長をある定数以下に抑えるための情報）をクライアント端末１００から得て、暗号文のノルム増大問題を解決している。暗号文抑制情報は、秘密鍵が生成する格子の部分格子基底からなり、暗号文ベクトルを常にこの部分格子基底の生成する基本領域に平行移動する事で、ノルム増大を防いでいる。この時、ベクトルを平行移動する際、加えるベクトルは部分格子のベクトルのため、暗号文ベクトルの平文情報を変更する事無く、ノルムを小さくできる。

また、前記暗号文抑制情報は、秘密鍵である格子の部分格子基底であるため、従来の公開鍵を用いた暗号化アルゴリズムにはそもそも利用できず、本実施形態の秘匿計算システムにおける暗号文抑制情報に対して格子簡約攻撃がなされるとしても、暗号文が解読され平文が出力されてしまう確率は非常に低い。実際、秘密鍵の格子基底のなす行列の行列式の絶対値をＤ、暗号文抑制情報の格子基底のなす行列の行列式の絶対値をＤ’とすると、暗号文解読の確率は、Ｄ／Ｄ’程度となる。従って、Ｄ’を十分大きく取る事によって、前記確率は、現実的には問題にならない程度に小さくする事が可能である。

しかして本実施形態によれば、平文ｂｉｔデータに加えるエラーベクトルを従来より低減し、暗号化データのブール演算によるエラーベクトル増大を抑制する一方、エラーベクトルが小さい場合に懸念される従来の格子簡約攻撃を回避することが可能である。従って、ｓｑｕａｈｉｎｇの如き、計算量や計算時間が非常大きい手法を採用する必要も無い。つまり、データ預託先のコンピュータにおいて、良好なセキュリティを維持しつつ、秘匿した状態での預託データに関する効率的な演算が実行可能となる。

本明細書の記載により、少なくとも次のことが明らかにされる。すなわち、前記秘匿計算システムにおいて、前記クライアントは、記憶装置に保持する秘密鍵行列と、所定の整数係数正則行列との行列積を実行し、該行列積の結果である行列を、前記抑制情報としてサーバに送信するものである、としてもよい。

また、前記秘匿計算システムにおいて、前記サーバは、前記クライアントから受信した抑制情報が示す、抑制情報行列の列ベクトルからなる一次結合で、係数の絶対値が１以下のベクトル全体の中で、原点からのユークリッド距離が最も大きいものを特定し、該特定したベクトルと原点との距離を前記所定閾値とするものである、としてもよい。

１０ 秘匿計算システム
１００ クライアント端末（クライアント）
１０１ ＣＰＵ
１０２ 補助記憶装置（記憶装置）
１０３ メモリ
１０４ 内部信号線
１０５ 耐タンパ記憶装置
１０６ 表示装置
１０７ 入出力インターフェイス
１０８ 通信装置
２００ 秘匿計算サーバ（サーバ）
２０１ ＣＰＵ
２０２ 補助記憶装置（記憶装置）
２０３ メモリ
２０４ 内部信号線
２０６ 表示装置
２０７ 入出力インターフェイス
２０８ 通信装置
３００ ネットワーク

Claims (6)

1. 準同型性を持つ暗号方式において秘密鍵を用いたデータ暗号化を実行し、該暗号化データをサーバに送信するクライアントと、クライアントから受信した暗号化データに対して準同型暗号方式に基づく秘匿計算処理を実行し、該演算結果をクライアントに返信するサーバとを含むコンピュータシステムであって、
   前記クライアントは、
   ｎ次元のイデアル格子基底を秘密鍵として、平文を、準同型性の暗号方式に対応した所定の暗号化関数を用いて暗号化し、前記データ暗号化を実行する処理と、前記秘密鍵が生成する格子の部分格子基底である抑制情報を前記サーバに送信する処理を実行するものであり、
   前記サーバは、
   前記クライアントから前記抑制情報を受信して記憶装置に保持する処理と、
   前記クライアントから受信した暗号化データに対する準同型暗号方式に基づく秘匿計算処理を、暗号化データ数に応じた回数で実行するに際し、少なくともいずれかの回での秘匿計算処理において、所定暗号化データに関して行った秘匿計算処理の結果であるベクトルについて、ノルムと所定の閾値とを比較した結果、ノルムが所定の閾値を超えている場合、前記抑制情報に基づいて、前記ベクトルの基底表現における実数係数を所定値以下に低減することで、前記ベクトルのノルムを前記閾値以下とする処理を実行するものであることを特徴とする秘匿計算システム。
2. 前記クライアントは、
   記憶装置に保持する前記秘密鍵であるｎ次元のイデアル格子基底に対し、所定の整数係数正則行列を乗じて行列積を実行し、該行列積の結果である行列を、前記抑制情報としてサーバに送信するものである、ことを特徴とする請求項１に記載の秘匿計算システム。
3. 前記サーバは、
   前記クライアン卜から受信した抑制情報である前記部分格子基底を、実係数の絶対値が１より小さいベクトルの一次結合とした場合、前記一次結合の中でノルムが最大であるベクトルのノルムを、前記閾値として、前記秘匿計算処理の結果であるベクトルについての、ノルムと所定の閾値との比較に用いる、
   ものであることを特徴とする請求項１に記載の秘匿計算システム。
4. 準同型性を持つ暗号方式において秘密鍵を用いたデータ暗号化を実行し、該暗号化データをサーバに送信するクライアントと、クライアントから受信した暗号化データに対して準同型暗号方式に基づく秘匿計算処理を実行し、該演算結果をクライアントに返信するサーバとを含むコンピュータシステムにおける、
   前記クライアントが、
   ｎ次元のイデアル格子基底を秘密鍵として、平文を、準同型性の暗号方式に対応した所定の暗号化関数を用いて暗号化し、前記データ暗号化を実行する処理と、前記秘密鍵が生成する格子の部分格子基底である抑制情報を前記サーバに送信する処理を実行し、
   前記サーバが、
   前記クライアントから前記抑制情報を受信して記憶装置に保持する処理と、
   前記クライアントから受信した暗号化データに対する準同型暗号方式に基づく秘匿計算処理を、暗号化データ数に応じた回数で実行するに際し、少なくともいずれかの回での秘匿計算処理において、所定暗号化データに関して行った秘匿計算処理の結果であるベクトルについて、ノルムと所定の閾値とを比較した結果、ノルムが所定の閾値を超えている場合、前記抑制情報に基づいて、前記ベクトルの基底表現における実数係数を所定値以下に低減することで、前記ベクトルのノルムを前記閾値以下とする処理を実行する、
   ことを特徴とする秘匿計算方法。
5. 準同型性を持つ暗号方式において秘密鍵を用いたデータ暗号化を実行し、該暗号化データをサーバに送信するクライアントと、クライアントから受信した暗号化データに対して準同型暗号方式に基づく秘匿計算処理を実行し、該演算結果をクライアントに返信するサーバとを含むコンピュータシステムにおける、
   前記クライアントに、
   ｎ次元のイデアル格子基底を秘密鍵として、平文を、準同型性の暗号方式に対応した所定の暗号化関数を用いて暗号化し、前記データ暗号化を実行する処理と、
   前記秘密鍵が生成する格子の部分格子基底である抑制情報を前記サーバに送信する処理と、
   を実行させることを特徴とする秘匿計算プログラム。
6. 準同型性を持つ暗号方式において秘密鍵を用いたデータ暗号化を実行し、該暗号化データをサーバに送信するクライアントと、クライアントから受信した暗号化データに対して準同型暗号方式に基づく秘匿計算処理を実行し、該演算結果をクライアントに返信するサーバとを含むコンピュータシステムにおける、
   前記サーバに、
   前記クライアントから前記抑制情報を受信して記憶装置に保持する処理と、
   前記クライアントから受信した暗号化データに対する準同型暗号方式に基づく秘匿計算処理を、暗号化データ数に応じた回数で実行するに際し、少なくともいずれかの回での秘匿計算処理において、所定暗号化データに関して行った秘匿計算処理の結果であるベクトルについて、ノルムと所定の閾値とを比較した結果、ノルムが所定の閾値を超えている場合、前記抑制情報に基づいて、前記ベクトルの基底表現における実数係数を所定値以下に低減することで、前記ベクトルのノルムを前記閾値以下とする処理と、
   を実行させることを特徴とする秘匿計算プログラム。

Images