(57)【要約】  通信コストを削減することができる秘密商転移装置を提供する。ｕは自然数であって境界値を表すものとし、ｍをｍ≦２ｕを充たす整数、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、平文ａを０以上任意の法ｐ未満となる整数とし、整数ａと０が２ｕを法として合同であるものとし、ａがｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、サブシェアの合計値ａＺのｐによる商ｑをｑ＝Σ（ｉ＜ｍ）ｘｉｍｏｄ２ｕと計算する秘密商転移装置。
2015053185.tif 000002
【特許請求の範囲】
【請求項１】
【数４１】
2015053185.tif 000043
を、整数ｘとｚがｙを法として合同であることを示す記号とし、
ｕは自然数であって境界値を表すものとし、ｍをｍ≦２ｕを充たす整数、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、平文ａを０以上任意の法ｐ未満であって、
【数４２】
2015053185.tif 000044
となる整数とし、前記ａが
【数４３】
2015053185.tif 000045
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、前記サブシェアの合計値ａＺを、
【数４４】
2015053185.tif 000046
としてｑを前記サブシェアの合計値ａＺのｐによる商とするとき、
前記商ｑを
【数４５】
2015053185.tif 000047
と計算する秘密商転移装置。
【請求項２】
ｐをメルセンヌ素数とし、ｍをｍ≦２ｕを充たす整数とし、自然数である境界値ｕを┌ｌｏｇｍ┐とし、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、ｊをｊ＝０，１,…,ｍ−１を充たす整数とし、任意の命題Ｐに対して、〔Ｐ〕は、Ｐの真偽を整数に変換する演算子とし、ａの線形秘密分散値を［ａ］と表記し、ａの複製秘密分散値を{ａ}と表記し、平文ａを０以上任意の法ｐ未満であって、
【数４６】
2015053185.tif 000048
となる整数とし、前記ａが
【数４７】
2015053185.tif 000049
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、
２ｕａ＜ｐの条件の下、複製秘密分散値｛ａ｝Ｚｐを取得して、公開値倍の秘密計算により変形秘密分散値｛ａ′｝Ｚｐ：＝２ｕ×Ｚｐ｛ａ｝Ｚｐを計算する公開値倍秘密計算部と、
ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉の０ビット目からｕビットをビットごとに分散して下位ビット分散値
【数４８】
2015053185.tif 000050
を取得する下位ビット分散部と、
ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉のｕビット目からｌビットをビットごとに分散して上位ビット分散値
【数４９】
2015053185.tif 000051
を取得する上位ビット分散部と、
加算回路の秘密計算により下位ビット加算値
【数５０】
2015053185.tif 000052
を計算する下位ビット加算部と、
前記下位ビット加算値のうち下位ｕビットを
【数５１】
2015053185.tif 000053
上位ｕビットを
【数５２】
2015053185.tif 000054
と表すものとし、
前記下位ビット加算値の下位ｕビットを取得して、零判定回路の秘密計算により、零判定値［〔ｒｕ≠０〕］Ｚ２を計算する零判定部と、
ｉ＜ｍを充たすすべてのｉについて、前記上位ビット加算値と、前記下位ビット加算値の上位ｕビットと、前記零判定値を取得して、加算回路の秘密計算により、ビットの秘密分散列
【数５３】
2015053185.tif 000055
を計算して出力する上位ビット加算部
を含む秘密ビット分解装置。
【請求項３】
ｐをメルセンヌ素数とし、ｍをｍ≦２ｕを充たす整数とし、自然数である境界値ｕを┌ｌｏｇｍ┐とし、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、ｊをｊ＝０，１,…,ｍ−１を充たす整数とし、任意の命題Ｐに対して、〔Ｐ〕は、Ｐの真偽を整数に変換する演算子とし、ａの線形秘密分散値を［ａ］と表記し、ａの複製秘密分散値を{ａ}と表記し、平文ａを０以上任意の法ｐ未満であって、
【数５４】
2015053185.tif 000056
となる整数とし、前記ａが
【数５５】
2015053185.tif 000057
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、
２ｕａ＜ｐの条件の下、ｍｏｄ  ｐ複製秘密分散値｛ａ｝Ｚｐを取得して、公開値倍の秘密計算により、変形秘密分散値｛ａ′｝Ｚｐ：＝２ｕ×Ｚｐ｛ａ｝Ｚｐを計算する公開値倍秘密計算部と、
ｉ＜ｍを充たすすべてのｉについて、モジュラス変形秘密分散値のｉ番目のパーティのシェアである
【数５６】
2015053185.tif 000058
の０ビット目からｕビットを分散して、モジュラス下位ビット分散値
【数５７】
2015053185.tif 000059
を取得するモジュラス下位ビット分散部と、
ｉ＜ｍを充たすすべてのｉについて、加算回路の秘密計算により、下位ビット加算値
【数５８】
2015053185.tif 000060
を計算し、計算結果を商の線形秘密分散値
【数５９】
2015053185.tif 000061
とするモジュラス下位ビット加算部と、
前記商の線形秘密分散値にｍｏｄ  ２→ｍｏｄ  ｐ′変換等の所定の変換処理を施して、変換された商の線形秘密分散値｛ｑ｝Ｚｐ′を取得する変換処理部と、
ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値
【数６０】
2015053185.tif 000062
のｍｏｄ  ｐ′である再変形秘密分散値
【数６１】
2015053185.tif 000063
を計算する再変形部と、
前記再変形秘密分散値と、前記変換された商の線形秘密分散値を取得して、加算および公開値倍の秘密計算を用いて、差分計算
【数６２】
2015053185.tif 000064
を計算して出力するモジュラス差分部
を含む秘密モジュラス変換装置。
【請求項４】
【数６３】
2015053185.tif 000065
を、整数ｘとｚがｙを法として合同であることを示す記号とし、
ｕは自然数であって境界値を表すものとし、ｍをｍ≦２ｕを充たす整数、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、平文ａを０以上任意の法ｐ未満であって、
【数６４】
2015053185.tif 000066
となる整数とし、前記ａが
【数６５】
2015053185.tif 000067
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、前記サブシェアの合計値ａＺを、
【数６６】
2015053185.tif 000068
としてｑを前記サブシェアの合計値ａＺのｐによる商とするとき、
前記商ｑを
【数６７】
2015053185.tif 000069
と計算する秘密商転移方法。
【請求項５】
ｐをメルセンヌ素数とし、ｍをｍ≦２ｕを充たす整数とし、自然数である境界値ｕを┌ｌｏｇｍ┐とし、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、ｊをｊ＝０，１,…,ｍ−１を充たす整数とし、任意の命題Ｐに対して、〔Ｐ〕は、Ｐの真偽を整数に変換する演算子とし、ａの線形秘密分散値を［ａ］と表記し、ａの複製秘密分散値を{ａ}と表記し、平文ａを０以上任意の法ｐ未満であって、
【数６８】
2015053185.tif 000070
となる整数とし、前記ａが
【数６９】
2015053185.tif 000071
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、
２ｕａ＜ｐの条件の下、複製秘密分散値｛ａ｝Ｚｐを取得して、公開値倍の秘密計算により変形秘密分散値｛ａ′｝Ｚｐ：＝２ｕ×Ｚｐ｛ａ｝Ｚｐを計算する公開値倍秘密計算ステップと、
ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉の０ビット目からｕビットをビットごとに分散して下位ビット分散値
【数７０】
2015053185.tif 000072
を取得する下位ビット分散ステップと、
ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉のｕビット目からｌビットをビットごとに分散して上位ビット分散値
【数７１】
2015053185.tif 000073
を取得する上位ビット分散ステップと、
加算回路の秘密計算により下位ビット加算値
【数７２】
2015053185.tif 000074
を計算する下位ビット加算ステップと、
前記下位ビット加算値のうち下位ｕビットを
【数７３】
2015053185.tif 000075
上位ｕビットを
【数７４】
2015053185.tif 000076
と表すものとし、
前記下位ビット加算値の下位ｕビットを取得して、零判定回路の秘密計算により、零判定値［〔ｒｕ≠０〕］Ｚ２を計算する零判定ステップと、
ｉ＜ｍを充たすすべてのｉについて、前記上位ビット加算値と、前記下位ビット加算値の上位ｕビットと、前記零判定値を取得して、加算回路の秘密計算により、ビットの秘密分散列
【数７５】
2015053185.tif 000077
を計算して出力する上位ビット加算ステップ
を含む秘密ビット分解方法。
【請求項６】
ｐをメルセンヌ素数とし、ｍをｍ≦２ｕを充たす整数とし、自然数である境界値ｕを┌ｌｏｇｍ┐とし、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、ｊをｊ＝０，１,…,ｍ−１を充たす整数とし、任意の命題Ｐに対して、〔Ｐ〕は、Ｐの真偽を整数に変換する演算子とし、ａの線形秘密分散値を［ａ］と表記し、ａの複製秘密分散値を{ａ}と表記し、平文ａを０以上任意の法ｐ未満であって、
【数７６】
2015053185.tif 000078
となる整数とし、前記ａが
【数７７】
2015053185.tif 000079
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、
２ｕａ＜ｐの条件の下、ｍｏｄ  ｐ複製秘密分散値｛ａ｝Ｚｐを取得して、公開値倍の秘密計算により、変形秘密分散値｛ａ′｝Ｚｐ：＝２ｕ×Ｚｐ｛ａ｝Ｚｐを計算する公開値倍秘密計算ステップと、
ｉ＜ｍを充たすすべてのｉについて、モジュラス変形秘密分散値のｉ番目のパーティのシェアである
【数７８】
2015053185.tif 000080
の０ビット目からｕビットを分散して、モジュラス下位ビット分散値
【数７９】
2015053185.tif 000081
を取得するモジュラス下位ビット分散ステップと、
ｉ＜ｍを充たすすべてのｉについて、加算回路の秘密計算により、下位ビット加算値
【数８０】
2015053185.tif 000082
を計算し、計算結果を商の線形秘密分散値
【数８１】
2015053185.tif 000083
とするモジュラス下位ビット加算ステップと、
前記商の線形秘密分散値にｍｏｄ  ２→ｍｏｄ  ｐ′変換等の所定の変換処理を施して、変換された商の線形秘密分散値｛ｑ｝Ｚｐ′を取得する変換処理ステップと、
ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値
【数８２】
2015053185.tif 000084
のｍｏｄ  ｐ′である再変形秘密分散値
【数８３】
2015053185.tif 000085
を計算する再変形ステップと、
前記再変形秘密分散値と、前記変換された商の線形秘密分散値を取得して、加算および公開値倍の秘密計算を用いて、差分計算
【数８４】
2015053185.tif 000086
を計算して出力するモジュラス差分ステップ
を含む秘密モジュラス変換方法。
【請求項７】
コンピュータを、請求項１に記載の秘密商転移装置として機能させるためのプログラム。
【請求項８】
コンピュータを、請求項２に記載の秘密ビット分解装置として機能させるためのプログラム。
【請求項９】
コンピュータを、請求項３に記載の秘密モジュラス変換装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は秘密分散によりデータを秘匿しつつデータ処理を行う秘密計算の技術分野における、秘密商転移装置、秘密ビット分解装置、秘密モジュラス変換装置、秘密商転移方法、秘密ビット分解方法、秘密モジュラス変換方法、プログラムに関する。
【背景技術】
【０００２】
従来、秘密分散によりデータを秘匿しつつデータ処理を行う秘密計算の技術分野において、分散された任意の法ｐ未満の数の列ｘ０，…，ｘｍ-１を加算した値
【数１】
2015053185.tif 000003
をｐで割った商ｑ（すなわちａＺ＝ａ＋ｑｐと表現した場合のｑ、ただし０≦ａ＜ｐ，０≦ｑ＜ｍ）を求める技術（「シェアの商計算」と呼ぶ）が知られている。シェアの商計算を実現する技術に、ビット分解（非特許文献１）がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記の従来技術においては、｜ｐ｜をｐのビット長とした場合に、通信量がＯ（｜ｐ｜２）ビットとなり通信コストが大きいという課題があった。そこで本発明では、通信コストを削減することができる秘密商転移装置を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の秘密商転移装置は、
【数２】
2015053185.tif 000004
を、整数ｘとｚがｙを法として合同であることを示す記号とし、
ｕは自然数であって境界値を表すものとし、ｍをｍ≦２ｕを充たす整数、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、平文ａを０以上任意の法ｐ未満であって、
【数３】
2015053185.tif 000005
となる整数とし、ａが
【数４】
2015053185.tif 000006
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、サブシェアの合計値ａＺを、
【数５】
2015053185.tif 000007
としてｑをサブシェアの合計値ａＺのｐによる商とするとき、
商ｑを
【数６】
2015053185.tif 000008
と計算する。
【発明の効果】
【０００６】
本発明の秘密商転移装置によれば、通信コストを削減することができる。
【図面の簡単な説明】
【０００７】
【図１】実施例１の秘密商転移装置の構成を示すブロック図。
【図２】実施例１の秘密商転移装置の動作を示すフローチャート。
【図３】線形複製変換装置の構成を示すブロック図。
【図４】線形複製変換装置の動作を示すフローチャート。
【図５】実施例２の秘密ビット分解装置の構成を示すブロック図。
【図６】実施例２の秘密ビット分解装置の動作を示すフローチャート。
【図７】変形例１の秘密ビット分解装置の構成を示すブロック図。
【図８】実施例３の秘密モジュラス変換装置の構成を示すブロック図。
【図９】実施例３の秘密モジュラス変換装置の動作を示すフローチャート。
【図１０】変形例２の秘密モジュラス変換装置の構成を示すブロック図。
【発明を実施するための形態】
【０００８】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【０００９】
＜用語の説明＞
以下、本明細書において使用される用語を説明する。
［ｓｅｍｉ−ｈｏｎｅｓｔ］
ｓｅｍｉ−ｈｏｎｅｓｔとは、攻撃者はデータを盗み見するが、処理は正しく行う前提のことである。
［ｍａｌｉｃｉｏｕｓ］
ｍａｌｉｃｉｏｕｓとは、攻撃者は任意の不正な動作を行う前提のことである。【００１０】
＜記法＞
以下、本明細書において共通で使用される記法について説明する。
【数７】
2015053185.tif 000009
は、整数ｘとｚがｙを法として合同であることを示す。任意の命題Ｐに対して、〔Ｐ〕は、Ｐの真偽を整数に変換する演算子とする。典型的にはＰが真ならば１、偽ならば０である。【００１１】
＜前提＞
本発明では全体的に、ｐ未満の数というデータ型の中に、実際には状況依存のあるＭ未満の数が格納されると想定する。例えば通常のコンピュータでも、３２ビット整数の中に「性別」という１ビット（Ｍ＝２）のデータが格納される場合がある。Ｍのビット数をｌと表記する。本発明ではこのような場合を想定し、｜ｐ｜に依存しない（｜ｐ｜に関してＯ（１））ビット通信量での非常に高速なシェアの商計算を実現する。シェアの商計算の高速化はビット分解、モジュラス変換など秘密計算の分野の多くの処理の高速化を導く。【００１２】
＜秘密商転移装置１＞
以下、図１、図２を参照して実施例１の秘密商転移装置について説明する。図１は本実施例の秘密商転移装置１の構成を示すブロック図である。図２は本実施例の秘密商転移装置１の動作を示すフローチャートである。【００１３】
ｕは自然数であって境界値を表すものとし、ｍをｍ≦２ｕを充たす整数、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、平文ａを０以上任意の法ｐ未満（０≦ａ＜ｐ）であって、
【数８】
2015053185.tif 000010
となる整数とし、ａが
【数９】
2015053185.tif 000011
となるｍ個のｘ０，…，ｘｍ-１の和として表現されるとする。整数ｉ＝０，１,…,ｍ−１とし、各ｘｉをａのサブシェアと呼ぶ。このときサブシェアの合計値ａＺを、
【数１０】
2015053185.tif 000012
としてｑをａＺのｐによる商とする。本実施例の秘密商転移装置１には、複数の装置からサブシェアが送信されるものとする。秘密商転移装置１は、商ｑを
【数１１】
2015053185.tif 000013
と計算し、計算された商ｑを出力する（Ｓ１）。すなわち、秘密商転移装置１は、各ｘｉのビット表現が得られたとき、その各下位ｕビットの加算回路または減算回路により商を計算することができる。本実施例の秘密商転移装置１によれば、ｕビット目より上位ビットの計算が不要となる点がポイントである。本実施例で開示された秘密商転移装置１、および秘密商転移方法は秘密分散されたデータに対してデータの秘匿性を保ったまま処理を行う秘密計算において多くの応用が考えられる。以下の実施例２、実施例３においてこれらの応用例について説明する。【００１４】
以下の実施例を説明するために、まず秘密分散の説明を行う。
＜（ｋ，ｎ）−線形秘密分散）＞
（ｋ，ｎ）−秘密分散とは、平文をｎ個のシェアとして分散し、そのうちｋ個のシェアを集めれば平文を復元でき、かつｋ−１個以下のシェアを集めても平文の情報が一切得られないデータ分散方式のことである。【００１５】
ここでは（ｋ，ｎ）−線形秘密分散は以下のように定義する。関数
【数１２】
2015053185.tif 000014
が（ｋ，ｎ）−線形秘密分散であるとは、任意の単射σ：｛０，…，ｋ-１｝→｛０，…，ｎ-１｝に対して以下の復元用の係数列が存在することとする。σはｎ個のシェアからｋ個のシェアを任意に選択することを表現している。ただしＲは可換群、ＣはＲとの積が定義される集合とする。【００１６】
＜復元＞
ある係数列
【数１３】
2015053185.tif 000015
が存在して、任意の入力ａに対して
【数１４】
2015053185.tif 000016
ＳＨＡＲＥｐｒ（ａ）をａの線形秘密分散値と呼び、［ａ］と表記する。また各ｉ∈｛０，…，ｎ-１｝に対してＳＨＡＲＥｐｒ（ａ）ｉを［ａ］ｉと表記し、ｉ番目の、またはパーティｉのシェアと呼ぶ。Ｓｈａｍｉｒの秘密分散は代表的な（ｋ，ｎ）−線形秘密分散である。Ｓｈａｍｉｒの秘密分散では係数列はＬａｇｒａｎｇｅ補完法におけるＬａｇｒａｎｇｅ係数である。また、本発明では線形秘密分散の中でも特に以下の複製秘密分散の利用も想定する。【００１７】
＜複製秘密分散＞
複製秘密分散とは次のような秘密分散である。まずｍ＝ｎＣｋ-１個の可換群Ｒの元ａ０，…，ａｍ-１をもって平文ａを
【数１５】
2015053185.tif 000017
とする。そして各ｋ-１パーティの組（ｉ番目のｋ-１パーティの組をＰｉとする）について、Ｐｉに属さないパーティがみなａｉを持つ。Ｐｉに属するパーティはみなａｉを持たない。以上のようにすると、任意のｋ-１パーティ組に対して、持たないａｉが存在するからｋ-１パーティまでの結託に対して安全である。またｋパーティ集まると、どのａｉも必ず誰かが持っているため、復元できる。よって（ｋ，ｎ）−秘密分散となっている。各ａｉをサブシェアと呼ぶ。例えば（２，３）−複製秘密分散は、ａ＝ａ０＋ａ１＋ａ２とし、各パーティのシェアは（ａ０，ａ１），（ａ１，ａ２），（ａ２，ａ０）となる。【００１８】
複製秘密分散の秘密分散値は｛ａ｝のように書き、ｉ番目のパーティのシェアは｛ａ｝ｉのように書く。また、ｊをｊ＝０，１,…,ｍ−１を充たす整数とし、ｊ番目のサブシェアは｛ａ｝〈ｊ〉のように書く。本発明のｓｅｍｉ−ｈｏｎｅｓｔプロトコルでは（ｋ，ｋ）−複製秘密分散を用いる。（ｋ，ｋ）−複製秘密分散は、ｋ人だけでシェアを１個ずつ持つため効率的であるという利点がある。また、（ｋ，ｋ）−複製秘密分散は任意の（ｋ，ｎ）−線形秘密分散からオフラインで簡単に変換できるという利点もある。すなわち、任意にｋパーティを選択し（簡略化のため本稿では０，…，ｋ-１のｋパーティとして書くが任意のｋパーティでよい。）、各ｉ＜ｋに対して以下のように復元時の係数を乗ずればよい。
｛ａ｝ｉ＝λｉ［ａ］ｉ【００１９】
以下、図３、図４を参照して、本発明で用いることができるＭａｌｉｃｉｏｕｓ対応プロトコルによる（ｋ，ｎ）−複製秘密分散を用いる線形複製変換装置２について説明する。図３は、線形複製変換装置２の構成を示すブロック図である。図４は、線形複製変換装置２の動作を示すフローチャートである。線形複製変換装置２への入力、線形複製変換装置２からの出力は以下である。
入力：線形秘密分散値［ａ］Ｚｐ
出力：複製秘密分散値｛ａ｝Ｚｐ【００２０】
図２に示すように、線形複製変換装置２は、乱数生成部２１と、線形変換部２２と、差分値計算部２３と、公開部２４と、和算部２５を含む。乱数生成部２１は、複製秘密分散された乱数｛ｒ｝Ｚｐを生成する（Ｓ２１）。線形変換部２２は、複製秘密分散された乱数｛ｒ｝Ｚｐを取得し、当該乱数を所望の線形秘密分散された乱数［ｒ］Ｚｐに変換する（Ｓ２２）。差分値計算部２３は、線形秘密分散値［ａ］Ｚｐ、線形秘密分散された乱数［ｒ］Ｚｐを取得して、差分値［ａ-ｒ］Ｚｐを計算する（Ｓ２３）。公開部２４は、差分値［ａ-ｒ］Ｚｐをｍａｌｉｃｉｏｕｓ対応の方式で公開（例えば、非特許文献１参照）して、差分値の復号値ａ-ｒを取得する（Ｓ２４）。和算部２５は、複製秘密分散された乱数｛ｒ｝Ｚｐと、差分値の復号値ａ-ｒを取得して、和算（ａ-ｒ）＋｛ｒ｝Ｚｐ＝｛ａ｝Ｚｐにより、複製秘密分散値｛ａ｝Ｚｐを取得する（Ｓ２５）。（ｋ，ｎ）−複製秘密分散は、（ｋ，ｋ）−複製秘密分散とは逆に、任意の（ｋ，ｎ）−線形秘密分散にオフラインで変換できる（詳細は参考非特許文献１参照）という利点がある。
（参考非特許文献１）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.
【実施例２】
【００２１】
＜秘密ビット分解装置＞
以下、図５、図６を参照して、実施例２の秘密ビット分解装置について説明する。図５は本実施例の秘密ビット分解装置３の構成を示すブロック図である。図６は本実施例の秘密ビット分解装置３の動作を示すフローチャートである。図５に示すように、秘密ビット分解装置３は、公開値倍秘密計算部３１と、下位ビット分散部３２と、上位ビット分散部３３と、下位ビット加算部３４と、零判定部３５と、上位ビット加算部３６を含む。【００２２】
ビット分解は、Ｍ未満の数ａの秘密分散値［ａ］Ｚｐを、ｌ個の秘密分散値の列
【数１６】
2015053185.tif 000018
に変換する操作である。ただし各ａ０，…，ａｌ-１はａを２進表現したときの各ビット（０が最下位）である。また［・］Ｚｐと［・］Ｚ２は同じ形式の秘密分散であっても異なる形式の秘密分散であっても構わない。【００２３】
【数１７】
2015053185.tif 000019
は長さｌの、［・］Ｚ２の形式の秘密分散の列である。秘密計算は加算・乗算を基本処理とするため、算術演算は高速であるが、算術演算の結果は１ビットを超えた数値となりうる。一方低速な代わりに任意の処理を実現する論理回路は１ビット値を入出力とする。両者を橋渡しし、算術演算を高速に処理した後に任意の処理を行うために数値を１ビット値の列に変換するのがビット分解であり、実用的な秘密計算においては無くてはならない処理である。【００２４】
＜実施例２の秘密ビット分解方法＞
以下、図６を参照して本実施例の秘密ビット分解装置３が実行する秘密ビット分解方法について説明する。ｐをメルセンヌ素数とする。つまりｐは２べき-１となる素数である。（ｘ０，…，ｘｍ-１）を０≦ａ＜ｐのサブシェアとする。境界値ｕを┌ｌｏｇｍ┐とし、さらに各ｑｉ，ｒｉをそれぞれｘｉのｕビット目以降およびｕ-１ビット以前を表現する数値とし、ｑｕ，ｒｕを
【数１８】
2015053185.tif 000020
のｕビット目以降およびｕ-１ビット以前を表現する数値とする。すると式（１）よりｌをｌ＋ｕ≦｜ｐ｜として以下の等式が成り立つ。
【数１９】
2015053185.tif 000021
【００２５】
このことを利用すると、複製秘密分散に対する本実施例のアルゴリズムが導かれる。本アルゴリズムは式（２）を計算している。通信量は｜ｐ｜，ｌに関してＯ（ｌ）ビットでｐに非依存であり、高速である。【００２６】
複製秘密分散へは任意の線形秘密分散から変換することができ（参考非特許文献１）、入力が複製秘密分散の形式に限定されていることは実際の利用上の制限とはならない。【００２７】
秘密ビット分解装置３への入力、秘密ビット分散装置３からの出力を以下に示す。
入力：｛ａ｝Ｚｐ，ただし２ｕａ＜ｐ
出力：ビットの秘密分散値列
【数２０】
2015053185.tif 000022
なお、パラメータ：サブシェア数ｍ∈Ｎ，ｕ＝┌ｌｏｇｍ┐，素数ｐとする。【００２８】
公開値倍秘密計算部３１は、２ｕａ＜ｐの条件の下、複製秘密分散値｛ａ｝Ｚｐを取得して、公開値倍の秘密計算により変形秘密分散値｛ａ′｝Ｚｐ：＝２ｕ×Ｚｐ｛ａ｝Ｚｐを計算する（Ｓ３１）。例えばｐ未満の任意の整数ｂに対して、複製秘密分散の公開値倍ｂ×Ｚｐ｛ａ｝Ｚｐは、｛ａ｝の各サブシェアにｂを乗ずることで実現される。また（ｋ，ｎ）―線形秘密分散の効果値倍ｂ×Ｚｐ［ａ］Ｚｐは、［ａ］の各シェアにｂを乗ずることで実現される。なお、前述の演算記号×などは、演算を行う代数構造ごとに区別して演算を行うことを意味する。以下のステップＳ３２、Ｓ３３、Ｓ３４、Ｓ３６は、ｉ＜ｍを充たすすべてのｉについて実行される。下位ビット分散部３２は、変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉の０ビット目からｕビットをビットごとに分散して下位ビット分散値
【数２１】
2015053185.tif 000023
を取得する（Ｓ３２）。上位ビット分散部３３は、変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉のｕビット目からｌビットをビットごとに分散して上位ビット分散値
【数２２】
2015053185.tif 000024
を取得する（Ｓ３３）。下位ビット加算部３４は、加算回路の秘密計算により下位ビット加算値
【数２３】
2015053185.tif 000025
を計算する（Ｓ３４）。以下、下位ビット加算値のうち下位ｕビットを
【数２４】
2015053185.tif 000026
上位ｕビットを
【数２５】
2015053185.tif 000027
とおく。零判定部３５は、下位ビット加算値の下位ｕビットを取得して、零判定回路の秘密計算により、零判定値［〔ｒｕ≠０〕］Ｚ２を計算する（Ｓ３５）。上位ビット加算部３６は、上位ビット加算値と、下位ビット加算値の上位ｕビットと、零判定値を取得して、加算回路の秘密計算により、ビットの秘密分散列
【数２６】
2015053185.tif 000028
を計算して出力する（Ｓ３６）。【００２９】
［変形例１］
以下、図７を参照して実施例２の秘密ビット分解装置３の変形例である秘密ビット分解装置３Ａについて説明する。図７は本変形例の秘密ビット分解装置３Ａの構成を示すブロック図である。図７に示すように、本変形例の秘密ビット分解装置３Ａは、上述の構成に加え、上述した線形秘密分散値を複製秘密分散値に変換する構成である線形複製変換装置２を含む。このように、秘密ビット分解装置３Ａが線形複製変換装置２を含むことにより、装置への入力が線形秘密分散値であったとしても、秘密ビット分解を実行することができる。なお、本変形例の秘密ビット分解装置３Ａは、（ｋ，ｎ）―線形秘密分散を（ｋ，ｋ）―複製秘密分散に変換してから秘密ビット分解処理を実行してもよいし、（ｋ，ｎ）―線形秘密分散を（ｋ，ｎ）―複製秘密分散に変換してから秘密ビット分解処理を実行してもよい。
【実施例３】
【００３０】
以下、図８、図９を参照して実施例３の秘密モジュラス変換装置について説明する。図８は本実施例の秘密モジュラス変換装置４の構成を示すブロック図である。図９は本実施例の秘密モジュラス変換装置４の動作を示すフローチャートである。図８に示すように、本実施例の秘密モジュラス変換装置４は、公開値倍秘密計算部４１と、モジュラス下位ビット分散部４２と、モジュラス下位ビット加算部４３と、変換処理部４４と、再変形部４５と、モジュラス差分部４６を含む。【００３１】
モジュラス変換とは、法ｐ未満の数の形式の秘密分散値を、別の法ｐ′未満の数の形式に変換する処理である。通常のコンピュータでは３２ビット整数から６４ビット整数への型変換などに相当し、これも実用的な秘密計算においては無くてはならない処理である。【００３２】
＜実施例３の秘密モジュラス変換方法＞
以下、図９を参照して本実施例の秘密モジュラス変換装置４が実行する秘密モジュラス変換方法について説明する。式（１）を利用して、複製秘密分散に対する本実施例のアルゴリズムが導かれる。通信量は｜ｐ｜，｜ｐ′｜に関してＯ（｜ｐ′｜）ビットでｐに非依存であり、高速である。複製秘密分散へは任意の線形秘密分散から変換することができ（詳細は線形複製変換装置２の記載を参照）、入力が複製秘密分散の形式に限定されていることは実際の利用上の制限とはならない。以下に、秘密モジュラス変換装置４への入力、秘密モジュラス変換装置４からの出力を示す。
入力：ｍｏｄ  ｐ複製秘密分散値｛ａ｝Ｚｐ、ただし２ｕａ＜ｐ，ｕ＝┌ｌｏｇｍ┐
出力：ｍｏｄ  ｐ′複製秘密分散値｛ａ｝Ｚｐ′【００３３】
公開値倍秘密計算部４１は、２ｕａ＜ｐ，ｕ＝┌ｌｏｇｍ┐の条件の下、ｍｏｄ  ｐ複製秘密分散値｛ａ｝Ｚｐを取得して、公開値倍の秘密計算により、変形秘密分散値｛ａ′｝Ｚｐ：＝２ｕ×Ｚｐ｛ａ｝Ｚｐを計算する（Ｓ４１）。以下のステップＳ４２、Ｓ４３、Ｓ４５、Ｓ４６は、ｉ＜ｍを充たすすべてのｉについて実行される。モジュラス下位ビット分散部４２は、モジュラス変形秘密分散値のｉ番目のパーティのシェアである
【数２７】
2015053185.tif 000029
の０ビット目からｕビットを分散して、モジュラス下位ビット分散値
【数２８】
2015053185.tif 000030
を取得する（Ｓ４２）。マイナスがＺｐ上ではなくＺ２ｕ上となっていることに注意する。モジュラス下位ビット加算部４３は、加算回路の秘密計算により、下位ビット加算値
【数２９】
2015053185.tif 000031
を計算し、計算結果を商の線形秘密分散値
【数３０】
2015053185.tif 000032
とする（Ｓ４３）。変換処理部４４は、商の線形秘密分散値にｍｏｄ  ２→ｍｏｄ  ｐ′変換等の所定の変換処理を施して、変換された商の線形秘密分散値｛ｑ｝Ｚｐ′を取得する（Ｓ４４）。ｍｏｄ  ２→ｍｏｄ  ｐ′変換の具体的な演算方法について以下に詳述する。【００３４】
＜ｍｏｄ  ２→ｍｏｄ  ｐ′変換（ステップ１〜７）＞
入力：｛ａ｝２
出力：｛ａ｝ｐ′
ステップ１：乱数ｒを平文に持つ２種類の秘密分散値｛ｒ｝２，｛ｒ｝ｐ′を生成する。
ステップ２：つまり、各ｉ番目のパーティは１ビットの乱数ｒｉを生成し、さらに｛・｝２，｛・｝ｐ′の２種類の形式で秘密分散して｛ｒｉ｝２，｛ｒｉ｝ｐ′を得る。【００３５】
ステップ３：秘密計算により、
【数３１】
2015053185.tif 000033
を計算する。ただし○に＋を重ねて表示した記号はＸＯＲ演算，ｎはパーティ数である。【００３６】
ステップ４：
【数３２】
2015053185.tif 000034
を計算して公開し、
【数３３】
2015053185.tif 000035
を得る。【００３７】
ステップ５：
【数３４】
2015053185.tif 000036
を計算する。【００３８】
ステップ６：つまり、
【数３５】
2015053185.tif 000037
【００３９】
ステップ７：
【数３６】
2015053185.tif 000038
【００４０】
次に、再変形部４５は、変形秘密分散値
【数３７】
2015053185.tif 000039
のｍｏｄ  ｐ′である再変形秘密分散値
【数３８】
2015053185.tif 000040
を計算する（Ｓ４５）。なお、式（１）より
【数３９】
2015053185.tif 000041
となっている。モジュラス差分部４６は、再変形秘密分散値と、変換された商の線形秘密分散値を取得して、加算および公開値倍の秘密計算を用いて、差分計算
【数４０】
2015053185.tif 000042
を計算して出力する（Ｓ４６）。【００４１】
［変形例２］
以下、図１０を参照して実施例３の秘密モジュラス変換装置４の変形例である秘密モジュラス変換装置４Ａについて説明する。図１０は本変形例の秘密モジュラス変換装置４Ａの構成を示すブロック図である。図１０に示すように、本変形例の秘密モジュラス変換装置４Ａは、上述の構成に加え、上述した線形秘密分散値を複製秘密分散値に変換する構成である線形複製変換装置２を含む。このように、秘密モジュラス変換装置４Ａが線形複製変換装置２を含むことにより、装置への入力が線形秘密分散値であったとしても、モジュラス秘密変換を実行することができる。なお、本変形例の秘密モジュラス変換装置４Ａは、（ｋ，ｎ）―線形秘密分散を（ｋ，ｋ）―複製秘密分散に変換してから秘密モジュラス変換処理を実行してもよいし、（ｋ，ｎ）―線形秘密分散を（ｋ，ｎ）―複製秘密分散に変換してから秘密モジュラス変換処理を実行してもよい。【００４２】
＜発明の要点＞
本発明の要点は、ビット分解、モジュラス変換ともシェアの商計算と密接な関係にあり、従来｜ｐ｜ビットの加算回路を用いて計算していたところ、商転移というアイデアを考案し、｜ｐ｜に依存しないｌｏｇｍビットの回路で計算できるようにしたことである。商転移は、通常加算結果の上位ビットに現れる商を、整数剰余の性質を利用して加算結果の下位ビットに現れるように移動させる、本発明で考案の新しい技法である。通信量はシェアの商計算、ビット分解、モジュラス変換とも｜ｐ｜に関してＯ（｜ｐ｜２）からＯ（１）となり、飛躍的に効率化されている。例えば｜ｐ｜＝３１でｌ＝２（すなわち３１ビット整数に２ビットデータが格納されている）ケースでは従来の最速実装（参考非特許文献２、図「ｓｈｉｆｔＲ」参照）よりも２６００倍程度高速である。
（参考非特許文献２） 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.【００４３】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。【００４４】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。【００４５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。【００４６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。【００４７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。【００４８】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2015053185.tif 000087
【図２】
2015053185.tif 000088
【図３】
2015053185.tif 000089
【図４】
2015053185.tif 000090
【図５】
2015053185.tif 000091
【図６】
2015053185.tif 000092
【図７】
2015053185.tif 000093
【図８】
2015053185.tif 000094
【図９】
2015053185.tif 000095
【図１０】
2015053185.tif 000096
【手続補正書】
【提出日】平成28年3月29日(2016.3.29)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００３
【補正方法】変更
【補正の内容】
【０００３】
【非特許文献１】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.
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
本発明の秘密商転移装置は、
【数２】
2015053185.tif 000097
を、整数ｘとｚがｙを法として合同であることを示す数式とし、
ｕは自然数であって境界値を表すものとし、ｍをｍ≦２ｕを充たす整数、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、平文ａを０以上任意の法ｐ未満であって、
【数３】
2015053185.tif 000098
となる整数とし、ａが
【数４】
2015053185.tif 000099
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、サブシェアの合計値ａＺを、
【数５】
2015053185.tif 000100
としてｑをサブシェアの合計値ａＺのｐによる商とするとき、
商ｑを
【数６】
2015053185.tif 000101
と計算する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
図３に示すように、線形複製変換装置２は、乱数生成部２１と、線形変換部２２と、差分値計算部２３と、公開部２４と、和算部２５を含む。乱数生成部２１は、複製秘密分散された乱数｛ｒ｝Ｚｐを生成する（Ｓ２１）。線形変換部２２は、複製秘密分散された乱数｛ｒ｝Ｚｐを取得し、当該乱数を所望の線形秘密分散された乱数［ｒ］Ｚｐに変換する（Ｓ２２）。差分値計算部２３は、線形秘密分散値［ａ］Ｚｐ、線形秘密分散された乱数［ｒ］Ｚｐを取得して、差分値［ａ-ｒ］Ｚｐを計算する（Ｓ２３）。公開部２４は、差分値［ａ-ｒ］Ｚｐをｍａｌｉｃｉｏｕｓ対応の方式で公開（例えば、非特許文献１参照）して、差分値の復号値ａ-ｒを取得する（Ｓ２４）。和算部２５は、複製秘密分散された乱数｛ｒ｝Ｚｐと、差分値の復号値ａ-ｒを取得して、和算（ａ-ｒ）＋｛ｒ｝Ｚｐ＝｛ａ｝Ｚｐにより、複製秘密分散値｛ａ｝Ｚｐを取得する（Ｓ２５）。（ｋ，ｎ）−複製秘密分散は、（ｋ，ｋ）−複製秘密分散とは逆に、任意の（ｋ，ｎ）−線形秘密分散にオフラインで変換できる（詳細は参考非特許文献１参照）という利点がある。
（参考非特許文献１）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.
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２８
【補正方法】変更
【補正の内容】
【００２８】
公開値倍秘密計算部３１は、２ｕａ＜ｐの条件の下、複製秘密分散値｛ａ｝Ｚｐを取得して、公開値倍の秘密計算により変形秘密分散値｛ａ′｝Ｚｐ：＝２ｕ×Ｚｐ｛ａ｝Ｚｐを計算する（Ｓ３１）。例えばｐ未満の任意の整数ｂに対して、複製秘密分散の公開値倍ｂ×Ｚｐ｛ａ｝Ｚｐは、｛ａ｝の各サブシェアにｂを乗ずることで実現される。また（ｋ，ｎ）―線形秘密分散の公開値倍ｂ×Ｚｐ［ａ］Ｚｐは、［ａ］の各シェアにｂを乗ずることで実現される。なお、前述の演算記号×などは、演算を行う代数構造ごとに区別して演算を行うことを意味する。以下のステップＳ３２、Ｓ３３、Ｓ３４、Ｓ３６は、ｉ＜ｍを充たすすべてのｉについて実行される。下位ビット分散部３２は、変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉の０ビット目からｕビットをビットごとに分散して下位ビット分散値
【数２１】
2015053185.tif 000102
を取得する（Ｓ３２）。上位ビット分散部３３は、変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉のｕビット目からｌビットをビットごとに分散して上位ビット分散値
【数２２】
2015053185.tif 000103
を取得する（Ｓ３３）。下位ビット加算部３４は、加算回路の秘密計算により下位ビット加算値
【数２３】
2015053185.tif 000104
を計算する（Ｓ３４）。以下、下位ビット加算値のうち下位ｕビットを
【数２４】
2015053185.tif 000105
上位ｕビットを
【数２５】
2015053185.tif 000106
とおく。零判定部３５は、下位ビット加算値の下位ｕビットを取得して、零判定回路の秘密計算により、零判定値［〔ｒｕ≠０〕］Ｚ２を計算する（Ｓ３５）。上位ビット加算部３６は、上位ビット分散値と、下位ビット加算値の上位ｕビットと、零判定値を取得して、加算回路の秘密計算により、ビットの秘密分散列
【数２６】
2015053185.tif 000107
を計算して出力する（Ｓ３６）。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００４２
【補正方法】変更
【補正の内容】
【００４２】
＜発明の要点＞
本発明の要点は、ビット分解、モジュラス変換ともシェアの商計算と密接な関係にあり、従来｜ｐ｜ビットの加算回路を用いて計算していたところ、商転移というアイデアを考案し、｜ｐ｜に依存しないｌｏｇｍビットの回路で計算できるようにしたことである。商転移は、通常加算結果の上位ビットに現れる商を、整数剰余の性質を利用して加算結果の下位ビットに現れるように移動させる、本発明で考案の新しい技法である。通信量はシェアの商計算、ビット分解、モジュラス変換とも｜ｐ｜に関してＯ（｜ｐ｜２）からＯ（１）となり、飛躍的に効率化されている。例えば｜ｐ｜＝３１でｌ＝２（すなわち３１ビット整数に２ビットデータが格納されている）ケースでは従来の最速実装（参考非特許文献２、図「ｓｈｉｆｔＲ」参照）よりも２６００倍程度高速である。
（参考非特許文献２） 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.
【手続補正６】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
【数４１】
2015053185.tif 000108
を、整数ｘとｚがｙを法として合同であることを示す記号とし、
ｕは自然数であって境界値を表すものとし、ｍをｍ≦２ｕを充たす整数、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、平文ａを０以上任意の法ｐ未満であって、
【数４２】
2015053185.tif 000109
となる整数とし、前記ａが
【数４３】
2015053185.tif 000110
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、前記サブシェアの合計値ａＺを、
【数４４】
2015053185.tif 000111
としてｑを前記サブシェアの合計値ａＺのｐによる商とするとき、
前記商ｑを
【数４５】
2015053185.tif 000112
と計算する秘密商転移装置。
【請求項２】
ｐをメルセンヌ素数とし、ｍをｍ≦２ｕを充たす整数とし、自然数である境界値ｕを┌ｌｏｇｍ┐とし、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、ｊをｊ＝０，１,…,ｍ−１を充たす整数とし、任意の命題Ｐに対して、〔Ｐ〕は、Ｐの真偽を整数に変換する演算子とし、ａの線形秘密分散値を［ａ］と表記し、ａの複製秘密分散値を{ａ}と表記し、平文ａを０以上任意の法ｐ未満であって、
【数４６】
2015053185.tif 000113
となる整数とし、前記ａが
【数４７】
2015053185.tif 000114
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、
２ｕａ＜ｐの条件の下、複製秘密分散値｛ａ｝Ｚｐを取得して、公開値倍の秘密計算により変形秘密分散値｛ａ′｝Ｚｐ：＝２ｕ×Ｚｐ｛ａ｝Ｚｐを計算する公開値倍秘密計算部と、
ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉の０ビット目からｕビットをビットごとに分散して下位ビット分散値
【数４８】
2015053185.tif 000115
を取得する下位ビット分散部と、
ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉のｕビット目からｌビットをビットごとに分散して上位ビット分散値
【数４９】
2015053185.tif 000116
を取得する上位ビット分散部と、
加算回路の秘密計算により下位ビット加算値
【数５０】
2015053185.tif 000117
を計算する下位ビット加算部と、
前記下位ビット加算値のうち下位ｕビットを
【数５１】
2015053185.tif 000118
上位ｕビットを
【数５２】
2015053185.tif 000119
と表すものとし、
前記下位ビット加算値の下位ｕビットを取得して、零判定回路の秘密計算により、零判定値［〔ｒｕ≠０〕］Ｚ２を計算する零判定部と、
ｉ＜ｍを充たすすべてのｉについて、前記上位ビット分散値と、前記下位ビット加算値の上位ｕビットと、前記零判定値を取得して、加算回路の秘密計算により、ビットの秘密分散列
【数５３】
2015053185.tif 000120
を計算して出力する上位ビット加算部
を含む秘密ビット分解装置。
【請求項３】
ｐをメルセンヌ素数とし、ｍをｍ≦２ｕを充たす整数とし、自然数である境界値ｕを┌ｌｏｇｍ┐とし、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、ｊをｊ＝０，１,…,ｍ−１を充たす整数とし、任意の命題Ｐに対して、〔Ｐ〕は、Ｐの真偽を整数に変換する演算子とし、ａの線形秘密分散値を［ａ］と表記し、ａの複製秘密分散値を{ａ}と表記し、平文ａを０以上任意の法ｐ未満であって、
【数５４】
2015053185.tif 000121
となる整数とし、前記ａが
【数５５】
2015053185.tif 000122
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、
２ｕａ＜ｐの条件の下、ｍｏｄ  ｐ複製秘密分散値｛ａ｝Ｚｐを取得して、公開値倍の秘密計算により、変形秘密分散値｛ａ′｝Ｚｐ：＝２ｕ×Ｚｐ｛ａ｝Ｚｐを計算する公開値倍秘密計算部と、
ｉ＜ｍを充たすすべてのｉについて、モジュラス変形秘密分散値のｉ番目のパーティのシェアである
【数５６】
2015053185.tif 000123
の０ビット目からｕビットを分散して、モジュラス下位ビット分散値
【数５７】
2015053185.tif 000124
を取得するモジュラス下位ビット分散部と、
ｉ＜ｍを充たすすべてのｉについて、加算回路の秘密計算により、下位ビット加算値
【数５８】
2015053185.tif 000125
を計算し、計算結果を商の線形秘密分散値
【数５９】
2015053185.tif 000126
とするモジュラス下位ビット加算部と、
前記商の線形秘密分散値にｍｏｄ  ２→ｍｏｄ  ｐ′変換等の所定の変換処理を施して、変換された商の線形秘密分散値｛ｑ｝Ｚｐ′を取得する変換処理部と、
ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値
【数６０】
2015053185.tif 000127
のｍｏｄ  ｐ′である再変形秘密分散値
【数６１】
2015053185.tif 000128
を計算する再変形部と、
前記再変形秘密分散値と、前記変換された商の線形秘密分散値を取得して、加算および公開値倍の秘密計算を用いて、差分計算
【数６２】
2015053185.tif 000129
を計算して出力するモジュラス差分部
を含む秘密モジュラス変換装置。
【請求項４】
【数６３】
2015053185.tif 000130
を、整数ｘとｚがｙを法として合同であることを示す記号とし、
ｕは自然数であって境界値を表すものとし、ｍをｍ≦２ｕを充たす整数、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、平文ａを０以上任意の法ｐ未満であって、
【数６４】
2015053185.tif 000131
となる整数とし、前記ａが
【数６５】
2015053185.tif 000132
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、前記サブシェアの合計値ａＺを、
【数６６】
2015053185.tif 000133
としてｑを前記サブシェアの合計値ａＺのｐによる商とするとき、
前記商ｑを
【数６７】
2015053185.tif 000134
と計算する秘密商転移方法。
【請求項５】
ｐをメルセンヌ素数とし、ｍをｍ≦２ｕを充たす整数とし、自然数である境界値ｕを┌ｌｏｇｍ┐とし、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、ｊをｊ＝０，１,…,ｍ−１を充たす整数とし、任意の命題Ｐに対して、〔Ｐ〕は、Ｐの真偽を整数に変換する演算子とし、ａの線形秘密分散値を［ａ］と表記し、ａの複製秘密分散値を{ａ}と表記し、平文ａを０以上任意の法ｐ未満であって、
【数６８】
2015053185.tif 000135
となる整数とし、前記ａが
【数６９】
2015053185.tif 000136
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、
２ｕａ＜ｐの条件の下、複製秘密分散値｛ａ｝Ｚｐを取得して、公開値倍の秘密計算により変形秘密分散値｛ａ′｝Ｚｐ：＝２ｕ×Ｚｐ｛ａ｝Ｚｐを計算する公開値倍秘密計算ステップと、
ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉の０ビット目からｕビットをビットごとに分散して下位ビット分散値
【数７０】
2015053185.tif 000137
を取得する下位ビット分散ステップと、
ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉のｕビット目からｌビットをビットごとに分散して上位ビット分散値
【数７１】
2015053185.tif 000138
を取得する上位ビット分散ステップと、
加算回路の秘密計算により下位ビット加算値
【数７２】
2015053185.tif 000139
を計算する下位ビット加算ステップと、
前記下位ビット加算値のうち下位ｕビットを
【数７３】
2015053185.tif 000140
上位ｕビットを
【数７４】
2015053185.tif 000141
と表すものとし、
前記下位ビット加算値の下位ｕビットを取得して、零判定回路の秘密計算により、零判定値［〔ｒｕ≠０〕］Ｚ２を計算する零判定ステップと、
ｉ＜ｍを充たすすべてのｉについて、前記上位ビット分散値と、前記下位ビット加算値の上位ｕビットと、前記零判定値を取得して、加算回路の秘密計算により、ビットの秘密分散列
【数７５】
2015053185.tif 000142
を計算して出力する上位ビット加算ステップ
を含む秘密ビット分解方法。
【請求項６】
ｐをメルセンヌ素数とし、ｍをｍ≦２ｕを充たす整数とし、自然数である境界値ｕを┌ｌｏｇｍ┐とし、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、ｊをｊ＝０，１,…,ｍ−１を充たす整数とし、任意の命題Ｐに対して、〔Ｐ〕は、Ｐの真偽を整数に変換する演算子とし、ａの線形秘密分散値を［ａ］と表記し、ａの複製秘密分散値を{ａ}と表記し、平文ａを０以上任意の法ｐ未満であって、
【数７６】
2015053185.tif 000143
となる整数とし、前記ａが
【数７７】
2015053185.tif 000144
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、
２ｕａ＜ｐの条件の下、ｍｏｄ  ｐ複製秘密分散値｛ａ｝Ｚｐを取得して、公開値倍の秘密計算により、変形秘密分散値｛ａ′｝Ｚｐ：＝２ｕ×Ｚｐ｛ａ｝Ｚｐを計算する公開値倍秘密計算ステップと、
ｉ＜ｍを充たすすべてのｉについて、モジュラス変形秘密分散値のｉ番目のパーティのシェアである
【数７８】
2015053185.tif 000145
の０ビット目からｕビットを分散して、モジュラス下位ビット分散値
【数７９】
2015053185.tif 000146
を取得するモジュラス下位ビット分散ステップと、
ｉ＜ｍを充たすすべてのｉについて、加算回路の秘密計算により、下位ビット加算値
【数８０】
2015053185.tif 000147
を計算し、計算結果を商の線形秘密分散値
【数８１】
2015053185.tif 000148
とするモジュラス下位ビット加算ステップと、
前記商の線形秘密分散値にｍｏｄ  ２→ｍｏｄ  ｐ′変換等の所定の変換処理を施して、変換された商の線形秘密分散値｛ｑ｝Ｚｐ′を取得する変換処理ステップと、
ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値
【数８２】
2015053185.tif 000149
のｍｏｄ  ｐ′である再変形秘密分散値
【数８３】
2015053185.tif 000150
を計算する再変形ステップと、
前記再変形秘密分散値と、前記変換された商の線形秘密分散値を取得して、加算および公開値倍の秘密計算を用いて、差分計算
【数８４】
2015053185.tif 000151
を計算して出力するモジュラス差分ステップ
を含む秘密モジュラス変換方法。
【請求項７】
コンピュータを、請求項１に記載の秘密商転移装置として機能させるためのプログラム。
【請求項８】
コンピュータを、請求項２に記載の秘密ビット分解装置として機能させるためのプログラム。
【請求項９】
コンピュータを、請求項３に記載の秘密モジュラス変換装置として機能させるためのプログラム。
【手続補正書】
【提出日】平成28年10月6日(2016.10.6)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
【数４１】
2015053185.tif 000152
を、整数ｘとｚがｙを法として合同であることを示す記号とし、
ｕは自然数であって境界値を表すものとし、ｍをｍ≦２ｕを充たす整数、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、平文ａを０以上任意の法ｐ未満であって、
【数４２】
2015053185.tif 000153
となる整数とし、前記ａが
【数４３】
2015053185.tif 000154
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、前記サブシェアの合計値ａＺを、
【数４４】
2015053185.tif 000155
としてｑを前記サブシェアの合計値ａＺのｐによる商とするとき、
前記サブシェアを取得する入力部と、
前記商ｑを
【数４５】
2015053185.tif 000156
と計算する加算／減算回路と、
前記商ｑを出力する出力部を含む
秘密商転移装置。
【請求項２】
ｐをメルセンヌ素数とし、ｍをｍ≦２ｕを充たす整数とし、自然数である境界値ｕを┌ｌｏｇｍ┐とし、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、ｊをｊ＝０，１,…,ｍ−１を充たす整数とし、任意の命題Ｐに対して、〔Ｐ〕は、Ｐの真偽を整数に変換する演算子とし、ａの線形秘密分散値を［ａ］と表記し、ａの複製秘密分散値を{ａ}と表記し、平文ａを０以上任意の法ｐ未満であって、
【数４６】
2015053185.tif 000157
となる整数とし、前記ａが
【数４７】
2015053185.tif 000158
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、
２ｕａ＜ｐの条件の下、複製秘密分散値｛ａ｝Ｚｐを取得して、公開値倍の秘密計算により変形秘密分散値｛ａ′｝Ｚｐ：＝２ｕ×Ｚｐ｛ａ｝Ｚｐを計算する公開値倍秘密計算部と、
ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉の０ビット目からｕビットをビットごとに分散して下位ビット分散値
【数４８】
2015053185.tif 000159
を取得する下位ビット分散部と、
ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉のｕビット目からｌビットをビットごとに分散して上位ビット分散値
【数４９】
2015053185.tif 000160
を取得する上位ビット分散部と、
加算回路の秘密計算により下位ビット加算値
【数５０】
2015053185.tif 000161
を計算する下位ビット加算部と、
前記下位ビット加算値のうち下位ｕビットを
【数５１】
2015053185.tif 000162
上位ｕビットを
【数５２】
2015053185.tif 000163
と表すものとし、
前記下位ビット加算値の下位ｕビットを取得して、零判定回路の秘密計算により、零判定値［〔ｒｕ≠０〕］Ｚ２を計算する零判定部と、
ｉ＜ｍを充たすすべてのｉについて、前記上位ビット分散値と、前記下位ビット加算値の上位ｕビットと、前記零判定値を取得して、加算回路の秘密計算により、ビットの秘密分散列
【数５３】
2015053185.tif 000164
を計算して出力する上位ビット加算部
を含む秘密ビット分解装置。
【請求項３】
ｐをメルセンヌ素数とし、ｍをｍ≦２ｕを充たす整数とし、自然数である境界値ｕを┌ｌｏｇｍ┐とし、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、ｊをｊ＝０，１,…,ｍ−１を充たす整数とし、任意の命題Ｐに対して、〔Ｐ〕は、Ｐの真偽を整数に変換する演算子とし、ａの線形秘密分散値を［ａ］と表記し、ａの複製秘密分散値を{ａ}と表記し、平文ａを０以上任意の法ｐ未満であって、
【数５４】
2015053185.tif 000165
となる整数とし、前記ａが
【数５５】
2015053185.tif 000166
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、
２ｕａ＜ｐの条件の下、ｍｏｄ  ｐ複製秘密分散値｛ａ｝Ｚｐを取得して、公開値倍の秘密計算により、変形秘密分散値｛ａ′｝Ｚｐ：＝２ｕ×Ｚｐ｛ａ｝Ｚｐを計算する公開値倍秘密計算部と、
ｉ＜ｍを充たすすべてのｉについて、モジュラス変形秘密分散値のｉ番目のパーティのシェアである
【数５６】
2015053185.tif 000167
の０ビット目からｕビットを分散して、モジュラス下位ビット分散値
【数５７】
2015053185.tif 000168
を取得するモジュラス下位ビット分散部と、
ｉ＜ｍを充たすすべてのｉについて、加算回路の秘密計算により、下位ビット加算値
【数５８】
2015053185.tif 000169
を計算し、計算結果を商の線形秘密分散値
【数５９】
2015053185.tif 000170
とするモジュラス下位ビット加算部と、
前記商の線形秘密分散値にｍｏｄ  ２→ｍｏｄ  ｐ′変換等の所定の変換処理を施して、変換された商の線形秘密分散値｛ｑ｝Ｚｐ′を取得する変換処理部と、
ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値
【数６０】
2015053185.tif 000171
のｍｏｄ  ｐ′である再変形秘密分散値
【数６１】
2015053185.tif 000172
を計算する再変形部と、
前記再変形秘密分散値と、前記変換された商の線形秘密分散値を取得して、加算および公開値倍の秘密計算を用いて、差分計算
【数６２】
2015053185.tif 000173
を計算して出力するモジュラス差分部
を含む秘密モジュラス変換装置。
【請求項４】
秘密商転移装置が実行する秘密商転移方法であって、
【数６３】
2015053185.tif 000174
を、整数ｘとｚがｙを法として合同であることを示す記号とし、
ｕは自然数であって境界値を表すものとし、ｍをｍ≦２ｕを充たす整数、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、平文ａを０以上任意の法ｐ未満であって、
【数６４】
2015053185.tif 000175
となる整数とし、前記ａが
【数６５】
2015053185.tif 000176
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、前記サブシェアの合計値ａＺを、
【数６６】
2015053185.tif 000177
としてｑを前記サブシェアの合計値ａＺのｐによる商とするとき、
前記秘密商転移装置の入力部は、前記サブシェアを取得するステップを実行し、
前記秘密商転移装置の加算／減算回路は、
前記商ｑを
【数６７】
2015053185.tif 000178
と計算するステップを実行し、
前記秘密商転移装置の出力部は、前記商ｑを出力するステップを実行する
秘密商転移方法。
【請求項５】
秘密ビット分解装置が実行する秘密ビット分解方法であって、
ｐをメルセンヌ素数とし、ｍをｍ≦２ｕを充たす整数とし、自然数である境界値ｕを┌ｌｏｇｍ┐とし、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、ｊをｊ＝０，１,…,ｍ−１を充たす整数とし、任意の命題Ｐに対して、〔Ｐ〕は、Ｐの真偽を整数に変換する演算子とし、ａの線形秘密分散値を［ａ］と表記し、ａの複製秘密分散値を{ａ}と表記し、平文ａを０以上任意の法ｐ未満であって、
【数６８】
2015053185.tif 000179
となる整数とし、前記ａが
【数６９】
2015053185.tif 000180
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、
前記秘密ビット分解装置の公開値倍秘密計算部は、２ｕａ＜ｐの条件の下、複製秘密分散値｛ａ｝Ｚｐを取得して、公開値倍の秘密計算により変形秘密分散値｛ａ′｝Ｚｐ：＝２ｕ×Ｚｐ｛ａ｝Ｚｐを計算する公開値倍秘密計算ステップを実行し、
前記秘密ビット分解装置の下位ビット分散部は、ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉の０ビット目からｕビットをビットごとに分散して下位ビット分散値
【数７０】
2015053185.tif 000181
を取得する下位ビット分散ステップを実行し、
前記秘密ビット分解装置の上位ビット分散部は、ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値のｊ番目のサブシェア｛ａ′｝Ｚｐ〈ｊ〉のｕビット目からｌビットをビットごとに分散して上位ビット分散値
【数７１】
2015053185.tif 000182
を取得する上位ビット分散ステップを実行し、
前記秘密ビット分解装置の下位ビット加算部は、加算回路の秘密計算により下位ビット加算値
【数７２】
2015053185.tif 000183
を計算する下位ビット加算ステップを実行し、
前記下位ビット加算値のうち下位ｕビットを
【数７３】
2015053185.tif 000184
上位ｕビットを
【数７４】
2015053185.tif 000185
と表すものとし、
前記秘密ビット分解装置の零判定部は、前記下位ビット加算値の下位ｕビットを取得して、零判定回路の秘密計算により、零判定値［〔ｒｕ≠０〕］Ｚ２を計算する零判定ステップを実行し、
前記秘密ビット分解装置の上位ビット加算部は、ｉ＜ｍを充たすすべてのｉについて、前記上位ビット分散値と、前記下位ビット加算値の上位ｕビットと、前記零判定値を取得して、加算回路の秘密計算により、ビットの秘密分散列
【数７５】
2015053185.tif 000186
を計算して出力する上位ビット加算ステップを実行する
秘密ビット分解方法。
【請求項６】
秘密モジュラス変換装置が実行する秘密モジュラス変換方法であって、
ｐをメルセンヌ素数とし、ｍをｍ≦２ｕを充たす整数とし、自然数である境界値ｕを┌ｌｏｇｍ┐とし、ｉをｉ＝０，１,…,ｍ−１を充たす整数とし、ｊをｊ＝０，１,…,ｍ−１を充たす整数とし、任意の命題Ｐに対して、〔Ｐ〕は、Ｐの真偽を整数に変換する演算子とし、ａの線形秘密分散値を［ａ］と表記し、ａの複製秘密分散値を{ａ}と表記し、平文ａを０以上任意の法ｐ未満であって、
【数７６】
2015053185.tif 000187
となる整数とし、前記ａが
【数７７】
2015053185.tif 000188
となるｍ個のサブシェアｘ０，…，ｘｍ-１の和として表現されるものとし、
前記秘密モジュラス変換装置の公開値倍秘密計算部は、２ｕａ＜ｐの条件の下、ｍｏｄ  ｐ複製秘密分散値｛ａ｝Ｚｐを取得して、公開値倍の秘密計算により、変形秘密分散値｛ａ′｝Ｚｐ：＝２ｕ×Ｚｐ｛ａ｝Ｚｐを計算する公開値倍秘密計算ステップを実行し、
前記秘密モジュラス変換装置のモジュラス下位ビット分散部は、ｉ＜ｍを充たすすべてのｉについて、モジュラス変形秘密分散値のｉ番目のパーティのシェアである
【数７８】
2015053185.tif 000189
の０ビット目からｕビットを分散して、モジュラス下位ビット分散値
【数７９】
2015053185.tif 000190
を取得するモジュラス下位ビット分散ステップを実行し、
前記秘密モジュラス変換装置のモジュラス下位ビット加算部は、ｉ＜ｍを充たすすべてのｉについて、加算回路の秘密計算により、下位ビット加算値
【数８０】
2015053185.tif 000191
を計算し、計算結果を商の線形秘密分散値
【数８１】
2015053185.tif 000192
とするモジュラス下位ビット加算ステップを実行し、
前記秘密モジュラス変換装置の変換処理部は、前記商の線形秘密分散値にｍｏｄ  ２→ｍｏｄ  ｐ′変換等の所定の変換処理を施して、変換された商の線形秘密分散値｛ｑ｝Ｚｐ′を取得する変換処理ステップを実行し、
前記秘密モジュラス変換装置の再変形部は、ｉ＜ｍを充たすすべてのｉについて、前記変形秘密分散値
【数８２】
2015053185.tif 000193
のｍｏｄ  ｐ′である再変形秘密分散値
【数８３】
2015053185.tif 000194
を計算する再変形ステップを実行し、
前記秘密モジュラス変換装置のモジュラス差分部は、前記再変形秘密分散値と、前記変換された商の線形秘密分散値を取得して、加算および公開値倍の秘密計算を用いて、差分計算
【数８４】
2015053185.tif 000195
を計算して出力するモジュラス差分ステップを実行する
秘密モジュラス変換方法。
【請求項７】
コンピュータを、請求項１に記載の秘密商転移装置として機能させるためのプログラム。
【請求項８】
コンピュータを、請求項２に記載の秘密ビット分解装置として機能させるためのプログラム。
【請求項９】
コンピュータを、請求項３に記載の秘密モジュラス変換装置として機能させるためのプログラム。
【国際調査報告】
2015053185.tif 000196
2015053185.tif 000197
2015053185.tif 000198
2015053185.tif 000199