JP5957126B1 - 秘密計算装置、秘密計算方法、およびプログラム - Google Patents

Abstract

【課題】秘密計算による空値検査を効率化する。【解決手段】秘密計算装置は、分散装置が生成した、対象ビット列１１００が表す値の秘密分散値を用い、秘密計算により、対象ビット列１１００をローテーションし、最上位ビットの値を最上位ビットよりも下位の検査ビット１２０１の値とした検査ビット列１２００が表す値の秘密分散値を得る。ただし、対象ビット列１１００は、最上位ビットが１の場合に空値に対応し、最上位ビットが０の場合に実数値に対応する。次に、秘密計算装置は検査ビット列１２００が表す値の秘密分散値を用い、秘密計算により、検査ビット列１２００の最下位ビットから検査ビット１２０１または１２１１までのビット値の秘密分散値を得る。【効果】検査ビットが最下位に近いほど秘密計算の対象となるビット数を小さくでき、通信量および／または通信段数を削減できる。【選択図】図５

Description

本発明は、秘密計算技術に関し、特に、秘密計算で空値検査を行う技術に関する。

秘密計算を用いて符号付き数を扱う技術が知られている（例えば、「非特許文献１」等参照）。

D. Bogdanov, M. Niitsoo, T. Toft, and J. Willemson, "High-performance secure multi-party computation for data mining applications," Int. J. Inf. Sec., 11(6):403-418, 2012.

上記の従来技術には、通信量・通信段数が大きいという課題がある。また秘密計算で空値検査を行うことには言及がない。

本発明の課題は、秘密計算による空値検査を効率化することである。

「第１対象ビット列」が表す値の秘密分散値を用い、「第１対象ビット列」の最上位ビットの値を最上位ビットよりも下位の「第１検査ビット」の値とした「第１検査ビット列」が表す値の秘密分散値を得る。ただし、「第１対象ビット列」は、最上位ビットが１の場合に空値に対応し、最上位ビットが０の場合に実数値に対応する。次に、「第１検査ビット列」が表す値の秘密分散値を用い、「第１検査ビット列」の最下位ビットから「第１検査ビット」までのビット値の秘密分散値を得る。

以上により、秘密計算による空値検査を効率化できる。

図１は実施形態の秘密計算システムの構成を例示したブロック図である。 図２は実施形態の秘密計算装置の構成を例示したブロック図である。 図３は第１実施形態の処理を例示するためのフロー図である。 図４は実施形態の処理を例示するための概念図である。 図５Ａは実施形態の対象ビット列の構成を例示するための概念図である。図５Ｂおよび図５Ｃは実施形態の検査ビット列の構成を例示するための概念図である。 図６は第２実施形態の処理を例示するためのフロー図である。 図７Ａおよび図７Ｂは実施形態の大小比較ビット列の構成を例示するための概念図である。 図８は第２実施形態の変形例１の処理を例示するためのフロー図である。 図９は第３実施形態の処理を例示するためのフロー図である。 図１０は第３実施形態の変形例１の処理を例示するためのフロー図である。

以下、本発明の実施形態を説明する。
［概要］
まず、概要を説明する。各実施形態の秘密計算装置は、「第１対象ビット列」が表す値の秘密分散値を用い、「第１対象ビット列」の最上位ビットの値を最上位ビットよりも下位の「第１検査ビット」の値とした「第１検査ビット列」が表す値の秘密分散値を得る。ただし、「第１対象ビット列」は、最上位ビットが１の場合に空値に対応し、最上位ビットが０の場合に実数値に対応する。なお、「第１検査ビット列」は、例えば「第１対象ビット列」のローテーションによって得られる。ローテーションは剰余環上の乗算で実現できる。秘密計算での剰余環上の乗算方法に限定はなく、公知の方法で実現できる（例えば、参考文献１「千田浩司,濱田浩気，五十嵐大，高橋克巳，“軽量検証可能３パーティ秘匿関数計算の再考”，ＣＳＳ２０１０，２０１０年」等参照）。ただし、これは一例であって、「第１対象ビット列」の最上位ビットの値を「第１検査ビット」の値とできるのであれば、その他の方法が用いられてもよい。次に秘密計算装置は、「第１検査ビット列」が表す値の秘密分散値を用い、「第１検査ビット列」の最下位ビットから「第１検査ビット」までのビット値の秘密分散値を得る。ここで、「第１対象ビット列」が空値に対応する場合には「第１検査ビット」の値は「１」となり、「第１対象ビット列」が実数値に対応する場合には「第１検査ビット」の値は「０」となる。そのため、「第１検査ビット」の値の秘密分散値は、空値検査結果を表す値の秘密分散値となる。また、「第１検査ビット列」の最下位ビットから「第１検査ビット」までのビット値の秘密分散値のみを求めればよいため、すべてのビットの秘密分散値を求めて空値検査結果を表す値の秘密分散値を得る場合に比べ、通信量および／または通信段数を削減できる。また「第１検査ビット」が最下位ビットに近いほど秘密計算の対象となるビット数を小さくでき、通信量および／または通信段数をより削減できる。そのため、「第１検査ビット」が最下位ビットであることがより望ましい。なお、「第１検査ビット列」の最下位ビットから「第１検査ビット」までのビット値の秘密分散値を得るための公知の方法としては、例えば参考文献２「五十嵐大，濱田浩気，菊池亮，千田浩司，“少パーティの秘密分散ベース秘密計算のためのＯ（ｌ）ビット通信ビット分解およびＯ（ｐ’）ビット通信ｍｏｄｕｌｕｓ変換法”，ＣＳＳ２０１３，２０１３年」の「商転移を用いたビット分解」がある。この方法では、最下位ビット（０ビット目）から所望のビットまでの各ビット値の秘密分散値を効率的に得ることができる。なお、最下位ビットから所望のビットまでの各ビット値の秘密分散値のみを効率的に得る方法は知られているが、最上位ビットから所望のビットまでの各ビット値の秘密分散値のみを効率的に得る方法や、最上位ビットと最下位ビットとの間に位置するビット値の秘密分散値のみを効率的に得る方法は知られていない。本形態の方式は、このことに着目して秘密計算での空値検査の効率を向上するものである。

上述の構成はメルセンヌ数Ｐ＝２^Ｎ−１を法とした剰余環上で実現できる。例えば、各秘密計算装置に入力値Ｗの秘密分散値［Ｗ］が入力されるとする。ただし、Ｎは２以上の整数であり、Ｐはメルセンヌ数Ｐ＝２^Ｎ−１であり、Ｎの値によってはメルセンヌ素数となる。空値に対応する値ＷがＷ＝（Ｐ＋１）／２ ｍｏｄ Ｐであり、０以上の整数Ｘに対応する値ＷがＷ＝Ｘ ｍｏｄ Ｐであり、負の整数Ｘに対応する値ＷがＷ＝（Ｐ＋Ｘ） ｍｏｄ Ｐである。Ｌは０≦Ｌ≦Ｎ−ｕ’の整数であり、Ｘは−２^Ｌ≦Ｘ≦２^Ｎ−１−２^Ｌ−１の整数である。ただし、ｕ’は秘密分散方式に応じた２以上Ｎ以下の正の整数である。例えば、2-out-of-3のShamirの秘密分散方式の場合、ｕ’＝２となる。この場合、０以上の整数Ｘは小さな入力値Ｗに対応し、負の整数Ｘは大きな入力値Ｗに対応し、「Ｘが空値であること」はそれらの間の入力値Ｗに対応する。各秘密計算装置は、入力値Ｗの秘密分散値［Ｗ］を用い、Ｙ＝（Ｗ＋２^Ｌ） ｍｏｄ Ｐの秘密分散値［Ｙ］を得る。この演算は秘密計算での剰余環上の加算である。秘密計算での剰余環上の加算方法に限定はなく、公知の方法で実現できる（例えば「参考文献１」等参照）。Ｙは空値に対してＹ＝｛２^Ｌ＋（Ｐ＋１）／２｝ ｍｏｄ Ｐとなり、０以上の整数Ｘに対してＹ＝（２^Ｌ＋Ｘ） ｍｏｄ Ｐとなり、負の整数Ｘに対してＹ＝（Ｐ＋２^Ｌ＋Ｘ） ｍｏｄ Ｐとなる。ここでメルセンヌ数Ｐ＝２^Ｎ−１の性質から、空値に対応するＹを表すＮビットのビット列の最上位ビットは１となり、実数値Ｘ（０以上の整数Ｘまたは負の整数Ｘ）に対応するＹを表すＮビットのビット列の最上位ビットは０となる。−２^Ｌ≦Ｘ≦２^Ｎ−１−２^Ｌ−１の条件を満たす限り、異なる実数値Ｘが同じＹに対応することはない。このようなＹを表すＮビットのビット列を「第１対象ビット列」とすることができる。この場合、「第１検査ビット列」が表す値をＶ＝２^Ｔ×Ｙ ｍｏｄ Ｐとでき、下位からＴビット目のビットを「第１検査ビット」とできる。ただし、Ｔは１≦Ｔ＜Ｎの整数である。好ましくはＴ＝１であり、この場合には「第１検査ビット」が最下位ビットとなる（「第１対象ビット列」および「第１検査ビット列」のフォーマットの具体例）。

上述した秘密計算での空値検査に加え、秘密計算で大小比較が行われてもよい。この場合、各秘密計算装置は、「比較結果値」の秘密分散値を得、「比較結果値」を表すビット列の下位からＫビット目の値の秘密分散値を得る。ただし、「比較結果値」は、「第１対象ビット列」が表す値から「第２対象ビット列」が表す値を減じた値に２^Ｋ−１を加算した値を表す。「第２対象ビット列」は、最上位ビットが１の場合に空値に対応し、最上位ビットが０の場合に実数値に対応するビット列である。また、Ｋが２以上の整数であり、最上位ビットが０の第１対象ビット列が表す値および最上位ビットが０の第２対象ビット列が表す値の大きさは０以上２^Ｋ−１未満である。なお、秘密計算での加減算およびビット値の抽出は公知の方法で実現できる（例えば「参考文献１，２」等参照）。ここで、「第１対象ビット列」が表す値が「第２対象ビット列」が表す値以上である場合、「比較結果値」を表すビット列の下位からＫビット目の値は「１」となる。一方、「第１対象ビット列」が表す値が「第２対象ビット列」が表す値未満である場合、「比較結果値」を表すビット列の下位からＫビット目の値は「０」となる。すなわち、「比較結果値」を表す下位からＫビット目の値は、「第１対象ビット列」が表す値と「第２対象ビット列」が表す値との大小比較結果を表す。

「第２対象ビット列」に対して秘密計算での空値検査が行われてもよい。すなわち、各秘密計算装置が、「第２対象ビット列」が表す値の秘密分散値を用い、「第２対象ビット列」の最上位ビットの値を最上位ビットよりも下位の「第２検査ビット」の値とした「第２検査ビット列」が表す値の秘密分散値を得、「第２検査ビット列」が表す値の秘密分散値を用い、「第２検査ビット」の値の秘密分散値を得てもよい。「第２対象ビット列」および「第２検査ビット列」のフォーマットの具体例は、前述の「第１対象ビット列」および「第１検査ビット列」のフォーマットの具体例と同じである。

上述した秘密計算での空値検査に加え、秘密計算でのソートが行われてもよい。この場合、各秘密計算装置は、「対象ビット列Ａ（ｄ）」が表す値の秘密分散値を用い、「対象ビット列Ａ（ｄ）」の最上位ビットの値を最上位ビットよりも下位の「検査ビット」の値ｒ（ｄ）とした「検査ビット列Ｃ（ｄ）」が表す値の秘密分散値を得る。ただし、ｄ＝０，…，Ｄ−１であり、Ｄが２以上の整数である。「対象ビット列Ａ（ｄ）」は、最上位ビットが１の場合に空値に対応し、最上位ビットが０の場合に実数値に対応する。各秘密計算装置は、「検査ビット列Ｃ（ｄ）」が表す値の秘密分散値を用い、「検査ビット列Ｃ（ｄ）」の最下位ビットから「対象ビット列Ａ（ｄ）」までのビット値の秘密分散値を得る。さらに、各秘密計算装置は、「対象ビット列Ａ（ｄ）」が表す値の大きさに応じたソート結果の秘密分散値を得る。ただし、最上位ビットが０の「対象ビット列Ａ（ｄ）」が表す値は、「対象ビット列Ａ（ｄ）」が表す値が大きいほど大きな実数値に対応する。各秘密計算装置は、「検査ビット列Ｃ（ｄ）」が表す値の大きさに応じたソート結果の秘密分散値を得てもよい。ただし、最上位ビットが０の「対象ビット列Ａ（ｄ）」に対応する「検査ビット列Ｃ（ｄ）」が表す値は、「検査ビット列Ｃ（ｄ）」が表す値が大きいほど大きな実数値に対応する。さらに、この秘密計算でのソート結果を用い、最大値、最小値、および中央値の少なくとも何れかの秘密分散値を得てもよい。なお、秘密計算でのソート方法には限定はなく、公知の方法でよい（例えば、参考文献３「五十嵐大，濱田浩気，菊池亮，千田浩司，“インターネット環境レスポンス１秒の統計処理を目指した，秘密計算基数ソートの改良”，ＳＣＩＳ２０１４，２０１４年」、参考文献４「濱田浩気，五十嵐大，千田浩司，高橋克巳，“秘匿関数計算上の線形時間ソート”，ＣＳＳ２０１１，２０１１年」等参照）。

［第１実施形態］
以降、図面を参照しつつ、各実施形態を説明する。
＜構成＞
図１に例示するように、第１実施形態の秘密計算システム１は、分散装置１１およびＭ個の秘密計算装置１２_０−１２_Ｍ−１を有し、これらはインターネット等のネットワーク経由で通信可能に構成される。ただし、Ｍは２以上の整数である。説明の便宜上、秘密計算システム１が１個の分散装置１１のみを有することにするが、複数個の分散装置１１が存在してもよい。あるいは、その他の秘密計算装置が存在してもよい。

図２に例示するように、本形態の秘密計算装置１２_ｍ（ただし、ｍ＝０，…，Ｍ−１）は、通信部１２１_ｍ、記憶部１２２_ｍ、制御部１２３_ｍ、入力演算部１２４_ｍ、検査ビット列取得部１２５_ｍ、および空値検査部１２６_ｍを有する。秘密計算装置１２_ｍは、制御部１２３_ｍの制御の下で各処理を実行する。各部で得られたデータは、一時メモリ（図示せず）に格納され、必要に応じて読み出されて使用される。

各装置は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。

＜処理＞
次に、図３を参照して本形態の処理を説明する。分散装置１１が入力値Ｗの秘密分散値［Ｗ］_ｍを生成して秘密計算装置１２_ｍ（ただし、ｍ＝０，…，Ｍ−１）に送信する。本形態の入力値Ｗのフォーマットは以下の通りである（図４参照）。
（１）空値に対応する値がＷ＝（Ｐ＋１）／２ ｍｏｄ Ｐである。
（２）０以上の整数であるＸに対応する値がＷ＝Ｘ ｍｏｄ Ｐである。
（３）負の整数であるＸに対応する値がＷ＝（Ｐ＋Ｘ） ｍｏｄ Ｐである。
ただし、Ｎが２以上の整数であり、Ｐがメルセンヌ数Ｐ＝２^Ｎ−１であり、Ｌが０≦Ｌ≦Ｎ−ｕ’の整数であり、Ｘが−２^Ｌ≦Ｘ≦２^Ｎ−１−２^Ｌ−１の整数である。Ｐは素数（メルセンヌ素数）であってもよいし、素数でなくてもよい。入力値ＷをＮ桁２進数で表したビット列を入力ビット列と呼ぶ。Ｎ＝７、ｕ’＝２、およびＬ＝５の場合、入力ビット列は以下のようになる。

なお、秘密分散方式に限定はなく、Ｓｈａｍｉｒの秘密分散方式等の線形秘密分散方式、複製秘密分散方式、その他どのような方式（例えば、「参考文献２」等参照）であってもよい。秘密分散値［Ｗ］_ｍは、秘密計算装置１２_ｍ（図２）の通信部１２１_ｍで受信され、入力演算部１２４_ｍに送られる（ステップＳ１１_ｍ）。

入力演算部１２４_ｍは、秘密計算により、入力値Ｗの秘密分散値［Ｗ］_ｍを用い、Ｙ＝（Ｗ＋２^Ｌ） ｍｏｄ Ｐの秘密分散値［Ｙ］_ｍを得て出力する。空値に対応するＹは｛２^Ｌ＋（Ｐ＋１）／２｝ ｍｏｄ Ｐであり、０以上の整数であるＸに対応するＹは（２^Ｌ＋Ｘ） ｍｏｄ Ｐであり、負の整数であるＸに対応するＹは（Ｐ＋２^Ｌ＋Ｘ） ｍｏｄ Ｐである（図４）。ＹをＮ桁２進数で表したビット列を対象ビット列と呼ぶ。図５Ａに例示するように、Ｙが空値に対応する場合、対象ビット列１１００の最上位ビット１１０１はａ_Ｎ−１＝１となる。Ｙが実数値Ｘ（−２^Ｌ≦Ｘ≦２^Ｎ−１−２^Ｌ−１の整数）に対応する場合、対象ビット列１１００の最上位ビット１１０１はａ_Ｎ−１＝０となる。この特徴はＰがメルセンヌ数であることに基づく。例えば、Ｎ＝７およびＬ＝５の場合、対象ビット列１１００は以下のようになる。

検査ビット列取得部１２５_ｍは、Ｙの秘密分散値［Ｙ］_ｍを入力とし、秘密計算により、Ｖ＝２^Ｔ×Ｙ ｍｏｄ Ｐの秘密分散値［Ｖ］_ｍを得て出力する。ただし、Ｔは１≦Ｔ＜Ｎの整数である。ＶをＮ桁２進数で表したビット列を検査ビット列と呼ぶ。検査ビット列は、対象ビット列１１００をＴビット左ローテーションしたビット列である。対象ビット列１１００の最上位ビット１１０１の値ａ_Ｎ−１は、検査ビット列の最上位ビットよりも下位のビット（検査ビット）の値となる。図５ＢはＴ＝１の例であり、検査ビット列１２００の最下位ビットが検査ビット１２０１となる。図５ＣはＴ＝２の例であり、検査ビット列１２００の最下位から２ビット目が検査ビット１２１１となる。例えば、Ｎ＝７およびＬ＝５の場合、検査ビットは以下のようになる。

このように、検査ビット列１２００の最下位からＴビット目の値が「Ｘが空値であるか否か」を表している（ステップＳ１３_ｍ）。

空値検査部１２６_ｍは、Ｖの秘密分散値［Ｖ］_ｍを入力とし、検査ビット列１２００の最下位ビットから検査ビットまでの各ビット値の秘密分散値［ｒ］_ｍを得て出力する。例えば、Ｔ＝１の場合、空値検査部１２６_ｍは、最下位ビットである検査ビットの値の秘密分散値［ｒ］_ｍを得て出力する。

《参考文献２のビット分解を用いる例》
参考文献２のビット分解を用いる例を示す。この例では、複製秘密分散方式に則った秘密分散値［Ｖ］_ｍを用いる。ただし、任意の線形秘密分散方式に則った秘密分散値を、複製秘密分散方式の秘密分散値に変換することが可能である（例えば、参考文献５「R. Cramer, I. Damg_ard, and Y. Ishai, “Share conversion, pseudorandom secret-sharing and applications to secure computation,” In J. Kilian ed., TCC, Vol. 3378 of Lecture Notes in Computer Science, pp. 342-362. Springer, 2005.」等参照）。そのため、複製秘密分散方式への限定は利用上の制限とはならない。

この例では、Ｖの線形秘密分散値を［Ｖ］と表記し、Ｖの複製秘密分散値を｛Ｖ｝と表記する。Ｖのサブシェアの個数をνとし、自然数である境界値ｕをｌｏｇ ν以上の最小の整数とする。νはν≦２^ｕを満たす整数である。Ｖが２^ｕを法として０と合同となり、ＶがＰを法としてサブシェアｘ_０，…，ｘ_ν-１の和ｘ_０＋…＋ｘ_ν-１と合同であるとする。この例のＰはメルセンヌ素数であるが、Ｐがその他のメルセンヌ数であってもよい。この例では２^ｕＶ＜Ｐとする。ｉをｉ＝０，１,…,ν−１を満たす整数とし、ｊをｊ＝０，１,…,ν−１を満たす整数とする。任意の命題ＰＲＯに対して、〔ＰＲＯ〕は、ＰＲＯの真偽を整数に変換する演算子である。

この例の空値検査部１２６_ｍの公開値倍秘密計算部は、複製秘密分散値｛Ｖ｝^ＺＰを取得して、公開値倍の秘密計算により変形秘密分散値｛Ｖ’｝^ＺＰ＝２^ｕ×_ＺＰ｛Ｖ｝^ＺＰを計算する。ただし、｛・｝^ＺＰはＺ_Ｐの元である複製秘密分散値を表し、「×_ＺＰ」はＺ_Ｐ上での乗算を表す。空値検査部１２６_ｍの下位ビット分散部は、ｉ＜νを満たすすべてのｉについて、変形秘密分散値｛Ｖ’｝^ＺＰのｊ番目のサブシェア｛Ｖ’｝^ＺＰ〈ｊ〉の０ビット目からｕビットをビットごとに分散して下位ビット分散値

を取得する。ただし、[・]^αはαの元である線形秘密分散値を表す。空値検査部１２６_ｍの上位ビット分散部は、ｉ＜νを満たすすべてのｉについて、変形秘密分散値のｊ番目のサブシェア｛Ｖ’｝^ＺＰ〈ｊ〉のｕビット目からＴビットをビットごとに分散して上位ビット分散値

を取得する。空値検査部１２６_ｍの下位ビット加算部は、加算回路の秘密計算により下位ビット加算値

を計算する。この下位ビット加算値のうち下位ｕビットを

上位ｕビットを

と表す。空値検査部１２６_ｍの零判定部は、下位ビット加算値の下位ｕビットを取得して、零判定回路の秘密計算により、零判定値［〔η_ｕ≠０〕］^Ｚ２を計算する。空値検査部１２６_ｍの上位ビット加算部は、ｉ＜νを満たすすべてのｉについて、上位ビット加算値と、下位ビット加算値の上位ｕビットと、零判定値を取得して、加算回路の秘密計算により、ビットの秘密分散列

を計算して出力する。ただし

はＺ_２ ^Ｔ上での総和を表し、

はＺ_２ ^Ｔ上での加算を表す。式（１）の演算により、ＶをＮ桁２進数表記した場合の最下位ビットからＴビット目（すなわち、検査ビット）までの各ビット値の秘密分散値［ｒ］_ｍが得られる。式（１）の演算は最下位ビットからＴビット目までのみについて実行され、その通信量および演算量は全体のビット数Ｎに依存しない。Ｔ＝１の場合、最下位ビットのみについて式（１）の演算を行えばよく、大変効率がよい。特に３パーティの秘密計算では数ビットの通信量と２ラウンドで処理可能である（ステップＳ１４_ｍ）。

秘密計算装置１２_ｍは秘密分散値［ｒ］_ｍを出力する（ステップＳ１５_ｍ）。

[第１実施形態の変形例１]
第１実施形態では、秘密計算装置１２_ｍが秘密分散値［ｒ］_ｍを出力した。しかしながら、Ｔ≧２の場合であっても、秘密分散値［ｒ］_ｍに代えて検査ビット列Ｃの各検査ビットの値の秘密分散値のみが出力されてもよい。

[第１実施形態の変形例２]
第１実施形態では各秘密計算装置１２_ｍに入力値Ｗの秘密分散値［Ｗ］_ｍが入力され、各秘密計算装置１２_ｍがＹ＝（Ｗ＋２^Ｌ） ｍｏｄ Ｐの秘密分散値［Ｙ］_ｍを得た。しかしながら、各秘密計算装置１２_ｍに秘密分散値［Ｙ］_ｍが入力され、ステップＳ１３_ｍからＳ１５_ｍの処理が実行されてもよい。

[第２実施形態]
第２実施形態では、秘密計算での空値検査に加え、秘密計算での大小比較を行う。以下では、これまでに説明した事項との相違点を中心に説明し、既に説明した事項についてはこれまでに用いた参照番号を流用して説明を簡略化する。

＜構成＞
図１に例示するように、第２実施形態の秘密計算システム２は、分散装置１１およびＭ個の秘密計算装置２２_０−２２_Ｍ−１を有し、これらはインターネット等のネットワーク経由で通信可能に構成される。図２に例示するように、本形態の秘密計算装置２２_ｍ（ただし、ｍ＝０，…，Ｍ−１）は、通信部１２１_ｍ、記憶部１２２_ｍ、制御部１２３_ｍ、入力演算部２２４_ｍ、検査ビット列取得部２２５_ｍ、空値検査部２２６_ｍ、大小比較ビット列取得部２２７_ｍ、および大小比較部２２８_ｍを有する。秘密計算装置２２_ｍは、制御部１２３_ｍの制御の下で各処理を実行する。

＜処理＞
次に、図３を参照して本形態の処理を説明する。
分散装置１１は入力値Ｗ（０）の秘密分散値［Ｗ（０）］_ｍおよび入力値Ｗ（１）の秘密分散値［Ｗ（１）］_ｍを生成して秘密計算装置２２_ｍ（ただし、ｍ＝０，…，Ｍ−１）に送信する。入力値Ｗ（０）は空値または実数値Ｘ（０）に対応し、入力値Ｗ（１）は空値または実数値Ｘ（１）に対応する。入力値Ｗ（０），Ｗ（１）のフォーマットは前述した入力値Ｗのフォーマットと同じである。秘密分散値［Ｗ（０）］_ｍ，［Ｗ（１）］_ｍは、秘密計算装置２２_ｍ（図２）の通信部１２１_ｍで受信され、入力演算部１２４_ｍに送られる（ステップＳ２１_ｍ）。

入力演算部２２４_ｍは、秘密計算により、入力値Ｗ（０）の秘密分散値［Ｗ（０）］_ｍを用いてＹ（０）＝（Ｗ（０）＋２^Ｌ） ｍｏｄ Ｐの秘密分散値［Ｙ（０）］_ｍを得て出力する。また、入力演算部２２４_ｍは、秘密計算により、入力値Ｗ（１）の秘密分散値［Ｗ（１）］_ｍを用い、Ｙ（１）＝（Ｗ（１）＋２^Ｌ） ｍｏｄ Ｐの秘密分散値［Ｙ（１）］_ｍを得て出力する。Ｙ（０）は「対象ビット列Ａ（０）が表す値」に相当し、Ｙ（１）は「対象ビット列Ａ（１）が表す値」に相当する。対象ビット列Ａ（０）およびＡ（１）は、最上位ビットが１の場合に空値に対応し、最上位ビットが０の場合に実数値に対応するビット列である（ステップＳ２２_ｍ）。

検査ビット列取得部２２５_ｍは、秘密分散値［Ｙ（０）］_ｍおよび［Ｙ（１）］_ｍを入力とし、秘密計算により、Ｖ（０）＝２^Ｔ×Ｙ（０） ｍｏｄ Ｐの秘密分散値［Ｖ（０）］_ｍおよびＶ（１）＝２^Ｔ×Ｙ（０） ｍｏｄ Ｐの秘密分散値［Ｖ（０）］_ｍを得て出力する。Ｖ（０）は「検査ビット列Ｃ（０）が表す値」に相当し、Ｖ（１）は「検査ビット列Ｃ（１）が表す値」に相当する（ステップＳ２３_ｍ）。

空値検査部２２６_ｍは、秘密分散値［Ｖ（０）］_ｍを入力とし、検査ビット列Ｃ（０）の最下位ビットから検査ビットまでの各ビット値の秘密分散値［ｒ（０）］_ｍを得て出力する。また空値検査部２２６_ｍは、秘密分散値［Ｖ（１）］_ｍを入力とし、検査ビット列Ｃ（１）の最下位ビットから検査ビットまでの各ビット値の秘密分散値［ｒ（１）］_ｍを得て出力する。例えば、Ｔ＝１の場合、空値検査部２２６_ｍは、最下位ビットである検査ビットの値の秘密分散値［ｒ（０）］_ｍおよび［ｒ（１）］_ｍを得て出力する（ステップＳ２４_ｍ）。

大小比較ビット列取得部２２７_ｍは、秘密分散値［Ｙ（０）］_ｍおよび［Ｙ（１）］_ｍを入力とし、秘密計算により、比較結果値（Ｙ（０）−Ｙ（１）＋２^Ｋ−１） ｍｏｄ Ｐ（対象ビット列Ａ（０）が表す値から対象ビット列Ａ（１）が表す値を減じた値に２^Ｋ−１を加算した値）の秘密分散値［（Ｙ（０）−Ｙ（１）＋２^Ｋ−１） ｍｏｄ Ｐ］_ｍを得て出力する。ただし、Ｋは２以上の整数であり、最上位ビットが０の対象ビット列Ａ（０）が表す値Ｙ（０）および最上位ビットが０の対象ビット列Ａ（１）が表す値Ｙ（１）の大きさは０以上２^Ｋ−１未満である。ここで、比較結果値（Ｙ（０）−Ｙ（１）＋２^Ｋ−１） ｍｏｄ ＰのＮ桁２進数表現であるビット列を大小比較ビット列と呼ぶ。図７ＡはＮ＝Ｋの場合の大小比較ビット列２２１０を例示した概念図であり、最上位ビットが検査ビット２２１１となっている。図７ＡはＮ＞Ｋの場合の大小比較ビット列２２２０を例示した概念図であり、最上位ビットよりも下位のビットが検査ビット２２２１となっている。

２^Ｋ−１ ｍｏｄ ＰのＮ桁２進数表現値の下位からＫビット目の値は１である。ここでＹ（０）−Ｙ（１）の大きさは０以上２^Ｋ−１未満であるため、Ｘ（０）≧Ｘ（１）である場合、（Ｙ（０）−Ｙ（１）＋２^Ｋ−１） ｍｏｄ ＰのＮ桁２進数表現値は２^Ｋ−１ ｍｏｄ ＰのＮ桁２進数表現値以上となり、下位からＫビット目の値は必ず１となる。一方、Ｘ（０）＜Ｘ（１）である場合、（Ｙ（０）−Ｙ（１）＋２^Ｋ−１） ｍｏｄ ＰのＮ桁２進数表現値は２^Ｋ−１ ｍｏｄ ＰのＮ桁２進数表現値未満となり、下位からＫビット目の値は必ず０となる。そのため、Ｘ（０）≧Ｘ（１）である場合、大小比較ビット列の下位からＫビット目の値は１となり、Ｘ（０）＜Ｘ（１）である場合、大小比較ビット列の下位からＫビット目の値は０となる。Ｎ＝Ｋ＝７およびＬ＝５の場合の具体例を示す。例えば、Ｘ（０）＝０，Ｘ（１）＝−１の場合、Ｙ（０）＝３２，Ｙ（１）＝３１であり、大小比較ビット列が１０００００１となり、下位から７ビット目の値が１となる。例えば、Ｘ（０）＝−１０，Ｘ（１）＝−５の場合、Ｙ（０）＝２２，Ｙ（１）＝２７であり、大小比較ビット列が０１１１０１１となり、下位から７ビット目の値が０となる（ステップＳ２５_ｍ）。

大小比較部２２８_ｍは、秘密分散値［（Ｙ（０）−Ｙ（１）＋２^Ｋ−１） ｍｏｄ Ｐ］_ｍを入力とし、秘密計算により、比較結果値（Ｙ（０）−Ｙ（１）＋２^Ｋ−１） ｍｏｄ Ｐを表す大小比較ビット列の下位からＫビット目の値ｑの秘密分散値［ｑ］_ｍを得て出力する。この処理は、例えば参考文献２のビット分解を用いて実行できる。ただし、その他のビット分解方法が用いられてもよい（例えば、参考文献６「I. Damgard, M. Fitzi, E. Kiltz, J. B. Nielsen, and T. Toft, “Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation,” In S. Halevi and T. Rabin eds., TCC, Vol. 3876 of Lecture Notes in Computer Science, pp. 285-304. Springer, 2006.」等参照）（ステップＳ２６_ｍ）。

秘密計算装置２２_ｍは、秘密分散値［ｒ（０）］_ｍ，［ｒ（１）］_ｍ，［ｑ］_ｍを出力する（ステップＳ２７_ｍ）。

［第２実施形態の変形例１］
第２実施形態では、（Ｙ（０）−Ｙ（１）＋２^Ｋ−１） ｍｏｄ Ｐを比較結果値（対象ビット列Ａ（０）が表す値から対象ビット列Ａ（１）が表す値を減じた値に２^Ｋ−１を加算した値）とした。しかしながら、Ｙ（０）＝（Ｗ（０）＋２^Ｌ） ｍｏｄ ＰおよびＹ（１）＝（Ｗ（１）＋２^Ｌ） ｍｏｄ Ｐであり、（Ｙ（０）−Ｙ（１）＋２^Ｋ−１） ｍｏｄ Ｐ＝（Ｗ（０）−Ｗ（１）＋２^Ｋ−１） ｍｏｄ Ｐである。そのため、（Ｗ（０）−Ｗ（１）＋２^Ｋ−１） ｍｏｄ Ｐを比較結果値（対象ビット列Ａ（０）が表す値から対象ビット列Ａ（１）が表す値を減じた値に２^Ｋ−１を加算した値）としてもよい。この場合には、図８に例示するように、第２実施形態のステップＳ２１_ｍ−Ｓ２４_ｍの実行後、大小比較ビット列取得部２２７_ｍが秘密分散値［Ｗ（０）］_ｍおよび［Ｗ（１）］_ｍを入力とし、秘密計算により、比較結果値（Ｗ（０）−Ｗ（１）＋２^Ｋ−１） ｍｏｄ Ｐの秘密分散値［（Ｗ（０）−Ｗ（１）＋２^Ｋ−１） ｍｏｄ Ｐ］_ｍを得て出力する（ステップＳ２５’_ｍ）。その後、秘密分散値［（Ｙ（０）−Ｙ（１）＋２^Ｋ−１） ｍｏｄ Ｐ］_ｍに代えて秘密分散値［（Ｗ（０）−Ｗ（１）＋２^Ｋ−１） ｍｏｄ Ｐ］_ｍを用い、第２実施形態のステップＳ２６_ｍ−Ｓ２７_ｍを実行する。

［第２実施形態の変形例２］
第２実施形態およびその変形例１では、秘密計算装置２２_ｍが秘密分散値［ｒ（０）］_ｍ，［ｒ（１）］_ｍ，秘密分散値［ｑ］_ｍを出力した。しかしながら、Ｔ≧２の場合であっても、［ｒ（０）］_ｍ，［ｒ（１）］_ｍに代えて検査ビット列Ｃ（０），Ｃ（１）の各検査ビットの値の秘密分散値のみが出力されてもよい。また、秘密計算装置２２_ｍが、各検査ビットの値がともに０の場合に秘密分散値［ｑ］_ｍとなり、何れかの検査ビットの値が１の場合にエラーを表す秘密分散値となる値を生成して出力してもよい。

［第２実施形態の変形例３］
各秘密計算装置２２_ｍに秘密分散値［Ｙ（０）］_ｍおよび［Ｙ（１）］_ｍが入力され、ステップＳ２３_ｍからＳ２７_ｍの処理が実行されてもよい。

[第３実施形態]
第３実施形態では、秘密計算での空値検査に加え、秘密計算でのソートを行う。
＜構成＞
図１に例示するように、第３実施形態の秘密計算システム３は、分散装置１１およびＭ個の秘密計算装置３２_０−３２_Ｍ−１を有し、これらはインターネット等のネットワーク経由で通信可能に構成される。図２に例示するように、本形態の秘密計算装置３２_ｍ（ただし、ｍ＝０，…，Ｍ−１）は、通信部１２１_ｍ、記憶部１２２_ｍ、制御部１２３_ｍ、入力演算部２２４_ｍ、検査ビット列取得部２２５_ｍ、空値検査部２２６_ｍ、ソート部３２７_ｍ、およびソート結果利用演算部３２８_ｍを有する。秘密計算装置３２_ｍは、制御部１２３_ｍの制御の下で各処理を実行する。

＜処理＞
次に、図３を参照して本形態の処理を説明する。
分散装置１１は入力値Ｗ（ｄ）の秘密分散値［Ｗ（ｄ）］_ｍを生成して秘密計算装置２２_ｍ（ただし、ｍ＝０，…，Ｍ−１、ｄ＝０，…，Ｄ−１であり、Ｄが２以上の整数である）に送信する。入力値Ｗ（ｄ）は空値または実数値Ｘ（ｄ）に対応する。入力値Ｗ（ｄ）のフォーマットは前述した入力値Ｗのフォーマットと同じである。秘密分散値［Ｗ（ｄ）］_ｍｍは、秘密計算装置３２_ｍ（図２）の通信部１２１_ｍで受信され、入力演算部１２４_ｍに送られる（ステップＳ３１_ｍ）。

入力演算部３２４_ｍは、秘密計算により、入力値Ｗ（ｄ）の秘密分散値［Ｗ（ｄ）］_ｍを用いてＹ（ｄ）＝（Ｗ（ｄ）＋２^Ｌ） ｍｏｄ Ｐの秘密分散値［Ｙ（ｄ）］_ｍを得て出力する。Ｙ（ｄ）は「対象ビット列Ａ（ｄ）が表す値」に相当する。対象ビット列Ａ（ｄ）は、最上位ビットが１の場合に空値に対応し、最上位ビットが０の場合に実数値に対応するビット列である（ステップＳ３２_ｍ）。

検査ビット列取得部３２５_ｍは、秘密分散値［Ｙ（ｄ）］_ｍを入力とし、秘密計算により、Ｖ（ｄ）＝２^Ｔ×Ｙ（ｄ） ｍｏｄ Ｐの秘密分散値［Ｖ（ｄ）］_ｍを得て出力する。Ｖ（ｄ）は「検査ビット列Ｃ（ｄ）が表す値」に相当する（ステップＳ３３_ｍ）。

空値検査部３２６_ｍは、秘密分散値［Ｖ（ｄ）］_ｍを入力とし、検査ビット列Ｃ（ｄ）の最下位ビットから検査ビットまでの各ビット値の秘密分散値［ｒ（ｄ）］_ｍを得て出力する。例えば、Ｔ＝１の場合、空値検査部３２６_ｍは、最下位ビットである検査ビットの値の秘密分散値［ｒ（ｄ）］_ｍを得て出力する（ステップＳ３４_ｍ）。

ソート部３２７_ｍは、対象ビット列Ａ（ｄ）（ただし、ｄ＝０，…，Ｄ−１）が表すＹ（ｄ）の秘密分散値［Ｙ（ｄ）］を入力とし、秘密計算により、Ｙ（ｄ）の大きさに応じたソートを行い、そのソート結果の秘密分散値［θ］_ｍを得て出力する。Ｙ（ｄ）はＹ（ｄ）が大きいほど大きな実数値Ｘ（ｄ）に対応している。なお、秘密計算によるソート方法に限定はなく、公知の方法によって実行すればよい。例えば、ソート部３２７_ｍは、参考文献２のビット分解により、象ビット列Ａ（ｄ）の各ビット値の秘密分散値からなるベクトル［ＢｉｔＡ（ｄ）］の列を得、ベクトル［ＢｉｔＡ（ｄ）］の列を参考文献３，４等の方法でソートし、その結果の秘密分散値［θ］_ｍを出力する。秘密分散値［θ］_ｍは、例えばソートされた［ＢｉｔＡ（ｄ）］の列である（ステップＳ３５_ｍ）。

ソート結果利用演算部３２８_ｍは、ソート結果の秘密分散値［θ］_ｍを得、最大値、最小値、中央値の少なくとも何れの秘密分散値［Φ］_ｍを得て出力する。最大値の秘密分散値を得る場合、ソート結果利用演算部３２８_ｍは、例えばソートされた［ＢｉｔＡ（ｄ）］の列のうち最後の要素を選択して出力する。最小値の秘密分散値を得る場合、ソート結果利用演算部３２８_ｍは、例えばソートされた［ＢｉｔＡ（ｄ）］の列のうち最初の要素を選択して出力する。中央値の秘密分散値を得る場合には、例えば次のような処理を行う。Ｄが奇数のとき、ソート結果利用演算部３２８_ｍは、ソートされた［ＢｉｔＡ（ｄ）］の列の中央の列の各要素の２倍値を要素とする列の秘密分散値を出力する。Ｄが偶数のとき、ソート結果利用演算部３２８_ｍは、ソートされた［ＢｉｔＡ（ｄ）］の列の中央に最も近い２列を加算した列の秘密分散値を出力する（ステップＳ３６_ｍ）。

秘密計算装置３２_ｍは、秘密分散値［ｒ（ｄ）］_ｍ（ただし、ｄ＝０，…，Ｄ−１）および［Φ］_ｍを出力する（ステップＳ３７_ｍ）。

[第３実施形態の変形例１]
第３実施形態では、ソート部３２７_ｍが、対象ビット列Ａ（ｄ）（ただし、ｄ＝０，…，Ｄ−１）が表すＹ（ｄ）の秘密分散値［Ｙ（ｄ）］を入力とし、秘密計算により、Ｙ（ｄ）の大きさに応じたソートを行い、そのソート結果の秘密分散値［θ］_ｍを得て出力した（ステップＳ３５_ｍ）。これに代え、図１０に示すように、ソート部３２７_ｍが、秘密分散値［Ｖ（ｄ）］_ｍを入力とし、秘密計算により、検査ビット列Ｃ（ｄ）が表す値Ｖ（ｄ）の大きさに応じたソートを行い、そのソート結果の秘密分散値［θ］_ｍを得て出力してもよい（ステップＳ３５’_ｍ）。

［第３実施形態の変形例２］
第３実施形態およびその変形例１では、秘密計算装置３２_ｍが、秘密分散値［ｒ（ｄ）］_ｍ（ただし、ｄ＝０，…，Ｄ−１）および［Φ］_ｍを出力した。しかしながら、Ｔ≧２の場合であっても、［ｒ（ｄ）］_ｍ（ただし、ｄ＝０，…，Ｄ−１）に代えて、検査ビット列Ｃ（ｄ）の各検査ビットの値の秘密分散値のみが出力されてもよい。［Φ］_ｍに代えて［θ］_ｍが出力されてもよい。また、秘密計算装置３２_ｍが、各検査ビットの値がすべて０の場合に秘密分散値［Φ］_ｍまたは［θ］_ｍとなり、何れかの検査ビットの値が１の場合にエラーを表す秘密分散値となる値を生成して出力してもよい。

［第３実施形態の変形例３］
各秘密計算装置３２_ｍに秘密分散値［Ｙ（ｄ）］_ｍが入力され、ステップＳ３３_ｍからＳ３７_ｍの処理が実行されてもよい。

［第４実施形態］
第１から第３実施形態を組み合わせた形態であってもよいし、それらの少なくとも一部が前述の変形例に置き換えられた形態であってもよい。図１に例示するように、このような形態の計算システム４は、分散装置１１およびＭ個の秘密計算装置４２_０−４２_Ｍ−１を有し、これらはインターネット等のネットワーク経由で通信可能に構成される。秘密計算装置４２_ｍ（ただし、ｍ＝０，…，Ｍ−１）は、通信部１２１_ｍ、記憶部１２２_ｍ、制御部１２３_ｍ、入力演算部１２４_ｍ、検査ビット列取得部１２５_ｍ、空値検査部１２６_ｍ、大小比較ビット列取得部２２７_ｍ、大小比較部２２８_ｍ、ソート部３２７_ｍ、およびソート結果利用演算部３２８_ｍを有する。秘密計算装置４２_ｍは、制御部１２３_ｍの制御の下で各処理を実行する。各部の処理は第１から第３実施形態およびそれらの変形例で説明した通りである。

［その他の変形例等］
本発明は上述の実施の形態に限定されるものではない。例えば、秘密分散値［Ｗ］_ｍがその他の秘密計算装置での秘密計算結果であってもよい。また、各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。あるいは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。これらの装置の一部からなる組み合わせが、同一の装置であってもよい。

上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。

上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。

このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。

このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。

上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。

１−４ 秘密計算システム
１１ 分散装置
１２_ｍ−４２_ｍ 秘密計算装置

Claims (8)

1. 最上位ビットが１の場合に空値に対応し、最上位ビットが０の場合に実数値に対応する第１対象ビット列が表す値の秘密分散値を用い、前記第１対象ビット列の最上位ビットの値を最上位ビットよりも下位の第１検査ビットの値とした第１検査ビット列が表す値の秘密分散値を得る第１検査ビット列取得部と、
   前記第１検査ビット列が表す値の秘密分散値を用い、前記第１検査ビット列の最下位ビットから前記第１検査ビットまでのビット値の秘密分散値を得る第１空値検査部と、
   を有する秘密計算装置。
2. 請求項１の秘密計算装置であって、
   Ｎが２以上の整数であり、Ｐ＝２^Ｎ−１であり、Ｌが０≦Ｌ≦Ｎ−ｕ’の整数であり、ｕ’が２以上Ｎ以下の正の整数であり、Ｘが−２^Ｌ≦Ｘ≦２^Ｎ−１−２^Ｌ−１の整数であり、
   前記第１対象ビット列がＮ個のビットからなる列であり、
   空値に対応する前記第１対象ビット列が表す値は、Ｙ＝｛２^Ｌ＋（Ｐ＋１）／２｝ ｍｏｄ Ｐであり、
   ０以上の整数であるＸに対応する前記第１対象ビット列が表す値は、Ｙ＝（２^Ｌ＋Ｘ） ｍｏｄ Ｐであり、
   負の整数であるＸに対応する前記第１対象ビット列が表す値は、Ｙ＝（Ｐ＋２^Ｌ＋Ｘ） ｍｏｄ Ｐである、秘密計算装置。
3. 請求項２の秘密計算装置であって、
   空値に対応する値がＷ＝（Ｐ＋１）／２ ｍｏｄ Ｐであり、０以上の整数であるＸに対応する値がＷ＝Ｘ ｍｏｄ Ｐであり、負の整数であるＸに対応する値がＷ＝（Ｐ＋Ｘ） ｍｏｄ Ｐである入力値Ｗの秘密分散値を用い、前記第１対象ビット列が表す値Ｙ＝（Ｗ＋２^Ｌ） ｍｏｄ Ｐの秘密分散値を得る入力演算部を有する、秘密計算装置。
4. 請求項１から３の何れかの秘密計算装置であって、
   第２対象ビット列が、最上位ビットが１の場合に空値に対応し、最上位ビットが０の場合に実数値に対応するビット列であり、
   前記第１対象ビット列が表す値から前記第２対象ビット列が表す値を減じた値に２^Ｋ−１を加算した値を表す比較結果値の秘密分散値を得る大小比較ビット列取得部と、
   前記比較結果値を表すビット列の下位からＫビット目の値の秘密分散値を得る大小比較部と、を有し、
   Ｋが２以上の整数であり、最上位ビットが０の前記第１対象ビット列が表す値および最上位ビットが０の前記第２対象ビット列が表す値の大きさは０以上２^Ｋ−１未満である、秘密計算装置。
5. 請求項４の秘密計算装置であって、
   前記第２対象ビット列が表す値の秘匿値を用い、前記第２対象ビット列の最上位ビットの値を最上位ビットよりも下位の第２検査ビットの値とした第２検査ビット列が表す値の秘密分散値を得る第２検査ビット列取得部と、
   前記第２検査ビット列が表す値の秘密分散値を用い、前記第１検査ビット列の最下位ビットから前記第２検査ビットまでのビット値の秘密分散値を得る第２空値検査部と、
   を有する、秘密計算装置。
6. ｄ＝０，…，Ｄ−１であり、Ｄが２以上の整数であり、最上位ビットが１の場合に空値に対応し、最上位ビットが０の場合に実数値に対応する対象ビット列Ａ（ｄ）が表す値の秘密分散値を用い、前記対象ビット列Ａ（ｄ）の最上位ビットの値を最上位ビットよりも下位の検査ビットの値ｒ（ｄ）とした検査ビット列Ｃ（ｄ）が表す値の秘密分散値を得る検査ビット列取得部と、
   前記検査ビット列Ｃ（ｄ）が表す値の秘密分散値を用い、前記第１検査ビット列Ｃ（ｄ）の最下位ビットから前記検査ビットまでのビット値の秘密分散値を得る空値検査部と、
   前記対象ビット列Ａ（ｄ）が表す値の大きさに応じたソート結果の秘密分散値、または検査ビット列Ｃ（ｄ）が表す値の大きさに応じたソート結果の秘密分散値を得るソート部と、
   を有し、
   前記ソート部で前記対象ビット列Ａ（ｄ）が表す値の大きさに応じたソート結果の秘密分散値を得る場合には、最上位ビットが０の前記対象ビット列Ａ（ｄ）が表す値が、前記対象ビット列Ａ（ｄ）が表す値が大きいほど大きな実数値に対応しており、
   前記ソート部で検査ビット列Ｃ（ｄ）が表す値の大きさに応じたソート結果の秘密分散値を得る場合には、最上位ビットが０の前記対象ビット列Ａ（ｄ）に対応する前記検査ビット列Ｃ（ｄ）が表す値が、前記検査ビット列Ｃ（ｄ）が表す値が大きいほど大きな実数値に対応している、秘密計算装置。
7. 第１検査ビット列取得部において、最上位ビットが１の場合に空値に対応し、最上位ビットが０の場合に実数値に対応する第１対象ビット列が表す値の秘密分散値を用い、前記第１対象ビット列の最上位ビットの値を最上位ビットよりも下位の第１検査ビットの値とした第１検査ビット列が表す値の秘密分散値を得るステップと、
   第１空値検査部において、前記第１検査ビット列が表す値の秘密分散値を用い、前記第１検査ビット列の最下位ビットから前記第１検査ビットまでのビット値の秘密分散値を得るステップと、
   を有する秘密計算方法。
8. 請求項１から６の何れかの秘密計算装置としてコンピュータを機能させるためのプログラム。

Images