(57)【要約】二つの整数の比較演算を、ＡＮＤ／ＸＯＲなしで計算する秘密計算装置を提供する。秘密計算装置は、０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されている場合に、第１の整数ａと第２の整数ｂとを比較する。秘密計算装置は、加減算回路部と、ビット分解回路部と、ビット抽出回路部と、を備える。加減算回路部は、第１の整数ａと第２の整数ｂと２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する。ビット分解回路部は、加減算結果をbit分散に変換して、bit分散された結果を出力する。ビット抽出回路部は、bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力する。
2018212015.tif 000002
【特許請求の範囲】
【請求項１】
０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されている場合に、前記第１の整数ａと前記第２の整数ｂとを比較する秘密計算装置であって、
前記第１の整数ａと前記第２の整数ｂと前記２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する加減算回路部と、
前記加減算結果をbit分散に変換して、bit分散された結果を出力するビット分解回路部と、
前記bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力するビット抽出回路部と、
を備える秘密計算装置。
【請求項２】
前記ビット抽出回路部は、前記bit分散された結果をｋビット右シフトして、前記抽出結果としてシフト結果を出力するシフト回路部から成る、請求項１に記載の秘密計算装置。
【請求項３】
前記シフト結果をring分散に変換して、ring分散された結果を出力するビット結合回路部を更に備える、請求項２に記載の秘密計算装置。
【請求項４】
前記第１の整数ａが前記第２の整数ｂ以下であるか否かを検出する場合、
前記加減算回路部は、ring分散で前記所定の加減算として(ｂ＋2^ｋ−ａ)を計算し、該(ｂ＋2^ｋ−ａ)を前記加減算結果として出力する、請求項１乃至３のいずれか１項に記載の秘密計算装置。
【請求項５】
前記第１の整数ａが前記第２の整数ｂより小さいか否かを検出する場合、
前記加減算回路部は、ring分散で前記所定の加減算として(ｂ＋2^ｋ−(ａ＋１))を計算し、該(ｂ＋2^ｋ−(ａ＋１))を前記加減算結果として出力する、請求項１乃至３のいずれか１項に記載の秘密計算装置。
【請求項６】
前記第１の整数ａが前記第２の整数ｂ以上であるか否かを検出する場合、
前記加減算回路部は、ring分散で前記所定の加減算として(ａ＋2^ｋ−ｂ)を計算し、該(ａ＋2^ｋ−ｂ)を前記加減算結果として出力する、請求項１乃至３のいずれか１項に記載の秘密計算装置。
【請求項７】
前記第１の整数ａが前記第２の整数ｂより大きいか否かを検出する場合、
前記加減算回路部は、ring分散で前記所定の加減算として(ａ＋2^ｋ−(ｂ＋１))を計算し、該(ａ＋2^ｋ−(ｂ＋１))を前記加減算結果として出力する、請求項１乃至３のいずれか１項に記載の秘密計算装置。
【請求項８】
請求項１乃至７のいずれか１項に記載の秘密計算装置を、Ｎ（Ｎは３以上の整数）台備えてなる、秘密計算システム。
【請求項９】
０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されている場合に、秘密計算装置において前記第１の整数ａと前記第２の整数ｂとを比較する方法であって、
前記第１の整数ａと前記第２の整数ｂと前記２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する加減算ステップと、
前記加減算結果をbit分散に変換して、bit分散された結果を出力するビット分解ステップと、
前記bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力するビット抽出ステップと、
を含む比較方法。
【請求項１０】
前記ビット抽出ステップは、前記bit分散された結果をｋビットシフトするシフトステップから成る、請求項９に記載の比較方法。
【請求項１１】
前記シフト結果をring分散に変換して、ring分散された結果を出力するビット結合ステップを更に備える、請求項１０に記載の比較方法。
【請求項１２】
前記第１の整数ａが前記第２の整数ｂ以下であるか否かを検出する場合、
前記加減算ステップは、ring分散で前記所定の加減算として(ｂ＋2^ｋ−ａ)を計算し、該(ｂ＋2^ｋ−ａ)を前記加減算結果として出力する、請求項９乃至１１のいずれか１項に記載の比較方法。
【請求項１３】
前記第１の整数ａが前記第２の整数ｂより小さいか否かを検出する場合、
前記加減算ステップは、ring分散で前記所定の加減算として(ｂ＋2^ｋ−(ａ＋１))を計算し、該(ｂ＋2^ｋ−(ａ＋１))を前記加減算結果として出力する、請求項９乃至１１のいずれか１項に記載の比較方法。
【請求項１４】
前記第１の整数ａが前記第２の整数ｂ以上であるか否かを検出する場合、
前記加減算ステップは、ring分散で前記所定の加減算として(ａ＋2^ｋ−ｂ)を計算し、該(ａ＋2^ｋ−ｂ)を前記加減算結果として出力する、請求項９乃至１１のいずれか１項に記載の比較方法。
【請求項１５】
前記第１の整数ａが前記第２の整数ｂより大きいか否かを検出する場合、
前記加減算ステップは、ring分散で前記所定の加減算として(ａ＋2^ｋ−(ｂ＋１))を計算し、該(ａ＋2^ｋ−(ｂ＋１))を前記加減算結果として出力する、請求項９乃至１１のいずれか１項に記載の比較方法。
【請求項１６】
０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されている場合に、秘密計算装置であるコンピュータに、前記第１の整数ａと前記第２の整数ｂとを比較させる比較プログラムを記録した記録媒体であって、前記比較プログラムは、前記コンピュータに、
前記第１の整数ａと前記第２の整数ｂと前記２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する加減算機能と、
前記加減算結果をbit分散に変換して、bit分散された結果を出力するビット分解機能と、
前記bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力するビット抽出機能と、
を実現させるための比較プログラム記録媒体。
【請求項１７】
前記ビット抽出機能は、前記bit分散された結果をｋビットシフトするシフト機能から成る、請求項１６に記載の比較プログラム記録媒体。
【請求項１８】
前記比較プログラムは、前記コンピュータに、前記シフト結果をring分散に変換して、ring分散された結果を出力するビット結合機能を更に実現させる、請求項１７に記載の比較プログラム記録媒体。
【請求項１９】
前記第１の整数ａが前記第２の整数ｂ以下であるか否かを検出する場合、
前記加減算機能は、ring分散で前記所定の加減算として(ｂ＋2^ｋ−ａ)を計算し、該(ｂ＋2^ｋ−ａ)を前記加減算結果として出力する、請求項１６乃至１８のいずれか１項に記載の比較プログラム記録媒体。
【請求項２０】
前記第１の整数ａが前記第２の整数ｂより小さいか否かを検出する場合、
前記加減算機能は、ring分散で前記所定の加減算として(ｂ＋2^ｋ−(ａ＋１))を計算し、該(ｂ＋2^ｋ−(ａ＋１))を前記加減算結果として出力する、請求項１６乃至１８のいずれか１項に記載の比較プログラム記録媒体。
【請求項２１】
前記第１の整数ａが前記第２の整数ｂ以上であるか否かを検出する場合、
前記加減算機能は、ring分散で前記所定の加減算として(ａ＋2^ｋ−ｂ)を計算し、該(ａ＋2^ｋ−ｂ)を前記加減算結果として出力する、請求項１６乃至１８のいずれか１項に記載の比較プログラム記録媒体。
【請求項２２】
前記第１の整数ａが前記第２の整数ｂより大きいか否かを検出する場合、
前記加減算機能は、ring分散で前記所定の加減算として(ａ＋2^ｋ−(ｂ＋１))を計算し、該(ａ＋2^ｋ−(ｂ＋１))を前記加減算結果として出力する、請求項１６乃至１８のいずれか１項に記載の比較プログラム記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密計算装置、比較方法、比較プログラム記録媒体、および秘密計算システムに関する。
【背景技術】
【０００２】
秘密計算方法とは、複数の秘密計算装置が互いに通信を介しながら計算することで、与えられた関数を計算する方法である。そして、秘密計算方法は、これらのいずれの秘密計算装置も十分な数の秘密計算装置間で互いに扱うデータを共有しない限り、関数への入力や出力に関する情報を得ることができない特徴を持つ。【０００３】
公知の秘密計算方法として、非特許文献１に挙げられる方法が知られている。【０００４】
非特許文献１に記載の方法では、ある体上の値である秘密Sを、この体上の多項式FでF(０)=Sとなるものを使って複数の秘密計算装置に分散する。秘密計算装置の数がN、秘密の個数がK未満であれば、関数の入力や出力に関する情報を得ることができないとする。この様な技術をこの技術分野では「秘密分散」という。秘密計算装置毎に異なるこの体上の値が割り当てられているとし、i番目の秘密計算装置に割り当てられている体の値をX[i]とする。ここで、１≦i≦Nである。【０００５】
秘密Aをこれら複数の秘密計算装置に分散する時、各i番目の秘密計算装置にはF(0)=Aなるランダムに選ばれた（K-1）次多項式Fに関する、F[i]:=F(X[i])を配る。【０００６】
秘密Bに関しても同様に、G(0)=Bなる（K-1）次多項式Gに関する、G[i]:=G(X[i])を各i番目の秘密計算装置に配る。【０００７】
秘密は、K個以上の秘密計算装置が集まれば（K-1）次多項式を解くことが可能で、FやGの係数を求めることができ、F(0)やG(0)を計算することが可能になる。【０００８】
A+Bを分散した値を計算するには、各i番目の秘密計算装置は H[i]=F[i]+G[i]を計算する。この値はFとGのそれぞれ対応する係数を足したものを係数とする多項式Hに、X[i]を代入して得られたものH(X[i])であるので、秘密Aや秘密Bと同様にA+Bを複数の秘密計算装置で分散したものとなる。【０００９】
秘密Aや秘密Bの場合と同様に、K個以上の秘密計算装置が集まれば（K-1）次多項式を解くことが可能で、Hの係数を求めることができ、H(0)を計算することが可能になる。【００１０】
K*2 ≦N+1 の場合は、A*Bを分散した値を計算するには、各i番目の秘密計算装置は H[i]=F[i]*G[i]を計算する。この値は2K次多項式H(X)=F(X)*G(X)に、X[i]を代入して得られたものH(X[i])であるので、秘密Aや秘密Bと同様にA*Bを複数の秘密計算装置で分散したものとなる。ただし、秘密Aや秘密Bの場合とは異なりHの次数は２Kとなるので、２K個以上の秘密計算装置が集まれば２K次多項式を解くことが可能で、Hの係数を求めることができ、H(0)を計算することが可能になる。【００１１】
A*Bの分散方法は、秘密Aや秘密Bとは分散のされ方が異なる。これを同様に（K-1）次多項式を用いた形で分散するには、それぞれi番目の秘密計算装置がH[i]から（K-1）次多項式Gを生成して、他のそれぞれj番目の秘密計算装置にG(X[j])を配ることでなされる。このようにして、非特許文献１記載の方法では、加算と乗算からなる全ての関数を計算することができる。【００１２】
この非特許文献１に記載の方法は、体上の乗算と加算が容易に行われるが、条件として2K≦N+１がある。Kは2以上でなければ秘密計算装置単独で秘密を求めることができないため、Nは３以上である。【００１３】
異なるiに関するX[i]は異ならなければならないので、非特許文献１記載の方法では、利用できる体にガロア体GF(2)は含まれない。ガロア体GF(2)が含まれないため、非特許文献１記載の方法では、加算を用いて排他的論理和とすることはできない。【００１４】
その他の公知の秘密計算方法として、非特許文献２に挙げられる方法が知られている。【００１５】
非特許文献２には、秘密計算装置の数が二つの場合の方法に関する記述がある。この方法では、二つの秘密計算装置がビット、すなわちガロア体GF(2)上のある要素bを分散して保持する場合は、 b+c=b mod 2 となるbとcを、それぞれの秘密計算装置で分けて保持する。【００１６】
この様な方法を使うと、あるビットAとあるビットBを第１の秘密計算装置と第２の秘密計算装置で分散する場合、A=C+D mod 2, B=E+F mod 2として、第１の秘密計算装置はCとEを、第２の秘密計算装置はDとFを保持する。この時、ビットAとビットBの排他的論理和Gは G=A+B mod 2となり、これらの第１の秘密計算装置と第２の秘密計算装置との分散は、それぞれ、H=C+E mod 2とJ=D+F mod 2 とすることができる。【００１７】
それぞれの秘密計算装置は、他の秘密計算装置と通信することなく、軽い計算で分散された二つの値の排他的論理和の分散が計算できたことになる。【００１８】
同様に、ビットAとビットBが分散されて保持しているとき、この二つのビットの論理積 K=A・Bのそれぞれの分散、すなわち L+M=K mod 2なるLとMを、第１の秘密計算装置がLを第２の秘密計算装置がMを得るように計算を行うには、次のようにする。【００１９】
第１の秘密計算装置はLをランダムに生成する。この時、M＝(C+D)・(E+F)=L mod 2 であるので、第２の秘密計算装置が持つ値DとFに応じて、第１の秘密計算装置がMの値を知らずに第２の秘密計算装置に次の値を返す。(D,F)=(0,0)ならM=(C+0)・(E+0)+L mod 2を返す。(D,F)=(0,1)ならM=(C+0)・(1+E)+L mod 2 を返す。(D,F)=(1,0)ならM=(1+C)・(E+0)+L mod 2 を返す。(D,F)=(1,1)ならM=(1+C)・(1+E)+L mod 2 を返す。【００２０】
第２の秘密計算装置の入力に依存する値を、第１の秘密計算装置が第２の秘密計算装置に送付する。第１の秘密計算装置が第２の秘密計算装置の入力を知ることができない方法は、第１の秘密計算装置と第２の秘密計算装置との間の oblivious transfer と呼ばれる技術で実現される。しかしながら、この技術では、一般に両者に多くの計算と通信を要求する。【００２１】
非特許文献１と２に開示された秘密計算方法では、各秘密計算装置が正直に振る舞うことを前提としている。【００２２】
特許文献１は、秘密分散と秘密計算とについて記載している。秘密分散とは、データを複数の分散値（秘密分散値）に変換し、一定個数以上の秘密分散値を用いれば元のデータを復元でき、一定個数未満の秘密分散値からは元のデータを一切復元できなくする技術である。秘密分散の一種である（ｋ、ｎ）−秘密分散は、入力された平文をｎ個に分割した秘密分散値をｎ個の計算主体に分散しておき、任意のｋ個の秘密分散値が揃えば平文を復元でき、ｋ個未満の秘密分散値からは平文に関する一切の情報を得られないような秘密分散である。秘密計算は、複数の計算主体に計算対象のデータ（元データ）を秘密分散して保存しておき、元データを復元することなく他の計算主体と協力して元データの関数値の秘密分散値を計算する技術である。【００２３】
特許文献２は、ビットWを第１乃至第３の秘密計算装置に分散して記憶する秘密計算システムの一例を開示している。この時、R[1]+R[2]+R[3]＝0 mod 2 なる三つのランダムに選ばれたビットR[1]、R[2]、R[3]をもちいる。第１の秘密計算装置は（R[1],W+R[2] mod 2）を格納する。第２の秘密計算装置は(R[2],W+R[3] mod 2)を格納する。第３の秘密計算装置は(R[3],W+R[1] mod 2)を格納する。【００２４】
特許文献３は、少ない通信量で加法的秘密分散の分散値を複製型秘密分散の分散値へ変換する分散値変換システムを開示している。複製型秘密分散（Replicated Secret Sharing）は、上記（ｋ、ｎ）−秘密分散の一つである。加法的秘密分散とは、複製型秘密分散による（ｋ、ｋ）−秘密分散である。（ｋ、ｋ）−秘密分散とは、（ｋ、ｎ）−秘密分散において、ｎ＝ｋとした場合である。（ｋ、ｋ）−秘密分散では、全パーティのシェアが集まらない限り平文を復元することはできない。特許文献３は、３台の分散値変換装置を含む分散値変換システムを開示している。各分散値変換装置のシェア生成部は、加法的秘密分散のシェアと乱数を用いて、複製型秘密分散のシェアを生成する。【００２５】
特許文献４は、Shamir秘密分散の分散値を複製型秘密分散の分散値へ変換する分散値変換システムを開示している。Shamir秘密分散も上記（ｋ、ｎ）−秘密分散の一つである。Shamir秘密分散では、ｉ番目のパーティに座標を割り当て、乱数を用いて平文を分散する。【００２６】
非特許文献３は、ビット分解について記載している。ビット分解は、lビットの数値が格納された１つの暗号文（もしくは秘密分散値）を、１ビットの真偽値の暗号文／秘密分散値から成る長さｌの列に変換する操作をいう。
【先行技術文献】
【特許文献】
【００２７】
【特許文献１】国際公開第２０１６／０５６４７３号
【特許文献２】国際公開第２０１６／０４２６９３号
【特許文献３】特開２０１６−１７３５３３号公報
【特許文献４】特開２０１６−１７３５３１号公報
【非特許文献】
【００２８】
【非特許文献１】Tal Rabin, Michael Ben-Or: Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract). STOC 1989: 73-85
【非特許文献２】Oded Goldreich, Ronen Vainish: How to Solve any Protocol Problem - An Efficiency Improvement. CRYPTO 1987: 73-86
【非特許文献３】五十嵐大、濱田浩気、菊池亮、千田浩司、「少パーティの秘密分散ベース秘密計算のためのＯ（ｌ）ビット通信ビット分解およびＯ（｜ｐ’｜）ビット通信Modulus変換法」、Computer Security Symposium 2013, 21-23 October 2013
【発明の概要】
【発明が解決しようとする課題】
【００２９】
上述した非特許文献１〜３および特許文献１〜４のいずれも、整数の比較演算を具体的にどのように行うかについて記載も開示もしていない。秘密計算においては、データを暗号化したまま演算を行う。そのため、一般的には、二つの整数の比較演算を行う場合には、後で詳細に説明するように、比較演算をＸＯＲ（排他的論理和）とＡＮＤ（論理積）演算との組み合わせで実現する必要がある。その結果、処理時間が延びるという問題がある。【００３０】
本発明の目的は、上記課題を解決できる秘密計算装置、比較方法、比較プログラム記録媒体、および秘密計算システムを提供することにある。
【課題を解決するための手段】
【００３１】
本発明の秘密計算装置は、０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されている場合に、前記第１の整数ａと前記第２の整数ｂとを比較する秘密計算装置であって、前記第１の整数ａと前記第２の整数ｂと前記２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する加減算回路部と；前記加減算結果をbit分散に変換して、bit分散された結果を出力するビット分解回路部と；前記bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力するビット抽出回路部と；を備える。【００３２】
本発明の秘密計算システムは、上記秘密計算装置を、Ｎ（Ｎは３以上の整数）台備えてなる。【００３３】
本発明の比較方法は、０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されている場合に、秘密計算装置において前記第１の整数ａと前記第２の整数ｂとを比較する方法であって、前記第１の整数ａと前記第２の整数ｂと前記２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する加減算ステップと；前記加減算結果をbit分散に変換して、bit分散された結果を出力するビット分解ステップと；前記bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力するビット抽出ステップと；を含む。【００３４】
本発明の比較プログラム記録媒体は、０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されている場合に、秘密計算装置であるコンピュータに、前記第１の整数ａと前記第２の整数ｂとを比較させる比較プログラムを記録した記録媒体であって、前記比較プログラムは、前記コンピュータに、前記第１の整数ａと前記第２の整数ｂと前記２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する加減算機能と；前記加減算結果をbit分散に変換して、bit分散された結果を出力するビット分解機能と；前記bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力するビット抽出機能と；を実現させる。
【発明の効果】
【００３５】
本発明によれば、ＡＮＤ／ＸＯＲ演算なしに、比較計算を行うこと可能な秘密計算装置、比較方法、比較プログラム記録媒体、および秘密計算システムを提供できる。
【図面の簡単な説明】
【００３６】
【図１】関連技術における、秘密にしたいデータＤsecを、３台の計算機（秘密計算装置）が、それぞれ、第１乃至第３の分散した値として分散して保管している例を示す図である。
【図２】本発明の一実施形態に係る秘密計算システムの構成を示すブロック図である。
【図３】図２に示した秘密計算システムに用いられる第ｎの秘密計算装置を示すブロック図である。
【図４】図３に示した第ｎの秘密計算装置の動作を説明するためのフローチャートである。
【発明を実施するための形態】
【００３７】
［関連技術］
本発明の理解を容易にするために、関連技術について説明する。
【００３８】
最初に、秘密計算の概要について説明する。
図１は、秘密にしたいデータＤsecを、３台の計算機（秘密計算装置）１−１、１−２、１−３が、それぞれ、第１乃至第３の分散した値として分散して保管している例を示す図である。このように、データＤsecを複数の分散した値に分割しているので、分散した値が全部もしくはＮ（Ｎは２以上の整数）個以上そろわないと、元のデータＤsecは分からない。なお、各計算機１−1〜１−３は、ノードやパーティとも呼ばれる。
【００３９】
このように、元のデータＤsecを複数の計算機１−１〜１−３で分散して管理しているので、ある計算機の管理者が自身の分散した値を漏洩しても、元のデータＤsecは安全である。
【００４０】
各計算機１−１〜１−３で計算した内容を合わせると、元のデータＤsecに対する計算結果が得られる。計算中も安全である。
【００４１】
次に、秘密分散について説明する。
整数ｖを三つに分割して、各ノード１−１〜１−３に分けるとする。秘密分散には、次に述べるような、bit分散とring分散とが知られている。
【００４２】
bit分散は、次式で表される。
ｖ ＝ ｖ０∧ｖ１∧ｖ２
ここで、演算子∧は排他的論理和（ＸＯＲ）を表す。
【００４３】
一方、ring分散は、次式で表される。
ｖ ＝ ｖ０＋ｖ１＋ｖ３
ここで、演算子＋は、ring上の加法（加算）を表す。
【００４４】
二つの分散の方法の間の変換は可能である。ring分散からbit分散に変換することは、「ビット分解」と呼ばれる。「ビット分解」の方法については、上記非特許文献３に記載されているので、ここではその説明を省略する。
【００４５】
一方、bit分散からring分散に変換することは、「ビット結合」と呼ばれる。次に、「ビット結合」の方法について説明する。
【００４６】
ビット結合は、次のようにして行われる。
1.環上の乱数rを分散する。
2.乱数rの分散情報をビット分解する。
3.ビット分解された乱数の分散情報と、ビット結合を行う対象のビットの分散情報について加算回路の秘密計算を行い、その結果を復元する。ビット結合した結果をxとするならば、r+xが復元される。
4.r+xをring分散し、環上のシェアの秘密計算として(r+x) -rを実行した結果がビット結合の結果となる。
【００４７】
これらbit分散およびring分散には、次に述べるような特徴がある。すなわち、二つを乱数とすることで、
1) 個々の分散した値からは元の値が分からず、
2) 分散した値の三つ全て揃わないと元の値に復元できない
という特徴がある。
【００４８】
各ノード（パーティ）１−１〜１−３は、三つの分散した値の内二つの分散した値を持つ。これを秘密分散と呼ぶ。例えば、パーティ１−１〜１−３を、それぞれ、Party0、Party1、およびParty2と表すと、それらは、次のような二つの分散した値を持つ。
Party0: (ｖ２, ｖ０)
Party1: (ｖ０, ｖ１)
Party2: (ｖ１, ｖ２)
したがって、少なくとも二つのパーティが結託しないと、元の値ｖには復元できない。
【００４９】
次に、具体的な秘密計算について説明する。秘密計算では、元の値ｖを復元することなく、演算を実行する。
【００５０】
具体的には、元の値ｖ、ｗに対して、bit分散およびring分散では、次に述べるような演算が可能である。
【００５１】
すなわち、bit分散の場合は、ｖ∧ｗとｖ＆ｗの演算が可能である。ここで、演算子＆は、ＡＮＤ（論理積）を表す。
【００５２】
一方、ring分散の場合は、ｖ＋ｗとｖ＊ｗの演算が可能である。ここで、演算子＊は、乗法（掛け算）を表す。
より複雑な演算は、これら演算を組み合わせることで行う。
【００５３】
次に、bit分散の場合において、秘密計算の具体例について説明する。最初に、ＸＯＲ（排他的論理和）の場合の秘密計算について説明する。
【００５４】
整数ｖ,ｗが、それぞれ、
ｖ ＝ v０∧ｖ１∧ｖ２
ｗ ＝ ｗ０∧ｗ１∧ｗ２
とbit分散されており、第１乃至第３のパーティ１−１〜１−３が、それぞれ、
Party0:  (ｖ２, ｖ０), (ｗ２, ｗ０)
Party1:  (ｖ０, ｖ１), (ｗ０, ｗ１)
Party2:  (ｖ１, ｖ２), (ｗ１, ｗ２)
を保持しているとする。
【００５５】
ｖ∧ｗは、次式で表される。
ｖ∧ｗ = (ｖ０∧ｗ０)∧(ｖ１∧ｗ１)∧(ｖ２∧ｗ２)
そこで、各パーティ１−１〜１−３が、次式を計算する。
Paryt0:  (ｘ２, ｘ０) = (ｖ２∧ｗ２, ｖ０∧ｗ０)
Party1:  (ｘ０, ｘ１) = (ｖ０∧ｗ０, ｖ１∧ｗ１)
Party2:  (ｘ１, ｘ２) = (ｖ１∧ｗ１, ｖ２∧ｗ２)
【００５６】
一方、ｘは、次式で表される。
ｘ = ｘ０∧ｘ１∧ｘ２ =ｖ∧ｗ
したがって、各パーティ１−１〜１−３は、ｖ∧ｗの結果の分散した値を持っていることになる。
ここで、パーティ１−１〜１−３間の通信は不要である。
【００５７】
次に、ＡＮＤ（論理積）の場合の秘密計算について説明する。
ｖ＆ｗは、次式で表される。
ｖ＆ｗ ＝ (Ｖ０∧Ｖ１∧Ｖ２)＆(ｗ０∧ｗ１∧ｗ２)
＝ (ｖ０＆ｗ０)∧(ｖ０＆ｗ２)∧(ｖ２＆ｗ０)
∧ (ｖ１＆ｗ１)∧(ｖ１＆ｗ０)∧(ｖ０＆ｗ１)
∧ (ｖ２＆ｗ２)∧(ｖ２＆ｗ１)∧(ｖ１＆ｗ２)
【００５８】
各パーティ１−１〜１−３が、ｍ０∧ｍ１∧ｍ２ ＝ ０ の乱数を用いて、次式を計算する。
Party0: ｘ０ ＝ (ｖ０＆ｗ０)∧(ｖ０＆ｗ２)∧(ｖ２＆ｗ０)∧ｍ０
Party1: ｘ１ ＝ (ｖ１＆ｗ１)∧(ｖ１＆ｗ０)∧(ｖ０＆ｗ１)∧ｍ１
Party2: ｘ２ ＝ (ｖ２＆ｗ２)∧(ｖ２＆ｗ１)∧(ｖ１＆ｗ２)∧ｍ２
この場合、次式が成り立つ。
ｘ０∧ｖ１∧ｘ２ ＝ ｖ＆ｗ
【００５９】
したがって、各パーティ１−１〜１−３が、隣のパーティにデータを渡すと、各パーティ１−１〜１−３は次式で表される分散した値を保持することになる。
Party0: (ｘ２, ｘ０)
Party1: (ｘ０, ｘ１)
Party2: (ｘ１, ｘ２)
【００６０】
その結果、各パーティ１−１〜１−３はｖ＆ｗ の分散した値を保持していることになる。
【００６１】
このとき、ｘ０，ｘ１,ｘ２は乱数でマスクされているので、情報は漏洩しない。
なお、ＡＮＤの計算には通信が必要である。
【００６２】
次に、ring分散の場合において、秘密計算について説明する。
【００６３】
ring分散の場合、ｖ＋ｗの演算は通信無しで可能であり、ｖ＊ｗの演算は通信が必要である。
【００６４】
基本的には上述したbit分散の場合と同じ導出になるので、詳しい説明については省略する。
【００６５】
次に、関連技術における比較演算について説明する。
整数 ｖ, ｗ の比較（例えば ｖ <= ｗ）は、bit分散して、ＸＯＲとＡＮＤとの組み合わせで計算可能である。
【００６６】
例えば、ｖ, ｗが１bitであるとする。この場合は、次式により比較（ｖ <= ｗ）が計算可能である。
(ｖ<=ｗ) ＝ (１∧ｖ)∧(ｖ＆ｗ)
したがって、比較には、ＡＮＤが一回、ＸＯＲが二回必要である。
【００６７】
これを秘密計算で行えば、秘密分散されているｖ,ｗに対して計算可能である。
そのため、３２bit整数の場合は、より多くのＡＮＤとＸＯＲが必要となる。
【００６８】
さらに、比較したい整数ｖ,ｗがring分散されており、比較結果をring分散で得たい場合は、次の処理が必要となる。
1) ｖ,ｗをring分散からbit分散に変換する（ビット分解）。
2) 上記のようにＡＮＤ／ＸＯＲで比較結果を計算する。
3) 結果をbit分散からring分散に変換する（ビット結合）。
このように、関連技術では、整数ｖ,ｗの比較演算にＡＮＤ／ＸＯＲが必要であり、計算時間が長くなるという課題がある。
【００６９】
［発明の概要］
次に、本発明の提案手法の原理について、（ａ <= ｂ）の場合の比較を例に挙げて説明する。
【００７０】
この場合、二つの整数ａ,ｂを、第１乃至第３の秘密計算装置に分散して保持する。
ring分散    ａ ＝ ａ０＋ａ１＋ａ２
ｂ ＝ ｂ０＋ｂ１＋ｂ２
であるとする。この場合、第１乃至第３の秘密計算装置（Party0、Party1、およびParty2）は、
Party0:  (ａ２, ａ０), (ｂ２, ｂ０)
Party1:  (ａ０, ａ１), (ｂ０, ｂ１)
Party2:  (ａ１, ａ２), (ｂ１, ｂ２)
を保持する。
【００７１】
したがって、第１乃至第３の秘密計算装置の加減算回路部は、二つの整数ａ,ｂそのものではなく、これらの分散した値を使用して加減算を行なうことに注意されたい。
【００７２】
以下では、０ <= ａ, ｂ < ２^ｋ に限った場合を実装する例について説明する。ここで、２^ｋは、２のｋ乗を表し、ｋは１以上の整数である。尚、変数にuint32_tを使えばｋ＝３１まで可能である。
【００７３】
ｃ ＝ ２^ｋ−ａ として、（ｂ＋ｃ)／(ａ＋ｃ)を計算する。
ここで、演算子／は、分子を分母で割り算して得られる結果（除算結果）の整数部分を求める関数である。換言すれば、演算子／は、除算結果の少数点以下を切り捨てて整数にする関数である。
【００７４】
２^ｋ <= ａ＋ｃ, ｂ＋ｃ < ２^(ｋ＋１)なので、次式が得られる。 
(ｂ＋ｃ)／(ａ＋ｃ) ＝ １  (ａ <= ｂ)
０  (ａ > ｂ)
【００７５】
また、ａ＋ｃ ＝ ２^ｋ なので、次式が成り立つ。
(ｂ＋ｃ)／(ａ＋ｃ) ＝ (ｂ＋ｃ)／２^ｋ
上式の右辺は、(ｂ＋ｃ)を２^ｋで割る（ｋビット右シフトする）ことに相当し、もしくは、k+1ビット目が比較結果を表していることを示している。また、シフトはbit分散で可能である。
【００７６】
次に、<ｋビット右シフトについて>説明する。
ｖ ＝ ｖ０∧ｖ１∧ｖ２
のとき、
ｖ >> ｋ ＝ (ｖ０ >> ｋ)∧(ｖ１ >> ｋ)∧(ｖ２ >> ｋ)
なので、秘密計算が可能である。
【００７７】
したがって、本発明の提案手法では、ａ <= ｂの場合の計算手順は次のようになる。
【００７８】
ａ, ｂが２^ｋより小さく、rinｇ分散されている場合の手順は次の通りである。
(1) ｂ＋2^ｋ−ａをring分散で計算(２^ｋは定数である）する。
(2) 結果(ｂ＋2^ｋ−ａ)をbit分散に変換する（ビット分解）。
(3) ｋビットシフトする。
(4) 結果をring分散に変換する(ビット結合)
【００７９】
尚、結果がbit分散で良い場合は、(4)のステップは不要である。また、(3)のステップの代わりに、ｋ+1ビット目を抽出してもよい。
【００８０】
次に、ａ <= ｂの比較以外への応用について説明する。
【００８１】
以下のようにすることで、ａ <= ｂの比較以外にも応用可能である。
ａ < ｂの比較のときは、ａ＋１ <= ｂを計算する。
ａ > ｂ、 ａ >= ｂの比較のときは、ａとｂを入れ替えて計算する。
以上を纏めると、次のようになる。
【００８２】
整数ａ,ｂが０ <= ａ, ｂ < ２^ｋの時、ａ <= ｂを、 (ｂ＋ｃ)／(ａ＋ｃ)で計算すること。
【００８３】
二つの整数ａ,ｂが秘密分散されていたときに、比較を上記の手順で秘密計算で行うこと。
【００８４】
［実施形態］
最初に、図２を参照して、本発明の一実施形態に係る秘密計算システム１Ａについて説明する。
【００８５】
図２は秘密計算システム１Ａの構成を示すブロック図である。秘密計算システム１Ａは、第１乃至第３の秘密計算装置１Ａ−１、１Ａ−２、および１Ａ−３から成る。
【００８６】
第１乃至第３の秘密計算装置１Ａ−１〜１Ａ−３は、後述するように、二つの整数の比較演算を行うことが可能な装置である。勿論、第１乃至第３の秘密計算装置１Ａ−１〜１Ａ−３は、比較演算以外の演算をも行うことができるが、それらは本発明とは関連がないので説明を省略する。
【００８７】
第１乃至第３の秘密計算装置１Ａ−１〜１Ａ−３は、同じ構成をしている。
【００８８】
詳述すると、第１の秘密計算装置１Ａ−１は、第１の加減算回路部１００−１と、第１のビット分解回路部２００−１と、第１のビット抽出回路部３００−１とを備える。同様に、第２の秘密計算装置１Ａ−２は、第２の加減算回路部１００−２と、第２のビット分解回路部２００−２と、第２のビット抽出回路部３００−２とを備える。第３の秘密計算装置１Ａ−３は、第３の加減算回路部１００−３と、第３のビット分解回路部２００−３と、第３のビット抽出回路部３００−３とを備える。
【００８９】
第１の秘密計算装置１Ａ−１は、破線で示されるように、第１のビット結合回路部４００−１を更に備えてもよい。同様に、第２の秘密計算装置１Ａ−２は、第２のビット結合回路部４００−２を更に備えてもよく、第３の秘密計算装置１Ａ−３は、第３のビット結合回路部４００−３を更に備えてもよい。
【００９０】
このように、第１乃至第３の秘密計算装置１Ａ−１〜１Ａ−３は同じ構成をしているので、説明を簡略化するために、以下では、第１の秘密計算装置１Ａ−１を代表して説明する。
【００９１】
０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されているとする。この場合、第１の秘密計算装置１Ａ−１は、次のように、第１の整数ａと第２の整数ｂとを比較する。以下では、第１の整数ａが第２の整数ｂ以下である（ａ <= ｂ）か否かを検出する場合を例に挙げて説明する。
【００９２】
第１の加減算回路部１００−１は、第１の整数ａと第２の整数ｂと２^ｋとを用いてring分散で所定の加減算を行い、第１の加減算結果を出力する。具体的には、第１の加減算回路部１００−１は、ring分散で所定の加減算として(ｂ＋2^ｋ−ａ)を計算し、この(ｂ＋2^ｋ−ａ)を第１の加減算結果として出力する。
【００９３】
第１のビット分解回路部２００−１は、第１の加減算結果をbit分散に変換して、第１のbit分散された結果を出力する。
【００９４】
第１のビット抽出回路部３００−１は、第１のbit分散された結果のｋ+1ビット目を抽出して、第１の抽出結果を出力する。第１のビット抽出回路部３００−１は、第１のbit分散された結果をｋビット右シフトして、第１の抽出結果として第１のシフト結果を出力する第１のシフト回路部として実現可能である。
【００９５】
第１のビット結合回路部４００−１は、第１の抽出結果をring分散に変換して、第１のring分散された結果を出力する。
【００９６】
（ａ <= ｂ）以外の他の比較計算も次のように行うことができる。
【００９７】
第１の整数ａが第２の整数ｂより小さい（ａ < ｂ）か否かを検出するとする。この場合、第１の加減算回路部１００−１は、ring分散で上記所定の加減算として(ｂ＋2^ｋ−(ａ＋１))を計算し、この(ｂ＋2^ｋ−(ａ＋１))を第１の加減算結果として出力する。ただし、この方法は、ａ＋１ < 2^ｋの場合に利用可能である。
【００９８】
また、第１の整数ａが第２の整数ｂ以上である（ａ >= ｂ）か否かを検出するとする。この場合、第１の加減算回路部２００−１は、ring分散で上記所定の加減算として(ａ＋2^ｋ−ｂ)を計算し、この(ａ＋2^ｋ−ｂ)を第１の加減算結果として出力する。
【００９９】
最後に、第１の整数ａが第２の整数ｂより大きい（ａ > ｂ）か否かを検出するとする。この場合、第１の加減算回路部２００−１は、ring分散で上記所定の加減算として(ａ＋2^ｋ−(ｂ＋１))を計算し、この(ａ＋2^ｋ−(ｂ＋１))を第１の加減算結果として出力する。ただし、この方法は、ａ＋１ < 2^ｋの場合に利用可能である。
【０１００】
このように、本実施形態では、ＡＮＤ／ＸＯＲ演算なしに、比較計算を行うことが可能である。
【実施例１】
【０１０１】
次に、本発明の第１の実施例について説明する。【０１０２】
図３は、図２に示した秘密計算システム１Ａに用いられる第ｎの秘密計算装置１Ａ−ｎ（ｎは、１、２、３の整数）を示すブロック図である。【０１０３】
第ｎの秘密計算装置１Ａ−ｎは、加減算回路部１００と、ビット分解回路部２００と、ビット抽出回路部３００とを備える。第ｎの秘密計算装置１Ａ−ｎは、破線で示されるように、ビット結合回路部４００を更に備えてもよい。【０１０４】
加減算回路部１００には、０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂと、２^ｋとが供給される。加減算回路部１００は、第１の整数ａと第２の整数ｂと２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する。本例では、比較演算として、第１の整数ａが第２の整数ｂ以下である（ａ <= ｂ）か否かを検出するとする。この場合、加減算回路部１００は、ring分散で上記所定の加減算として(ｂ＋2^ｋ−ａ)を計算し、この(ｂ＋2^ｋ−ａ)を加減算結果として出力する。【０１０５】
加減算結果はビット分解回路部２００へ供給される。ビット分解回路部２００は、加減算結果をbit分散に変換して、bit分散された結果を出力する。【０１０６】
bit分散された結果はビット抽出回路３００へ供給される。ビット抽出回路部３００は、bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力する。なお、ビット抽出回路部３００は、bit分散された結果をｋビット右シフトして、抽出結果としてシフト結果を出力するシフト回路部として実現可能である。【０１０７】
シフト結果は、ビット結合回路部４００へ供給される。ビット結合回路部４００は、シフト結果をring分散に変換して、ring分散された結果を出力する。【０１０８】
図４は、図３に示した第ｎの秘密計算装置１Ａ−ｎの動作を説明するためのフローチャートである。【０１０９】
加減算回路部１００は、(ｂ＋2^ｋ−ａ)をring分散で計算して、この(ｂ＋2^ｋ−ａ)を加減算結果として出力する（ステップＳ１０１）。【０１１０】
次に、ビット分解回路部２００は、加減算結果をbit分散に変換して、bit分散された結果を出力する（ステップＳ１０２）。【０１１１】
引き続いて、ビット抽出回路部３００は、bit分散された結果をｋビット右シフトして、抽出結果としてシフト結果を出力する（ステップＳ１０３）。【０１１２】
オプションとして、ビット結合回路部４００は、シフト結果をring分散に変換して、ring分散された結果を出力する（ステップＳ１０４）。【０１１３】
（ａ <= ｂ）以外の他の比較計算も、上述したように、加減算回路部１００が所定の加減算を行うことにより可能である。【０１１４】
次に、本発明の第１の実施例の効果について説明する。【０１１５】
本比較方法を用いれば、ＡＮＤ／ＸＯＲ演算なしに、比較計算を行うことが可能となる効果を奏する。
【実施例２】
【０１１６】
次に、本発明の第２の実施例について説明する。【０１１７】
この第２の実施例では、<2^4(=16)の環での例>について説明する。ここでは、k=3 (2^k=8) とする。そして、本例では、a=5, b=7でa<=bを計算する場合について説明する。【０１１８】
まず、a,b,2^kは以下のようにring分散されているとする。
a=7+6+8           (=21%16=5)
b=9+3+11          (=23%16=7)
2^k=1+15+8        (=24%16=8)
ここで、％は、modを意味し、法として合同であることを示す。従って、例えば、21%16=5は、２１を１６で割ったときの余りが５に等しいことを示している。【０１１９】
各パーティで(b+2^k-a)を計算する。尚、n=4である。
party0: (b + 2^k - a) % 2^n = ( 9 +  1 -  7) % 16 =  3
party1: (b + 2^k - a) % 2^n = ( 3 + 15 -  6) % 16 = 12
party2: (b + 2^k - a) % 2^n = (11 +  8 -  8) % 16 = 11
なお，この加減算結果を複号すると、(3 + 12 + 11)%16=10 である。【０１２０】
この加減算結果をbit分解して得られた、bit分散された結果が以下である。
party0: 1111
party1: 0110
party2: 0011
なお、これを復号すると、1111 ∧ 0110 ∧ 0011 = 1010 (10進数で10)である。k+1 ビット目（すなわち4ビット目）は1であり，これがa<=b(5<=7)の結果を表している。【０１２１】
k+1ビット目を取り出すために、kビット右シフトを行うと、以下のようになる。
party0: 0001
party1: 0000
party2: 0000
なお、これを復号すると、  0000∧0001∧0000=0001であり、a<=bの結果のbit分散である。【０１２２】
ring分散で結果を得るために、bit結合を行うと以下のようになる。
party0:  1
party1:  4
party2: 12
これを復号すると、(1+4+12)%16=1であり、a<=bの結果のring分散である。【０１２３】
このように、第２の実施例によれば、ＡＮＤ／ＸＯＲ演算なしに、比較計算を行うことが可能となることが分かる。【０１２４】
なお、本発明は、上記実施形態や上記実施例そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、上記実施形態（実施例）では、秘密計算装置が３台ある秘密計算システムの場合についてのみ説明している。しかしながら、本発明は、一般的に、秘密計算装置がＮ台（Ｎは３以上の整数）ある秘密計算システムの場合にも同様に適用できるのは言うまでもない。【０１２５】
なお、本発明に記載した方法は、コンピュータに実行させることができる。この方法を実行させるプログラムは、フロッピー（登録商標）ディスク、ハードディスクなどの磁気ディスク、ＣＤ-ＲＯＭ（Compact Disc- Read Only Memory）、ＤＶＤ（digital versatile disc）などの光ディスク、光磁気ディスク（magneto-optical disc）、半導体メモリなどの記録媒体に格納して頒布することもできる。【０１２６】
また、この記録媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記録媒体であれば、その記憶形式は何れの形態であってもよい。【０１２７】
また、記録媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているオペレーティングシステムや、データベース管理ソフト、ネットワークソフト等のミドルウェアなどが各処理の一部を実行してもよい。【０１２８】
さらに、本発明における記録媒体は、コンピュータと独立した媒体に限らず、ＬＡＮ（Local Area Network）やインターネットなどにより伝送されたプログラムをダウンロードして記憶または一時記憶した記録媒体も含まれる。【０１２９】
また、記録媒体は１つに限らず、複数の媒体から上記実施形態（実施例）における処理が実行される場合も本発明における記録媒体に含まれ、媒体構成は何れの構成であってもよい。【０１３０】
本発明におけるコンピュータは、記録媒体に記憶されたプログラムに基づき各処理を実行するものであって、パソコンなどからなる装置、複数の装置がネットワーク接続されたシステムなどの何れの構成であってもよい。【０１３１】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置を含み、プログラムによって本発明の機能を実現することが可能な機器、装置である。【０１３２】
すなわち、第ｎの秘密計算装置１Ａ−ｎの各部は、ハードウェアとソフトウェアとの組み合わせを用いて実現可能である。ハードウェアとソフトウェアとを組み合わせた形態では、ＲＡＭ（random access memory）に比較プログラムが展開され、該比較プログラムに基づいて制御部（ＣＰＵ（central processing unit））等のハードウェアを動作させることによって、各部を各種手段として実現する。そして、該比較プログラムは、上述したように、記録媒体に記録されて頒布されても良い。当該記録媒体に記録された顔認証プログラムは、有線、無線、又は記録媒体そのものを介して、メモリに読込まれ、制御部等を動作させる。尚、記録媒体を例示すれば、オプティカルディスクや磁気ディスク、半導体メモリ装置、ハードディスクなどが挙げられる。【０１３３】
上記実施の形態を別の表現で説明すれば、第ｎの秘密計算装置１Ａ−ｎとして動作させるコンピュータを、ＲＡＭに展開された比較プログラムに基づき、加減算回路部１００、ビット分解回路部２００、ビット抽出回路部３００、およびビット結合回路部４００として動作させることで実現することが可能である。【０１３４】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。【０１３５】
（付記１）  ０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されている場合に、前記第１の整数ａと前記第２の整数ｂとを比較する秘密計算装置であって、
前記第１の整数ａと前記第２の整数ｂと前記２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する加減算回路部と、
前記加減算結果をbit分散に変換して、bit分散された結果を出力するビット分解回路部と、
前記bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力するビット抽出回路部と、
を備える秘密計算装置。【０１３６】
（付記２）  前記ビット抽出回路部は、前記bit分散された結果をｋビット右シフトして、前記抽出結果としてシフト結果を出力するシフト回路部から成る、付記１に記載の秘密計算装置。【０１３７】
（付記３）  前記シフト結果をring分散に変換して、ring分散された結果を出力するビット結合回路部を更に備える、付記２に記載の秘密計算装置。【０１３８】
（付記４）  前記第１の整数ａが前記第２の整数ｂ以下であるか否かを検出する場合、
前記加減算回路部は、ring分散で前記所定の加減算として(ｂ＋2^ｋ−ａ)を計算し、該(ｂ＋2^ｋ−ａ)を前記加減算結果として出力する、付記１乃至３のいずれか１項に記載の秘密計算装置。【０１３９】
（付記５）  前記第１の整数ａが前記第２の整数ｂより小さいか否かを検出する場合、
前記加減算回路部は、ring分散で前記所定の加減算として(ｂ＋2^ｋ−(ａ＋１))を計算し、該(ｂ＋2^ｋ−(ａ＋１))を前記加減算結果として出力する、付記１乃至３のいずれか１項に記載の秘密計算装置。【０１４０】
（付記６）  前記第１の整数ａが前記第２の整数ｂ以上であるか否かを検出する場合、
前記加減算回路部は、ring分散で前記所定の加減算として(ａ＋2^ｋ−ｂ)を計算し、該(ａ＋2^ｋ−ｂ)を前記加減算結果として出力する、付記１乃至３のいずれか１項に記載の秘密計算装置。【０１４１】
（付記７）  前記第１の整数ａが前記第２の整数ｂより大きいか否かを検出する場合、
前記加減算回路部は、ring分散で前記所定の加減算として(ａ＋2^ｋ−(ｂ＋１))を計算し、該(ａ＋2^ｋ−(ｂ＋１))を前記加減算結果として出力する、付記１乃至３のいずれか１項に記載の秘密計算装置。【０１４２】
（付記８）  付記１乃至７のいずれか１項に記載の秘密計算装置を、Ｎ（Ｎは３以上の整数）台備えてなる、秘密計算システム。【０１４３】
（付記９）  ０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されている場合に、秘密計算装置において前記第１の整数ａと前記第２の整数ｂとを比較する方法であって、
前記第１の整数ａと前記第２の整数ｂと前記２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する加減算ステップと、
前記加減算結果をbit分散に変換して、bit分散された結果を出力するビット分解ステップと、
前記bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力するビット抽出ステップと、
を含む比較方法。【０１４４】
（付記１０）  前記ビット抽出ステップは、前記bit分散された結果をｋビットシフトするシフトステップから成る、付記９に記載の比較方法。【０１４５】
（付記１１）  前記シフト結果をring分散に変換して、ring分散された結果を出力するビット結合ステップを更に備える、付記１０に記載の比較方法。【０１４６】
（付記１２）  前記第１の整数ａが前記第２の整数ｂ以下であるか否かを検出する場合、
前記加減算ステップは、ring分散で前記所定の加減算として(ｂ＋2^ｋ−ａ)を計算し、該(ｂ＋2^ｋ−ａ)を前記加減算結果として出力する、付記９乃至１１のいずれか１項に記載の比較方法。【０１４７】
（付記１３）  前記第１の整数ａが前記第２の整数ｂより小さいか否かを検出する場合、
前記加減算ステップは、ring分散で前記所定の加減算として(ｂ＋2^ｋ−(ａ＋１))を計算し、該(ｂ＋2^ｋ−(ａ＋１))を前記加減算結果として出力する、付記９乃至１１のいずれか１項に記載の比較方法。【０１４８】
（付記１４）  前記第１の整数ａが前記第２の整数ｂ以上であるか否かを検出する場合、
前記加減算ステップは、ring分散で前記所定の加減算として(ａ＋2^ｋ−ｂ)を計算し、該(ａ＋2^ｋ−ｂ)を前記加減算結果として出力する、付記９乃至１１のいずれか１項に記載の比較方法。【０１４９】
（付記１５）  前記第１の整数ａが前記第２の整数ｂより大きいか否かを検出する場合、
前記加減算ステップは、ring分散で前記所定の加減算として(ａ＋2^ｋ−(ｂ＋１))を計算し、該(ａ＋2^ｋ−(ｂ＋１))を前記加減算結果として出力する、付記９乃至１１のいずれか１項に記載の比較方法。【０１５０】
（付記１６）  ０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されている場合に、秘密計算装置であるコンピュータに、前記第１の整数ａと前記第２の整数ｂとを比較させる比較プログラムを記録した記録媒体であって、前記比較プログラムは、前記コンピュータに、
前記第１の整数ａと前記第２の整数ｂと前記２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する加減算機能と、
前記加減算結果をbit分散に変換して、bit分散された結果を出力するビット分解機能と、
前記bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力するビット抽出機能と、
を実現させるための比較プログラム記録媒体。【０１５１】
（付記１７）  前記ビット抽出機能は、前記bit分散された結果をｋビットシフトするシフト機能から成る、付記１６に記載の比較プログラム記録媒体。【０１５２】
（付記１８）  前記比較プログラムは、前記コンピュータに、前記シフト結果をring分散に変換して、ring分散された結果を出力するビット結合機能を更に実現させる、付記１７に記載の比較プログラム記録媒体。【０１５３】
（付記１９）  前記第１の整数ａが前記第２の整数ｂ以下であるか否かを検出する場合、
前記加減算機能は、ring分散で前記所定の加減算として(ｂ＋2^ｋ−ａ)を計算し、該(ｂ＋2^ｋ−ａ)を前記加減算結果として出力する、付記１６乃至１８のいずれか１項に記載の比較プログラム記録媒体。【０１５４】
（付記２０）  前記第１の整数ａが前記第２の整数ｂより小さいか否かを検出する場合、
前記加減算機能は、ring分散で前記所定の加減算として(ｂ＋2^ｋ−(ａ＋１))を計算し、該(ｂ＋2^ｋ−(ａ＋１))を前記加減算結果として出力する、付記１６乃至１８のいずれか１項に記載の比較プログラム記録媒体。【０１５５】
（付記２１）  前記第１の整数ａが前記第２の整数ｂ以上であるか否かを検出する場合、
前記加減算機能は、ring分散で前記所定の加減算として(ａ＋2^ｋ−ｂ)を計算し、該(ａ＋2^ｋ−ｂ)を前記加減算結果として出力する、付記１６乃至１８のいずれか１項に記載の比較プログラム記録媒体。【０１５６】
（付記２２）  前記第１の整数ａが前記第２の整数ｂより大きいか否かを検出する場合、
前記加減算機能は、ring分散で前記所定の加減算として(ａ＋2^ｋ−(ｂ＋１))を計算し、該(ａ＋2^ｋ−(ｂ＋１))を前記加減算結果として出力する、付記１６乃至１８のいずれか１項に記載の比較プログラム記録媒体。【０１５７】
この出願は、２０１７年５月１８日に出願された日本出願特願２０１７−９８８５３を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０１５８】
１Ａ    秘密計算システム
１Ａ−１    第１の秘密計算装置
１Ａ−２    第２の秘密計算装置
１Ａ−３    第３の秘密計算装置
１Ａ−ｎ    第ｎの秘密計算装置
１００、１００−１〜１００−３    加減算回路部
２００、２００−１〜２００−３    ビット分解回路部
３００、３００−１〜３００−３    ビット抽出回路部（シフト回路部）
４００、４００−１〜４００−３    ビット結合回路部
【図１】
2018212015.tif 000003
【図２】
2018212015.tif 000004
【図３】
2018212015.tif 000005
【図４】
2018212015.tif 000006
【手続補正書】
【提出日】令和1年11月8日(2019.11.8)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されている場合に、前記第１の整数ａと前記第２の整数ｂとを比較する秘密計算装置であって、
前記第１の整数ａと前記第２の整数ｂと前記２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する加減算回路部と、
前記加減算結果をbit分散に変換して、bit分散された結果を出力するビット分解回路部と、
前記bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力するビット抽出回路部と、
を備える秘密計算装置。
【請求項２】
前記ビット抽出回路部は、前記bit分散された結果をｋビット右シフトして、前記抽出結果としてシフト結果を出力するシフト回路部から成る、請求項１に記載の秘密計算装置。
【請求項３】
前記シフト結果をring分散に変換して、ring分散された結果を出力するビット結合回路部を更に備える、請求項２に記載の秘密計算装置。
【請求項４】
前記第１の整数ａが前記第２の整数ｂ以下であるか否かを検出する場合、
前記加減算回路部は、ring分散で前記所定の加減算として(ｂ＋2^ｋ−ａ)を計算し、該(ｂ＋2^ｋ−ａ)を前記加減算結果として出力する、請求項１乃至３のいずれか１項に記載の秘密計算装置。
【請求項５】
前記第１の整数ａが前記第２の整数ｂより小さいか否かを検出する場合、
前記加減算回路部は、ring分散で前記所定の加減算として(ｂ＋2^ｋ−(ａ＋１))を計算し、該(ｂ＋2^ｋ−(ａ＋１))を前記加減算結果として出力する、請求項１乃至３のいずれか１項に記載の秘密計算装置。
【請求項６】
前記第１の整数ａが前記第２の整数ｂ以上であるか否かを検出する場合、
前記加減算回路部は、ring分散で前記所定の加減算として(ａ＋2^ｋ−ｂ)を計算し、該(ａ＋2^ｋ−ｂ)を前記加減算結果として出力する、請求項１乃至３のいずれか１項に記載の秘密計算装置。
【請求項７】
前記第１の整数ａが前記第２の整数ｂより大きいか否かを検出する場合、
前記加減算回路部は、ring分散で前記所定の加減算として(ａ＋2^ｋ−(ｂ＋１))を計算し、該(ａ＋2^ｋ−(ｂ＋１))を前記加減算結果として出力する、請求項１乃至３のいずれか１項に記載の秘密計算装置。
【請求項８】
請求項１乃至７のいずれか１項に記載の秘密計算装置を、Ｎ（Ｎは３以上の整数）台備えてなる、秘密計算システム。
【請求項９】
０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されている場合に、秘密計算装置において前記第１の整数ａと前記第２の整数ｂとを比較する方法であって、
前記第１の整数ａと前記第２の整数ｂと前記２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する加減算ステップと、
前記加減算結果をbit分散に変換して、bit分散された結果を出力するビット分解ステップと、
前記bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力するビット抽出ステップと、
を含む比較方法。
【請求項１０】
０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されている場合に、秘密計算装置であるコンピュータに、前記第１の整数ａと前記第２の整数ｂとを比較させる比較プログラムであって、前記コンピュータに、
前記第１の整数ａと前記第２の整数ｂと前記２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する加減算機能と、
前記加減算結果をbit分散に変換して、bit分散された結果を出力するビット分解機能と、
前記bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力するビット抽出機能と、
を実現させるための比較プログラム。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は、秘密計算装置、比較方法、比較プログラム、および秘密計算システムに関する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
本発明の目的は、上記課題を解決できる秘密計算装置、比較方法、比較プログラム、および秘密計算システムを提供することにある。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００３４
【補正方法】変更
【補正の内容】
【００３４】
本発明の比較プログラムは、０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されている場合に、秘密計算装置であるコンピュータに、前記第１の整数ａと前記第２の整数ｂとを比較させる比較プログラムであって、前記コンピュータに、前記第１の整数ａと前記第２の整数ｂと前記２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する加減算機能と；前記加減算結果をbit分散に変換して、bit分散された結果を出力するビット分解機能と；前記bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力するビット抽出機能と；を実現させる。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００３５
【補正方法】変更
【補正の内容】
【００３５】
本発明によれば、ＡＮＤ／ＸＯＲ演算なしに、比較計算を行うことが可能な秘密計算装置、比較方法、比較プログラム、および秘密計算システムを提供できる。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００４３
【補正方法】変更
【補正の内容】
【００４３】
一方、ring分散は、次式で表される。
ｖ ＝ ｖ０＋ｖ１＋ｖ２
ここで、演算子＋は、ring上の加法（加算）を表す。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００５７
【補正方法】変更
【補正の内容】
【００５７】
次に、ＡＮＤ（論理積）の場合の秘密計算について説明する。
ｖ＆ｗは、次式で表される。
ｖ＆ｗ ＝ (ｖ０∧ｖ１∧ｖ２)＆(ｗ０∧ｗ１∧ｗ２)
＝ (ｖ０＆ｗ０)∧(ｖ０＆ｗ２)∧(ｖ２＆ｗ０)
∧ (ｖ１＆ｗ１)∧(ｖ１＆ｗ０)∧(ｖ０＆ｗ１)
∧ (ｖ２＆ｗ２)∧(ｖ２＆ｗ１)∧(ｖ１＆ｗ２)
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００５８
【補正方法】変更
【補正の内容】
【００５８】
各パーティ１−１〜１−３が、ｍ０∧ｍ１∧ｍ２ ＝ ０ の乱数を用いて、次式を計算する。
Party0: ｘ０ ＝ (ｖ０＆ｗ０)∧(ｖ０＆ｗ２)∧(ｖ２＆ｗ０)∧ｍ０
Party1: ｘ１ ＝ (ｖ１＆ｗ１)∧(ｖ１＆ｗ０)∧(ｖ０＆ｗ１)∧ｍ１
Party2: ｘ２ ＝ (ｖ２＆ｗ２)∧(ｖ２＆ｗ１)∧(ｖ１＆ｗ２)∧ｍ２
この場合、次式が成り立つ。
ｘ０∧ｘ１∧ｘ２ ＝ ｖ＆ｗ
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００９８
【補正方法】変更
【補正の内容】
【００９８】
また、第１の整数ａが第２の整数ｂ以上である（ａ >= ｂ）か否かを検出するとする。この場合、第１の加減算回路部１００−１は、ring分散で上記所定の加減算として(ａ＋2^ｋ−ｂ)を計算し、この(ａ＋2^ｋ−ｂ)を第１の加減算結果として出力する。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００９９
【補正方法】変更
【補正の内容】
【００９９】
最後に、第１の整数ａが第２の整数ｂより大きい（ａ > ｂ）か否かを検出するとする。この場合、第１の加減算回路部１００−１は、ring分散で上記所定の加減算として(ａ＋2^ｋ−(ｂ＋１))を計算し、この(ａ＋2^ｋ−(ｂ＋１))を第１の加減算結果として出力する。ただし、この方法は、ａ＋１ < 2^ｋの場合に利用可能である。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】０１３２
【補正方法】変更
【補正の内容】
【０１３２】
すなわち、第ｎの秘密計算装置１Ａ−ｎの各部は、ハードウェアとソフトウェアとの組み合わせを用いて実現可能である。ハードウェアとソフトウェアとを組み合わせた形態では、ＲＡＭ（random access memory）に比較プログラムが展開され、該比較プログラムに基づいて制御部（ＣＰＵ（central processing unit））等のハードウェアを動作させることによって、各部を各種手段として実現する。そして、該比較プログラムは、上述したように、記録媒体に記録されて頒布されても良い。当該記録媒体に記録された比較プログラムは、有線、無線、又は記録媒体そのものを介して、メモリに読込まれ、制御部等を動作させる。尚、記録媒体を例示すれば、オプティカルディスクや磁気ディスク、半導体メモリ装置、ハードディスクなどが挙げられる。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】０１５０
【補正方法】変更
【補正の内容】
【０１５０】
（付記１６）  ０以上で２^ｋ（ｋは１以上の整数）より小さい、第１の整数ａおよび第２の整数ｂがring分散されている場合に、秘密計算装置であるコンピュータに、前記第１の整数ａと前記第２の整数ｂとを比較させる比較プログラムであって、前記コンピュータに、
前記第１の整数ａと前記第２の整数ｂと前記２^ｋとを用いてring分散で所定の加減算を行い、加減算結果を出力する加減算機能と、
前記加減算結果をbit分散に変換して、bit分散された結果を出力するビット分解機能と、
前記bit分散された結果のｋ+1ビット目を抽出して、抽出結果を出力するビット抽出機能と、
を実現させるための比較プログラム。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】０１５１
【補正方法】変更
【補正の内容】
【０１５１】
（付記１７）  前記ビット抽出機能は、前記bit分散された結果をｋビットシフトするシフト機能から成る、付記１６に記載の比較プログラム。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】０１５２
【補正方法】変更
【補正の内容】
【０１５２】
（付記１８）  前記比較プログラムは、前記コンピュータに、前記シフト結果をring分散に変換して、ring分散された結果を出力するビット結合機能を更に実現させる、付記１７に記載の比較プログラム。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】０１５３
【補正方法】変更
【補正の内容】
【０１５３】
（付記１９）  前記第１の整数ａが前記第２の整数ｂ以下であるか否かを検出する場合、
前記加減算機能は、ring分散で前記所定の加減算として(ｂ＋2^ｋ−ａ)を計算し、該(ｂ＋2^ｋ−ａ)を前記加減算結果として出力する、付記１６乃至１８のいずれか１項に記載の比較プログラム。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】０１５４
【補正方法】変更
【補正の内容】
【０１５４】
（付記２０）  前記第１の整数ａが前記第２の整数ｂより小さいか否かを検出する場合、
前記加減算機能は、ring分散で前記所定の加減算として(ｂ＋2^ｋ−(ａ＋１))を計算し、該(ｂ＋2^ｋ−(ａ＋１))を前記加減算結果として出力する、付記１６乃至１８のいずれか１項に記載の比較プログラム。
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】０１５５
【補正方法】変更
【補正の内容】
【０１５５】
（付記２１）  前記第１の整数ａが前記第２の整数ｂ以上であるか否かを検出する場合、
前記加減算機能は、ring分散で前記所定の加減算として(ａ＋2^ｋ−ｂ)を計算し、該(ａ＋2^ｋ−ｂ)を前記加減算結果として出力する、付記１６乃至１８のいずれか１項に記載の比較プログラム。
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】０１５６
【補正方法】変更
【補正の内容】
【０１５６】
（付記２２）  前記第１の整数ａが前記第２の整数ｂより大きいか否かを検出する場合、
前記加減算機能は、ring分散で前記所定の加減算として(ａ＋2^ｋ−(ｂ＋１))を計算し、該(ａ＋2^ｋ−(ｂ＋１))を前記加減算結果として出力する、付記１６乃至１８のいずれか１項に記載の比較プログラム。
【国際調査報告】
2018212015.tif 000007
2018212015.tif 000008
2018212015.tif 000009
2018212015.tif 000010