(57)【特許請求の範囲】
【請求項１】
複数のパーティを構成する複数のコンピュータ装置の各々が、各々の入力を他のパーティのコンピュータ装置に明かすことなく、所定の関数をそれぞれ計算するマルチパーティ計算方法であって、
前記複数のパーティを構成する前記複数のコンピュータ装置の各々が、前記関数の計算が正しく実行されたことを確認する確認ステップを含み、
前記確認ステップは、
複数の検証済みの乗算三つ組（multiplication triple）を用意しておき、要求されると、少なくとも１つの乗算三つ組を第２のステップに供給する第１のステップと、
前記第１のステップで生成されランダムに選択された乗算三つ組を消費する前記第２のステップと、
を含み、
前記第１のステップにおいて、
各パーティの前記コンピュータ装置は、
生成した複数の乗算三つ組のうち所定個の乗算三つ組について検証を行い、残りを複数のベクトルに分割し、
前記複数のベクトルの各々を等しいサイズの複数の部分配列に分割し、
各部分配列に含まれる前記乗算三つ組の順序を共同でランダムに並び替え、さらに、
前記複数の部分配列の順序を共同で並び替え、
過半数のパーティの前記コンピュータ装置において、前記部分配列に含まれる最初の所定個の乗算三つ組を開き乗算が成り立つか検証する、ことを特徴とするマルチパーティ計算方法。
【請求項２】
複数のパーティを構成する複数のコンピュータ装置の各々が、各々の入力を他のパーティのコンピュータ装置に明かすことなく、所定の関数をそれぞれ計算するマルチパーティ計算方法であって、
前記複数のパーティを構成する前記複数のコンピュータ装置の各々が、前記関数の計算が正しく実行されたことを確認する確認ステップを含み、
前記確認ステップは、
複数の確認済みの乗算三つ組（multiplication triple）を用意しておき、要求されると、少なくとも１つの乗算三つ組を第２のステップに供給する第１のステップと、
前記第１のステップで生成されランダムに選択された乗算三つ組を消費する前記第２のステップと、
を含み、
前記第１のステップにおいて、
各パーティの前記コンピュータ装置は、
複数個（N個）の乗算三つ組で第１及び第２のバッファを満たし、
前記第１及び第２のバッファを所定サイズの複数の部分配列に分割し、
前記第１のバッファからランダムに選択された前記部分配列の乗算三つ組に基づき、乗算の計算が正しく実行されたことの検証を行い、
前記第１のバッファの前記部分配列はランダムに選択され検証に用いられた後、前記第２のバッファから補充される、ことを特徴とするマルチパーティ計算方法。
【請求項３】
前記第１のステップにおいて、各パーティの前記コンピュータ装置は、
複数個（N個）の乗算三つ組で第１及び第２のバッファを満たし、
前記第１及び第２のバッファを所定サイズの複数の部分配列に分割し、
前記第１のバッファからランダムに選択された前記部分配列の乗算三つ組に基づき、乗算の計算が正しく実行されたことの検証を行い、
前記第１のバッファの前記部分配列はランダムに選択され検証に用いられた後、前記第２のバッファから補充される、ことを特徴とする請求項１に記載のマルチパーティ計算方法。
【請求項４】
ランダムに選択されシャッフルされた要素が検証に用いられた直後、前記第１のバッファの前記部分配列は、前記第２のバッファから補充され、前記乗算三つ組（triple）が選択される前記第１のバッファのサイズを同じに保つ、ことを特徴とする請求項２又は３に記載のマルチパーティ計算方法。
【請求項５】
前記第２のバッファ内の乗算三つ組は、予め設定されたサイズのチャンクによって消費され補充される、ことを特徴とする請求項２乃至４のいずれか一項に記載の方法。
【請求項６】
前記第１のステップは、複数の乗算三つ組を用いて１つの乗算三つ組を検証する、ことを特徴とする請求項２乃至５のいずれか一項に記載の方法。
【請求項７】
メモリを有し、所定の関数のマルチパーティ計算が正しく実行されていることを確認するための回路確認プロセス（circuit validation process）を実行するプロセッサを含み、
前記回路確認プロセスは、
複数の確認済みの乗算三つ組（multiplication triple）を用意しておき、要求されると、少なくとも１つの乗算三つ組を第２の処理に供給する第１の処理と、
前記第１の処理で生成され、ランダムに選択された乗算三つ組を消費する前記第２の処理と、
を含み、
前記第１の処理では、前記生成された乗算三つ組のシャッフルを、１つの列内でのシャッフルと、列のシャッフルと、のうち少なくとも一つにて行い、
前記第１の処理において、各パーティの前記プロセッサは、
生成した複数の乗算三つ組のうち所定個の乗算三つ組について検証を行い、残りを複数のベクトルに分割し、
前記複数のベクトルの各々を等しいサイズの複数の部分配列に分割し、
各部分配列に含まれる前記乗算三つ組の順序を共同でランダムに並び替え、さらに、前記複数の部分配列の順序を共同で並び替え、
過半数のパーティの前記プロセッサにおいて、前記部分配列に含まれる最初の所定個の乗算三つ組を開き乗算が成り立つか検証する、ことを特徴とするマルチパーティ計算装置。
【請求項８】
メモリを有し、所定の関数のマルチパーティ計算が正しく実行されていることを確認するための回路確認プロセス（circuit validation process）を実行するプロセッサを含み、
前記回路確認プロセスは、
複数の確認済みの乗算三つ組を用意し、要求されると、少なくとも１つの乗算三つ組（multiplication triple）を第２の処理に供給する第１の処理と、
前記第１の処理で生成され、ランダムに選択された乗算三つ組（multiplication triple）を消費する前記第２の処理と、
を含み、
前記第１の処理において、各パーティの前記プロセッサは、
複数個（N個）の乗算三つ組で第１及び第２のバッファを満たし、
前記第１及び第２のバッファを所定サイズの複数の部分配列に分割し、
前記第１のバッファからランダムに選択された前記部分配列の乗算三つ組に基づき、乗算の計算が正しく実行されたことの検証を行い、
前記第１のバッファの前記部分配列はランダムに選択され検証に用いられた後、前記第２のバッファから補充される、ことを特徴とするマルチパーティ計算装置。
【請求項９】
前記第１の処理において、各パーティの前記プロセッサは、
複数個（N個）の乗算三つ組で第１及び第２のバッファを満たし、
前記第１及び第２のバッファを所定サイズの複数の部分配列に分割し、
前記第１のバッファからランダムに選択された前記部分配列の乗算三つ組に基づき、乗算の計算が正しく実行されたことの検証を行い、
前記第１のバッファの前記部分配列はランダムに選択され検証に用いられた後、前記第２のバッファから補充される、ことを特徴とする請求項７に記載のマルチパーティ計算装置。
【請求項１０】
前記第２の処理は、前記関数に相当する回路のゲートの三つ組（triple）が生成された後、前記第１のバッファに格納された前記乗算三つ組をランダムに選択する、ことを特徴とする請求項８又は９に記載のマルチパーティ計算装置。
【請求項１１】
前記第２の処理は、ランダムに選択されシャッフルされた要素が検証に用いられた直後、前記第１のバッファの前記部分配列は、前記第２のバッファから補充され、前記乗算三つ組（triple）が選択される前記第１のバッファのサイズを同じに保つ、ことを特徴とする請求項８乃至１０のいずれか一項に記載のマルチパーティ計算装置。
【請求項１２】
前記第２の処理は、前記第２のバッファ内の前記乗算の三つ組（triple）を、予め設定されたサイズのチャンクによって消費し補充する、ことを特徴とする請求項８乃至１１のいずれか一項に記載のマルチパーティ計算装置。
【請求項１３】
前記第１の処理は、複数の乗算三つ組を用いて１つの乗算三つ組を検証する、ことを特徴とする請求項８乃至１２のいずれか一項に記載のマルチパーティ計算装置。
【請求項１４】
所定の関数のマルチパーティ計算が正しく実行されていることを確認する回路確認プロセスをコンピュータに実行させるプログラムであって、
前記回路確認プロセスは、
複数の確認済みの乗算三つ組（multiplication triple）を用意し、要求されると少なくとも１つの乗算三つ組を第２の処理に供給する第１の処理と、
前記第１の処理で生成され、ランダムに選択された乗算三つ組を消費する前記第２の処理と、
を含み、
前記第１の処理において、各パーティの前記コンピュータは、
生成した複数の乗算三つ組のうち所定個の乗算三つ組について検証を行い、残りを複数のベクトルに分割し、
前記複数のベクトルの各々を等しいサイズの複数の部分配列に分割し、
各部分配列に含まれる前記乗算三つ組の順序を共同でランダムに並び替え、さらに、前記複数の部分配列の順序を共同で並び替え、
過半数のパーティの前記コンピュータにおいて、前記部分配列に含まれる最初の所定個の乗算三つ組を開き乗算が成り立つか検証する、ことを特徴とするプログラム。
【請求項１５】
所定の関数のマルチパーティ計算が正しく実行されていることを確認する回路確認プロセスをコンピュータに実行させるプログラムであって、
前記回路確認プロセスは、
複数の確認済みの乗算三つ組（multiplication triple）を用意し、要求されると、少なくとも１つの乗算三つ組を第２の処理に供給する第１の処理と、
前記第１の処理で生成され、ランダムに選択された乗算三つ組（multiplication triple）を消費する前記第２の処理と、
を含み、
前記第１の処理において、各パーティの前記コンピュータは、
複数個（N個）の乗算三つ組で第１及び第２のバッファを満たし、
前記第１及び第２のバッファを所定サイズの複数の部分配列に分割し、
前記第１のバッファからランダムに選択された前記部分配列の乗算三つ組に基づき、乗算の計算が正しく実行されたことの検証を行い、
前記第１のバッファの前記部分配列はランダムに選択され検証に用いられた後、前記第２のバッファから補充される、ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は秘密計算（multiparty computation；ＭＰＣ）方法、装置、およびプログラムに関する。
【背景技術】
【０００２】
ＭＰＣでは、プライベートデータをそれぞれ持つ所定の数のパーティは、各々がその入力を他者へ明かすことなく入力としてプライベートデータの関数を計算することができる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】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.
【非特許文献３】Ivan Damgaard, Valerio Pastro, Nigel P. Smart, Sarah Zakarias, "Multiparty Computation from Somewhat Homomorphic Encryption", CRYPTO 2012: 643-662.
【非特許文献４】Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof and Kazuma Ohara, "High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority", CCS ‘16 Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Pages 805-817.
【非特許文献５】Jun Furukawa, Yehuda Lindell, Ariel Nof and Or Weinstein, "High-Throughput Secure Three-Party Computation for Malicious Adversaries and an Honest Majority", Advances in Cryptology - EUROCRYPT 2017. EUROCRYPT 2017. Lecture Notes in Computer Science, vol.10211. Springer, Cham
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１や非特許文献２などの関連技術は、すべてのパーティが関連するプロトコルに従う場合にのみ安全であり、正直に（honestly）当該プロトコルに従わないパーティに対しては安全ではない。すなわち、すべてのパーティは、プロトコルに正直に従う限り、他のパーティから受信したデータから何も学習しない。そのようなプロトコルは、セミオネスト（semi-honest）な秘匿性を実現すると言われている。
【０００５】
非特許文献３に開示されている関連技術は、プロトコルを正直に従わないパーティに対して安全だが、重い事前計算が必要になる。
【０００６】
従って、本発明の目的は、多くの事前計算を必要とせず、悪意を持つ攻撃者に対して安全な秘密計算方法、装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【０００７】
本発明の１つの側面によれば、複数のパーティの各々が、各々の入力を他のパーティに明かすことなく、予め設定された関数をそれぞれ計算する秘密計算のための方法であり、
前記複数のパーティの各々が前記関数の計算が正しく実行されたことを検証する検証ステップを含み、
前記検証ステップは、
複数の検証済みの乗算三つ組（multiplication triple）を用意し、要求があれば、少なくとも１つの乗算三つ組（multiplication triple）を第２のステップに供給する第１のステップと、
前記第１のステップで生成されランダムに選択された乗算三つ組（multiplication triple）を消費する前記第２のステップと、
を含み、
前記第１のステップは、前記生成された乗算三つ組（multiplication triple）のシャッフルを、１つの列内でのシャッフルと列のシャッフルとのうち少なくとも１つで行う、方法が提供される。
【０００８】
本発明の他の側面によれば、複数のパーティの各々が、各々の入力を他のパーティに明かすことなく、予め設定された関数をそれぞれ計算する秘密計算のための方法であり、
前記複数のパーティの各々が前記関数の計算が正しく実行されたことを検証する検証ステップを含み、
前記検証ステップは、
複数の検証済みの乗算三つ組（multiplication triple）を用意し、要求されると少なくとも１つの乗算三つ組（multiplication triple）を第２のステップに供給する第１のステップと、
前記第１のステップで生成され、ランダムに選択された 乗算三つ組（multiplication triple）を消費する前記第２のステップと、
を含み、
前記第１のステップは、要求があれば、全体の中からランダムに選択された乗算三つ組（multiplication triple）を提供する第１のバッファを用い、前記第１のバッファは、第２のバッファから順次補充される方法が提供される。
【０００９】
本発明の１つの側面によれば、メモリを有し、予め設定された関数の秘密計算が正しく実行されていることを検証する回路検証プロセスを実行するプロセッサを含み、
前記回路検証プロセスは、複数の検証済みの乗算三つ組（multiplication triple）を用意し、要求されると、少なくとも１つの乗算三つ組（multiplication triple）を第２の処理に供給する第１の処理と、
前記第１の処理で生成されランダムに選択された乗算三つ組（multiplication triple）を消費する前記第２の処理と、
を含み、前記第１の処理では、１つの列内でのシャッフルと列のシャッフルとのうち少なくとも１つで、前記生成された乗算三つ組（multiplication triple）のシャッフルを行う秘密計算装置が提供される。
【００１０】
本発明の他の側面によれば、メモリを有し、予め設定された関数の秘密計算が正しく実行されていることを検証するための回路検証プロセスを実行するプロセッサを含み、前記回路検証プロセスは、複数の検証済みの乗算三つ組（multiplication triple）を用意し、要求されると、少なくとも１つの乗算三つ組（multiplication triple）を第２の処理に供給する第１の処理と、
前記第１の処理で生成され、ランダムに選択された乗算三つ組（multiplication triple）を消費する前記第２の処理と、
を含み、前記第１の処理は、要求されると、全体の中からランダムに選択された乗算三つ組（multiplication triple）を提供する第１のバッファを含み、
前記第１のバッファは第２のバッファから順次補充される秘密計算装置が提供される。
【００１１】
本発明の１つの側面によれば、予め設定された関数の秘密計算が正しく実行されていることを検証する回路検証プロセスをコンピュータに実行させるプログラムであり、前記回路検証プロセスは、複数の検証済みの乗算三つ組（multiplication triple）を用意し、要求されると、少なくとも１つの乗算三つ組（multiplication triple）を第２の処理に供給する第１の処理と、前記第１の処理で生成されランダムに選択された乗算三つ組（multiplication triple）を消費する前記第２の処理と、
を含み、前記第１の処理では、１つの列内でのシャッフルと列のシャッフルとのうち少なくとも１つで、前記生成された乗算三つ組（multiplication triple）のシャッフルを行うプログラムが提供される。
【００１２】
本発明の他の側面によれば、予め設定された関数の秘密計算が正しく実行されていることを検証する回路検証プロセスをコンピュータに実行させるプログラムであり、前記回路検証プロセスは、複数の検証済みの乗算三つ組（multiplication triple）を用意し、要求されると少なくとも１つの乗算三つ組（multiplication triple）を第２の処理に供給する第１の処理と、前記第１の処理で生成されランダムに選択された乗算三つ組（multiplication triple）を消費する前記第２の処理とを含み、前記第１の処理は、要求されると全体の中からランダムに選択された乗算三つ組（multiplication triple）を提供する第１のバッファを用い、前記第１のバッファは第２のバッファから順次補充されるプログラムが提供される。
【００１３】
本発明の他の側面によれば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＥＥＰＲＯＭ（Electrically Erasable Programmable Read-Only Memory）、ＵＳＢ(Universal Serial Bus)デバイス、ＳＳＤ（Solid State Device）などの半導体メモリ、又は例えばＨＤＤ（Hard Disk Drive）、ＣＤ（Compact Disc）又はＤＶＤ（Digital Versatile Disc）などの記憶装置などのような、上記のプログラムを記録した、非一時的なコンピュータ読み出し可能な記録媒体が提供される。
【発明の効果】
【００１４】
本発明によれば、悪意を持つ攻撃者に対して安全な秘密計算が、事前計算を必要とせず可能となる。
本発明のさらに他の特徴及び利点は、本発明を実施することが企図されている最良の形態の単なる例示により、本発明の実施形態のみを図示及び説明した添付の図面と併せて以下の詳細な説明から当業者には容易に明らかになるであろう。理解されるように、本発明は、他の異なる実施形態が可能であり、そのいくつかの詳細は、本発明から逸脱することなく、様々な明白な点において変更可能である。したがって、図面及び説明は、本質的に例示的であるとみなされるべきであり、限定的ではないとみなされるべきである。
【図面の簡単な説明】
【００１５】
【図１Ａ】（2,3）秘密分散方式を説明する図である。
【図１Ｂ】（2,3）秘密分散方式を説明する図である。
【図２】本発明の第１の実施形態の動作を示すフローチャートである。
【図３】本発明の第１の実施形態の構成を示す図である。
【図４】本発明の第１の実施形態における三つ組（triple）生成の動作を示すフローチャートである。
【図５】本発明の第１の実施形態における三つ組（triple）を生成するためのメモリ構成を模式的に示す図である。
【図６】本発明の第１の実施形態における三つ組（triple）を生成するためのメモリ構成を模式的に示す図である。
【図７】本発明の第１の実施形態における三つ組（triple）を生成するためのメモリ構成を模式的に示す図である。
【図８】本発明の第１の実施形態における回路計算の動作を示すフローチャートである。
【図９】本発明の第１の実施形態における回路計算を模式的に示す図である。
【図１０】本発明の第１の実施形態における回路検証の動作を示すフローチャートである。
【図１１】本発明の第１の実施形態における回路検証のためのバッファ構成を模式的に示す図である。
【図１２】本発明の第２の実施形態の構成を示す図である。
【発明を実施するための形態】
【００１６】
例示的な実施形態を図面を参照して説明する。以下、本発明の実施形態の基本について概説する。秘密計算（ＭＰＣ）のプロトコルは、攻撃者に対する閾値の要件を持つ。例えば、パーティの数がnで、攻撃者によって汚染されたパーティの数をtとした場合、ＭＰＣプロトコルは、t < n = 3、または、t < n = 2を必要とする。nを、ＭＰＣプロトコルに参加するパーティの数とし、P（1）、..、P（n）を、これらn個のパーティそれぞれを表すとする。
【００１７】
Rを、加算と乗算とが定義されている環（ring）とする。環は、2^nを法とする環（^は２のべき乗の演算子）または任意の有限体でもよい。3^（-1）が存在する任意の有限体と環では、すべてが成り立つ。
【００１８】
SecretShare（）を、Rの要素が与えられると、シェア（share）と呼ばれるx（1）,...,x（n）を出力する（t、n）-秘密分散方式の関数とする。
【００１９】
これらのシェアは、以下を満たす。
（i）n個のシェアのうち、任意のt個のシェアの組が入力されると、xを出力する関数Reconstruct（）が存在し、
（ii）任意のt-1個のシェアの組からは、xの任意の部分を復元することが、計算上実行不可能である。
【００２０】
i（= 1、...、n）の各々について、P（i）がx（i）を持つ場合、xは秘密分散（secretly shared）されていると言う。これを[x]と表す。すなわち、値xがP（1）〜P（n）などの複数のパーティ間において秘密分散されていることを示すために、[x]という表記を用いる。
【００２１】
＜（2,3）-秘密分散方式＞
以下に（2,3）−秘密分散の例を説明する。要素v mod 2 ^ nを分散するため、ディーラーは、次の条件の下、３つのランダムな要素r（1）、r（2）、r（3）を選ぶ。
r(1)+ r(2)+ r(3) = 0
【００２２】
P（1）のシェアは、x（1）=（r（1), t（1））になり（ただし、t（1）= r（3）-v）、
P（2）のシェアは、x（2）=（r（2）, t（2））になり（ただし、t（2）= r（1）-v）、
P（3）のシェアは、x（3）=（r（3）, t（3））になる（ただし、t（3）= r（2）-v）。
単一のパーティのシェアは秘密(secret)vについて何も明らかにしないことは明白である。
【００２３】
関数Reconstruct（）に関して、例えば、x（1）=（r（1）, t（1））およびx（2）=（r（2）, t（2））が与えられた場合、１つのパーティ（例えばP（1））は、v = r（1）-t（2）= r（1）-（r（1）-v）を計算することができる。
【００２４】
同様に、P（2）は、x（2）とx（3）の組からvを計算できる（すなわち、v = r（2）-（r（2）-v）。そしてP（3）は、x（3）およびx（1）の組からvを計算できる（すなわち、v = r（3）-（r（3）-v）。上記秘密分散方式に従って値vの３つのうち２つの分散を[v]で表記する 。なお、秘密vは、１つのビットでもよく、r（1）、r（2）、r（3）は、
0006973868.tif 000002
の条件の下、
0006973868.tif 000003
となる３つのランダムビットになり、ここで、円に「+」はビット毎の排他的論理和を示す。この場合、
0006973868.tif 000004
（非特許文献４を参照）。
【００２５】
vを復元するのに必要なデータのすべてが、パーティのシェアとして分散されており、すべてのデータがこれらのパーティのいずれかに収集され、各パーティが、Reconstruct（）を用いてvを復元できる場合、パーティの組が[v]を開く（open）と言い、サブプロシージャ：「open（[v]）」は以下のように定義できる。
秘密値vのシェアが{（r（1）, t（i））}（i = 1、...、3）で表記される場合、各パーティP（i）は、t（i）をP（i + 1）に送信し、P（4）はP（1）に送信し、各P（i）は、v = r（i）-t（i-1）（すなわち、
0006973868.tif 000005
）を出力する（ただし、t（0）はt（3））。
【００２６】
[x]と[y]が与えられるとき、n個のパーティP（1）,...,P（n）は、ＭＰＣによって、互い通信せずに、セミオネストな秘匿性（semi-honest secrecy）で、[z] = [x + y] を計算可能とされる。この手順は、[z] = [x] + [y]で表される。
【００２７】
以下、ＭＰＣの加算の例を説明する。xとyが（2,3）-秘密分散方式によって秘密分散されているとする。より具体的には、
P（1）のxのシェアは、(x(11), x(12))であり（ただし、x(12)=x(31)-x）、
P（2）のxのシェアは、(x(21), x(22))であり（ただし、x(22)=x(11)-x）、
P（3）のxのシェアは、(x(31), x(32))である（ただし、x(32)=x(21)-x）。
【００２８】
P（1）のyのシェアは、(y(11), y(12))であり（ただし、y(12)=y(31)-y）、
P（2）のyのシェアは、(y(21), y(22))であり（ただし、y(22)=y(11)-y）、
P（3）のyのシェアは、(y(31), y(32))である（ただし、y(32)=x(21)-y）。
【００２９】
すると、
P（1）のx + yのシェアは、(x(11)+y(11), x(12)+y(12))、
P（2）のx + yのシェアは、(x(21)+y(21), x(22)+y(22))、
P（3）のx + yのシェアは、(x(31)+y(31), x(32)+y(32))
となる。
【００３０】
x + yは、(x(11)+y(11), x(12)+y(12))と、(x(21)+y(21), x(22)+y(22))の組から以下のとおり復元できる。
x+y = x(11)+y(11) - (x(22)+y(22))
= x(11)+y(11) - ( x(11)-x + y(11)-y)
【００３１】
[x]とyが与えられ、yが各パーティに知られているとき、n個のパーティP（1）、...、P（n）は、ＭＰＣによって、互い通信せずにセミオネストな秘匿性で、[z]=[x+y]を計算可能とされる。この手順は、[z]=[x]+y または[z]=y+[x]で表される。
【００３２】
以下、ＭＰＣ加算の例を説明する。xが上記（2,3）-秘密分散方式によって秘密に分散され、yが各パーティに知られているとする。より具体的には、
P（1）のxのシェアは、(x(11), x(12))であり（ただし、x(12)=x(31)-x）、
P（2）のxのシェアは、(x(21), x(22))であり（ただし、x(22)=x(11)-x）、
P（3）のxのシェアは、(x(31), x(32))である（ただし、x(32)=x(21)-x）。
【００３３】
すると、
P（1）のx + yのシェアは、(x(11), x(12)-y)、
P（2）のx + yのシェアは、(x(21), x(22)-y)、
P（3）のx + yのシェアは、(x(31), x(32)-y)となる。
x + yは、(x(11), x(12)-y)、及び(x(21),x(22)-y)の組から以下のとおり復元できる。
x+y = x(11) - (x(22) - y) = x(11) - ((x(11) - x) - y)
【００３４】
[x]とyが与えられ、yが各パーティに知られているとき、P（1）、...、P（n）は、ＭＰＣによって、互い通信せずに、セミオネストな秘匿性で、[z]=[xy] を計算可能とされる。この手順は、[z]=[x]y または[z]=y[x]で表される。
【００３５】
以下、このＭＰＣの乗算の例を説明する。
xが上記（2,3）-秘密分散方式によって秘密に分散され、yが各パーティに知られているとする。より具体的には、
P（1）のxのシェアは(x(11), x(12))であり（x(12)=x(31)/x）、
P（2）のxのシェアは(x(21), x(22))であり（x(22)=x(11)/x）、
P（3）のxのシェアは(x(31), x(32))である（x(32)=x(21)/x）。
【００３６】
すると、
P（1）のxyのシェアは、(x(11)y, x(12))、
P（2）のxyのシェアは、(x(21)y, x(22))、
P（3）のxyのシェアは、(x(31)y, x(32))である。
xyは、(x(11)y, x(12))、及び(x(21)y, x(22))の組から以下のとおり復元できる。
xy = (x(11)y)/x(22) = (x(11)y)/(x(11)/x)
【００３７】
[x]と[y]が与えられるとき、P（1）、...、P（n）それぞれは、ＭＰＣを用い、若干の通信により、semi-honestな秘匿性で、[z] = [xy]を計算可能とされる。この手順は、[z]=[x]*[y]で表される。
【００３８】
以下、ＭＰＣの乗算の例を説明する。xとyが上記（2,3）-秘密分散方式によって秘密分散されているとする。
より具体的には、
P（1）のxのシェアは、(x(11), x(12))であり、
P（2）のxのシェアは、(x(21), x(22))であり、
P（3）のxのシェアは、(x(31), x(32))であり、
P（1）のyのシェアは、(y(11), y(12))であり、
P（2）のyのシェアは、(y(21), y(22))であり、
P（3）のyのシェアは、(y(31), y(32))である。
【００３９】
ランダムに選択され、r（1）+ r（2）+ r（3）= 0を満たす、r（1）、r（2）、r（3）の組が存在するとする。また、P（1）がr（1）を持ち、P（2）がr（2）を持ち、P（3）はr（3）を持つものとする。
P（1）は、t(1) = (-x(11)y(11) + x(12)y(12) + r(1))/3 を計算し、t（1）をP（2）に送信する。
P（2）は、t(2) = (-x(21)y(21) + x(22)y(22) + r(2))/3 を計算し、t（2）をP（3）に送信する。
P（3）は、t(3) = (-x(31)y(31) + x(32)y(32) + r(3))/3 を計算し、t（3）をP（1）に送信する。
【００４０】
P（1）のxyのシェアは、(z1 = t(3)-t(1), c1=-2t(3)-t(1))であり、
P（2）のxyのシェアは、(z2 = t(1)-t(2), c2=-2t(1)-t(2))であり、
P（3）のxyのシェアは、(z3 = t(2)-t(3), c3=-2t(2)-t(3))である。
【００４１】
x(12)y(12) = (x(31) - x)(y(31) - y) = x(31)y(31) - x(31)y - y(31)x + xy
x(22)y(22) = (x(11) - x)(y(11) - y) = x(11)y(11) - x(11)y - y(11)x + xy
x(32)y(32) = (x(21) - x)(y(21) - y) = x(21)y(21) - x(21)y - y(21)x + xy
従って、
3(t(1)+t(2)+t(3)) = -x(11)y(11) + x(12)y(12) + r(1)
- x(21)y(21) + x(22)y(22) + r(2)
-x(31)y(31) + x(32)y(32) + r(3)
= x(12)y(12)+x(22)y(22)+x(32)y(32)-x(11)y(11)-x(21)y(21)-x(31)y(31)
= 3xy-x(y(11)+y(21)+y(31))-y(x(11)+x(21)+x(31))
= 3xy
【００４２】
n個のパーティP（1）からP（n）が、それぞれ、Rのランダムな要素を、互いに通信せず他の誰にも開示せずに、必要なだけシェア（共有）できるものとする。
【００４３】
以下、３つのパーティ間で共有されるランダム要素の例を説明する。複数の乱数種（random seeds）S（1）、S（2）、及びS（3）が既に以下のように共有されているものとする。
P（1）は、S（3）とS（1）とを持ち、
P（2）は、S（1）とS（2）とを持ち、
P（3）は、S（2）とS（3）とを持つ。
【００４４】
HashR（）をRの要素を出力する暗号学的ハッシュ関数とする。
P（1）は、i番目のランダム要素r（1i）のシェアを、HashR(S(3),i)-HashR(S(1),i)として生成する。
P（2）は、i番目のランダム要素r（2i）のシェアを、HashR(S(1),i)-HashR(S(2),i)として生成する。
P（3）は、i番目のランダム要素r（3i）のシェアを、HashR(S(2),i)-HashR(S(3),i)として生成する。
【００４５】
図２は、本発明の実施形態による動作を例示するフローチャートである。図２は、例示的な実施形態による（2,3）秘密分散方式に基づいて秘密を分散する各パーティによって実行される回路検証(circuit validation)の動作を示す。
【００４６】
図２を参照すると、各パーティによるステップＳ１（第１のプロセス）は、複数の検証された乗算三つ組（multiplication triple:乗算トリプル）を用意し、要求されると少なくとも１つの乗算三つ組をステップＳ２に供給する。
【００４７】
各パーティによるステップＳ２（第２のプロセス）において、ステップＳ１で生成され、ランダムに選択された乗算三つ組を消費する。
【００４８】
各パーティによるステップＳ１（第１のプロセス）において、生成された乗算三つ組のシャッフルを行い、１つの列の三つ組（triple）が三つ組単位でシャッフルされる列におけるシャッフル（並べ替え）か、列が列単位でシャッフルされる列のシャッフルかの少なくとも１つのシャッフルが行われる。
【００４９】
あるいは、各パーティによるステップＳ１（第１のプロセス）は、要求されると全体の中からランダムに選択された乗算三つ組を提供する第１のバッファを使用または含んでもよく、第１のバッファは第２のバッファから、順次、補充される。
【００５０】
図３は、１つの実施形態による１つのパーティの構成の一例を示す図である。パーティ（ｎパーティ、n=3）は同じ構成を有するので、１つのパーティの構成が図３に示されている。図３を参照すると、パーティ１００は、図３に不図示のメモリを有するプロセッサと通信インタフェースを含み、乗算三つ組生成プロセス１０２、回路計算プロセス１０４、および回路検証（circuit validation）プロセス１０６を実行する。
【００５１】
乗算三つ組生成プロセス１０２は、検証されたＮ個の乗算三つ組を生成する。
【００５２】
ゲートの入力配線（input wire）へのシェアを与えられたパーティの回路計算プロセス１０４は、ゲートの入力配線についての関数fを計算する。ゲートの出力配線（output wire）における結果は、パーティのシェアとして定義されてもよい。
【００５３】
回路検証プロセス１０６は、秘密計算が正しく実行されたことを検証する。
【００５４】
例示的な実施形態について、図面を参照してより詳細に説明する。
【００５５】
＜三つ組の検証(Triple Verification)＞
以下、乗算三つ組の検証について説明する。この検証方法に関して、例えば非特許文献５が参照できる。
【００５６】
B組（タプル）の乗算三つ組、（[a（1）]、[b（1）]、[c（1）]）、...、（[a（B）]、[b（B）]、[c（B）]）が与えられる。ただし、[a（i）]、[b（i）]、[c（i）]（i = 1、...、B）は、a（i）、b（i）、c（i）（i = 1、...、B）が、それぞれ、パーティ間で秘密分散されていることを表す。各i番目の乗算三つ組について、a（i）* b（i）= c（i）が成り立たないとすると、ある程度高い確率で検出される。もし、（[a（i）]、[b（i）]、[c（i）]）が、[a（i）] * [b（i）] = [c（i）]の関係を満たさないとすると、以下のテストでは、より高い確率で検出できる。
【００５７】
このテストの後、a（1）、b（1）、c（1）は、他のシェア、（[a（2）]、[b（2）]、[c（2）]）、...、（[a（B）]、[b（B）]、[c（B）]）が開かれない限り、秘密に分散され続ける。
【００５８】
i = 2、...、Bについて、各パーティは、[a（i）+ a（1）]及び[b（i）+ b（1）]を、ローカルに計算し、それぞれr（i）およびs（i）として開く。ここで「開く」とは、過半数のパーティの各組がそれらを開くことを意味する。
【００５９】
そして、各パーティは、r（i）及びs（i）（i = 2、...、B）について学習したことに基づき、それぞれのシェア
[c'(i)] = r(i)*s(i) - r(i)*[b(i)] - s(i)*[a(i)] + [c(i)]
=([a(i)+a(1)])*([b(i)+b(1)])-([a(i)+a(1)])*[b(i)]-([b(i)+b(1)])*[a(i)]+[c(i)]
=[a(1)]*[b(1)] - [a(i)]*[b(i)] + [c(i)]
を計算し、以下を開いてチェックする。
[c'(i)-c(i)]=[c'(i)]-[c(i)]
【００６０】
この等式は、a（i）b（i）= c（i）がすべてのiに対して成り立つか、iに対して成り立たない場合（either for all i or for no i）に成り立つ。したがって、このテストに合格する確率は、やや高い確率の積に近くなる。
【００６１】
以下、本実施形態によるプロトコルを説明する。まず最初に、乗算三つ組の秘密生成について、図４を参照して説明する。
【００６２】
＜三つ組の生成（Generating Triples）＞
パーティの乗算三つ組生成プロセス１０２によるN個の乗算三つ組の生成動作を、図４を参照して説明する。
【００６３】
＜ステップＳ１０１＞
生成される三つ組の個数Nが入力される。N =（X-C）* Lとなる補助パラメータB、C、X、及びLが入力される。
ただし、Xは、各部分配列のサイズ、
Cは、各部分配列で開かれた三つ組の数、
Bは、バケットの数、
Lは、１つのバケット内の部分配列の数である。
【００６４】
＜M個のランダム値のシェアリング生成(Generating sharing of M random values)（ステップＳ１０２）＞
各パーティの乗算三つ組生成プロセス１０２は、2M個のランダム値のシェアリングを生する。
2M = 2(N + C*L)*(B -1) + 2N= 2(N + C*L)*Bは、パーティが受け取るシェア[（[a（i）]、[b（i）]）]（i = 1、...、M）によって示される。各パーティは、どのパーティも知らないランダムな秘密値vのシェアリングを生成できる。
【００６５】
＜乗算三つ組の生成 (ステップＳ１０３）＞
各パーティの乗算三つ組生成プロセス１０２は、セミオネストな乗算プロトコルを実行し、[c(i)] = [a(i)]*[b(i)]を計算する。D = [([ai]; [bi]; [ci])] (i=1,..., M = (N + C*L)*B)となり、[c（i）]は上記プロトコルの結果であり、必ずしも正しいとは限らない。
【００６６】
＜カット及びバケット(Cut and bucket)（ステップＳ１０４）＞
各パーティの乗算三つ組生成プロセス１０２は、いくつかの三つ組（C個の三つ組）を開き、三つ組が正しく生成されているか、最初の検証を行い、残りを複数のバケット(buckets)へランダムに分割する。
【００６７】
(a)各パーティの乗算三つ組生成プロセス１０２は、(N + C*L)*(B - 1) + N個の三つ組を有するDを、D'（1）、...、D'（B）のベクトルに分割し、図５に示すように、D'（1）がN個の三つ組を含み、各D'（j）（j = 2、...、B）が（N + C * L）個の三つ組を含むようにする。ここで、各パーティは、他のパーティも同じことを行うという前提で、Dの自身のシェアのみを分割する。
【００６８】
(b)k = 2〜Bについて、各パーティの乗算三つ組生成プロセス１０２は、D'（k）を、等しいサイズXのL個の部分配列に分割する（L *（X-C）= N）。図６に示すように、等しいサイズXのL個の部分配列は、D''（k、1）、...、D ''（k、L）となる。ここでも各パーティは、自身のシェアのみを分割する。図６では、D''（k、1）、...、D''（k、L）（k=1,...,B）それぞれにおけるC個の三つ組が、開かれるべき三つ組となる。
【００６９】
(c)k = 2、...、B、及びj = 1、...、Lについて、各パーティの乗算三つ組生成プロセス１０２は、D ''（k、j）に含まれる三つ組の順序を共同でランダムに並べ替える。ここで、各パーティは、それぞれのシェアのみをランダムに並べ替える。ただし、すべてのパーティが同意するランダム性を使用することにより、すべての順列が同じになるように調整される。
【００７０】
(d)k = 2、...、Bについて、各パーティの乗算三つ組生成プロセス１０２は、D ''（k、1）、...、D ''（k、L）間のL個の部分配列の順序を共同で並べ替える。
【００７１】
(e)k = 2、...、B、及びj = 1、...、Lについて、 過半数のパーティそれぞれの乗算三つ組生成プロセス１０２は、図６に示すように、D''(k, j)に含まれる最初のC個の三つ組を開き、a(i)b(i)=c(i)が成り立つか否か検証する（インデックスiは、選択した三つ組のインデックス）。
【００７２】
上記のように、各過半数のパーティのうち少なくとも１つのパーティは、a（i）、b（i）、c（i）を復元し、当該パーティは次の方程式を検証できる。a（i）b（i）= c（i）
【００７３】
いずれの過半数のパーティの組もこれを拒否しない場合、すべてのパーティはD''（k、j）からこれらを削除する。
【００７４】
過半数のパーティの組のいずれかが、検証を拒否した場合、他のパーティに「停止（Abort）」を送信し、プロトコルとして「停止」を出力する。
【００７５】
(f)残りの三つ組は、図７に示すように、それぞれBのサイズの（B個の三つ組を含む）N組の三つ組 E '（1）、...、E'（N）に分割される。
【００７６】
＜バケットのチェック（Check buckets）（ステップＳ１０５）＞
ベクトルdの長さをNとする。i= 1、...、Nについて、E '（i）では、B個の三つ組のうち、最初の三つ組 ([a(1)], [b(1)], [c(1)])は、残りのB -1個の三つ組 ([a(j)], [b(j)], [c(j)]) (j=2,...,B)を用いて、上記の三つ組検証方法にて検証される。図７に示すように、パーティは、長さNのベクトルdのi番目のエントリd(i)に([a(1)], [b(1)], [c(1)])を設定する。
【００７７】
＜ステップＳ１０６＞
現時点で、各パーティにおいて、N個の乗算三つ組がベクトルdに用意されている。パーティは、N個の乗算三つ組を出力する。
【００７８】
追加のN個の三つ組が必要な場合には、常に、上記のプロトコルを実行して取得できる（ステップＳ１０１〜Ｓ１０６）。
【００７９】
＜回路計算（Circuit Computation）＞
図８を参照して、各パーティの回路計算プロセス１０４の動作を説明する。
【００８０】
回路および回路への入力のシェアが入力される（ステップＳ２０１）。回路にはゲートと配線が含まれる。各ゲートは、乗算または加算ゲートのいずれかになる。各乗算ゲートと加算ゲートとは、２本の入力配線と１本の出力配線を有する。
【００８１】
図９に示すように、入力配線のぞれぞれは、回路への入力またはゲートの出力のいずれかとなることができる。出力配線のそれぞれは、回路の出力、他のゲートへの入力、またはその両方になることができる。入力配線と出力配線はそれぞれ、１つの秘密シェアに関連付けられている。したがって、各ゲートは、秘密のシェア入力（例えば[x]、[y]、...）が与えられると、秘密のシェア出力（例えば [z]、..）を生成する。
【００８２】
回路における計算段階の開始時、秘密シェアの組である入力が回路へ与えられ、各値はゲートへの入力となる（ステップＳ２０２）。
【００８３】
両方の入力配線の秘密シェアが既に生成されている各ゲートにおいて、その出力配線の秘密値は、セミオネストな秘密計算（セミオネストな攻撃者に対する安全なマルチパーティ計算）によって生成することができる（ステップＳ２０３）。
【００８４】
秘密シェアがその入力配線のために用意されたすべてのゲートに対してステップＳ２０３の手順を繰り返すことにより（ステップＳ２０４）、回路のすべての出力の秘密値が生成できる（ステップＳ２０５）。
【００８５】
＜回路検証（Circuit Validation）＞
各パーティの回路検証（circuit validation）プロセス１０６の動作を、図１０を参照して説明する。
【００８６】
各パーティの回路検証プロセス１０６は、それぞれN個の三つ組の、２つのバッファベクトルV及びV'を用意する。回路検証プロセス１０６は、乗算三つ組生成プロセス１０２によって生成されたN個の三つ組で２つのバッファベクトルV及びV'を満たす（N=(X-C)*L）（ステップＳ３０１）。
【００８７】
各パーティの回路検証プロセス１０６は、バッファベクトルV及びV'を満たすのに十分な数の三つ組を生成するのに必要な回数だけ乗算三つ組生成プロセス１０２を実行する。
【００８８】
図１１に示すように、各パーティの回路検証プロセス１０６は、バッファベクトルV及びV'を、それぞれのサイズがX'=X-CであるL個の部分配列V（1）、...、V（L）、及びV'（1）、...、V'（L）にそれぞれ分割する（ステップＳ３０２）。
【００８９】
回路計算プロセス１０４による回路計算の結果は、それぞれが秘密分散入力(secrete shared inputs)および秘密分散出力(secrete shared outputs)を含む一連のゲートとして見ることができる。
【００９０】
加算ゲートの場合、非対話型プロトコルであるため、ゲートが他のパーティのデータを操作できるという意味で、いずれのパーティも他のパーティに対して効果的に悪意を持つことはできない。
【００９１】
乗算ゲートの場合、パーティは効果的に悪意のある動作をすることができる。したがって、一連の乗算ゲートの妥当性のみを検証すれば十分である。ここで、一連の乗算ゲートをQと称する。
【００９２】
一連の乗算ゲートの数をM'とし、L'に対して、M'=X'L'+K（ただし、X'=X-C、及び、K < X'）。
【００９３】
図１１に示すように、Qを、順次Q（1）、...、Q（L'）、及びQ（L' + 1）に分割し、Q（1）、...、Q（L'）はサイズX'であり、Q(L'+1)はサイズKである（ステップＳ３０３）。
【００９４】
i=1〜L'+1について（ステップＳ３０４）、以下のステップＳ３０５乃至Ｓ３０８を実行する。
【００９５】
＜ステップＳ３０５＞
各パーティの回路検証プロセス１０６は、バッファベクトルV'から１つの部分配列をランダムに選ぶ。この部分配列をランダムにシャッフルしてもよい。これを部分配列S(i)と称する。
【００９６】
＜ステップＳ３０６〜Ｓ３０７＞
j=1〜X'の場合、各パーティの回路検証プロセス１０６は、S(i)のj番目の組（乗算三つ組）を用いて、Q(i)のj番目の組（回路内のゲートのj番目の三つ組）を検証する。i = L'+ 1の場合、jはX'ではなくKまでである。例えば、（[x], [y]）がj番目の三つ組への入力配線のシェアであり、[z]がj番目のfQ（i）の出力配線のシェアであるとすると、パーティは、([x], [y], [z])及び([a(j)], [b(j)], [c(j)])に対して三つ組の検証を行い、([x], [y], [z])を検証する。すなわち、関連するゲートの計算が正しく実行されたことを検証する。いずれかのパーティがすべての処理を受け入れない場合、当該パーティは「停止（Abort）」を他のパーティに送信する。
【００９７】
＜ステップＳ３０８＞
各パーティの回路検証プロセス１０６は、V'のS（i）をV（i）に置き換え、VのV（i）を削除する。
【００９８】
＜ステップＳ３０９〜Ｓ３１０＞
上記の処理が完了すると、j=L'+2〜M’の全てについて、各パーティの回路検証プロセス１０６は、V(j)をV(j-L'+1)にリネーム（rename）する。ここで、M'は、V（M' + 1）が空になる。
【００９９】
なお、上記の改名ステップ（Ｓ３０９〜Ｓ３１０）では、V（j）が補充されない限り、一部のjに対してV（j）は空になる。
【０１００】
上記の処理により、バッファベクトルV内のすべての部分配列(subarray)が削除される。そして、これは、乗算三つ組生成プロセス１０２により補充できる。バッファベクトルV内の三つ組は、予め設定された大きいサイズのチャンクによってのみ消費され補充される。
【０１０１】
M/2個の三つ組が、LK+M個の三つ組から選択され、上記のように検証されたものとする。GとTを適切な値として、この検証で正しく生成されていない三つ組を検出しない確率は、1/T個を超える三つ組が正しく生成されない場合、G未満になる。
【０１０２】
上記の実施形態において、１つの三つ組を検証するためにB-1個の三つ組を用いるため、乗算三つ組生成プロセス１０２の出力が、（1/T）^B個を超える数の正しく生成されていない三つ組を含む確率はGになる（^はべき乗演算子）。
【０１０３】
選択されたGが非常に小さい確率なため、システムのユーザはTを増大させることでこれを無視できるとする（これは常に可能である）。ユーザは、正しく生成されていない三つ組の予想数を（このような悪意のある三つ組の生成が検出されない場合）、Bを増大させることによって減らすことができる。
【０１０４】
バッファベクトルV'に格納されている三つ組は、回路内のゲートの三つ組が生成された後にランダムに選択されるため、悪意のあるパーティは、バッファベクトルV'の三つ組の非常に小さな部分が正しく生成されない場合でも、検出される危険を冒さずに上記ゲートの計算を偽ることはできない。
【０１０５】
バッファベクトルV'は、その要素（V'（i）：ランダムに選ばれシャッフルされる）が検証に用いられた後、常にバッファベクトルVから補充されるため、三つ組が選択される集合のサイズは、同じで十分な大きさのままである。これにより、悪意のあるゲート計算を検出する能力は高く保たれる。さらに、この処理では、消費された三つ組が即座に補充されるため、バッファベクトルV'における消費された三つ組の位置を記憶するためのメモリは必要ない。
【０１０６】
バッファベクトルV内の乗算三つ組は、予め設定された（大きい）サイズのチャンクによってのみ消費され補充される。消費される三つ組は、バッファベクトルV内でランダムに分散される訳ではなく、最後に消費された三つ組の位置を使用して順番に消費されるため、バッファ管理が簡単になる。
【０１０７】
シャッフル操作は２つの方法で実行される。その内の１つは、短い列における細かいシャッフルである。列を十分に短くすることにより、キャッシュメモリに置き、高速操作を達成することができる。
【０１０８】
他の１つの方法は、シャッフルされる単位が上記の列である長い列の粗いシャッフルである。データのみが特定のサイズのチャンク内で移動するため、各三つ組に対する操作コストは小さくなる。
【０１０９】
上記の２つのシャッフルの組み合わせは、全体として完全なシャッフルにはならないが、本発明の実施形態が関与する秘匿性には十分である。したがって、高速操作で十分に高い秘匿性が得られる。
【０１１０】
本発明の実施形態により、各パーティは、他のパーティの入力を知ることなく、分散した方法で入力の任意の関数を計算することが可能になる。
【０１１１】
あるパーティがプロトコルに従わない場合、他のパーティはこれを検知できる。このような計算方法は、マシンのマルウェア又はマシンの操作者がデータを盗もうとする可能性がある、機密データが処理されるサービスに適用できる。
【０１１２】
上記のパーティは、例えば図１２に示されるようなコンピュータシステム上で実現されてもよい。図１２を参照すると、コンピュータ装置１１０は、プロセッサ(Central Processing Unit)１１２と、例えば半導体メモリ（例えばＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＥＥＰＲＯＭ（Electrically Erasable Programmable ROM））、及び／又はＨＤＤ（Hard Disk Drive）、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disc）のうち少なくとも１つを含む記憶装置などを含むメモリ１１４と、表示装置１１６（ディスプレイ）と、通信インタフェース１１８とを含む。通信インタフェース１１８（ネットワークインタフェースコントローラ（Network Interface Controller；ＮＩＣ）など）は、他のパーティと通信するように構成されてもよい。図２のパーティの処理を実行するプログラムは、メモリ１１４に記憶されており、プロセッサ１１２が、メモリからプログラムを読み取り、プログラムを実行して秘密計算を行うパーティを実現する。
【０１１３】
なお、上記非特許文献１乃至５の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせ乃至選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１１４】
１００  パーティ
１０２  乗算三つ組生成プロセス
１０４  回路計算プロセス
１０６  回路検証プロセス
１１０  コンピュータ装置
１１２  プロセッサ
１１４  メモリ
１１６  表示装置
１１８  通信インタフェース
【図１Ａ】
0006973868.tif 000006
【図１Ｂ】
0006973868.tif 000007
【図２】
0006973868.tif 000008
【図３】
0006973868.tif 000009
【図４】
0006973868.tif 000010
【図５】
0006973868.tif 000011
【図６】
0006973868.tif 000012
【図７】
0006973868.tif 000013
【図８】
0006973868.tif 000014
【図９】
0006973868.tif 000015
【図１０】
0006973868.tif 000016
【図１１】
0006973868.tif 000017
【図１２】
0006973868.tif 000018