JP2019207281A - 大小判定サーバ、大小判定暗号化システム、及び大小判定方法 - Google Patents

Abstract

【課題】暗号化データにおける大小判定を、特定のもののみが実行可能であり、かつ当該大小判定における処理量を低減する。【解決手段】大小判定サーバは、第１秘密鍵と、複数の数値それぞれに対応する大小判定用タグと、を保持し、各大小判定用タグは、該複数の数値それぞれが、加法的準同型性を有する暗号方式で、第１秘密鍵を含む複数の秘密鍵と第１パラメータとを用いて暗号化された暗号文であり、該暗号方式において、平文空間が自然数を法とした剰余演算を有し、大小判定サーバは、第１秘密鍵と２つの大小判定用タグから、加法的準同型性を用いて、該２つの大小判定用タグに対応する数値の大小判定のための値を生成し、生成した値の第１パラメータに関する離散対数が所定範囲の値において算出可能であるか否かに基づいて、該２つの大小判定用タグに対応する数値の大小を判定する。【選択図】図２

Description

本発明は、大小判定サーバ、大小判定暗号化システム、及び大小判定方法に関する。

近年、膨大なデータから未知の、かつ有効な知識を引き出すビッグデータ分析が、注目を集めている。また、企業が、自社保有のデータはもとより、社外のデータも収集し、マーケティングや業務効率化に活用するなど、情報の種々の分析はますます重要な活動として認識されるようになっている。

一方で保有データの管理に不備があり、顧客の個人情報を含む情報が大量に漏えいする事件及び事故が多発しており、社会問題となっている。このような漏えい事故を起こした企業は多額の補償金を負担することになり、場合によっては企業の存亡に関わる事態となる。またこのような漏えい事故が発生すると、情報保有者である個人などが情報提供を躊躇するおそれがある。従って、漏えい事故と無関係に企業であっても、情報を収集しにくくなり、有効な分析結果を得られなくなるなど、悪影響が出ることが懸念される。

これらの状況に対し、正しく情報を収集、利活用するための法整備が進んでいる。また、各業界において情報の取り扱いにおけるガイドライン（特に個人情報についての機微性、及びプライバシ性は業界ごとに異なる）も整備されつつある。しかし、これらの法律面の整備や自主規制によって情報漏えいに対する抑止効果はあるものの、技術的な情報漏えい対策が求められる。

情報漏えい及び情報漏えいが引き起こすプライバシ侵害を防ぐ技術としては、従来から、情報にアクセス可能な人を制限するアクセスコントロールや、機材の盗難などに対して効果的な暗号化などがある。しかし、昨今の情報漏えい事件では計算機リソースの管理を任された外部委託業者の権限悪用によるものが少なくない。管理者に対して、データベースなどにアクセスする正当な権限が渡されたるため、管理者は本来の管理業務に不必要な情報まで閲覧可能となり、このような情報が悪用されるおそれがある。

このような状況に対しては、従来のアクセスコントロールは無力である。また、暗号化がされていたとしても、ストレージ暗号のように記憶媒体からデータを取り出して利用する際には復号化する方式で運用されている場合には、管理者は正当な手続きのもと、復号されたデータを閲覧できてしまう。

外部委託者、又は外部委託者の傍には復号鍵を置かず、社内の限られた正当なユーザのみが復号鍵を持ち、データの利用時には暗号化データを取得して復号する運用がある。しかし、従来の暗号技術では、データベースに暗号化データを保管した場合、暗号化されたままの状態では、検索、及び数値データの集計等の基本的な処理すら実行できない。従って、この場合には、データベースが単なる暗号文保管庫でしかなく、データベース機能を無駄にしてしまう。

そこで昨今、安全性の高い暗号化技術を用いながら、暗号化データを復号化することなく所定の処理を可能にする技術の研究に注目が集まっている。例えば、暗号化データを復号化することなく平文の一致不一致が判定できる検索可能暗号の研究が盛んに行われている。しかし、平文が文字列(氏名、住所など)である暗号文を対象とした検索可能暗号では、数値データの大小比較処理、及び順序関係の判定処理を実行することは難しい。

数値データの大小比較処理は、データのソート処理、及び閾値判定処理によるデータ抽出処理等の分析に用いられるのみならず、通常業務においても頻出する重要な演算機能である。比較対象の数値データが、医療系の個人情報である場合や、企業の機密情報である場合には、外部のクラウド等を含む第三者に数値データを開示して処理させることは情報漏えいの観点から望ましくない。よって、数値を暗号化したまま大小比較できる暗号方式が必要である。

大小比較が可能な暗号方式として、順序保存暗号と呼ばれる暗号方式が知られている。順序保存暗号方式において、平文における大小の順序が、そのまま暗号文においても保存される。従って、暗号文を入手した誰もが、データのソートが可能である。

つまり、暗号文が漏えいすることは、平文の順序情報が漏えいすることと同じであり、平文の総数が少ない場合のような特定の条件下では、暗号文から平文を推測可能であり、安全性が高くない。そこで、非特許文献１には、大小比較用の秘密鍵の保有するもののみが暗号化データにおける大小判定が可能な暗号方式が記載されている。

Nathan Chenette et al, "Practical Order-Revealing Encryption with Limited Leakege", FSE 2016 Revised Selected Papers of the 23rd International Conference on Fast Software Encryption - Volume 9783, March 20, 2016, Pages 474-493

しかし、非特許文献１に記載の暗号方式において、暗号文長は平文の総数に比例して長くなる。従って、平文の総数が大きくなると、暗号化データにおける大小判定のための処理量が過大となる。

そこで、本発明の一態様は、暗号化データにおける大小判定を、特定のもののみが実行可能であり、かつ当該大小判定における処理量を低減することを目的とする。

上記した課題を解決するために本発明の一態様は以下の構成を採用する。大小判定サーバは、プロセッサとメモリとを備え、前記メモリは、第１秘密鍵と、複数の数値それぞれに対応する大小判定用タグと、を保持し、前記大小判定用タグそれぞれは、前記複数の数値それぞれが、加法的準同型性を有する暗号方式で、前記第１秘密鍵を含む複数の秘密鍵と、第１パラメータと、を用いて暗号化された暗号文であり、前記暗号方式において、平文空間が自然数を法とした剰余演算を有し、前記プロセッサは、大小判定処理において、前記第１秘密鍵と２つの前記大小判定用タグから、前記加法的準同型性を用いて、前記２つの大小判定用タグに対応する数値の大小判定のための値を生成し、前記生成した値の前記第１パラメータに関する離散対数が所定範囲の値において算出可能であるか否かに基づいて、前記２つの大小判定用タグに対応する数値の大小を判定する。

本発明の一態様によれば、暗号化データにおける大小判定を、特定のもののみが実行可能であり、かつ当該大小判定における処理量を低減することができる。

上記した以外の課題、構成及び効果は、以下の実施形態の説明により明らかにされる。

実施例１における大小判定可能暗号システムの構成例を示すブロック図である。 実施例１における大小判定サーバの構成例を示すブロック図である。 実施例１におけるユーザ端末の構成例を示すブロック図である。 実施例１における暗号化対象データの暗号化処理、暗号化データの送信処理、及び暗号文の保管処理の一例を示すシーケンス図である。 実施例１における大小判定用タグと暗号化された数値セルの値と、が結合された暗号文の一例である。 実施例１における暗号化データの一例である。 実施例１における大小比較処理とソート処理の一例を示すシーケンス図である。 実施例１における大小判定用タグ生成処理の一例を示すフローチャートである。 実施例１におけるシステムパラメータと大小判定用タグ生成用秘密鍵の一覧を示す説明図である。 実施例１におけるシステムパラメータと大小判定用タグ生成用秘密鍵の一覧を示す説明図である。 実施例１におけるシステムパラメータと大小判定用タグ生成用秘密鍵の一覧を示す説明図である。 実施例１における大小判定処理の一例を示すフローチャートである。 実施例１における暗号化実行画面の一例である。 実施例１におけるソート依頼画面の一例である。 実施例１における閾値判定処理の一例を示すフローチャートである。

以下、本発明の実施形態を図面に基づいて詳細に説明する。本実施形態において、同一の構成には原則として同一の符号を付け、繰り返しの説明は省略する。なお、本実施形態は本発明を実現するための一例に過ぎず、本発明の技術的範囲を限定するものではないことに注意すべきである。

（システム構成）
図１は、大小判定可能暗号システムの構成例を示すブロック図である。大小判定可能暗号システムは、例えば、１以上のユーザ端末３００と、大小判定サーバ２００と、を含む。ユーザ端末３００それぞれと大小判定サーバ２００は、ネットワーク１００を介して互いに接続されている。

ユーザ端末３００は、数値型の値を含む暗号化対象のデータを保持する。ユーザ端末３００は、数値型の値について後述する大小判定用タグを生成した上で、当該データを暗号化する。つまり、ユーザ端末３００は、暗号化を実行する暗号化端末の一例である。ユーザ端末３００は、暗号化されたデータを、大小判定サーバ２００に送信する。

大小判定サーバ２００は、ユーザ端末３００からの依頼に基づいて、暗号化されたデータを暗号化したままの状態で、当該データに含まれる数値型の値の、大小判定を行う。大小判定サーバ２００は、大小判定結果に基づいて、当該データのソートを行う。大小判定サーバ２００は、大小判定結果又はソート結果をユーザ端末３００に送信する。

大小判定サーバ２００は、例えば、クラウド事業者に設置される。クラウド事業者のサービスを利用するユーザが、ユーザ端末３００を所有する。ユーザ端末３００は、例えば、携帯電話などである。

（大小判定サーバ）
図２は、大小判定サーバ２００の構成例を示すブロック図である。大小判定サーバ２００は、例えば、制御部２１０、記憶部２２０、入力部２０１、出力部２０２、及び通信部２０３を含む計算機によって構成される。

制御部２１０は、プロセッサを含む。記憶部２２０は、データ記憶部２３０及び一時情報記憶部２４０を含む。データ記憶部２３０は、例えば、補助記憶装置から構成される。一時情報記憶部２４０は、例えば、メモリから構成される。

制御部２１０に含まれるプロセッサは、メモリに格納されたプログラムを実行する。メモリは、不揮発性の記憶素子であるＲＯＭ及び揮発性の記憶素子であるＲＡＭを含む。ＲＯＭは、不変のプログラム（例えば、ＢＩＯＳ）などを格納する。ＲＡＭは、ＤＲＡＭ（Ｄｙｎａｍｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）のような高速かつ揮発性の記憶素子であり、プロセッサが実行するプログラム及びプログラムの実行時に使用されるデータを一時的に格納する。

補助記憶装置は、例えば、磁気記憶装置（ＨＤＤ）、フラッシュメモリ（ＳＳＤ）等の大容量かつ不揮発性の記憶装置であり、プロセッサが実行するプログラム及びプログラムの実行時に使用されるデータを格納する。すなわち、プログラムは、補助記憶装置から読み出されて、メモリにロードされて、プロセッサによって実行される。

入力部２０１は、例えば、キーボードやマウスなどの、オペレータからの入力を受ける装置である。出力部２０２は、ディスプレイ装置やプリンタなどの、プログラムの実行結果をオペレータが視認可能な形式で出力する装置である。大小判定サーバ２００は、入力部２０１及び出力部２０２が接続される入力インターフェース及び出力インターフェースを有する。

通信部２０３は、例えば、所定のプロトコルに従って、他の装置との通信を制御するネットワークインターフェース装置である。また、通信部２０３は、例えば、ＵＳＢ等のシリアルインターフェースを含む。

プロセッサが実行するプログラムは、リムーバブルメディア（ＣＤ−ＲＯＭ、フラッシュメモリなど）又はネットワークを介して大小判定サーバ２００に提供され、非一時的記憶媒体である不揮発性の補助記憶装置に格納される。このため、大小判定サーバ２００は、リムーバブルメディアからデータを読み込むインターフェースを有するとよい。

大小判定サーバ２００は、物理的に一つの計算機上で、又は、論理的又は物理的に構成された複数の計算機上で構成される計算機システムであり、同一の計算機上で別個のスレッドで動作してもよく、複数の物理的計算機資源上に構築された仮想計算機上で動作してもよい。ユーザ端末３００についても同様である。

制御部２１０は、全体処理部２１１及び大小判定部２１２を含む。例えば、制御部２１０に含まれるプロセッサは、メモリにロードされた全体処理プログラムに従って動作することで、全体処理部２１１として機能し、メモリにロードされた大小判定プログラムに従って動作することで、大小判定部２１２として機能する。後述するユーザ端末３００の制御部に含まれる各部についても同様である。

全体処理部２１１は、大小判定サーバ２００による処理を統括制御する。全体処理部２１１は、入力部２０１を介して受け付けた情報を記憶部２２０に格納する。全体処理部２１１は、ユーザ端末３００を含む他の装置との情報の送受信を制御する。

また、全体処理部２１１は、データを出力部２０２に出力する。全体処理部２１１は、記憶部２２０に格納されているデータを読み込み、通信部２０３を介して、ユーザ端末３００へ送信する。全体処理部２１１は、通信部２０３を介して、ユーザ端末３００からデータを受信する。

記憶部２２０のデータ記憶部２３０は、暗号化データ記憶部２３１と、大小判定用パラメータ記憶部２３２を含む。暗号化データ記憶部２３１は、例えば、ユーザ端末３００から受信した暗号化済みのデータを保持する。大小判定用パラメータ記憶部２３２は、暗号化データに含まれる暗号化された数値の大小を判定するためのパラメータ及び鍵を保持する。

なお、本実施例及び他の実施例において、大小判定可能暗号システムが使用する情報は、データ構造に依存せずどのようなデータ構造で表現されていてもよい。例えば、テーブル、リスト、データベース又はキューから適切に選択したデータ構造体が、情報を格納することができる。情報記憶システムが使用する情報は、データ記憶装置における対応するデータ記憶領域に格納される。

（ユーザ端末）
図３は、ユーザ端末３００の構成例を示すブロック図である。ユーザ端末３００は、例えば、制御部３１０、記憶部３２０、入力部３０１、出力部３０２、及び通信部３０３を含む計算機によって構成される。記憶部３２０は、データ記憶部３３０及び一時情報記憶部３４０を含む。

制御部３１０、記憶部３２０、入力部３０１、出力部３０２、通信部３０３、データ記憶部３３０、及び一時情報記憶部３４０を構成するハードウェアは、それぞれ、制御部２１０、記憶部２２０、入力部２０１、出力部２０２、通信部２０３、データ記憶部２３０、及び一時情報記憶部２４０を構成するハードウェアと同様であるため、説明を省略する。

制御部３１０は、全体処理部３１１、暗号化処理部３１２、復号化処理部３１３、及び大小判定用タグ生成部３１４を含む。全体処理部３１１は、ユーザ端末３００による処理を統括制御する。全体処理部３１１は、入力部３０１を介して受け付けた情報を記憶部３２０に格納する。全体処理部３１１は、大小判定サーバ２００を含む他の装置との情報の送受信を制御する。

また、全体処理部３１１は、データを出力部３０２に出力する。全体処理部３１１は、記憶部３２０に格納されているデータを読み込み、暗号化処理部３１２にデータの暗号化をさせたり、復号化処理部３１３に暗号化データの復号化をさせたり、通信部３０３を介して、大小判定サーバ２００へ送信する。全体処理部３１１は、通信部３０３を介して、大小判定サーバ２００からデータを受信する。

データ記憶部３３０は、暗号化鍵記憶部３３１、復号化鍵記憶部３３２、タグ生成用パラメータ記憶部３３３、及び暗号化対象データ記憶部３３４を含む。暗号化鍵記憶部３３１は、暗号化対象データを暗号化するための鍵を保持する。復号化鍵記憶部３３２は、当該暗号化鍵で暗号化されたデータを復号するための復号化鍵を保持する。当該暗号化鍵及び復号化鍵は、例えば、それぞれ、暗号化鍵記憶部３３１及び復号化鍵記憶部３３２に予め格納されていてもよいし、ユーザ端末３００自身が生成してもよい。

タグ生成用パラメータ記憶部３３３は、大小判定用タグを生成するための暗号化鍵及びパラメータを保持する。暗号化対象データ３３４は、暗号化対象の平文データである暗号化データを保持する。

＜大小判定可能暗号システムによる処理＞
（暗号化処理及び暗号文の保管処理）
図４は、暗号化対象データの暗号化処理、暗号化データの送信処理、及び暗号文の保管処理の一例を示すシーケンス図である。以下、説明の便宜のため、暗号化データがテーブル形式のデータである例を説明する。以下、暗号化対象のテーブルは、数値型の値を有する数値セルからなるカラムを含むものとする。

大小判定用タグ生成部３１４は、暗号化対象データ記憶部３３４が保持する暗号化データの各数値セルの値に対して大小判定用のタグを生成する（Ｓ４０１）。大小判定用タグ生成部３１４は、ステップＳ４０１において、平文空間が剰余演算を有する（例えば、平文空間が剰余群Ｚ／ｎＺの部分加法群（Ｚは整数全体がなす群、ｎは２以上の自然数））暗号方式であって、加法的準同型性を有する暗号方式、で各数値セルの値を暗号化することで大小判定用タグを生成する。なお、詳細は後述するが、秘密鍵を有するものだけが、秘密鍵と２つの大小判定用タグから生成された値の、所定のシステムパラメータに関する離散対数、を所定範囲の値から算出できる可能性がある。

なお、大小判定用タグ生成部３１４は、大小判定用タグの生成における暗号化に、タグ生成用パラメータ記憶部３３３が保持する暗号化鍵を用いる。ステップＳ４０３における大小判定用タグ生成処理の詳細については後述する。

続いて、暗号化処理部３１２は暗号化鍵記憶部３３１が保持する暗号化鍵を用いて暗号化対象データに含まれる、各セルを暗号化して暗号化データを生成する（Ｓ４０２）。なお、ステップＳ４０２において、任意の暗号方式（例えば、共通鍵暗号又は公開鍵暗号）を用いることができる。なお、ステップＳ４０１とステップＳ４０２の実行順序は逆であってもよい。

次に、大小判定用タグ生成部３１４は、暗号化データ内の各数値セルの値（暗号文）と、当該数値セルの値に対応する大小判定用タグと、を結合する（Ｓ４０３）。続いて、全体処理部３１１は、大小判定用タグが結合された暗号化データを大小判定サーバ２００に（Ｓ４０４）。全体処理部２１１は受信した暗号化データを暗号化データ記憶部２３１に格納する（Ｓ４０５）。

図５Ａは、大小判定用タグと暗号化された数値セルの値と、が結合された暗号文の一例である。図５Ａの例では、大小判定用タグＣｉのビット列の直後に、平文ｍｉが暗号化された暗号文Ｅｉのビット列が結合されたことにより、暗号文Ｄｉが生成された。なお、例えば、大小判定用タグＣｉのビット総数が予め定められていることにより、暗号文Ｄｉのうち、大小判定用タグＣｉに相当するビットと、暗号文Ｅｉに相当するビットと、を判別することができる。

図５Ｂは、暗号化データの一例である。図５Ｂの例では、数値型の値である年齢が本実施形態の大小判定可能暗号で暗号化されている。Ｄｉ（ｉ＝１，２，３）は、図５Ａと同様の暗号文である。Ｃｉ｜｜Ｅｉはビット系列ＣｉとＥｉの結合を表す。Ｅｎｃ１、Ｅｎｃ２は共通鍵暗号、又は公開鍵暗号等の任意の暗号方式を表す、住所のような順序関係は重要でない文字型の値が暗号化されている。

図５Ｂの例では、数値型のセルに対する暗号方式と文字型のセルに対する暗号方式が異なる。なお、Ｅｎｃ１とＥｎｃ２は同じ暗号方式で、同一の鍵で暗号化されたものでもよいし、異なる方式でもよい。なお、図５Ｂの例では、項目名を示す最上段のレコード、及びレコードの識別子を示す最左列のカラムが暗号化されていないが、これらのレコード及びカラムについても暗号化されていてもよい。

（大小比較処理及びソート処理）
図６は、大小比較処理とソート処理の一例を示すシーケンス図である。全体処理部２１１は、例えばユーザから入力された指示に従って、大小判定サーバ２００に送信した暗号化データの大小比較処理及びソート処理を依頼する（Ｓ５０１）。なお、全体処理部２１１は、当該依頼において、例えば、ソート対象の暗号化データと、当該暗号化データ内の数値型のセルからなるソート対象のカラムと、を指定する。なお、暗号化データを数値セルの値の昇順に並び替えること、及び降順に並び替えることはいずれもソート処理の一例である。

大小判定部２１２は、指定された暗号化データの指定された数値セルの値の大小判定を、大小判定用タグを用いて実行する（Ｓ５０２）。なお、ステップＳ５０２における大小判定処理の詳細は後述する。

続いて、大小判定部２１２は、大小判定結果を用いて暗号化データのソートを行う（Ｓ５０３）。全体処理部２１１は、大小判定部２１２がソートした暗号化データを、復号することなく、ユーザ端末３００に送信する（Ｓ５０４）。復号化処理部３１３は、受信した暗号化データの暗号文を、復号化鍵記憶部３３２が保持する復号化鍵を用いて復号する（Ｓ５０５）。

なお、図６では、ソート処理が行われる例を説明したが、ユーザ端末３００は、暗号化データの複数の数値セルを指定して、当該複数の数値セルの大小判定処理のみを、大小判定サーバ２００に依頼してもよい。この場合、大小判定サーバ２００は、当該複数のセルにおける大小判定結果をユーザ端末３００に返す。

（大小判定用タグ生成）
図７は、大小判定用タグ生成処理（Ｓ４０１）の一例を示すフローチャートである。ユーザ端末３００はタグ生成処理（Ｓ４０１）の開始時までに、大小判定サーバ２００は大小判定処理（Ｓ５０２）の開始時までに、システムパラメータＧ，ｇ，ｕ，ｈ，Ｕを取得する。

なお、これらのシステムパラメータは、例えば、他の装置又はユーザから予め与えられてもよいし、大小判定用タグ生成部３１４によって算出されてもよい。また、これらのシステムパラメータは、ユーザ端末３００のタグ生成用パラメータ記憶部３３３及び大小判定サーバ２００の大小判定用パラメータ記憶部２３２に格納される。なお、大小判定サーバ２００はシステムパラメータのうち、ｈを保持しなくてもよい。

なお、Ｇは、Ｇにおける離散対数問題を解くことが計算量的に困難である有限巡回群（例えば、Ｚ／ｐＺ（ｐは素数））である。なお、Ｇにおける離散対数問題を解くことが計算量的に困難であるとは、例えば、所定のアルゴリズム（例えば、Ｂａｂｙ−ｓｔｅｐ Ｇｉａｎｔ−ｓｔｅｐ）が用いられた場合に、所定の計算回数（例えば２^８０回）で、Ｇにおける離散対数問題が解ける確率が所定値（例えば１／２以下）であることを示す。

ｇ及びｕは、ランダムに選択されたＧの相異なる生成元である。ｈはｈ＝ｇ^Ｓで定義される。なお、ｓはランダムに生成された１より大きい整数である。

Ｕは、自然数であり、Ｇにおける底ｕに関する離散対数問題の解が、Ｕ以下の整数値であれば容易に解ける値であるとする。具体的には、例えば、解がＵ以下の整数値であれば、所定のアルゴリズム（例えば、Ｂａｂｙ−ｓｔｅｐ Ｇｉａｎｔ−ｓｔｅｐ）が用いられた場合に、所定の計算回数で、Ｇにおける底ｕに離散対数問題が解けることが望ましい。なお、Ｕは、Ｇの位数より十分小さく（例えば、少なくとも１ビット以上小さい）、数値セルの全ての平文より十分大きい（例えば、少なくとも１ビット以上大きい）ものとする。Ｕは、例えば、予め与えられているものとする。

さらに、大小判定用タグ生成部３１４は、暗号化対象データに含まれる平文の数値セルの値の上限をＴである場合に、ＲＴ＜Ｕを満たす３以上の自然数Ｒをランダムに生成する。なお、Ｔは、Ｇの位数より小さいものとする。

また、ユーザ端末３００はタグ生成処理（Ｓ４０１）の開始時までに、大小判定用タグ生成用秘密鍵ｘ，Ｒ，ｓを取得し、タグ生成用パラメータ記憶部３３３に格納する。なお、これらの大小判定用タグ生成用秘密鍵は、例えば、他の装置又はユーザから予め与えられてもよいし、大小判定用タグ生成部３１４によって算出されてもよい。なお、ｘはランダムに生成されたＧの元である。

また、大小判定サーバ２００は、大小判定用タグ生成用秘密鍵ｓ（ｓは大小判定用の秘密鍵でもある）を、大小判定処理（Ｓ５０２）の開始時までに取得し、大小判定用パラメータ記憶部２３２に格納する。なお、大小判定用タグ生成用秘密鍵ｓは、大小判定の実行を許可されていない第三者に見られないように安全に保管される。

図８Ａ〜図８Ｃは、前述したシステムパラメータと大小判定用タグ生成用秘密鍵の一覧を示す説明図である。図８の例では、Ｇは位数が素数ｐの巡回群としている。

図７の説明に戻る。全体処理部３１１は、システムパラメータＧ，ｇ，ｕ，ｈ，Ｕをタグ生成用パラメータ記憶部３３３から読み出し、大小判定用タグ生成部３１４に入力する（Ｓ６０１）。全体処理部３１１は、大小判定用タグ生成用秘密鍵ｘ，Ｒ，ｓをタグ生成用パラメータ記憶部３３３から読み出し、大小判定用タグ生成部３１４に入力する（Ｓ６０２）。

全体処理部３１１は変数ｉをｉ＝１に設定する（Ｓ６０３）。大小判定用タグ生成対象の数値セルの平文がｎ個（ｍ１，・・・，ｍｎ）あるものとする。なお、例えば、ｍ１，・・・，ｍｎに、非負整数でない値が存在する場合には、例えば、ｍ１，・・・，ｍｎの全てを、１０^ｋ倍（ｋは自然数）したり、ｍ１，・・・，ｍｎの全てに同じ値を加えたりして、ｍ１，・・・，ｍｎの全てが非負整数に変換されていることが望ましい。

全体処理部３１１は、ソート対象の（i番目の）の数値セルの平文ｍｉを大小判定用タグ生成部３１４に入力する（Ｓ６０４）。大小判定用タグ生成部３１４は、０＜αi＜Ｒ／２＜βi＜Ｒを満たす整数αi,βiと、Ｇの位数より小さい正整数δi,λiをランダムに生成する（Ｓ６０５）。また、大小判定用タグ生成部３１４は、Ｇの元である、Ｃｉ（１）＝ｇ^δｉｘ，Ｃｉ（２）＝ｇ^λｉｘ^−１，Ｃｉ（３）＝ｈ^δｉｕ^{Ｒｍｉ＋αｉ}，Ｃｉ（４）＝ｈ^λｉｕ^{−Ｒｍｉ−βｉ}を計算する（Ｓ６０６）。

大小判定用タグ生成部３１４は、平文ｍｉに対する大小判定用タグとしてこれらの結合Ｃｉ＝（Ｃｉ（１），Ｃｉ（２），Ｃｉ（３），Ｃｉ（４））を全体処理部３１１に出力（Ｓ６０７）する。大小判定用タグＣｉは、秘密鍵ｘ，Ｒ，ｓを用いて平文ｍｉから得られた暗号文である。

全体処理部３１１は、ｉ＝ｎであるか否かを判定する（６０８）。全体処理部３１１は、ｉ＝ｎでないと判定した場合（Ｓ６０８：Ｎｏ）、ｉにｉ＋１を代入し（Ｓ６０９）、ステップＳ６０４に戻る。全体処理部３１１は、ｉ＝ｎであると判定した場合（Ｓ６０８：Ｙｅｓ）、大小判定用タグ生成処理を終了する。

（大小判定用タグを用いた大小比較）
図９は、大小判定処理（Ｓ５０２）の一例を示すフローチャートである。全体処理部２１１はシステムパラメータＧ，ｇ，ｕ，ｈ，Ｕを大小判定用パラメータ記憶部２３２から読み出し、大小判定部２１２に入力する（Ｓ７０１）。なお、大小判定部２１２は、システムパラメータのうちｈについては読み出さなくてもよい。全体処理部２１１は、大小判定用秘密鍵ｓを、大小判定用パラメータ記憶部２３２から読み出し、大小判定部２１２に入力する（Ｓ７０２）。

次に全体処理部２１１は、異なる自然数を要素とする未選択のベクトル（ｉ，ｊ）を決定する（ステップＳ７０３）。但し、ｉ，ｊは、それぞれ大小判定対象のタグの個数以下であるものとする。全体処理部２１１は、大小比較の対象となる二つのタグＣｉ＝（Ｃｉ（１），Ｃｉ（２），Ｃｉ（３），Ｃｉ（４））、Ｃｊ＝（Ｃｊ（１），Ｃｊ（２），Ｃｊ（３），Ｃｊ（４））を暗号化データ記憶部２３１から読み出し、大小判定部２１２に入力する（Ｓ７０４）。

大小判定部２１２は、加法的準同型性を用いて、Ｘ＝Ｃｉ（１）Ｃｊ（２）＝ｇ^{δｉ＋λｊ}を計算（Ｓ７０５）する。大小判定部２１２は、Ｘ^ｓ＝ｇ^{ｓ（δｉ＋λｊ）}＝ｈ^{δｉ＋λｊ}を計算する（Ｓ７０６）大小判定部２１２は、加法的準同型性とステップＳ７０６の計算結果とを用いてＹ＝Ｃｉ（３）Ｃｊ（４）＝ｈ^{δｉ＋λｊ}ｕ^{Ｒ（ｍｉ−ｍｊ）＋（αｉ−βｊ）}を計算する（Ｓ７０７）。大小判定部２１２は、Ｚ＝Ｙ／Ｘ^Ｓ＝ｕ^{Ｒ（ｍｉ−ｍｊ）＋（αｉ−βｊ）}を計算する（Ｓ７０８）。

次に、大小判定部２１２は、閾値Ｕ以下の範囲で、Ｚのｕに関する離散対数の計算を試みる（Ｓ７０９）。なお、ステップＳ７０９における離散対数の計算には、例えば、Ｂａｂｙ ｓｔｅｐ Ｇｉａｎｔ ｓｔｅｐなどの手法が用いられる。大小判定部２１２は、離散対数を算出できた場合（Ｓ７０９：Ｙｅｓ）Ｃｉの平文の数値はＣｊの平文の数値より大きいであると判定し、判定結果を全体処理部２１１に通知する、（Ｓ７１０）。大小判定部２１２は、離散対数を算出できた場合（Ｓ７０９：Ｎｏ）、Ｃｉの平文の数値はＣｊの平文の数値以下であると判定し、判定結果を全体処理部２１１に通知する（Ｓ７１１）。

ステップＳ７０９における離散対数の計算可否と大小判定結果との関連について詳細に説明する。Ｚのｕに関する離散対数がＵ以下の範囲で算出不可能である場合、平文ｍｉ，ｍｊは、Ｒ（ｍｉ−ｍｊ）＋（αｉ−βｊ）＜０、又はＵ＜Ｒ（ｍｉ−ｍｊ）＋（αｉ−βｊ）＜（群Ｇの位数）を満たす。

一方、数値セルの値の上限Ｔに対してＲＴ＜Ｕであり、０＜αi＜Ｒ／２＜βｊ＜Ｒであるため、Ｒ（ｍｉ−ｍｊ）＋（αｉ−βｊ）＜ＲＴ＜Ｕである。従って、不等式Ｒ（ｍｉ−ｍｊ）＋（αｉ−βｊ）＜０が成立する。ｍｉ≦ｍｊであれば、明らかに当該不等式を満たす。仮にｍｉ＞ｍｊとすると０＞Ｒ（ｍｉ−ｍｊ）＋（αｉ−βｊ）＞Ｒ×１＋（０−Ｒ）＝０となり矛盾する。従って、Ｚのｕに関する離散対数がＵ以下の範囲で算出不可能である場合、ｍｉ≦ｍｊである。

一方、Ｚのｕに関する離散対数がＵ以下の範囲で算出可能である場合、平文ｍｉ，ｍｊは、不等式０≦Ｒ（ｍｉ−ｍｊ）＋（αｉ−βｊ）≦Ｕを満たす。仮に、ｍｉ≦ｍｊとすると、当該不等式に明らかに矛盾するため、少なくともｍｉ＞ｍｊである。また、ｍｉ＞ｍｊである場合、１≦ｍｉ−ｍｊ≦Ｔである。

このとき、Ｍｉｎ｛Ｒ（ｍｉ−ｍｊ）＋（αｉ−βｊ）｝＞Ｒ×１＋（０−Ｒ）＝０、Ｍａｘ｛Ｒ（ｍｉ−ｍｊ）＋（αｉ−βｊ）｝＜ＲＴ＋（αｉ−βｊ）＜Ｕ＋（αｉ−βｊ）であり、Ｒ（ｍｉ−ｍｊ）＋（αｉ−βｊ）は（ｍｉ−ｍｊ）の単調増加関数であるため、ｍｉ＞ｍｊを満たす全てのｍｉ、ｍｊは、上記不等式を満たす。従って、Ｚのｕに関する離散対数がＵ以下の範囲で算出可能である場合、ｍｉ＞ｍｊである。

全体処理部２１１は、未選択のベクトル（ｉ，ｊ）があるか否かを判定する（Ｓ７１２）。全体処理部２１１は、未選択の（ｉ，ｊ）があると判定した場合（Ｓ７１２：Ｙｅｓ）、ステップＳ７０３に戻る。全体処理部２１１は、未選択の（ｉ，ｊ）がないと判定した場合（Ｓ７１２：Ｎｏ）、全ての大小判定結果を大小判定部２１２に返し、大小判定処理を終了し、ステップＳ５０３に移行する。

なお、例えば、平文ｍｋ，ｍｌに対して、（ｉ，ｊ）＝（ｋ，ｌ）とした場合においても、（ｉ，ｊ）＝（ｌ，ｋ）とした場合においても、ステップＳ７０９における離散対数（即ちＵ以下の離散対数）が計算不可能な場合、ｍｋ＝ｍｌである。また、平文ｍｋ，ｍｌに対して、（ｉ，ｊ）＝（ｋ，ｌ）とした場合にステップＳ７０９における離散対数が計算不可能、かつ（ｉ，ｊ）＝（ｌ，ｋ）とした場合にステップＳ７０９における離散対数が計算可能な場合は、ｍｋ＜ｍｌである。

なお、全体処理部２１１は、ステップＳ７１２において未選択のベクトル（ｉ，ｊ）があると判定した場合であっても、全ての未選択のベクトルそれぞれに対応するｍｉとｍｊの大小関係が、出力済みの判定結果から判定可能である場合には、ステップＳ７０３に戻らずステップＳ７１２に移行してもよい。

具体的には、例えば、ｍ１＜ｍ２、かつｍ２＜ｍ３という判定結果が既に得られている場合には、（ｉ，ｊ）＝（１，３）及び（ｉ，ｊ）＝（３，１）を未選択であっても、全体処理部２１１は、ｍ１＜ｍ３と判定すればよい。

なお、平文ｍｉとｍｊの大小判定処理において、ｍｉ＞ｍｊであるか又はｍｉ≦ｍｊであるかのみを判定できればよい場合（即ち、ｍｉ＝ｍｊであるか、又はｍｉ＜ｍｊであるかは不明であってもよい場合）には、ステップＳ７０３及びステップＳ７１２における異なる自然数を要素とするベクトル（ｉ，ｊ）を、異なる自然数の組み合わせ（ｉ，ｊ）と置き換えればよい。

なお、前述したように、群Ｇを用いて大小比較用タグは生成される。群Ｇは、有限体の乗法群、有限体上の楕円曲線の有理点の成す群など、離散対数問題の解の算出が困難であると考えられている群であればよく、前述した群に限定されない。

図１０は、ユーザ端末３００に表示される操作画面例である。具体的には、図１０は、暗号化実行画面１１００の一例である。暗号化実行画面１１００は、例えば、データ表示領域１１０１、ラジオボタン１１０２、暗号化実行ボタン１１０３、及びサーバ送信ボタン１１０４を含む。データ表示領域１１０１には、暗号化対象データの一部又は全部が表示される。

ラジオボタン１１０２は、本実施例の大小比較可能暗号で暗号化される対象となる、数値型のセルからなるカラム、を選択するためのラジオボタンである。暗号化実行ボタン１１０３は、ラジオボタン１１０２によって数値型のカラムを選択した後に、暗号化対象データの暗号化を実行するための選択ボタンである。前述したように、例えば、数値型として選択されたカラムは本実施例における大小判定可能暗号で暗号化され、他のカラムは通常の暗号方式で暗号化される。

暗号化が終了したら、暗号化されたデータがデータ表示領域１１０１に表示されてもよい。サーバ送信ボタン１１０４は、暗号化対象データが暗号化された後に、当該データを大小判定サーバ２００に送信するための選択ボタンである。

図１１は、ユーザ端末３００に表示される操作画面例である。具体的には、図１１は、大小判定サーバ２００に送信された暗号化データのソートを依頼するためのソート依頼画面１２００の一例である。ソート依頼画面１２００は、例えば、ラジオボタン１２０１、ソート依頼ボタン１２０２、データ表示領域１２０３、復号実行ボタン１２０４、及び復号結果保存ボタン１２０５を含む。

ラジオボタン１２０１は、ソート対象のカラムを選択するためのラジオボタンである。ソート依頼ボタン１２０２は、大小判定サーバ２００に対してソート対象のカラムをキーとした暗号化データのソートを依頼するための選択ボタンである。

前述したように、大小判定サーバ２００はソート依頼に従って暗号化データを暗号化したままソートし、ソート後の暗号化データをユーザ端末３００に送信する。データ表示領域１２０３には、大小判定サーバ２００から受信した、ソート後の暗号化データが表示される。

復号実行ボタン１２０４は、ソート後の暗号化データを復号するための選択ボタンである。復号結果、即ちソート後の平文がデータ表示領域１２０３に表示されてもよい。復号結果保存ボタン１２０５は、復号結果を、記憶部２２０に格納するための選択ボタンである。図１０、図１１の操作画面は一例であり、画面構成、選択ボタン等の操作順序、及び画面推移などはこの限りでない。

（実施例１のまとめ）
本実施例の大小判定可能暗号システムにおいて、ユーザ端末３００が数値セルを含む暗号化データを大小判定サーバ２００に送信する。さらに大小判定サーバ２００は、暗号化データを暗号化したままの状態で、数値の大小判定を実行する。さらに、大小判定サーバ２００は、大小判定結果を用いたソートを実行する。

大小判定サーバ２００は、大小判定結果又はソート後の暗号化データを、ユーザ端末３００に送信する。ユーザ端末３００は、大小判定サーバ２００から受信したソート後の暗号化データを復号する。

なお、大小判定サーバ２００は、大小判定用の秘密鍵を用いて大小判定を実施するが、当該秘密鍵を持たないものは大小判定ができない。従って、暗号文漏えいした場合であっても、大小判定用の秘密鍵が漏えいしなければ、第三者に大小比較を実施されることはなく、情報漏えいは最小限に抑えられると考えられる。また、大小判定用の秘密鍵だけを用いて、暗号化データを復号することはできない。

また、本実施例によれば大小判定用タグの長さは平文の最大ビット長に依存するが、大小判定用タグ生成対象の平文の総数に比例することは無く、大小判定用タグの長さが短く抑えられる。

なお、大小判定用タグ生成に用いられる暗号方式は、他の暗号方式であってもよい。但し、当該他の暗号方式において平文空間が剰余演算を有し、かつ当該他の暗号方式は、加法的準同型性を有する。さらに当該他の暗号方式において、秘密鍵を有するものだけが、秘密鍵と２つの大小判定用タグとから生成された値の、所定のシステムパラメータに関する離散対数を算出できる可能性があるものとする。

本実施例の大小判定可能暗号システムは、さらに閾値判定処理を実行可能である。図１２は、閾値判定処理の一例を示すフローチャートである。図４の処理が既に終了しているものとする。即ち、実施例１の暗号方式で暗号化された暗号化データを大小判定サーバ２００が保持している。また、全体処理部３１１が、閾値判定対象の閾値ｍを取得し、大小判定用タグ生成部３１４に出力しているものとする。閾値ｍは、例えば、入力部２０１を介してユーザによって指定される。

大小判定用タグ生成部３１４は、は閾値ｍに対して、例えば、図７と同様の処理により、大小判定用タグＤを生成する（Ｓ１００１）。全体処理部３１１は、大小判定用タグＤを含む閾値判定依頼を生成し、大小判定サーバ２００に送信する（Ｓ１００２）。また、閾値判定依頼は、暗号化データの指定されたカラムを含み、大小判定用タグＤに対応する値である閾値ｍより大きい数値セル、を大小判定サーバ２００に抽出させて返送させるための依頼を含む。なお、当該カラムは、例えば、入力部２０１を介してユーザによって指定される。

大小判定部２１２は、大小判定用タグＤと、暗号化データの大小判定用タグそれぞれと、を用いて、閾値ｍと、暗号化データの各数値セルの値と、の大小判定処理を行う（Ｓ１０００３）。大小判定処理は、図９の処理と同様である。

全体処理部３１１は、大小判定処理において、閾値ｍより大きいと判断された数値セルを選択し（Ｓ１００４）、当該数値セル又は当該数値セルを含むレコードを、暗号化したままユーザ端末３００に送信する（Ｓ１００５）。

復号化処理部３１３は大小判定サーバ２００から受信した暗号化データの暗号文部分を、復号化鍵記憶部３３２に格納された復号化鍵を用いて復号する（Ｓ１００６）。

なお、図１２では、大小判定サーバ２００が閾値ｍより大きい数値を検索する例を説明したが、例えば、閾値ｍより小さい数値を検索してもよいし、二つの閾値の間に含まれる数値を検索（範囲検索）してもよい。

なお、本発明は上記した実施例に限定されるものではなく、様々な変形例が含まれる。例えば、上記した実施例は本発明を分かりやすく説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、ある実施例の構成の一部を他の実施例の構成に置き換えることも可能であり、また、ある実施例の構成に他の実施例の構成を加えることも可能である。また、各実施例の構成の一部について、他の構成の追加・削除・置換をすることが可能である。

また、上記の各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。また、上記の各構成、機能等は、プロセッサがそれぞれの機能を実現するプログラムを解釈し、実行することによりソフトウェアで実現してもよい。各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリや、ハードディスク、ＳＳＤ（Ｓｏｌｉｄ Ｓｔａｔｅ Ｄｒｉｖｅ）等の記録装置、または、ＩＣカード、ＳＤカード、ＤＶＤ等の記録媒体に置くことができる。

また、制御線や情報線は説明上必要と考えられるものを示しており、製品上必ずしも全ての制御線や情報線を示しているとは限らない。実際には殆ど全ての構成が相互に接続されていると考えてもよい。

２００ 大小判定サーバ、２１０ 制御部、２１１ 全体処理部、２１２ 大小判定部、２３０ データ記憶部、２３１ 暗号化データ記憶部、２３２ 大小判定用パラメータ記憶部、２４０ 一時情報記憶部、３００ ユーザ端末、３１０ 制御部、３１１ 全体処理部、３１２ 暗号化処理部、３１３ 復号化処理部、３１４ 大小判定用タグ生成部、３３０ データ記憶部、３３１ 暗号化鍵記憶部、３３２ 復号化鍵記憶部、３３３ タグ生成用パラメータ記憶部、３３４ 暗号化対象データ記憶部、３４０ 一時情報記憶部

Claims (11)

1. 大小判定サーバであって、
   プロセッサとメモリとを備え、
   前記メモリは、第１秘密鍵と、複数の数値それぞれに対応する大小判定用タグと、を保持し、
   前記大小判定用タグそれぞれは、前記複数の数値それぞれが、加法的準同型性を有する暗号方式で、前記第１秘密鍵を含む複数の秘密鍵と、第１パラメータと、を用いて暗号化された暗号文であり、
   前記暗号方式において、平文空間が自然数を法とした剰余演算を有し、
   前記プロセッサは、
   大小判定処理において、
   前記第１秘密鍵と２つの前記大小判定用タグから、前記加法的準同型性を用いて、前記２つの大小判定用タグに対応する数値の大小判定のための値を生成し、
   前記生成した値の前記第１パラメータに関する離散対数が所定範囲の値において算出可能であるか否かに基づいて、前記２つの大小判定用タグに対応する数値の大小を判定する、大小判定サーバ。
2. 請求項１に記載の大小判定サーバであって、
   前記大小判定用タグの個数以下である任意の自然数ｉに対して、ｉ番目の大小判定用タグＣｉは、Ｃｉ＝（Ｃｉ（１），Ｃｉ（２），Ｃｉ（３），Ｃｉ（４））で表され、
   Ｃｉ（１）＝ｇ^δｉｘ，Ｃｉ（２）＝ｇ^λｉｘ^−１，Ｃｉ（３）＝ｈ^δｉｕ^{Ｒｍｉ＋αｉ}，Ｃｉ（４）＝ｈ^λｉｕ^{−Ｒｍｉ−βｉ}であり、
   ｇ及びｕは、有限巡回群であるＧの異なる生成元であり、
   ｕは、前記第１パラメータであり、
   ｘはＧの元であり、
   所定のアルゴリズムを用いて、所定の計算回数で、Ｇにおける離散対数問題が解ける確率は、所定値以下であり、
   ｈは前記秘密鍵であるｓに対して、ｈ＝ｇ^Ｓであり、
   δi及びλiは、Ｇの位数より小さい正整数であり、
   αi及びβiは、ＲＴ＜Ｕを満たす３以上の自然数Ｒに対して、０＜αi＜Ｒ／２＜βi＜Ｒを満たす整数であり、
   Ｔは、前記複数の数値の上限であり、
   Ｕは、所定のアルゴリズムを用いて、所定の計算回数で、Ｇにおけるｕに関する離散対数問題の解がＵ以下の範囲であれば、当該離散対数問題が解けるよう定められている、大小判定サーバ。
3. 請求項２に記載の大小判定サーバであって、
   前記メモリは、
   Ｇ、ｇ、ｕ、Ｕを特定する情報を保持し、
   前記プロセッサは、
   前記２つの大小判定用タグＣｉ＝（Ｃｉ（１），Ｃｉ（２），Ｃｉ（３），Ｃｉ（４））と、Ｃｊ＝（Ｃｊ（１），Ｃｊ（２），Ｃｊ（３），Ｃｊ（４））と、に対して、前記加法的準同型性を用いて、Ｘ＝Ｃｉ（１）Ｃｊ（２）＝ｇ^{δｉ＋λｊ}と、Ｙ＝Ｃｉ（３）Ｃｊ（４）＝ｈ^{δｉ＋λｊ}ｕ^{Ｒ（ｍｉ−ｍｊ）＋（αｉ−βｊ）}と、を算出し、
   Ｘ^ｓ＝ｇ^{ｓ（δｉ＋λｊ）}＝ｈ^{δｉ＋λｊ}を算出し、
   前記大小判定のための値として、Ｚ＝Ｙ／Ｘ^Ｓ＝ｕ^{Ｒ（ｍｉ−ｍｊ）＋（αｉ−βｊ）}を算出し、
   Ｚのｕに関する離散対数をＵ以下の範囲で算出可能であると判定した場合、Ｃｉに対応する数値が、Ｃｊに対応する数値より大きいと判定し、
   Ｚのｕに関する離散対数をＵ以下の範囲で算出不可能であると判定した場合、Ｃｉに対応する数値が、Ｃｊに対応する数値以下であると判定する、大小判定サーバ。
4. 請求項１に記載の大小判定サーバであって、
   前記メモリは、
   前記秘密鍵で復号不可能な暗号方式で暗号化された前記複数の数値それぞれを、前記大小判定用タグと対応付けて保持し、
   前記プロセッサは、
   前記複数の大小判定用タグに含まれる大小判定用タグの組み合わせそれぞれについて前記大小判定処理を実行し、
   当該大小判定処理の結果に基づいて、前記暗号化された複数の数値をソートする、大小判定サーバ。
5. 請求項１に記載の大小判定サーバであって、
   前記メモリは、閾値に対応する大小判定用タグ、を保持し、
   前記閾値に対応する大小判定用タグそれぞれは、前記閾値が、前記暗号方式で、前記秘密鍵と前記第１パラメータとを用いて暗号化された暗号文であり、
   前記メモリは、前記複数の数値それぞれが前記秘密鍵と異なる秘密鍵で暗号化された暗号化数値を、前記大小判定用タグと対応付けて保持し、
   前記プロセッサは、
   前記閾値に対応する前記大小判定用タグと、前記複数の大小判定用タグそれぞれと、について前記大小判定処理を実行し、
   当該大小判定処理の結果に基づいて、前記暗号化数値の前記閾値に対する閾値処理を実行する、大小判定サーバ。
6. 暗号化端末と、大小判定サーバと、を含む大小判定暗号化システムであって、
   前記暗号化端末は、
   複数の数値と、第１秘密鍵を含む複数の秘密鍵と、第１パラメータと、を保持し、
   加法的準同型性を有する暗号方式で、前記複数の秘密鍵と前記第１パラメータとを用いて、複数の数値それぞれを暗号化して、前記複数の数値それぞれに対応する大小判定用タグを生成し、
   前記暗号方式において、平文空間が自然数を法とした剰余演算を有し、
   前記暗号化端末は、前記大小判定用タグを前記大小判定サーバに送信し、
   前記大小判定サーバは、
   前記第１秘密鍵を保持し、
   大小判定処理において、
   前記第１秘密鍵と２つの前記大小判定用タグから、前記加法的準同型性を用いて、前記２つの大小判定用タグに対応する数値の大小判定のための値を生成し、
   前記生成した値の前記第１パラメータに関する離散対数が所定範囲の値において算出可能であるか否かに基づいて、前記２つの大小判定用タグに対応する数値の大小を判定する、大小判定暗号化システム。
7. 請求項６に記載の大小判定暗号化システムであって、
   前記暗号化端末は、
   有限巡回群であるＧの異なる生成元であるｇ及びｕを選択し、
   Ｇの元であるｘを選択し、
   前記第１秘密鍵であるｓに対して、ｈ＝ｇ^Ｓを算出し、
   Ｇの位数より小さい正整数であるδi及びλiを選択し、
   ＲＴ＜Ｕを満たす３以上の自然数Ｒに対して、０＜αi＜Ｒ／２＜βi＜Ｒを満たす整数αi及びβiを選択し、
   ｕは前記第１パラメータであり、
   所定のアルゴリズムを用いて、所定の計算回数で、Ｇにおける離散対数問題が解ける確率は、所定値以下であり、
   Ｔは、前記複数の数値の上限であり、
   Ｕは、所定のアルゴリズムを用いて、所定の計算回数で、Ｇにおけるｕに関する離散対数問題の解がＵ以下の範囲であれば、当該離散対数問題が解けるよう定められる、
   前記暗号化端末は、
   前記複数の数値の個数以下である任意の自然数ｉに対して、ｉ番目の前記数値に対応する大小判定用タグＣｉ＝（Ｃｉ（１），Ｃｉ（２），Ｃｉ（３），Ｃｉ（４））を算出し、
   Ｃｉ（１）＝ｇ^δｉｘ，Ｃｉ（２）＝ｇ^λｉｘ^−１，Ｃｉ（３）＝ｈ^δｉｕ^{Ｒｍｉ＋αｉ}，Ｃｉ（４）＝ｈ^λｉｕ^{−Ｒｍｉ−βｉ}である、大小判定暗号化システム。
8. 請求項７に記載の大小判定暗号化システムであって、
   前記大小判定サーバは、
   Ｇ、ｇ、ｕ、Ｕを特定する情報を保持し、
   前記２つの大小判定用タグＣｉ＝（Ｃｉ（１），Ｃｉ（２），Ｃｉ（３），Ｃｉ（４））と、Ｃｊ＝（Ｃｊ（１），Ｃｊ（２），Ｃｊ（３），Ｃｊ（４））と、に対して、前記加法的準同型性を用いて、Ｘ＝Ｃｉ（１）Ｃｊ（２）＝ｇ^{δｉ＋λｊ}と、Ｙ＝Ｃｉ（３）Ｃｊ（４）＝ｈ^{δｉ＋λｊ}ｕ^{Ｒ（ｍｉ−ｍｊ）＋（αｉ−βｊ）}と、を算出し、
   Ｘ^ｓ＝ｇ^{ｓ（δｉ＋λｊ）}＝ｈ^{δｉ＋λｊ}を算出し、
   前記大小判定のための値として、Ｚ＝Ｙ／Ｘ^Ｓ＝ｕ^{Ｒ（ｍｉ−ｍｊ）＋（αｉ−βｊ）}を算出し、
   Ｚのｕに関する離散対数をＵ以下の範囲で算出可能であると判定した場合、Ｃｉに対応する数値が、Ｃｊに対応する数値より大きいと判定し、
   Ｚのｕに関する離散対数をＵ以下の範囲で算出不可能であると判定した場合、Ｃｉに対応する数値が、Ｃｊに対応する数値以下であると判定する、大小判定暗号化システム。
9. 請求項６に記載の大小判定暗号化システムであって、
   前記暗号化端末は、
   前記第１秘密鍵と異なる秘密鍵を用いて前記複数の数値それぞれを暗号化した、暗号化数値を生成し、
   前記暗号化数値それぞれと、前記複数の大小判定用タグそれぞれと、を対応付けて、前記大小判定サーバに送信し、
   前記大小判定サーバは、
   前記複数の大小判定用タグに含まれる大小判定用タグの組み合わせそれぞれについて前記大小判定処理を実行し、
   当該大小判定処理の結果に基づいて、前記暗号化数値をソートし、
   ソート後の前記暗号化数値を、前記暗号化端末に送信する、大小判定暗号化システム。
10. 請求項６に記載の大小判定暗号化システムであって、
    前記暗号化端末は、
    閾値を、前記暗号方式で、前記秘密鍵と前記第１パラメータとを用いて暗号化して、前記閾値に対応する大小判定用タグを生成し、
    前記閾値に対応する大小判定用タグを前記大小判定サーバに送信し、
    前記第１秘密鍵と異なる秘密鍵を用いて前記複数の数値それぞれを暗号化した、暗号化数値を生成し、
    前記暗号化数値それぞれと、前記複数の大小判定用タグそれぞれと、を対応付けて、前記大小判定サーバに送信し、
    前記大小判定サーバは、
    前記閾値に対応する前記大小判定用タグと、前記複数の大小判定用タグそれぞれと、について前記大小判定処理を実行し、
    当該大小判定処理の結果に基づいて、前記暗号化数値の前記閾値に対する閾値処理を実行し、
    前記閾値処理の結果を、前記暗号化端末に送信する、大小判定暗号化システム。
11. 大小判定サーバによる大小判定方法であって、
    前記大小判定サーバは、プロセッサとメモリとを備え、
    前記メモリは、第１秘密鍵と、複数の数値それぞれに対応する大小判定用タグと、を保持し、
    前記大小判定用タグそれぞれは、前記複数の数値それぞれが、加法的準同型性を有する暗号方式で、前記第１秘密鍵を含む複数の秘密鍵と、第１パラメータと、を用いて暗号化された暗号文であり、
    前記暗号方式において、平文空間が自然数を法とした剰余演算を有し、
    前記大小判定方法は、
    前記プロセッサが、前記第１秘密鍵と２つの前記大小判定用タグから、前記加法的準同型性を用いて、前記２つの大小判定用タグに対応する数値の大小判定のための値を生成し、
    前記プロセッサが、前記生成した値の前記第１パラメータに関する離散対数が所定範囲の値において算出可能であるか否かに基づいて、前記２つの大小判定用タグに対応する数値の大小を判定する、ことを含む大小判定方法。

Images