(57)【要約】【課題】数値データの保持者２者が互いの値を明かさず互いの値が近いかどうかを知るための秘匿比較技術に関し、互いの値を明かさず、互いの値の比較結果を、互いに知ることを可能にする。【解決手段】計算機100（A,B）の要素分解部102（A,B）は、比較対象の第１の数値および第２の数値をそれぞれ、互いの数値を共通要素数により比較判定可能な要素の第１の集合および第２の集合に変換する。計算機100（A,B）の暗号化部１０３（A,B）および計算機100(S)の共通要素数計上部109等は、第１の集合および第２の集合の共通要素数を秘匿計算で算出する。計算機100（A,B）の比較結果算出部104（A,B）は、上記共通要素数を比較結果に変換して出力する。【選択図】図１
2015108682.tif 000002
【特許請求の範囲】
【請求項１】
比較対象の第１の数値および第２の数値をそれぞれ、互いの数値を共通要素数により比較判定可能な要素の第１の集合および第２の集合に変換し、
前記第１の集合および前記第２の集合の共通要素数を秘匿計算で算出し、
算出した前記第１の集合および前記第２の集合の共通要素数を比較し、比較結果を出力する、
処理を含むことを特徴とする秘匿比較方法。
【請求項２】
前記第１の数値は第１の利用者が操作するコンピュータから入力し、前記第２の数値は第２の利用者が操作するコンピュータから入力し、前記共通要素数の算出は前記第１の利用者および前記第２の利用者以外の第三者が管理するコンピュータで行う、
処理を含むことを特徴とする請求項１に記載の秘匿比較方法。
【請求項３】
前記第１の数値および前記第２の数値からそれぞれ前記第１の集合および前記第２の集合への変換は、
前記第１の数値および前記第２の数値をそれぞれ第１の非負整数および第２の非負整数へ変換し、
前記第１の非負整数および前記第２の非負整数のそれぞれの２進数表現の長さのうちの長いほうの値をbビットとしたときに、前記第１の非負整数および前記第２の非負整数をそれぞれ、b次の第１の接頭辞配列および第２の接頭辞配列に分解して前記第１の集合および第２の集合とする、
処理を含むことを特徴とする請求項１または２のいずれかに記載の秘匿比較方法。
【請求項４】
前記第１の接頭辞配列または前記第２の接頭辞配列が、奇数の場合には１を加算し、偶数の場合には１を減算し、前記加算または前記減算の結果を前記第１の接頭辞配列または前記第２の接頭辞配列として出力する、
処理を含むことを特徴とする請求項３に記載の秘匿比較方法。
【請求項５】
前記加算または前記減算の結果がアンダーフローあるいはオーバーフローを起こしたときに、前記加算または前記減算の結果に対して単射であるようにパディングを行い、該パディングの結果を前記第１の接頭辞配列または前記第２の接頭辞配列として出力する、
処理を含むことを特徴とする請求項４に記載の秘匿比較方法。
【請求項６】
前記共通要素数から前記比較結果への変換は、前記第１の非負整数または前記第２の非負整数について、前記bビットが前記共通要素数に等しくなければ、値０から前記第１の非負整数または前記第２の非負整数までの第１の範囲と、前記第１の非負整数または前記第２の非負整数から２のb乗までの第２の範囲のそれぞれで、２分検索により、共通要素数が前記共通要素数となる値の各範囲を計算し、当該各範囲を前記比較結果として出力し、前記bビットが前記共通要素数に等しければ前記第１の非負整数または前記第２の非負整数を前記比較結果として出力する近さ判定を行う、
処理を含むことを特徴とする請求項３ないし６のいずれかに記載の秘匿比較方法。
【請求項７】
前記共通要素数から前記比較結果への変換は、
値０以上前記第１の集合または前記第２の集合の要素数未満の各整数値をランダムに並べた第１のリストまたは第２のリストについて、当該第１のリストまたは第２のリストの各要素を、当該要素の値が当該リストの長さの半分の値未満なら値１で、そうでなければ値０で、それぞれ置き換えた第１の修正リストまたは第２の修正リストをそれぞれ作成し、
前記第１の集合および前記第２の集合の各要素のうち、それぞれ前記第１の修正リストおよび前記第２の修正リストの要素が値１である位置の要素を抽出し、当該抽出した要素のうち共通のものの数を第２の共通要素数として秘匿計算で算出し、
前記第１の非負整数または前記第２の非負整数について、前記bビットが前記第２の共通要素数に等しくなければ、前記第１の非負整数または前記第２の非負整数を２進数表現に変換し当該２進数表現の前記第２の共通要素数に値１をプラスした値に対応するビット位置の値が１であれば、前記第１の非負整数または前記第２の非負整数が前記第２の非負整数または前記第１の非負整数よりも大きいことを示す大小比較結果を出力し、そうでなければ前記第１の非負整数または前記第２の非負整数が前記第２の非負整数または前記第１の非負整数よりも小さいことを示す大小比較結果を出力し、前記bビットが前記第２の共通要素数に等しければ前記第１の非負整数と前記第２の非負整数が等しいことを示す大小比較結果を出力する大小判定を行う、
処理を含むことを特徴とする請求項３ないし６のいずれかに記載の秘匿比較方法。
【請求項８】
請求項７に記載の近さ判定の処理と請求項８に記載の大小判定の処理とから、前記比較結果を出力する、
処理を含むことを特徴とする請求項６および７に記載の秘匿比較方法。
【請求項９】
比較対象の第１の数値および第２の数値をそれぞれ、互いの数値を共通要素数により比較判定可能な要素の第１の集合および第２の集合に変換する手段と、
前記第１の集合および前記第２の集合の共通要素数を秘匿計算で算出する手段と、
前記共通要素数を比較結果に変換して出力する手段と、
を備えることを特徴とする秘匿比較システム。
【請求項１０】
比較対象の第１の数値および第２の数値をそれぞれ、互いの数値を共通要素数により比較判定可能な要素の第１の集合および第２の集合に変換し、
前記第１の集合および前記第２の集合の共通要素数を秘匿計算で算出し、
前記共通要素数を比較結果に変換して出力する、
ステップをコンピュータに実行させるための秘匿比較プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘匿比較方法、プログラム、およびシステムに関する。
【背景技術】
【０００２】
数値データ保持者２者が、互いの値を明かさず、互いの値が近いかどうか知りたい場合がある。
【０００３】
たとえば、競合他社同士のＡ社とＢ社が、どちらもC社の製品やサービスを利用している場合、その利用価格が同程度か両者共に知りたい、ただし同程度でないときは互いの利用価格は教えたくない、という場合を考える。
【０００４】
以降ではそれぞれの数値を rA, rB とする。たとえば、Ａ社の利用価格が50,000円なら、rA=50000 となる。
【０００５】
両社は競合他社同士なので、自社が正しい答えが得られる限り、他社にはできるだけ自社情報を提供したくないとする。よって、たとえばＡ社がＢ社にrAを教え、Ｂ社がＡ社にrAとrBが同程度か教える、といった単純な方法は成り立たない。なぜなら、Ｂ社はＡ社に本当の情報を教える動機がなく、でたらめな情報を教える方がrBについての情報を漏らさずに済むからである。また、rAとrBが同程度でないとしても、rAの正確な値がＢ社に伝わってしまうのも問題である。
【０００６】
従来から、クライアントは自身の入力を漏らさず、サーバは自身の関数を漏らさず、クライアントが入力に対する関数出力を取得できる、SFE（Secure Function Evaluation、秘匿関数評価）という方法がある（例えば非特許文献１）。
【０００７】
このSFEを使うと、Ｂ社が、入力がrBと同程度であるか判定する関数を用意することで、Ａ社は自社の情報を知らせずにrAとrBが同程度か知ることができる、というシステムを構築することができる。たとえば、Ｂ社が関数 f(x) = (rB-d < x < rB+d) （d=10,000 など）を用意してサーバとなり、Ａ社がクライアントとなれば、Ａ社はrAをＢ社に知らせずに、Ｂ社は f(x) をＡ社に知らせずに、Ａ社が f(rA) （つまり、rA が rB±d 以内か）を得られるようにすることができる。
【０００８】
しかし、この方法では、Ｂ社が何も情報を得られないという問題がある。Ａ社は既に正しい答えを得ており、Ｂ社に正しい結果を教えてあげる動機がない。
【０００９】
他に、関数を限定することで準同型暗号を使い計算を高速化する技術などはあるが、この問題の解決はされていない（例えば特許文献１）。
【００１０】
また、他者と結託をしないことを前提とした第三者を介すことで、２者の値が同程度か判定する方法がある（例えば特許文献２）。
【００１１】
この方法では２者が乱数を共有し、それを使って暗号化することで、第三者には値がわからないようにする。この暗号化は準同型性を有するものを使い、第三者は暗号化されたまま元の値が一致しているか判定できるようにする。
【００１２】
しかし、その第三者が一方と結託として乱数を知ることで、もう一方の値を（総当たりにより）知ることができてしまう。たとえば、Ａ社が第三者と結託することでrBを知る事ができ正しい情報を得ることができるので、Ａ社はＢ社のために正しいrAを使う動機がなくなり、Ｂ社だけが正しい情報を得られなくなる。
【００１３】
これらのように、準同型暗号は暗号化されたまま計算ができるが、２者のうち秘密鍵（復号鍵）を（必要なら結託をして）入手できる者が一方的に有利になってしまうという問題がある。
【００１４】
一方、互いに自身の秘密鍵で暗号化する上、暗号化されたまま一致判定をできるようにする方法がある（例えば非特許文献２）。
【００１５】
この方法は、互いの集合を明かさず、互いの集合の共通要素の数を互いに得るために有用である。まず、ステップ１として、互いに秘密鍵を用意し、自身の集合の各要素を暗号化して相手に送信する。ここで、暗号化は可換鍵付ハッシュ関数により行う。たとえば h(k, m) = mk mod p （k は鍵、m は要素の値、p は両者で予め共有した適当な自然数）という関数である。ステップ２として、受信した各要素を同様に暗号化し、（要素順序をランダムにして）送信する。ステップ３として、受信した集合と、ステップ２で暗号化した後の集合の、共通要素数を計算する。これにより、自身の秘密鍵を知らない任意の者から自身のデータを秘密にしつつ、相手の集合との共通要素数を計算できる。
【００１６】
しかし、この方法は互いの集合の共通要素の数を知ることしかできず、互いの数値が同程度かを知ることはできない。また、ステップ２で正しい値を送信する動機がない（でたらめな値を送っても、自分は正しい情報を得られる）という問題がある。
【００１７】
以上のように、従来技術では、数値データ保持者２者が、結託されても自身の値が知られないようにしながら、互いの値が近いかどうか知ることはできなかった。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開２０１１−１１４３９２号公報
【特許文献２】特開２０１０−２３７６５３号公報
【非特許文献】
【００１９】
【非特許文献１】Andrew C. Yao. Protocols for Secure Computations. Proceedings of 23rd Annual Symposium on Foundations of Computer Science (FOCS 1982), IEEE Computer Society, pp.160-164, 1982.
【非特許文献２】Rakesh Agrawal, Alexandre Evfimievski, and Ramakrishnan Srikant. Information Sharing Across Private Databases. Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pp.86-97, 2003.
【発明の概要】
【発明が解決しようとする課題】
【００２０】
そこで、本発明の１つの側面では、互いの値を明かさず、互いの値の比較結果を、互いに取得することを可能にすることを目的とする。
【課題を解決するための手段】
【００２１】
態様の一例では、比較対象の第１の数値および第２の数値をそれぞれ、互いの数値を共通要素数により比較判定可能な要素の第１の集合および第２の集合に変換し、第１の集合および第２の集合の共通要素数を秘匿計算で算出し、算出した第１の集合および第２の集合の共通要素数を比較し、比較結果を出力する、処理を含む。
【発明の効果】
【００２２】
互いの値を明かさず、互いの値の比較結果を取得することが可能となる。
【図面の簡単な説明】
【００２３】
【図１】本実施形態の構成例を示す図である。
【図２】要素分解部が実行する非負整数の分解の処理例を示すフローチャートである。
【図３】暗号化部が実行する暗号化およびシャッフルの処理例を示すフローチャートである。
【図４】比較結果算出部が実行する比較結果算出の処理例を示すフローチャートである。
【図５】比較結果算出部が実行するリストＭの変換の処理例を示すフローチャートである。
【図６】比較結果算出部が実行する大小判定の処理例を示すフローチャートである。
【図７】本実施形態における３つのコンピュータ間の処理関係の例を示すシーケンス図である。
【図８】本実施形態のシステムを実現可能なハードウェアシステムの構成図である。
【発明を実施するための形態】
【００２４】
以下、本発明を実施するための形態について図面を参照しながら詳細に説明する。
本発明の実施形態は、数値データ保持者２者が、それぞれ自身の数値を共通要素数により比較判定可能な集合に変換し、共通要素数を秘匿計算で算出し、それぞれがその結果を変換して比較結果を得る方式である。
【００２５】
本発明の実施形態として、ソフトウェアで実現したものについて説明する。
【００２６】
本実施形態への入力は、次の通りである。
・数値rx
・暗号鍵kx
・共有の変換方法 f(r)
・共有のビット長b
・共有の暗号化方法 h(k, m)
【００２７】
rxはＡ社およびＢ社が保持するそれぞれの秘密の数値である。xはAかBで、それぞれＡ社とＢ社のデータであることをあらわす。たとえば、rAはＡ社の保持する数値である。
【００２８】
kxはそれぞれの秘密の暗号鍵である。たとえば、kAはＡ社のみが知る暗号鍵である。
f(r)はＡ社とＢ社で共有の、実数から非負整数への変換方法である。
【００２９】
b は共有のビット長である。
h(k, m) は共有の暗号化方法であり、可換鍵付ハッシュ関数である。
【００３０】
本実施形態の出力は、次の通りである。
・相手の数値の範囲 Rx。
【００３１】
Ａ社は、Ｂ社の数値の範囲RBを知ることができる。同様に、Ｂ社はRAを知ることができる。また、お互いの数値が近いほどRの範囲が狭くなる。
【００３２】
図１は、本実施形態に係る秘匿比較システムの構成例を示す図である。
Ａ社のデータを保持している計算機を100(A)とし、Ｂ社のデータを保持している計算機を100(B)とする。
【００３３】
以降では、例として rA=50000, rB=30000 を用いて説明する。
まず、適当な時期に、変換方法f(r)とビット長 b そして暗号化方法 h(k, m) を、計算機100(A)と100(B)の間で何らかの手段で予め決め、共有しておく。たとえば、Ａ社とＢ社の社員同士が話し合って決める。また、計算機100(S)が両社員にコミュニケーション支援サービスを提供しても良い。
【００３４】
変換方法f(r)には、たとえば次の式を使う。
nx=f(rx)=floor(srx+t)
ここで、floor(x) は床関数である。
例として、s=1/10000, t=0 とする。このとき、nA=5, nB=3 となる。
【００３５】
また、len(x) を非負整数の２進数表現の長さを返す関数とすると、b≧max(len(nA), len(nB)) が必要である。よって、本例では、b≧max(len(5), len(3))=max(len(1012), len(112))=max(3, 2)=3 である。
【００３６】
また、例として、b=4 、h(k, m)=mkmod p （p は非特許文献２に記載されているような適当な自然数）とする。
【００３７】
計算機100(A)または計算機100(B)は、記憶部101(A)または101(B)、要素分解部102(A)または102(B)、暗号化部103(A)または103(B)、比較結果算出部104(A)または104(B)、および通信部105(A)または105(B)を備える。
【００３８】
計算機100(S)は、記憶部106、データ転送部107、集合受付部108、共通要素数計上部109、結果出力部110、および通信部105(S)を備える。
【００３９】
記憶部101(A)、102(B)、および106は、本実施形態で使用される入力値、途中経過値、出力値等を記憶する。また、図２〜図６のフローチャートで示される各処理の制御プログラムを記憶する。
その他の部分については、以下の説明で詳述する。
【００４０】
以上の構成を有する本実施形態の詳細な動作について、以下に説明する。
【００４１】
本実施形態に係る図１の秘匿比較システムは、次のような処理を実施する。計算機100(A)、100(B)という別の場所の２つの整数値を、ｎ次接頭辞配列（上位ビットから1ビットずつシフトして分解した配列）に分解してできる各列を、奇数か偶数かにより1を加算、また減算した配列を作成し、得られた2つの配列をそれぞれ暗号化する。そして、第三者である計算機100(S)が暗号化した配列同士を比較することにより整数の一致度である共通要素数を計算する。計算機100(A)、100(B)は、この共通要素数を受け取ることにより、比較結果に変換して出力する。
【００４２】
要素分解部102(A)および102(B)は、入力 rx を要素へ分解する。より詳細には、非負整数nxへの変換と、要素への分解をおこなう。
【００４３】
非負整数nxへの変換は上記の通り、rxにf(r)を適用することでおこなう。
続いて、計算機100(A)と計算機100(B)それぞれで、非負整数nxを、bを使って同じ方法により分解する。
【００４４】
図２は、図１の要素分解部102（102(A)または102(B))が実行する、分解の処理例を示すフローチャートである。各ステップについて計算機100(B)での処理例を説明する。
【００４５】
n=nB=3、b=4 を入力として受け入れる（図２のステップS1）。
nの、長さｂの２進数表現の、接頭辞配列を格納したリストLを作成する（図２のステップS2）。接頭辞配列とは、文字列についての、先頭文字を含む全ての部分文字列であり、上位ビットから１ビットずつシフトして分解した配列をいう。n=3=00112 であるため、L=[0011, 001, 00, 0]となる。
【００４６】
i=0 を用意する（図２のステップS3）。
i<b か否かを判定する（図２のステップS4）。
いま、b=4 であり i<b なので、図２のステップS4の判定がYESとなって、ステップS5に制御を移す。
【００４７】
iを1増やし、i=1 となる（図２のステップS5）。
Lのi番目の要素をコピーし、e=0011 となる（図２のステップS6）。
【００４８】
eの最下位ビットが0か否かを判定する（図２のステップS7）。
いま、eの最下位ビットは1でステップS7の判定はNOであるため、図２のステップS12に制御を移す。
【００４９】
eを1増やし、e=0100 となる（図２のステップS12）。なお、このとき、文字列長を保持したまま計算する。
【００５０】
eの全ビットが0か否かを判定する（図２のステップS13）。
いま、eには1のビットが含まれステップS13の判定はNOであるため、ステップS11に制御を移す。
【００５１】
eをLの末尾に追加する（図２のステップS11）。結果、L=[0011, 001, 00, 0, 0100]となる。その後、図２のステップS4に制御を移す。
【００５２】
i=1, b=4 であり i<b で図２のステップS4の判定はYESなので、ステップS5に制御を移す。同様にステップS14まで繰り返し、i=2の状態になる。このとき、L=[0011, 001, 00, 0, 0100, 010] である。本ステップに再度戻ったときには i=2, b=4 であり i<b でステップS4の判定はYESなので、ステップS5に制御を移す。
【００５３】
iを1増やし、i=3 となる（図２のステップS5）。
Lのi番目の要素をコピーし、e=00 となる（図２のステップS6）。
【００５４】
eの最下位ビットは0なので図２のステップS7の判定はYESとなり、ステップS8に制御を移す。
【００５５】
eを1減らし、e=11 となる（図２のステップS8）。なお、このとき、文字列長を保持したまま計算する。これは、アンダーフローを起こした結果である。
【００５６】
Eの全ビットが1であるか否かを判定する（図２のステップS9）。
いま、eの全ビットが1なのでステップS9の判定はYESとなり、図２のステップS10に制御を移す。
【００５７】
eにパディングをし、e=00111 となる（図２のステップS10）。パディングは、本実施形態では、まず先頭に1を追加し、さらに全体長がb+1になるまで0を追加する、という方式を使用する。一般的には、パディングされたか判別でき、単射な方式ならどのようなものでも良い。本実施形態の方式は、全体長がb+1の場合のみパディングされていることがわかり、その場合ははじめの1までがパディングなので単射である。
【００５８】
eをLの末尾に追加する（図２のステップS11）。その結果、L=[0011, 001, 00, 0, 0100, 010, 00111]となる。その後、図２のステップS4に制御を移す。
【００５９】
i=3, b=4 であり i<b なのでステップS4の判定はYESとなり、ステップS5に制御を移す。同様にステップS14まで繰り返し、i=4の状態になる。このとき、L=[0011, 001, 00, 0, 0100, 010, 00111, 00011] である。本ステップに再度戻ったときには i=b=4 なのでステップS4の判定はNOとなり、図２のステップS14に制御を移す。
【００６０】
Lを出力する（図２のステップS14）。つまり、LB=[0011, 001, 00, 0, 0100, 010, 00111, 00011] である。
【００６１】
同様に、計算機100(A)において、nA=5 は、LA=[0101, 010, 01, 0, 0110, 001, 10, 00011] と分解される。
【００６２】
次に、互いの集合を明かさず、互いの集合の共通要素の数を互いに得る方法を使い、LAとLBの共通要素数を互いに得る。
【００６３】
本実施形態では、次のように行う。
まず、Lの各要素を非負整数に変換する。単射であることが必要であり、たとえば、各要素の先頭に"1"を追加して2進数とみなすことで実現できる。
【００６４】
たとえば、LAを変換すると、LA=[101012, 10102, 1012, 102, 101102, 10012, 1102, 1000112]=[21, 10, 5, 2, 22, 9, 6, 35] となる。同様に、LB=[100112, 10012, 1002, 102, 101002, 10102, 1001112, 1000112]=[19, 9, 4, 2, 20, 10, 39, 35] となる。
【００６５】
次に、図１の暗号化部103（103(A)または103(B))で、リストLの各要素を暗号化し、シャッフルして送信する。
【００６６】
図３は、図１の暗号化部１０３（103(A)または103(B)）が実行する、暗号化およびシャッフルの処理例を示すフローチャートである。各ステップについて計算機100(A)での処理を説明する。
【００６７】
鍵k=kA、暗号化方法 h(k, m)、リストL=LAを入力として受け入れる（図３のステップS1）。
【００６８】
Lの各要素を暗号化したリストL'を作成する（図３のステップS2）。よって、LA'=[h(kA, 21), h(kA, 10), h(kA, 5), h(kA, 2), h(kA, 22), h(kA, 9), h(kA, 6), h(kA, 35)] となる。
【００６９】
0以上8（Lの要素数）未満の各整数値をランダムに並べたリストMを作成する（図３のステップS3）。これをM1とする。たとえば、MA1=[2, 6, 7, 0, 3, 1, 4, 5] を作る。
【００７０】
L'[i] に、元の L'[M[i]] を再格納する（図３のステップS4）。ここで、L[i] はLのi+1番目の要素の意味である。つまり、たとえばLA' の最初（1番目）の要素には、LA'[MA1[0]]=LA'[2]=h(kA, 5) が再格納される。全ての要素についてこれが行われ、LA'=[h(kA, 5), h(kA, 6), h(kA, 35), h(kA, 21), h(kA, 2), h(kA, 10), h(kA, 22), h(kA, 9)] となる。
【００７１】
MA1, LA' を出力する（図３のステップS5）。
同様に、計算機100(B)では、たとえば MB1=[1, 6, 4, 2, 0, 3, 7, 5] が作成され、それと LB'=[h(kB, 9), h(kB, 39), h(kB, 20), h(kB, 4), h(kB, 19), h(kB, 2), h(kB, 35), h(kB, 10)] が出力される。
【００７２】
計算機100(A)はLA'を計算機100(B)に、計算機100(B)はLB'を計算機100(A)に、通信部105(A)および105(B)を介して送信する。このとき、直接送信せず、計算機100(S)に仲介してもらい受け渡しても良い。
【００７３】
計算機100(S)が仲介する場合、図１のデータ転送部107がその処理を実行する。データ転送部107は、計算機100(A)からLA'を受信して計算機100(B)に送信し、計算機100(B)からLB'を受信して計算機100(A)に送信する。仲介により、計算機100(A)と計算機100(B)が直接通信できなくても良いという効果がある。
【００７４】
暗号化部103(A)または103(B)は、それぞれさらに、受信したリストLの各要素を暗号化し、シャッフルして計算機100(S)に送信する。処理は図３のフローチャートで示される処理例と同じであるが、計算機100(A)はLB'を入力としてMA2, LB'' を出力し、計算機100(B)はLA'を入力としてMB2, LA'' を出力する。
【００７５】
たとえば、計算機100(A)は MA2=[4, 3, 0, 6, 7, 2, 1, 5] を作成し、それと LB''=[h(kc, 19), h(kc, 4), h(kc, 9), h(kc, 35), h(kc, 10), h(kc, 20), h(kc, 39), h(kc, 2)] を出力する。ここで、h(kc, m)=h(kA, h(kB, m))=h(kB, h(kA, m)) である。また、計算機100(B)はMB2=[6, 2, 7, 1, 3, 4, 0, 5] を作成し、それとLA''=[h(kc, 22), h(kc, 35), h(kc, 9), h(kc, 6), h(kc, 21), h(kc, 2), h(kc, 5), h(kc, 10)] を出力する。
【００７６】
そして、計算機100(A)はLB''を、計算機100(B)はLA''を、それぞれ計算機100(S)へ送信する。
【００７７】
計算機100(S)の集合受付部108は、LA''とLB''を受信する。
計算機100(S)の共通要素数計上部109は、LA''とLB''の共通要素数cを計算する。今回の場合、h(kc, 2), h(kc, 9), h(kc, 10), h(kc, 35) の4要素が共通であるので、c=4となる。
【００７８】
計算機100(S)の結果出力部110は、cを、通信部106を介して、計算機100(A)と計算機100(B)へ送信する。
【００７９】
最終的に、計算機100(A)と計算機100(B)それぞれが、比較結果算出部104(A)および104(B)で、通信部105(A)および105(B)を介して受信したcから、相手の数値の範囲NあるいはRを求める。
【００８０】
図４は、図１の比較結果算出部104（104(A)または104(B)）が実行する比較結果算出の処理例を示すフローチャートである。各ステップについて計算機100(A)の視点で説明する。
【００８１】
nA=5, b=4, c=4 を入力として受け入れる（図４のステップS1）。
c=2bか否かを判定する（図４のステップS2）。
【００８２】
いま、c<2b なのでステップS2の判定はNOとなり、図２のステップS4に制御を移す。なお、c=2b の場合、nA=nB であることが互いにわかり、その場合はステップS2の判定がYESとなって、N=[n] （[n, n] の意味）とされる（図２のステップS3）。
【００８３】
範囲[0, n], [n, 2b) それぞれで、２分探索により、共通要素数がcとなる値の範囲Nを計算する（図２のステップS4）。前述の分解方法により、相手の値が近いほど c は大きくなる。たとえば、範囲[0, nA]について説明すると、その範囲ではnB∈[0, nA] に対してcは狭義の単調増加となる。よって、２分探索により、共通要素数がcとなる値の範囲Nを効率的に計算することができる。たとえば、範囲[0, nA]でのnBの最大値xを求めることを考える。nA=5を分解して作った集合と、範囲[0, nA]の（ほぼ）中点2 を分解して作った集合の共通集合数を計算すると、4(=c) となるため、2≦x であることがわかる。同様に、範囲[2, nA]の（ほぼ）中点3との共通集合数は4(=c) となるため、3≦x であることがわかる。さらに、範囲[3, nA]の中点４との共通集合数は6(>c) となるため、3≦x<4 つまり x=3 であることがわかる。最小値も同様に計算することで、範囲[0, nA]でのnB の取り得る値の範囲は[2, 3]であることが計算できる。範囲[n, 2b)についても同様に計算することで、nA=5, b=4, c=4 の場合 nB の値の範囲NB=[2, 3]∪[7] であることを計算できる。ところで、相手の値が近いほど c は大きくなると説明した通り、実際、たとえばもし共通要素数がより少ない c=2 だった場合、NB=[0, 1]∪[8, 11] とより遠く広い範囲でしかnB を限定できない。
【００８４】
Nを出力する（図２のステップS5）。NB=[2, 3]∪[7]である。
同様に、計算機100(B)の計算により NA=[0, 1]∪[5] となる。
【００８５】
さらに、変換方法f(r)の逆変換を適用することで、rの範囲Rを計算しても良い。
たとえば、rBが整数の場合、NB=[2, 3]∪[7] ⇔ RB=[20000, 39999]∪[70000, 79999] となる。つまり、Ａ社にとって、Ｂ社の利用価格はＡ社の利用価格である50,000円に比べ、20〜60%異なる値だと知ることができる。同様に、Ｂ社にとっては、Ａ社の価格は33〜100%異なる値だと知ることができる。
【００８６】
以上の方法により、数値データ保持者２者が、互いの値を明かさず、互いの値が近いかどうか知ることができる。互いの値が近いほど相手の値の範囲が限定されるという性質がある。原則的には互いの値は範囲でしか明かさないが、互いの値がとても近い（nA=nBとなった）場合に限り、互いの値が一意にわかる可能性がある。
【００８７】
最後に、図１の比較結果算出部104（104(A)または104(B)）で、大小比較結果を得る方法を説明する。
【００８８】
大小比較は、前述の近さ判定の方法の一部を使って実現できる。最初から大小比較を目的として処理をしても良いが、本実施形態では近さ判定後の判断で続けて大小比較をする場合の方法について説明する。
【００８９】
たとえば、数値データ保持者２者が、互いの値が近いと知った後、両者共が大小比較を行いたいと考えたとする。上記例では、両社ともに価格のおよその違いはわかったので、どちらが高いかを改めて知りたいような場合である。その実現方法を以下で説明する。
【００９０】
まず、計算機100(S)は、LA''およびLB''を記憶しておく。
そして、計算機100(A)と計算機100(B)はそれぞれ、MA1とMB1を変換する。
【００９１】
図５は、図１の比較結果算出部104（104(A)または104(B)）が実行する、Mを変換する処理例を示すフローチャートである。各ステップについて計算機100(A)の視点で説明する。
【００９２】
M=MA1=[2, 6, 7, 0, 3, 1, 4, 5] を入力として受け入れる（図５のステップS1）。
bにリストMの長さの半分の値を入れる（図５のステップS2）。いま、b=4 となる。
【００９３】
Mの各要素につき、b未満なら1に、それ以外なら0を格納したリストM'を作成する（図５のステップS3）。よって、MA1'=[1, 0, 0, 1, 1, 1, 0, 0] となる。
【００９４】
M'を出力する（図５のステップS4）。
同様に、計算機100(B)では、MB1=[1, 6, 4, 2, 0, 3, 7, 5] なので MB1'=[1, 0, 0, 1, 1, 1, 0, 0] となる。
【００９５】
次に、計算機100(A)は MA1', MA2 を、計算機100(B)はMB1', MB2 を、それぞれ計算機100(S)に送信する。
【００９６】
計算機100(S)は、リストMA' をMA'[i]=MA1'[MB2[i]] となるように作成する。MA1'=[1, 0, 0, 1, 1, 1, 0, 0], MB2=[6, 2, 7, 1, 3, 4, 0, 5] なので、MA'=[0, 0, 0, 0, 1, 1, 1, 1] となる。同様に、リストMB' をMB'[i]=MB1'[MA2[i]] となるように作成し、MB'=[1, 1, 1, 0, 0, 0, 0, 1] となる。
【００９７】
続いて、図１の計算機100(S)の共通要素数計上部109は、LA''とLB''の各要素のうち、それぞれMA'とMB'の要素が1の位置の要素を抽出し、その要素のうち共通のものの数cを計上する。そして、結果出力部110が、cを計算機100(A)と計算機100(B)に送信する。これまでの例で説明すると、LA''=[h(kc, 22), h(kc, 35), h(kc, 9), h(kc, 6), h(kc, 21), h(kc, 2), h(kc, 5), h(kc, 10)] から MA'=[0, 0, 0, 0, 1, 1, 1, 1] の1の位置の要素を抽出すると [h(kc, 21), h(kc, 2), h(kc, 5), h(kc, 10)] である。また、LB''=[h(kc, 19), h(kc, 4), h(kc, 9), h(kc, 35), h(kc, 10), h(kc, 20), h(kc, 39), h(kc, 2)] から MB'=[1, 1, 1, 0, 0, 0, 0, 1] の1の位置の要素を抽出すると [h(kc, 19), h(kc, 4), h(kc, 9), h(kc, 2)] である。従って、これらの共通要素は h(kc, 2) のみなので、c=1を計算機100(A)と計算機100(B)に送信する。
【００９８】
最後に、計算機100(A)および100(B)の比較結果算出部104(A)および104(B)は、それぞれcを使い大小判定をおこなう。
【００９９】
図６は、図１の比較結果算出部104（104(A)または104(B)）が実行する、大小判定の処理例のフローチャートである。各ステップについて計算機100(A)の視点で説明する。
【０１００】
ビット数b=4、非負整数n=nA=5、共通要素数c=1 を、入力として受け入れる（図６のステップS1）。
【０１０１】
b=cか否かを判定する（図６のステップS2）。
いま、b>c なのでステップS2の判定はNOとなり、図６のステップS4に制御を移す。
【０１０２】
nを長さbの２進数表現zに変換する（図６のステップS4）。いま、z=0101 となる。
zのc+1番目のビットが1か否かを判定する（図６のステップS5）。
【０１０３】
いま、zのc+1=2番目のビットは1なので、図６のステップS6に制御を移す。
「大」を出力する（図６のステップS6）。
【０１０４】
同様に、計算機100(B)の視点で説明する。
b=4、n=nB=3、c=1 を入力として受け入れる（図６のステップS1）。
【０１０５】
b>c なので図６のステップS2の判定がNOとなり、図６のステップS4に制御を移す。
z=0011 となる（図６のステップS4）。
【０１０６】
zのc+1=2番目のビットは0なので図６のステップS5の判定はNOとなり、図６のステップS7に制御を移す。
「小」を出力する（図６のステップS7）。
【０１０７】
このように、出力の「大」「小」が、相手の数値と比較した自分の数値の大小に対応する。また、数値が同じ場合（図６のステップS2の判定がYES）は、「等」が出力される（図６のステップS3）。
【０１０８】
つまり、計算機100(A)は、NB=[2, 3]∪[7, 7] を知った上、nB<nA=5 であることを知ったので、NB=[2, 3] まで限定できたことになる。同様に、計算機100(B)はnA=5 であることを特定できた。
【０１０９】
このように、近さ判定のときに使ったデータを再利用することで大小判定もできる。大小判定のために再び暗号化からやり直しても実現できるが、再利用により暗号化処理を省くことができるという効果がある。
【０１１０】
共通要素数の計算は、図１の計算機100(S)の共通要素数計上部109が、LA''とLB''を入力としておこなうため、どちらかが偽のデータであると正しい計算結果とならない可能性が高い。そのため、計算機100(A)か計算機100(B)がこの方法に従わないことにより自分だけが正しい結果を得る、ということは困難にすることが可能となる。
【０１１１】
また、計算機100(S)が一方と結託することにより、「計算機100(A)と計算機100(B)のどちらか片方だけが正しい結果を得る」ことが可能になるが、結託してももう一方のデータを知ることは難しくすることが可能となる。たとえば計算機100(A)と結託すると鍵kAを得ることができるが、それを使っても LB'=[h(kB, 9), ...] の各要素は鍵kBによる暗号文なので平文を知ることはできない。また、LB' や LB'' は計算機100(B)しか知らないMでシャッフルされているので、その要素順から平文を推測することもできない。計算機100(A)や計算機100(B)は計算機100(S)と結託しても知ることができるデータが増えるわけではないので、結託する動機が少なく、お互いに安心して本実施形態が実現するシステムを利用できると考えられる。
【０１１２】
本実施形態では図２で接頭辞配列を全て使っているが、その一部しか使わないようにしても良い。たとえば、一番長い接頭辞である元の文字列自身を使わないことで、N=[n]となることが起きないようにすることができる。
【０１１３】
図７は、上述の実施形態における図１の計算機100(A)、計算機100(B)、および計算機100(S)の３つのコンピュータ間の処理関係の例を示すシーケンス図である。
【０１１４】
まず、計算機100(A)および100(B)の要素分解部102(A)および102(B)が、図２に示したフローチャートの処理例に従って、非負整数の分解処理を実行する（図７のステップS1(A)およびS1(B)）。
【０１１５】
次に、計算機100(A)および100(B)の暗号化部103(A)および103(B)が、図３に示したフローチャートの処理例に従って、暗号化およびシャッフルの処理を実行する。そして、計算機100(A)はLA'を計算機100(B)に、計算機100(B)はLB'を計算機100(A)に送信する（以上、図７のステップS2(A)およびS2(B)）。
【０１１６】
計算機100(A)および100(B)の暗号化部103(A)または103(B)は、それぞれさらに、図３に示したフローチャートの処理例に従って、受信したリストLの各要素を暗号化しシャッフルする。そして、計算機100(A)はLB''を、計算機100(B)はLA''を、それぞれ計算機100(S)へ送信する（以上、図７のステップS3(A)およびS3(B)）。
【０１１７】
計算機100(S)では、集合受付部108がLA''とLB''を受信し、共通要素数計上部109がLA''とLB''の共通要素数cを計算し、結果出力部110がcを計算機100(A)と計算機100(B)へ送信する（図７のステップS1(S)）。
【０１１８】
計算機100(A)および100(B)の比較結果算出部104(A)および104(B)は、図４に示したフローチャートの処理例に従って、比較結果算出の処理を実行する（図７のステップS4(A)およびS4(B)）。
【０１１９】
計算機100(A)および100(B)の比較結果算出部104(A)および104(B)はさらに、図５に示したフローチャートの処理例に従って、リストMを変換する処理を実行する。その結果、計算機100(A)は MA1', MA2 を、BはMB1', MB2 を、それぞれ計算機100(S)に送信する（以上、図７のステップS5(A)およびS5(B)）。
【０１２０】
計算機100(S)は、リストMA' およびMB' を作成する（図７のステップS2(S)）。
その後、共通要素数計上部109が、LA''とLB''の各要素のうち、それぞれMA'とMB'の要素が1の位置の要素を抽出し、その要素のうち共通のものの数cを計上し、結果出力部110が、cを計算機100(A)と計算機100(B)に送信する（図７のステップS3(S)）。
【０１２１】
計算機100(A)および100(B)の比較結果算出部104(A)および104(B)は、図６に示したフローチャートの処理例に従って大小判定の処理を実行する（図７のステップS6(A)およびS6(B)）。
【０１２２】
図８は、図１に示される各機能を、ソフトウェア処理として実現できる計算機100(A)、計算機100(B)、および計算機100(S)のハードウェア構成の一例を示す図である。
【０１２３】
図８に示されるコンピュータは、CPU（中央演算処理装置）801、メモリ802、入力装置803、出力装置804、外部記憶装置805、可搬記録媒体809が挿入される可搬記録媒体駆動装置806、及び通信インタフェース807を有する。そして、これらがバス808によって相互に接続された構成を有する。同図に示される構成は上記システムを実現できる計算機100(A)、計算機100(B)、および計算機100(S)の一例であり、そのようなコンピュータはこの構成に限定されるものではない。
【０１２４】
CPU801は、当該コンピュータ全体の制御を行う。メモリ802は、プログラムの実行、データ更新等の際に、外部記憶装置805（或いは可搬記録媒体809）に記憶されているプログラム又はデータを一時的に格納するRAM（ランダムアクセスメモリ）等のメモリである。ＣＵＰ801は、プログラムをメモリ802に読み出して実行することにより、全体の制御を行う。
【０１２５】
入力装置803は、ユーザによるキーボードやマウス等による入力操作を検出し、その検出結果をCPU801に通知する。
【０１２６】
出力装置804は、CPU801の制御によって送られてくるデータを表示装置や印刷装置に出力する。
【０１２７】
外部記憶装置805は、例えばハードディスク記憶装置である。主に各種データやプログラムの保存に用いられる。
【０１２８】
可搬記録媒体駆動装置806は、光ディスクやSDRAM、コンパクトフラッシュ（登録商標）等の可搬記録媒体809を収容するもので、外部記憶装置805の補助の役割を有する。
【０１２９】
通信インタフェース807は、例えばLAN（ローカルエリアネットワーク）又はＷＡＮ（ワイドエリアネットワーク）の通信回線を接続するための装置である。
【０１３０】
本実施形態によるシステムは、計算機100(A)または計算機100(B)においては、図１の102、103、104の各機能に対応する図２から図６のフローチャート等で実現される機能を搭載したプログラムをCPU801が実行することで実現される。そのプログラムは、例えば外部記憶装置805や可搬記録媒体809に記録して配布してもよく、或いは通信インタフェース807によりネットワークから取得できるようにしてもよい。また、メモリ802は、図１の記憶部101の機能を実現し、通信インタフェース807は、図１の通信部105(A)または105(B)の機能を実現する。
【０１３１】
計算機100(S)においては、図１の107から110の各機能を搭載したプログラムをCPU801が実行することで実現される。そのプログラムは、例えば外部記憶装置805や可搬記録媒体809に記録して配布してもよく、或いは通信インタフェース807によりネットワークから取得できるようにしてもよい。また、メモリ802は、図１の記憶部１０６の機能を実現し、通信インタフェース807は、図１の通信部105(S)の機能を実現する。
【０１３２】
上述した実施形態では、計算機100(A)および100(B)にて入力された第１の数値および第２の数値をそれぞれ非負整数に変換した後、さらに第１および第２の接頭辞配列に変換して第１および第２の集合として出力し、これらの共通要素数を算出している。このほか、「互いの数値を共通要素数により比較判定可能な要素の集合に変換」する手法であれば、どのような手法を用いてもよい。
【０１３３】
以上説明した本実施形態により、互いの値を明かさず、互いの値の比較結果を、互いに知ることが可能となる。
【０１３４】
本実施形態の方式は公平である。つまり、片方だけが正しい結果を得ることは困難であるため、両者が協力して実施することが期待できる。
【０１３５】
これにより、たとえば上記例、競合他社同士のＡ社とＢ社が、利用価格が同程度か両者共に知りたい、ただし同程度でないときは互いの利用価格は教えたくない、といった要望を実現することが可能となる。
【０１３６】
以上の実施形態に関して、更に以下の付記を開示する。
（付記１）
比較対象の第１の数値および第２の数値をそれぞれ、互いの数値を共通要素数により比較判定可能な要素の第１の集合および第２の集合に変換し、
前記第１の集合および前記第２の集合の共通要素数を秘匿計算で算出し、
算出した前記第１の集合および前記第２の集合の共通要素数を比較し、比較結果を出力する、
処理を含むことを特徴とする秘匿比較方法。
（付記２）
前記第１の数値は第１の利用者が操作するコンピュータから入力し、前記第２の数値は第２の利用者が操作するコンピュータから入力し、前記共通要素数の算出は前記第１の利用者および前記第２の利用者以外の第三者が管理するコンピュータで行う、
処理を含むことを特徴とする付記１に記載の秘匿比較方法。
（付記３）
前記第１の数値および前記第２の数値からそれぞれ前記第１の集合および前記第２の集合への変換は、
前記第１の数値および前記第２の数値をそれぞれ第１の非負整数および第２の非負整数へ変換し、
前記第１の非負整数および前記第２の非負整数のそれぞれの２進数表現の長さのうちの長いほうの値をbビットとしたときに、前記第１の非負整数および前記第２の非負整数をそれぞれ、b次の第１の接頭辞配列および第２の接頭辞配列に分解して前記第１の集合および第２の集合とする、
処理を含むことを特徴とする付記１または２のいずれかに記載の秘匿比較方法。
（付記４）
前記第１の接頭辞配列または前記第２の接頭辞配列が、奇数の場合には１を加算し、偶数の場合には１を減算し、前記加算または前記減算の結果を前記第１の接頭辞配列または前記第２の接頭辞配列として出力する、
処理を含むことを特徴とする付記３に記載の秘匿比較方法。
（付記５）
前記加算または前記減算の結果がアンダーフローあるいはオーバーフローを起こしたときに、前記加算または前記減算の結果に対して単射であるようにパディングを行い、該パディングの結果を前記第１の接頭辞配列または前記第２の接頭辞配列として出力する、
処理を含むことを特徴とする付記４に記載の秘匿比較方法。
（付記６）
前記共通要素数から前記比較結果への変換は、前記第１の非負整数または前記第２の非負整数について、前記bビットが前記共通要素数に等しくなければ、値０から前記第１の非負整数または前記第２の非負整数までの第１の範囲と、前記第１の非負整数または前記第２の非負整数から2のb乗までの第２の範囲のそれぞれで、２分検索により、共通要素数が前記共通要素数となる値の各範囲を計算し、当該各範囲を前記比較結果として出力し、前記bビットが前記共通要素数に等しければ前記第１の非負整数または前記第２の非負整数を前記比較結果として出力する近さ判定を行う、
処理を含むことを特徴とする付記３ないし６のいずれかに記載の秘匿比較方法。
（付記７）
前記共通要素数から前記比較結果への変換は、
値０以上前記第１の集合または前記第２の集合の要素数未満の各整数値をランダムに並べた第１のリストまたは第２のリストについて、当該第１のリストまたは第２のリストの各要素を、当該要素の値が当該リストの長さの半分の値未満なら値１で、そうでなければ値０で、それぞれ置き換えた第１の修正リストまたは第２の修正リストをそれぞれ作成し、
前記第１の集合および前記第２の集合の各要素のうち、それぞれ前記第１の修正リストおよび前記第２の修正リストの要素が値１である位置の要素を抽出し、当該抽出した要素のうち共通のものの数を第２の共通要素数として秘匿計算で算出し、
前記第１の非負整数または前記第２の非負整数について、前記bビットが前記第２の共通要素数に等しくなければ、前記第１の非負整数または前記第２の非負整数を２進数表現に変換し当該２進数表現の前記第２の共通要素数に値１をプラスした値に対応するビット位置の値が１であれば、前記第１の非負整数または前記第２の非負整数が前記第２の非負整数または前記第１の非負整数よりも大きいことを示す大小比較結果を出力し、そうでなければ前記第１の非負整数または前記第２の非負整数が前記第２の非負整数または前記第１の非負整数よりも小さいことを示す大小比較結果を出力し、前記bビットが前記第２の共通要素数に等しければ前記第１の非負整数と前記第２の非負整数が等しいことを示す大小比較結果を出力する大小判定を行う、
処理を含むことを特徴とする付記３ないし６のいずれかに記載の秘匿比較方法。
（付記８）
付記７に記載の近さ判定の処理と付記８に記載の大小判定の処理とから、前記比較結果を出力する、
処理を含むことを特徴とする付記６および７に記載の秘匿比較方法。
（付記９）
比較対象の第１の数値および第２の数値をそれぞれ、互いの数値を共通要素数により比較判定可能な要素の第１の集合および第２の集合に変換する手段と、
前記第１の集合および前記第２の集合の共通要素数を秘匿計算で算出する手段と、
算出した前記第１の集合および前記第２の集合の共通要素数を比較し、比較結果を出力する手段と、
を備えることを特徴とする秘匿比較システム。
(付記１０)
比較対象の第１の数値および第２の数値をそれぞれ、互いの数値を共通要素数により比較判定可能な要素の第１の集合および第２の集合に変換し、
前記第１の集合および前記第２の集合の共通要素数を秘匿計算で算出し、
算出した前記第１の集合および前記第２の集合の共通要素数を比較し、比較結果を出力する、
ステップをコンピュータに実行させるための秘匿比較プログラム。
【符号の説明】
【０１３７】
100、100(A)、100(B)、100(S)  計算機
101、101(A)、101(B)、106  記憶部
102、102(A)、102(B)  要素分解部
103、103(A)、103(B)  暗号化部
104、104(A)、104(B)  比較結果算出部
105、105(A)、105(B)  通信部
107  データ転送部
108  集合受付部
109  共通要素数計上部
110  結果出力部
801  CPU（中央演算処理装置）
802  メモリ
803  入力装置
804  出力装置
805  外部記憶装置
806  可搬記録媒体駆動装置
807  通信インタフェース
808  バス
809  可搬記録媒体
【図１】
2015108682.tif 000003
【図２】
2015108682.tif 000004
【図３】
2015108682.tif 000005
【図４】
2015108682.tif 000006
【図５】
2015108682.tif 000007
【図６】
2015108682.tif 000008
【図７】
2015108682.tif 000009
【図８】
2015108682.tif 000010