(57)【特許請求の範囲】
【請求項１】
秘密分散法に基づく秘密計算により画像の評価を行うコンピュータである画像評価装置と秘密分散格納部とが通信ネットワークにより接続された画像評価システムにおいて、前記画像評価装置におけるプログラムにより前記画像評価装置が実行する画像評価方法であって、
前記秘密分散格納部に、第１のパラメータで暗号化された２つの画像の画像特徴量と、第２のパラメータで暗号化された前記２つの画像の画像特徴量が格納されており、
前記画像評価装置が、前記第１のパラメータで暗号化された前記２つの画像の画像特徴量を前記秘密分散格納部から取得し、当該第１のパラメータで暗号化された前記２つの画像の画像特徴量の差分を第１の差分として計算し、
前記画像評価装置が、前記第２のパラメータで暗号化された前記２つの画像の画像特徴量を前記秘密分散格納部から取得し、当該第２のパラメータで暗号化された前記２つの画像の画像特徴量の差分を第２の差分として計算し、
前記画像評価装置が、前記第１の差分と前記第２の差分とを掛け合わせ、掛け合わせた結果を復号し、当該復号の結果を用いて画像の評価を行う、画像評価方法であり、
前記暗号化は、秘密分散法を用いてなされたものである
ことを特徴とする画像評価方法。
【請求項２】
前記第１の差分に係る前記暗号化された各画像の画像特徴量は、当該画像の画像特徴量と所定数個の乱数からなるベクトルに前記第１のパラメータを用いて構成された行列を掛けることにより得られた行列であり、前記第２の差分に係る前記暗号化された各画像の画像特徴量は、当該画像の画像特徴量と所定数個の乱数からなるベクトルに前記第２のパラメータを用いて構成された行列を掛けることにより得られた行列であり、
前記第１の差分と前記第２の差分とを掛け合わせる際に、当該第１の差分である行列と、当該第２の差分である行列の転置行列とを掛け合わせる
請求項１に記載の画像評価方法。
【請求項３】
前記各画像の画像特徴量は、当該画像の画像特徴量ベクトルにおける成分であり、
前記第１の差分と前記第２の差分とを掛け合わせた結果を各成分について足し合わせ、足し合わせた結果を復号し、当該復号の結果を利用することにより画像の評価を行う
請求項１又は２に記載の画像評価方法。
【請求項４】
前記復号の結果を画像特徴量ベクトルの差分二乗和として利用することにより、前記２つの画像間の類似性を評価する
請求項３に記載の画像評価方法。
【請求項５】
前記２つの画像のうちの一方の画像はクエリ画像であり、他方の画像は検索先画像である
請求項１ないし４のうちいずれか１項に記載の画像評価方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化したまま演算処理を行う秘密計算に関するものであり、特に画像データに対する秘密計算に関するものである。
【背景技術】
【０００２】
ソーシャルネットワーキングサービスやコンシューマ向けのクラウドサービス等の普及によって、あらゆるデータをネットワークを介したサーバ上に保存することが可能なサービスが増加している。中でも画像データは、スマートホンの普及等により、誰でも簡単にネットワークサービスを介してアップロードすることが可能となり、多くの画像データがネットワーク上で保存されるようになった。そこで、ネットワーク上に保存するデータに対して安全性を確保するには暗号化によりセキュリティ保護が重要となる。
【０００３】
これまで、ネットワークサービス上でセキュリティ保護されるべきデータの代表例はテキストベースの個人情報であった。今後はネットワーク上に保存されるデータは多種に及ぶことが想定され、その中には顔写真や位置が特定できるような風景画像等、個人情報が含まれる画像データも多く存在するが、ネットワーク上に保存される画像データに対するセキュリティについては問題視されてこなかった。
【０００４】
また、多くの保護されるべきデータがネットワーク上に保存されている一方で、これらのデータを利用したクラウドサービスが増加している。そういったネットワークサービス上で画像データに対して何らかの処理を行う時、一般的には画像データは暗号化されていない平文の状態で処理される。クラウドサービス上でネットワークに保存されている画像データを暗号化によってセキュリティを確保する場合、これまで通り画像データを平文で処理しようとする際に一度画像データの復号をしなければならず、暗号化によるデータ保護はその時点では崩れてしまう問題が発生する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Andrew Chi-Chih Yao、"How to Generate and Exchange Secrets"、Foundations of Computer Science, 1986., 27th Annual Symposium on, P. 162 - 167.
【非特許文献２】千田 浩司、「効率的な３パーティ秘匿関数計算の提案とその運用モデルの考察」、情報処理学会研究報告. CSEC, [コンピュータセキュリティ] 2010-CSEC-48(1), 1-7, 2010-02-25
【非特許文献３】柴田賢介 、「表計算ソフトをフロントエンドとした委託型２パーティ秘匿回路計算システム」、情報処理学会シンポジウム論文集、2009年、11号、p. 625-630.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は上記の問題点に鑑みてなされたものである。以下、画像データに対するセキュリティ保護のためのアプローチを説明しながら、本発明が解決しようとする課題について説明する。
【０００７】
1．ネットワーク上に保存されている画像データは常に暗号化し、情報漏洩と情報損失のリスクを回避する。
【０００８】
2．暗号化されているデータは復号せずに、暗号化されたまま直接演算処理を行う。
【０００９】
以上２点が実現できれば、ネットワーク上のデータに対して暗号化によるセキュリティを保ち、かつネットワーク上で画像処理を行うことができると考えられる。
【００１０】
図１に示すように、従来の共通鍵や公開鍵を利用した一般的な暗号通信モデルでは、データをネットワーク上で送受信する際や、ローカルで保存する際に、ネットワーク通信路上やローカル保存領域でデータを暗号化することでデータの安全性を確保することを前提としている。そして、データを処理する際にはデータをローカルで復号した後に処理を行っている。このモデルでは上述したように暗号化によるデータ保護が失われる場合があるという問題がある。
【００１１】
そこで、図２に示すように、従来の一般的な暗号通信モデルによる暗号化ではなく、ネットワーク上で処理中のデータに対して復号せずに処理を行う暗号モデルを採用することを検討する。ここで、暗号化されたデータに対して処理を行う技術として秘密計算技術が存在する。秘密計算は暗号化した数値や文字などのテキストデータに対して復号すること無く演算を行うことが可能な暗号プロトコルである。この秘密計算可能な暗号として準同型暗号等がある。
【００１２】
画像データに対する処理に対し秘密計算を実装することが可能になれば、クラウド上に常に画像データを暗号化した状態で保存し、さらに秘密計算によって演算処理をすることも可能となる。
【００１３】
本発明は上記の点に鑑みてなされたものであり、暗号化した画像データに対して復号せずに画像の評価等の画像処理を行う技術を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記の課題を解決するために、本発明は、秘密分散法に基づく秘密計算により画像の評価を行うコンピュータである画像評価装置と秘密分散格納部とが通信ネットワークにより接続された画像評価システムにおいて、前記画像評価装置におけるプログラムにより前記画像評価装置が実行する画像評価方法であって、
前記秘密分散格納部に、第１のパラメータで暗号化された２つの画像の画像特徴量と、第２のパラメータで暗号化された前記２つの画像の画像特徴量が格納されており、
前記画像評価装置が、前記第１のパラメータで暗号化された前記２つの画像の画像特徴量を前記秘密分散格納部から取得し、当該第１のパラメータで暗号化された前記２つの画像の画像特徴量の差分を第１の差分として計算し、
前記画像評価装置が、前記第２のパラメータで暗号化された前記２つの画像の画像特徴量を前記秘密分散格納部から取得し、当該第２のパラメータで暗号化された前記２つの画像の画像特徴量の差分を第２の差分として計算し、
前記画像評価装置が、前記第１の差分と前記第２の差分とを掛け合わせ、掛け合わせた結果を復号し、当該復号の結果を用いて画像の評価を行う、画像評価方法であり、
前記暗号化は、秘密分散法を用いてなされたものであることを特徴とする画像評価方法として構成される。
【００１５】
前記画像評価方法において、前記第１の差分に係る前記暗号化された各画像の画像特徴量は、当該画像の画像特徴量と所定数個の乱数からなるベクトルに前記第１のパラメータを用いて構成された行列を掛けることにより得られた行列であり、前記第２の差分に係る前記暗号化された各画像の画像特徴量は、当該画像の画像特徴量と所定数個の乱数からなるベクトルに前記第２のパラメータを用いて構成された行列を掛けることにより得られた行列であり、前記第１の差分と前記第２の差分とを掛け合わせる際に、当該第１の差分である行列と、当該第２の差分である行列の転置行列とを掛け合わせるように構成してもよい。
【００１６】
前記画像評価方法において、前記各画像の画像特徴量は、当該画像の画像特徴量ベクトルにおける成分であり、前記第１の差分と前記第２の差分とを掛け合わせた結果を各成分について足し合わせ、足し合わせた結果を復号し、当該復号の結果を利用することにより画像の評価を行うようにしてもよい。
【００１７】
また、前記復号の結果を画像特徴量ベクトルの差分二乗和として利用することにより、前記２つの画像間の類似性を評価するようにしてもよい。
【００１８】
また、例えば、前記２つの画像のうちの一方の画像はクエリ画像であり、他方の画像は検索先画像である。
【発明の効果】
【００１９】
本発明によれば、暗号化した画像データに対して復号せずに画像処理を行う技術が提供される。すなわち、画像データに対する秘密計算を実現できる。
【図面の簡単な説明】
【００２０】
【図１】従来技術を説明するための図である。
【図２】本発明の課題を説明するための図である。
【図３】マルチパーティプロトコルの概念を示す図である。
【図４】本発明の実施の形態の概要を示す図である。
【図５】本発明の実施の形態に係る画像検索システムの構成図である。
【図６】本発明の実施の形態に係る画像検索システムの動作を説明するためのフローチャートである。
【発明を実施するための形態】
【００２１】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施の形態に限定されるものではない。本実施の形態を詳細に説明するにあたり、まず、本実施の形態に係る技術の概要、及び本実施の形態で用いる要素技術を説明する。
【００２２】
（実施の形態の概要、要素技術）
本実施の形態では、暗号化したデータに対して演算する技術として秘密計算技術を用いる。前述したように、秘密計算は暗号化した数値や文字などのテキストデータに対して復号すること無く演算を行うことが可能な暗号技術であり、その演算結果は復号した平文に反映される。
【００２３】
現在、加算・乗算や絶対値・大小比較やソート等の基本的な演算が実現されている。ある暗号において、その暗号化に用いる関数がとある演算において準同型性を持つことができれば、その暗号はその演算において秘密計算が可能となる。この準同型性を持つ暗号としてエルガマル暗号やRSA暗号、秘密分散法が知られている。特に秘密分散法を利用し、複数のユーザがそれぞれ自身が保持する情報を秘密にし、図３に示すように、お互いの値の演算結果のみを共有することが可能なアルゴリズムをマルチパーティプロトコルという。図３において、ｘ、ｙ、ｚはそれぞれユーザＡ、Ｂ、Ｃの秘匿情報である。秘密分散法とマルチパーティプロトコルの詳細については後述する。
【００２４】
従来から、秘密計算技術を数値やテキストデータに対する演算に適用する適用例はあるが、本実施の形態では、従来はなかった画像処理に対する秘密計算技術を実現している。
【００２５】
すなわち、本実施の形態では、ネットワークサービス上での画像データに対して秘密計算を適用し、画像検索等のメディア処理を暗号化領域でセキュアに行えるアルゴリズムを提供し、実運用に耐えうるセキュリティシステムを実現する。なお、本実施の形態では、メディア処理として画像検索を行っているが、本発明の技術は画像検索に限られるものでない。例えば、秘密計算で画像圧縮や映像編集を行うことも可能である。
【００２６】
また、データの安全性を確保するには、破損によるデータ損失も考慮しなければならない。よってネットワーク上のデータを損失するリスクを避ける為に、保存するデータを分散化することによりデータの安全性を向上させることも考慮する為、データは秘密計算が可能な暗号によって暗号化し、かつロバストに分散化するのが望ましい。そこで、本実施の形態では、ロバストな保存・データの暗号化領域の演算の２点を実現するために、秘密計算可能な暗号として秘密分散法を用いている。
【００２７】
一般に画像処理では、画像の特徴的な成分や性質を抽出して処理をする場合が多い。例えば画像では画素の統計的な特徴を抽出し、特徴量空間で処理を行う。そこで、本実施の形態では、画像を暗号化していない状態である平文から特徴量（画像特徴量）を抽出し、特徴量空間での秘密計算処理を行っている。
【００２８】
図４に、本実施の形態の概要を示す。図４に示すように、本実施の形態での画像検索は、クエリを画像として、秘密計算により、クエリ画像と検索先画像との間の特徴量の距離を計算することにより、検索先の多数の画像から、クエリ画像と類似度の高い画像を出力する。つまり、検索先画像及びクエリ画像の各々から特徴量が抽出され、これらが秘密分散暗号化され、暗号化領域で特徴量の距離の演算が行われる。このように、検索に係る演算処理を全て暗号化領域で行うことによって、映像コンテンツなど、セキュリティ性の高いデータを暗号化したまま保存することができ、ユーザは自分の欲しい映像をクエリとして簡易的な画像を送り検索することで、誰にも中身を知られること無く出力結果を知ることができる。
【００２９】
次に、本実施の形態で使用する要素技術の内容について説明する。
【００３０】
[秘密分散法]
前述したように、本実施の形態では、秘密計算可能な暗号としてロバストな保存によってデータ損失からも保護が可能である秘密分散法を用いている。秘密分散法は、データを複数に分散・暗号化する暗号アルゴリズムで、復号するには一定数以上の分散情報を集める必要がある。一定数未満の場合は情報理論的に復号をすることができない。つまり、分散情報を一定数以上集めない限りは、不足した分散情報のみでは平文の情報は一切漏れることは無いとされる。その性質から情報の欠損に対して強い安全性を保つことができ、公開鍵暗号に利用する秘密鍵等、機密性の高い情報を保存する際などにリスク分散をする為に利用されている。また、暗号式の性質により元々が別の平文同士を同一のパラメータで暗号化した場合、暗号化された分散情報を演算することによってマルチパーティプロトコルを実現することができる。
【００３１】
秘密分散法にはいくつかのアルゴリズムが存在するが、本実施の形態では、一例としてShamirの秘密分散法を使用している。また、秘密分散法を利用した基本的な秘密計算としてマルチパーティプロトコルを使用している。以下、Shamir の秘密分散法、及びマルチパーティプロトコルについて説明する。なお、本発明に適用できる秘密分散法はShamirの秘密分散法に限られるわけではない。
【００３２】
[Shamir の秘密分散アルゴリズム]
準備として以下のパラメータを与える。
【００３３】
暗号化
S：平文
k：復号に必要なしきい値
n：分散数
r：乱数
xi：自然数（パラメータ）  xi≠xj(i ≠ j)
p：素数
wi：分散暗号文
次に以下の行列Xを定義する。
【００３４】
【数１】
0005687601.tif 000002
この行列の行列式はVandermondeの行列式と呼ばれ、その値は必ず0にならないことが知られているので、必ず逆行列を持つ。
【００３５】
以下の行列演算によって平文Sをn個に分散暗号化する。
【００３６】
【数２】
0005687601.tif 000003
復号
k個以上の分散暗号文を集め、さらにパラメータから逆行列を生成すると平文Sを復号できる。
【００３７】
【数３】
0005687601.tif 000004
[マルチパーティプロトコル]
マルチパーティプロトコルは、秘密分散法を利用した秘密計算のプロトコルであり、各ユーザの秘匿情報を互いに知られること無く、計算が可能である。平文での計算結果のみを互いに共有することがきる。一般にマルチパーティプロトコルでは、以下の手順により、平文での演算結果が共有される。
【００３８】
ステップ１）各自秘匿にしたい情報を暗号化する。
【００３９】
ステップ２）暗号化した情報を各自共有する。
【００４０】
ステップ３）共有した暗号文から秘密計算によって各自平文の演算結果を出力する。
【００４１】
また、秘密分散法は加算においての準同型性を保持している。よって以下の演算によって加算のマルチパーティプロトコルを実現できる。ここでは２つの平文S1、S2の加算を求めるアルゴリズムを示す。次式では準同型性によって分散暗号化された値を加算した場合、その演算結果が復号された値にされる。
【００４２】
【数４】
0005687601.tif 000005
上記の式（４）は、式（３）と同様に逆行列を左から掛けることで、復号可能であるので、S1+S2を求めることができる。
【００４３】
後述するように、本実施の形態では、Shamirの秘密分散法によるマルチパーティプロトコルによって差分の自乗和を計算可能なアルゴリズムに拡張している。この差分の自乗和を距離計算に利用することで、暗号化した特徴量同士の距離計算を可能にする。
【００４４】
[画像検索]
本実施の形態では、特徴量空間での処理例として画像検索を行う。本実施の形態での画像検索は、クエリを画像として、検索先の多数の画像から画像特徴の類似度の高い画像を出力する。この処理を全て暗号化することによって、映像コンテンツなど、セキュリティ性の高いデータを暗号化したまま保存することができ、ユーザは自分の欲しい映像をクエリとして簡易的な画像を送り検索することで、誰にも中身を知られること無く出力結果を知ることができる。
【００４５】
具体的には、クエリ画像と検索先画像の画素の統計的特徴成分を抽出し、その類似度をマッチングさせるなどの方式がある。本実施の形態では、特徴量として統計的特徴量ベクトルをクエリ画像と検索先画像から抽出し、互いの特徴ベクトルの画像全体の位置をマッチングし、ベクトルの距離を計算し、距離が小さい画像を結果として出力する。よって暗号化したデータに対して画像検索処理を行うには以下のステップを全て暗号化領域で処理する必要がある。
【００４６】
ステップ１１）検索先画像から統計的特徴量を抽出
ステップ１２）クエリ画像から統計的特徴量を抽出
ステップ１３）クエリ画像と検索先画像の特徴量のマッチング
ステップ１４） 特徴量の距離を計算
ステップ１５） 距離が短い検索目的画像を出力
本実施の形態では、一番演算が複雑であるステップ１１の、画像から統計的特徴量を抽出する処理を、クエリ画像・検索先画像共に暗号化する前に行い、特徴量と平文画像をそれぞれ暗号化し、保存するという手法をとる。類似度をとる計算を暗号化し、元データは別途暗号化して保存することで最初のステップを暗号化領域で行うことができる。
【００４７】
また、本実施の形態の検索では、特徴量が元画像のどの平面空間上にあるかも考慮したものにする。よって類似した画素成分の類似度が高く、かつ類似した画素成分がクエリ画像上の座標と近い座標にあるような画像が結果として出力される。本実施の形態では、特徴量ベクトル同士の距離を暗号化領域で演算し、その復号した値を類似度とする。具体的には、互いの特徴量ベクトルの各成分の差分を自乗した値の総和を距離としている。また、周辺画素の平均値の差が大きいものほど特徴的な画素として優先的に距離計算をし、優先度の低い特徴量の演算を省略することで、検索の効率化を図ることとしてもよく、これにより、検索の効率化を図ることができる。
【００４８】
（実施の形態の詳細な説明）
[システム構成]
以下、本発明の実施の形態をより具体的に説明する。図５に、本実施の形態に係る画像検索システム１０の構成図を示す。
【００４９】
図５に示すように、画像検索システム１０は、クエリ画像情報秘密分散格納部１１、検索先画像情報秘密分散格納部１２、画像検索部１３を有し、これらが通信ネットワークを介して互いに通信可能に構成されている。また、画像検索システム１０にはクライアント端末２０が通信ネットワークを介して接続されている。
【００５０】
クエリ画像情報秘密分散格納部１１は、クエリ画像の暗号化された特徴量を分散格納する格納部であり、例えば、複数のサーバがネットワーク接続されて構成されている。検索先画像情報秘密分散格納部１２は、暗号化された検索先画像と、検索先画像の暗号化された特徴量とを分散格納する格納部であり、例えば、複数のサーバがネットワーク接続されて構成されている。なお、図５の例では、クエリ画像情報秘密分散格納部１１と、検索先画像情報秘密分散格納部１２とを分けて示しているが、これらを一体として構成してもよい。
【００５１】
画像検索部１３は、後述する演算を実行することにより、クライアント端末２０から指定されたクエリ画像に類似する暗号化された画像を検索先画像情報秘密分散格納部１２から検索し、クライアント端末２０に送信する機能部である。画像検索部１３は、例えばサーバ（コンピュータ）により実現される。画像検索部１３は、処理を実行するＣＰＵ、及びメモリやハードディスク等の記憶手段を備えており、当該記憶手段には、ＣＰＵによる演算に使用されるデータやパラメータが記憶される。また、画像検索部１３は、秘密計算により画像の評価を行う装置であることから、画像評価装置と呼んでもよい。
【００５２】
クライアント端末２０は、クエリ画像から特徴量を抽出し、特徴量を秘密分散暗号化し、暗号化したデータをクエリ画像情報秘密分散格納部１１に格納する機能、画像検索部１３に対し、クエリ画像を指定して検索を指示する機能、及び、画像検索部１３から受け取った暗号化された画像を復号する機能などを備える。また、クライアント端末２０は、検索先画像となる画像から特徴量を抽出し、暗号化した当該画像と暗号化した特徴量とを検索先画像情報秘密分散格納部１２に格納する機能を備えてもよい。更に、クライアント端末２０が画像検索部１３の機能を備えることとしてもよい。
【００５３】
上述した「暗号化」とは、後述するとおりの秘密分散法による暗号化である。また、図５では、クライアント端末２０が１つだけ示されているが、実際には、多くのクライアント端末が接続されている。
【００５４】
また、図５に示す本実施の形態のシステム構成は一例に過ぎない。本発明に係る処理内容を実現できるシステム構成であれば、図５に示すシステム構成以外の構成を用いてもよい。
【００５５】
[システムの動作]
次に、図６のフローチャートを参照して、画像検索システム１０の動作の概要について説明する。以下の動作例では、検索先画像の暗号化データ及びその特徴量の暗号化データは、各クライアント端末により作成され、検索先画像情報秘密分散格納部１２に格納するものとするが、これは一例に過ぎず、検索先画像の暗号化データ及びその特徴量の暗号化データは、クライアント端末以外の装置で作成され格納されてもよい。
【００５６】
ステップ１０１）各クライアント端末で検索先画像の特徴量ベクトルを計算する。この特徴量ベクトルは特徴が強い順にソートされているものとする。
【００５７】
ステップ１０２）各クライアント端末で検索先画像の画像特徴量の成分を秘密分散法によって暗号化する。また、検索先画像も秘密分散法によって暗号化する。暗号化された画像特徴量の成分、及び暗号化された検索先画像は検索先画像情報秘密分散格納部１２に格納される。なお、暗号化された特徴量のデータが、どの検索先画像のデータであるかは、例えば、暗号化された特徴量のデータに、検索先画像を識別する識別情報を付加することにより識別可能であるものとする。
【００５８】
ステップ１０３）クライアント端末２０は、クエリ画像の特徴量ベクトルを計算し、当該特徴量ベクトルの成分を暗号化し、暗号化されたデータをクエリ画像情報秘密分散格納部１１に格納する。なお、暗号化された特徴量のデータが、どのクエリ画像のデータであるかは、例えば、暗号化された特徴量のデータに、クエリ画像を識別する識別情報を付加することにより識別可能であるものとする。ステップ１０３では、更に、クライアント端末２０は、画像検索部１３に対して上記クエリ画像を指定する（識別情報を指定する）ことにより、クエリ画像に類似した画像の検索を指示する。
【００５９】
ステップ１０４）検索の指示を受け取った画像検索部１３は、クエリ画像情報秘密分散格納部１１と、検索先画像情報秘密分散格納部１２とを参照することにより、クエリ画像の暗号化された特徴量と、検索先画像の特徴量とを取得し、これらの差分の自乗和を暗号化領域で計算する。
【００６０】
ステップ１０５）画像検索部１３は、暗号化領域で求めた距離（差分の自乗和）を復号し、その値を類似度とする。なお、ステップ１０４、１０５の演算内容の詳細は後述する。
【００６１】
ステップ１０６）ステップ１０４とステップ１０５は、検索先画像毎に行われ、検索先画像毎のクエリ画像に対する類似度が算出される。画像検索部１３は、算出された類似度をソートし、ソートした結果、類似度が近いもの（距離が小さいもの）から順に、暗号化された画像を検索先画像情報秘密分散格納部１２から取得し、クライアント端末２０に送る。例えば、類似度が高いほうから上位N番目（Nは予め定めた自然数）までの暗号化画像をクライアント端末２０に送るようにする。
【００６２】
なお、画像検索部１３が、画像の識別情報をクライアント端末２０に送信し、クライアント端末２０が検索先画像情報秘密分散格納部１２から暗号化された画像を取得することとしてもよい。  
ステップ１０７）クライアント端末２０は、取得した暗号化画像を復号し、復号された画像を表示する。
【００６３】
上記のように、本実施の形態によれば、ネットワーク上においては、画像及び特徴量を暗号化した状態で処理を実行することができる。
【００６４】
[演算の詳細]
以下、画像の特徴量の暗号化とマルチパーティプロトコルによる差分自乗の総和の演算について詳細に説明する。本実施の形態では、画像特徴量の暗号化は各クライアント端末により実行され、差分自乗の総和の演算は画像検索部１３により実行される。
【００６５】
まず、クエリ画像の特徴量ベクトルを
S = (s1, s2, ....., sm)             (5)
とおき、検索先画像の特徴量ベクトルを
T = (t1, t2, ......, tm)             (6)
とおく。
【００６６】
この両ベクトルの距離を求めることで特徴量ベクトルの距離とする。よって、両ベクトルの差分自乗の総和である次式（７）が本実施の形態における検索に用いる各画像の類似度となる。
【００６７】
【数５】
0005687601.tif 000006
本実施の形態では、この値を各成分を暗号化した状態で求めている。具体的には、以下で説明するように、Shamirの秘密分散法によるマルチパーティプロトコルを差分の自乗を求めるための形式に拡張することにより求める。以下に暗号化のプロセスと差分の自乗を求めるアルゴリズムについて説明する。このアルゴリズムは、例えばプログラムとして実現でき、コンピュータである画像検索部１３により実行される。
【００６８】
まず、本実施の形態では、検索先画像とクエリ画像の特徴量ベクトルを暗号化領域で処理を行いたいので、ベクトルの成分であるsiとtiを以下のパラメータを用いて秘密分散法によって暗号化する。
【００６９】
si：平文
ti：平文
k：復号に必要なしきい値
n：分散数
r：乱数
xj：自然数（パラメータ）  xj ≠ xh(j ≠ h)
yj：自然数（パラメータ）  yj ≠ yh(j ≠ h)
wj：分散暗号文
ここで、xjとyjは秘密鍵として扱うこととする。つまり、本実施の形態では、各クライアント端末において２種類のパラメータで画像特徴量を暗号化し、それぞれが秘密分散格納部に格納される。
【００７０】
こうすることによってk個以上の情報を集めた者はマルチパーティプロトコルによる演算のみを行うことが可能であり、暗号化された演算結果と秘密鍵を持つ者のみが復号に必要な逆行列を生成できるので、演算結果を復号することが可能になる。本実施の形態では、この「暗号化された演算結果と秘密鍵を持つ者」は画像検索部１３である。
【００７１】
次に、差分は式（４）の加算と同様に成り立ち、その暗号文は以下のようになる。
【００７２】
【数６】
0005687601.tif 000007
ただし、Δdi = si − ti 、Δrj = rj −  r'jである。
【００７３】
次に以下のようにパラメータyiによって秘密分散暗号化した暗号化データについても差分を用意する。以下の行列Ｙは、例えば式（１）のＸと同様の構成を有するが、パラメータとしてxiではなくyiを用いている。
【００７４】
【数７】
0005687601.tif 000008
次にこの暗号文を転置したベクトルを算出する。
【００７５】
【数８】
0005687601.tif 000009
このベクトルの右側の行列YTはパラメータ行列を転置したものであるが、転置行列は行列式の値が変化しないので、この行列についても逆行列が存在する。次に、以下のように、元の暗号文（式（８））と転置した暗号文（式（１０））を掛ける。
【００７６】
【数９】
0005687601.tif 000010
こうすることによって(1, 1)成分が
【００７７】
【数１０】
0005687601.tif 000011
となる。さらにこの行列(１１)は加算の準同型性を持つので、特徴量の各成分について同様に暗号化した差分の自乗を演算した結果同士を加算すると、(1, 1) 成分が特徴量ベクトルの差分の自乗の総和となる。これでマルチパーティプロトコルによる差分の自乗の総和が暗号領域で算出される。最後にX-1を行列（１１）の左から掛け、(YT)-1 を右から掛け、(1, 1) 成分を取り出すことで復号が完了し以下の定義した距離を求めることができる。
【００７８】
【数１１】
0005687601.tif 000012
画像検索部１３は、このような演算を検索先画像毎に行い、距離を評価して、類似度を判断し、類似すると判断された暗号化画像をクライアント端末２０に送信する。
【００７９】
（実施の形態のまとめ）
上述したように、本実施の形態によれば、画像検索を暗号化領域で可能にするアルゴリズムが実現される。本実施の形態の画像検索ではクエリを画像として、複数の画像から類似した画像を探し出すために、画像の画素値の統計的な性質を局所特徴量ベクトルとして抽出し、クエリの局所特徴量ベクトルとの距離を演算し、距離が近いものを類似画像として選び出す。
【００８０】
これら全ての演算について暗号化領域で演算することは困難であることから、本実施の形態では、暗号化されていない平文画像から特徴量ベクトルを抽出し、特徴量ベクトルを暗号化することしている。そして距離計算を復号せずにマルチパーティプロトコルによって演算する。
【００８１】
実際のサービス上では、例えば、暗号化した特徴量ベクトルと別途暗号化した画像の両方をネットワーク上におくことで、復号鍵を持つユーザが暗号化したクエリ画像の特徴量によって検索した結果である類似画像を取得し、復号することが可能となる。
【００８２】
すなわち、従来、暗号化した数値データに対する秘密計算があったが、画像データに対する秘密計算は実現されていなかった。そこで、本実施の形態では、加算の準同型性の性質を有する秘密分散法を利用して、暗号化された画像特徴量どうしの差分二乗和を暗号領域で演算し、復号化することで、平文における差分二乗和を抽出し、画像どうしの類似性の評価を実現している。
【００８３】
また、本実施の形態の技術は、従来技術の演算対象を数値データから画像データに変更しただけの技術ではなく、汎用性の高いShamirの秘密分散法によるマルチパーティプロトコルを利用し、分散数の制限を受けることがないという特徴や、マルチパーティプロトコルによる積の演算を簡易的な方法で実現し、転置した行列の積を求めることで秘密計算の積の演算を可能にしたという従来技術にない特徴を有する。
【００８４】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００８５】
１０  画像検索システム
１１  クエリ画像情報秘密分散格納部
１２  検索先画像情報秘密分散格納部
１３  画像検索部
２０  クライアント端末
【図１】
0005687601.tif 000013
【図２】
0005687601.tif 000014
【図３】
0005687601.tif 000015
【図４】
0005687601.tif 000016
【図５】
0005687601.tif 000017
【図６】
0005687601.tif 000018