(57)【要約】  プライバシ保護またはセキュアマルチパーティ計算を行うための方法により、複数のパーティが協力して、個々のパーティによって与えられた入力データのプライバシを保護しながら、分散型結果を出すことができる。本方法は、パーティ間通信が過度に負担となることなく、結果の完全に正確な平文（非プライバシ保護）計算に関して、特定の高精度または高い正確さで結果を出すことができる。マルチパーティ計算には、例えば、秘密分散型入力データを使用する機械学習分類器の訓練における、連続関数のフーリエ級数近似、または三角多項式を使用する連続関数の近似を含めることができる。マルチパーティ計算には、計算され、浮動小数点表示で格納された秘密分散型データのインスタンスを、メモリ記憶要件が緩い計算済み秘密分散型データの同等な、同等に正確で、かつ同等にセキュアなインスタンスに変換する秘密シェア縮小を含めることができる。【選択図】図１６
2020532771.tif 000002
【特許請求の範囲】
【請求項１】
個々のパーティによって与えられた入力データのプライバシを保護しながら、セキュアマルチパーティ計算を行って、結果を出すための方法であって、
ディーラコンピューティングシステムが、複数の関連数字マスキングデータ成分セットを作り出すことであって、関連数字マスキングデータ成分セットごとに、前記セットの各成分が、スカラ、ベクトル、および行列のうちの１つである、作り出すことと、
前記ディーラコンピューティングシステムが、複数のパーティコンピューティングシステム間で、前記複数の関連数字マスキングデータ成分セットの各セットの各成分を秘密分散させることと、
前記複数のパーティコンピューティングシステムのパーティコンピューティングシステムごとに、前記パーティコンピューティングシステムが、
信頼できるディーラから、前記複数の数字マスキングデータ成分セットの各セットの各成分のそれぞれの秘密シェアを受信することと、
少なくとも１つの入力データセットに対して、前記入力データセットの秘密シェアを受信することと、
前記パーティコンピューティングシステムに、前記パーティコンピューティングシステムのうちのその他とともに、かつその他と連絡して、計算済み秘密分散型データの１つ以上のインスタンスを作り出させる、プログラム命令セットを実行することであって、インスタンスごとに、前記パーティコンピューティングシステムが、入力データセットの少なくとも１つの秘密シェアか、または計算済み秘密分散型データの別のインスタンスの少なくとも１つの秘密シェアに基づき、前記インスタンスの秘密シェアを計算し、数字マスキングデータ成分の受信した秘密シェアが、前記計算中に伝えられたデータをマスクするのに使用され、前記計算が、
（ａ）連続関数のフーリエ級数近似、または連続関数の三角多項式を使用する近似、
（ｂ）計算され、浮動小数点表示で格納された秘密分散型データのインスタンスを、メモリ記憶要件が緩い計算済み秘密分散型データの同等な、同等に正確で、かつ同等にセキュアなインスタンスに変換する秘密シェア縮小、のうちの少なくとも１つを含む、実行することと、
計算済み秘密分散型データのインスタンスの秘密シェアを、前記複数のパーティコンピューティングシステムのうちの１つ以上の他のシステムに送信することと、
前記複数のパーティコンピューティングシステムのうちの少なくとも１つのパーティコンピューティングシステムでは、前記パーティコンピューティングシステムが、
前記複数のパーティコンピューティングシステムのうちの１つ以上の他のシステムから、計算済み秘密分散型データのインスタンスの１つ以上の秘密シェアを受信し、かつ
計算済み秘密分散型データの前記インスタンスの前記受信した秘密シェアを結合して、前記結果を出すことと、を含む、方法。
【請求項２】
前記計算が、（ａ）および（ｂ）の両方を含む、請求項１に記載の方法。
【請求項３】
前記計算が、
関数の定義域を複数の部分区間に分割することと、
前記複数の部分区間の部分区間ごとに、
前記部分区間における前記関数の近似値を定めることと、
ガーブル化回路および紛失選択のうちの少なくとも１つを使用して、計算済み秘密分散型データのインスタンスを計算することと、をさらに含む、請求項１に記載の方法。
【請求項４】
前記計算が、（ａ）を含む、請求項１に記載の方法。
【請求項５】
前記近似値が、ある区間における前記連続関数のものである、請求項４に記載の方法。
【請求項６】
前記近似値が、前記連続関数の一様近似値である、請求項５に記載の方法。
【請求項７】
前記連続関数が、機械学習活性化関数である、請求項４に記載の方法。
【請求項８】
前記機械学習活性化関数が、シグモイド関数である、請求項７に記載の方法。
【請求項９】
前記機械学習活性化関数が、双曲線正接関数である、請求項７に記載の方法。
【請求項１０】
前記機械学習活性化関数が、ニューラルネットワーク向けの整流器活性化関数である、請求項７に記載の方法。
【請求項１１】
前記連続関数が、前記シグモイド関数である、請求項４に記載の方法。
【請求項１２】
前記計算が、（ｂ）を含む、請求項１に記載の方法。
【請求項１３】
前記秘密シェア縮小が、計算済み秘密分散型データのインスタンスの各秘密シェアの１つ以上の最上位ビットをマスクすることを含む、請求項１２に記載の方法。
【請求項１３】
前記結果が、ロジスティック回帰分類モデルの係数集合である、請求項１に記載の方法。
【請求項１４】
前記方法が、ロジスティック回帰分類器を実装し、前記結果が、前記入力データに基づく前記ロジスティック回帰分類器の予測である、請求項１に記載の方法。
【請求項１５】
前記ディーラコンピューティングシステムが、信頼できるディーラコンピューティングシステムであり、前記パーティコンピューティングシステム間の通信が、前記信頼できるディーラコンピューティングシステムにはアクセス不能である、請求項１に記載の方法。
【請求項１６】
前記ディーラコンピューティングシステムが、ｈｏｎｅｓｔ−ｂｕｔ−ｃｕｒｉｏｕｓディーラコンピューティングシステムであり、前記パーティコンピューティングシステム間の通信が前記ｈｏｎｅｓｔ−ｂｕｔ−ｃｕｒｉｏｕｓディーラコンピューティングシステムによってアクセスされ得るか否かに関わらず、前記パーティコンピューティングシステムのうちの１つ以上によって与えられた秘密分散型入力データのプライバシが保護される、請求項１に記載の方法。
【請求項１７】
少なくとも１つの入力データセットに対し、前記入力データセットにおいて統計解析を行って、入力データセット統計値を確定することと、
前記入力データセット統計値を使用して、ソースコード命令セットの事前実行を行い、１つ以上の変数型の各々に対して統計的型パラメータを生成することと、
前記統計的型パラメータ集合に基づいて、前記ソースコード命令セットをコンパイルして、前記プログラム命令セットを生成することと、をさらに含む、請求項１に記載の方法。
【請求項１８】
前記事前実行が、
反復回数が確定可能である前記ソースコード命令セットにおいてｌｏｏｐを公開することと、
前記ソースコード命令セットにおいて関数呼び出しを公開することと、に続いて行われる、請求項１７に記載の方法。
【請求項１９】
少なくとも１つの関連数字マスキングデータ成分セットが、３つの成分から成り、前記３つの成分は、前記成分のうちの１つが前記成分のうちの残りの２つの乗算積に等しいという関係性を有する、請求項１に記載の方法。
【請求項２０】
少なくとも１つの関連数字マスキングデータ成分セットが、数字と、前記数字に対して評価されたフーリエ基底関数の１つ以上の対応値集合と、を含む、請求項１に記載の方法。
【請求項２１】
前記結果が、前記結果の平文計算に関して所定の精度を有する、請求項１〜２０のいずれか一項に記載の方法。
【請求項２２】
前記複数のパーティコンピューティングシステムのうちの少なくとも１つが、前記複数のパーティコンピューティングシステム間で、それぞれの入力データセットを秘密分散させることをさらに含む、請求項１〜２０のいずれか一項に記載の方法。
【請求項２３】
複数のコンピューティングシステムを備えるシステムであって、前記複数のコンピューティングシステムが、請求項１〜２０のいずれか一項に記載の方法を行うように構成されている、システム。
【請求項２４】
請求項１〜２０のいずれか一項に記載のプログラム命令セットで符号化された非一時的コンピュータ可読媒体。
【請求項２４】
複数のコンピュータシステムによって実行されると、前記複数のコンピュータシステムに、請求項１〜２０のいずれか一項に記載の方法を行わせる、コンピュータコードで符号化された非一時的コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本出願の主題は、２０１７年８月３０日出願の米国仮特許出願第６２５５２１６１号、２０１７年９月１８日出願の米国仮特許出願第６２５６０１７５号、２０１８年３月９日出願の米国仮特許出願第６２６４１２５６号、および２０１８年３月２４日出願の米国仮特許出願第６２６４７６３５号に関連しており、これらの出願のすべては、それらの全体が参照により本明細書に組み込まれる。
【背景技術】
【０００２】
プライバシ保護またはセキュアマルチパーティ計算において、先行技術では有効な解決策が見出せない問題がある。例えば、金融詐欺またはフィッシング攻撃などの不正行為を検出するために、いくつかの組織が、機械学習分類器の訓練に協調して取り組むことを望んでいると仮定する。各組織には、合法行為および不正行為の例を含む訓練データセットがあるが、個々の組織は、彼らのデータのプライバシおよび秘密性を保持する一方、まだ分類器の訓練に彼らのデータを協力して与えることができることを望む。このような訓練は、理論上、プライバシ保護技法またはセキュアマルチパーティ計算技法を使用して達成され得る。ただし、有効であるためには、分類器は、何が、はるかに頻度の高い合法行為に比べて、相対的に稀に起こる不正行為であるかを検出する非常に高い精度レベルに対応している必要もある。既存のセキュアマルチパーティ計算技法は、過度に負担となるほどのパーティ間通信を必要とせずには、このような訓練に不可欠な精度レベルをもたらすことはない。
【発明の概要】
【０００３】
プライバシ保護またはセキュアマルチパーティ計算を行うための方法により、複数のパーティが協力して、個々のパーティによって与えられた入力データのプライバシを保護しながら、分散型結果を出すことができる。この方法は、パーティ間通信が過度に負担となることなく、結果の完全に正確な平文（非プライバシ保護）計算に関して、特定の高精度または高い正確さでその結果を出すことができる。マルチパーティ計算には、例えば秘密分散型入力データを使用する機械学習分類器の訓練における、連続関数のフーリエ級数近似、または三角多項式を使用する連続関数の近似を含めることができる。マルチパーティ計算には、計算され、浮動小数点表示で格納された秘密分散型データのインスタンスを、メモリ記憶要件が緩い計算済み秘密分散型データの同等な、同等に正確で、かつ同等にセキュアなインスタンスに変換する秘密シェア縮小を含めることができる。
【０００４】
当業者には分かるように、この概要の他の個所に記載の複数の態様を、様々な実施可能な実施形態において様々に組み合わせることができる。本開示では、このような実施可能な組合せのすべてについて、効率の点で明確に示さないことがあるが、その可能性を具体的にじっくり考える。
【０００５】
セキュアマルチパーティ計算を行うための方法は、個々のパーティによって与えられた入力データのプライバシを保護しながら、結果を出すことができる。
【０００６】
この方法では、ディーラコンピューティングシステムが、複数の関連数字マスキングデータ成分セットを作り出すことができ、関連数字マスキングデータ成分セットごとに、そのセットの各成分が、スカラ、ベクトル、および行列のうちの１つである。ディーラコンピューティングシステムは、複数のパーティコンピューティングシステム間で、複数の関連数字マスキングデータ成分セットの各セットの各成分を秘密分散させることができる。
【０００７】
この方法では、複数のパーティコンピューティングシステムの各パーティコンピューティングシステムでは、パーティコンピューティングシステムは、複数の数字マスキングデータ成分セットの各セットの各成分のそれぞれの秘密シェアを、信頼できるディーラから受信することができる。パーティコンピューティングシステムは、少なくとも１つの入力データセットに対して、その入力データセットの秘密シェアを受信することができる。パーティコンピューティングシステムは、パーティコンピューティングシステムに、パーティコンピューティングシステムのうちの他のシステムとともに、また他のシステムと連絡して、計算済み秘密分散型データの１つ以上のインスタンスを作り出させるプログラム命令セットを実行することができる。インスタンスごとに、パーティコンピューティングシステムは、入力データセットの少なくとも１つの秘密シェアかまたは計算済み秘密分散型データの別のインスタンスの少なくとも１つの秘密シェアに基づき、インスタンスの秘密シェアを計算することができる。数字マスキングデータ成分の受信秘密シェアを使用して、計算の最中に伝えられたデータをマスクすることができる。
【０００８】
計算には、例えば、連続関数のフーリエ級数近似、または三角多項式を使用する連続関数の近似を含めることができる。計算には、例えば、計算され、浮動小数点表示で格納された秘密分散型データのインスタンスを、メモリ記憶要件が緩い計算済み秘密分散型データの同等の、同等に正確で、かつ同等にセキュアなインスタンスに変換する秘密シェア縮小も含めることができ、または代替として含めることができる。
【０００９】
この方法では、パーティコンピューティングシステムは、複数のパーティコンピューティングシステムのうちの１つ以上の他のシステムに、計算済み秘密分散型データのインスタンスの秘密シェアを送信することができる。少なくとも１つのパーティコンピューティングシステムでは、パーティコンピューティングシステムは、複数のパーティコンピューティングシステムのうちの１つ以上の他のシステムから、計算済み秘密分散型データのインスタンスの１つ以上の秘密シェアを受信することができる。パーティコンピューティングシステムは、計算済み秘密分散型データのインスタンスの受信秘密シェアを結合して、結果を出すことができる。
【００１０】
計算が、関数の定義域を複数の部分区間に分割することと、複数の部分区間の部分区間ごとに、部分区間に対して関数の近似を確定し、ガーブル化回路および紛失選択（ｏｂｌｉｖｉｏｕｓ  ｓｅｌｅｃｔｉｏｎ）のうちの少なくとも１つを使用して、計算済み秘密分散型データのインスタンスを計算することと、をさらに含むような方法が行われ得る。
【００１１】
連続関数の近似は、ある区間にあり得る。近似は、連続関数の一様近似であり得る。連続関数は、機械学習活性化関数であり得る。機械学習活性化関数は、シグモイド関数であり得る。機械学習活性化関数は、双曲線正接関数であり得る。機械学習活性化関数は、ニューラルネットワーク向けの整流器活性化関数であり得る。連続関数は、シグモイド関数であり得る。
【００１２】
秘密シェア縮小には、計算済み秘密分散型データのインスタンスの各秘密シェアの１つ以上の最上位ビットをマスクすることを含めることができる。結果は、ロジスティック回帰分類モデルの係数集合であり得る。方法は、ロジスティック回帰分類器を実装することができ、結果は、入力データに基づくロジスティック回帰分類器の予測であり得る。
【００１３】
ディーラコンピューティングシステムは、信頼できるディーラコンピューティングシステムであり得、パーティコンピューティングシステム間の通信を、信頼できるディーラコンピューティングシステムにはアクセス不可にすることができる。
【００１４】
ディーラコンピューティングシステムは、ｈｏｎｅｓｔ−ｂｕｔ−ｃｕｒｉｏｕｓディーラコンピューティングシステムであり得、パーティコンピューティングシステム間の通信がｈｏｎｅｓｔ−ｂｕｔ−ｃｕｒｉｏｕｓディーラコンピューティングシステムによってアクセスされ得るか否かに関わらず、パーティコンピューティングシステムのうちの１つ以上によって与えられた秘密分散型入力データのプライバシが保護され得る。
【００１５】
方法には、入力データセットが少なくとも１つある場合、入力データセットに対して統計的解析を行って、入力データセット統計値を確定することと、入力データセット統計値を使用してソースコード命令セットの事前実行を行って、１つ以上の変数型のそれぞれに対して統計的型パラメータを生成することと、統計的型パラメータ集合に基づきソースコード命令セットをコンパイルして、プログラム命令セットを生成することと、をさらに含めることができる。事前実行は、反復回数が確定可能であるソースコード命令セットにおいてｌｏｏｐ（ループ）を公開し、そのソースコード命令セットにおいて関数呼び出しを公開するのに続いて行われ得る。
【００１６】
少なくとも１つの関連数字マスキングデータ成分セットが、３つの成分から成り、この３つの成分は、成分のうちの１つが成分のうちの残りの２つの乗算積に等しいという関係性を有するような方法が行われ得る。
【００１７】
少なくとも１つの関連数字マスキングデータ成分セットが、数字と、その数字に対して評価されたフーリエ基底関数の１つ以上の対応値集合と、を含むような方法が行われ得る。
【００１８】
結果が、その結果の平文計算に関連して所定の精度を有するような方法が行われ得る。
【００１９】
複数のパーティコンピューティングシステムのうちの少なくとも１つが、複数のパーティコンピューティングシステム間で、それぞれの入力データセットを秘密分散させるような方法が行われ得る。
【００２０】
システムは、複数のコンピュータシステムを含み得、複数のコンピュータシステムは、方法を行うように構成されている。
【００２１】
非一時的コンピュータ可読媒体が、プログラム命令セットで符号化され得る。
【００２２】
非一時的コンピュータ可読媒体が、複数のコンピュータシステムによって実行されると、複数のコンピュータシステムに、方法を行わせるコンピュータコードで符号化され得る。
【図面の簡単な説明】
【００２３】
【図１】リスケール済みシグモイドの奇数−偶数周期拡張のグラフを示す図である。
【図２】定理１によるシグモイドの漸近近似を示す図である。
【図３】一実施形態によるＭＰＣプロトコルのオフライン段階中の接続の概略図である。
【図４】一実施形態によるオンライン段階中の参加者間の通信チャネルの概略図である。
【図５】ｎ＝３参加者対象の本発明の実験中に得た様々な測定値をまとめた本発明の実装形態の結果の表である。
【図６】ロジスティック回帰の最中の費用関数の開方を反復回数の関数として示す図である。
【図７】同じロジスティック回帰の最中のＦ−スコアの開方を反復回数の関数として示す図である。
【図８】真理値表例および対応する暗号化真理値表（暗号化表）を示す図である。
【図９】様々なカーブル化最適化に対し、ガーブル化時間、カーブル化サイズ、および評価時間を与える表である。
【図１０】比較回路例を示す図である。
【図１１】秘密加算回路例を示す図である。
【図１２】関数の２つの例の図である。
【図１３】ｎ個の文字を処理する状態機械の概略図である。
【図１４】一実施形態によるコンパイルを行うための方法を示す図である。
【図１５】様々な実施形態による、開示された構成要素を実装するように適宜構成され得る汎用コンピュータアーキテクチャを示す図である。
【図１６】様々な実施形態による、セキュアマルチパーティ計算を行うための方法を示す図である。
【発明を実施するための形態】
【００２４】
以下の説明では、それに従って本開示の発明の対象が実施され得る、様々な実施形態について述べる。実施形態によっては、１つの／ある／別の実施形態などといった表現を使用して記述されることがあり、そのうちの複数の場合が、必ずしも同じ実施形態を指すわけではない。このような場合に関連する特定の特徴、構造、または特性は、特に断りのない限り、様々な実施形態において、任意の好適な方式で組み合わせられ得る。
【００２５】
Ｉ．高精度プライバシ保護実数値関数評価
０  概要
高数値精度で連続実数値関数を評価するのに新奇のマルチパーティ計算プロトコルを提案する。本発明の方法は、フーリエ級数を用いた近似に基づき、オンライン段階中に、多くても２回の通信しか使用しない。オフライン段階では、それぞれ、信頼できるディーラ支援型ソリューションとｈｏｎｅｓｔ−ｂｕｔ−ｃｕｒｉｏｕｓ支援型ソリューションを提案する。稀な事象を検出し、前に提案したプライバシ保護最適化方法（例えば、シグモイド関数の区分線形近似に基づく）を使用して解くことのできない、不均衡な分類問題を計算するように、ニュートン法の一種によってロジスティック回帰分類器を訓練するのに、この方法を適用する。本発明のプロトコルは、標準４倍精度浮動小数点算術を使用して実装することができるので効率的である。複数の実験を報告し、ロジスティック回帰モデルを訓練するための本発明の方法を実装するデモアプリケーションを提供する。
【００２６】
１  序文
プライバシ保護計算により、複数のパーティが、入力を内密にしておき、関数の出力のみ明かして、他は何も明かさないまま、関数を評価することができる。マルチパーティ計算（ＭＰＣ：Ｍｕｌｔｉ−Ｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ）、準同型暗号、および差分プライバシにおける最近の進歩が、これらのモデルを実用的にしている。このような計算の例には、医薬や金融の用途では、数ある中でも、入力データが別々の秘密データソース［１７］、［２３］、［２５］、［２６］から来る監視下モデルの訓練と、これらのモデルを使用する予測の評価がある。
【００２７】
機械学習分類問題では、新しい入力を別々の範疇に写像することによって、その新しい入力を予測するように、所与のデータセットにおいてモデルを訓練する。古典的なロジスティック回帰モデルは、予測に関連付けられた確率を提供することによって、クラスを予測する。モデルの品質を測定することができるいくつかの方法があり、最も一般的なものは、正しく予測された回答の割合を示す正確さである。
【００２８】
データセット（例えば、手書き数字のＭＮＩＳＴデータベース［１５］またはＡＲＣＥＮＥデータセット［１４］）の大半で、分類は、シグモイド関数
2020532771.tif 000003
2020532771.tif 000004
と定義、
の区分線形近似を使用して勾配降下を数回反復しただけで、その時の費用関数は最小値［２５］にはまだ遠いが、非常によい正確さを得るように思われる。これまで、シグモイド関数の他の近似方法も提案されてきた。［２９］において、低次多項式による近似は、より効率的であるがそれほど正確ではない方法をもたらした。反対に、［２４］における深層学習方法に適用されたより高次多項式近似は、より正確であるが、それほど効果的ではない方法（そのため、プライバシ保護計算にはあまり好適ではない）をもたらした。並行して、分類方法および深層学習の両方の背景において、準同型暗号［２］、［２７］、［１８］、［２２］および差分プライバシ［１］、［１０］に基づくプライバシ保護方法のための近似ソリューションが提案されている。
【００２９】
それにも関わらず、特に、［１９、ｐ．４２３］で述べたように、本発明の目標が、稀な疾患または不正金融取引などの稀な事象を検出することにある場合、正確さそのものは、モデルの品質にとって必ずしも十分な尺度ではない。例えば、１０００回の取引当たりの１回が不正である場合、すべての取引を正当として分類する単純モデルは、９９．９％の正確さを達成するが、このモデルには、予測能力がない。このような場合、精度、リコール、およびＦ１−スコアなどの尺度は、モデルの品質をよりよく判断するのを可能にさせる。それらは、データセット全体ではなく肯定的な事象のみに対して、偽陽性または偽陰性の割合を結び付けた。
【００３０】
上記の技法は、ほとんどのバランスのとれたデータセットに優れた正確さをもたらすが、シグモイド関数の大雑把な近似に頼っていることから、これらの技法は、同じモデルに収束せず、それにより、非常に低い合格率でデータセットに対して悪いスコアを与える。本明細書では、ＭＰＣにおいてこの数値精度をどのように回復させるか、またどのように平文回帰と同じスコアに達するかを示す。このＭＰＣ手法は、大部分、事前計算済み乗算数字マスキングデータ［４］による加法的秘密シェアに基づく。これは、計算が二段階に分けられていることを意味し、１つは、データが参加者（パーティまたはパーティコンピューティングシステムとも呼ばれる）間で分散される前に実行され得るオフライン段階と、もう１つは、実際の結果を計算するオンライン段階である。オフライン段階について、信頼できるディーラに基づく第１のソリューションを提案し、次に、ディーラがｈｏｎｅｓｔ−ｂｕｔ−ｃｕｒｉｏｕｓである場合のプトロコルについて考察する。ディーラまたは信頼できるディーラは、ディーラコンピューティングシステムと呼ばれる場合もある。
【００３１】
１．１  貢献
第１の貢献は、シグモイド関数のフーリエ近似である。プライバシ保護計算では、実数値関数の評価が、広く使用されてきた。例えば、線形回帰モデルおよびロジスティック回帰モデルを訓練するためには、平方根、指数、対数、シグモイド関数、またはソフトマックス関数などの実数値関数を計算し、それを使用して、非線形最適化問題を解く必要がある。ロジスティック回帰モデルを訓練するためには、連続シグモイド関数の対数の観点から表される費用関数を最小化する必要がある。この最小値は、通常、勾配降下などの反復法によって計算される。低合格率のデータセットの場合、十分に精密なモデルを得るためには、正確な最小値により近づくことが重要である。したがって、反復回数を大幅に増やすか（ナイーブ勾配降下または確率的勾配降下）、より高速の収束法（例えば、ＩＲＬＳ［５、§４．３］）を使用する必要がある。後者は、特に入力データが、正規化も特徴量スケールもされない場合、これまでＭＰＣの背景において達成されてきたものよりもずっと優れるシグモイドの数値近似を必要とする。一点（その点でのみローカルに良い近似をもたらす）の周りのテイラー級数による近似または多項式近似などの様々な手法がこれまで考えられてきた。最初のものよりも良いが、この方法は、係数のサイズのバラツキにより数値的に安定していない。区分線形関数による近似に基づく代替方法も考えられてきた。ＭＰＣでは、秘密分散およびマスキングに代わってガーブル化回路とともに使用されると、この方法はうまく働くが、十分な正確さをもたらさない。
【００３２】
本発明の場合、この背景において初めて適用された手法であるフーリエ級数を使用して、シグモイドを概算する。この方法は、関数が十分にスムーズである（シグモイドの場合のように）と仮定すると、より一様な近似をもたらすようにうまく働く。具体的には、事実上、シグモイドをスケール変換し直し、周期関数に広げ、この周期関数は、三角多項式で近似され、次に、安定したプライバシ保護方式で値が求められる。ＭＰＣにおいて値が求められ得る汎用関数を三角多項式で近似するには、滑らかな周期拡張のフーリエ級数を使用するか、または、半周期における距離に対して、最小二乗の方法によって、直接、最も近い三角多項式を見付けるかのいずれかである。最初の手法は、せいぜい超代数的収束しかもたらさないが、２番目の手法は、指数関数的に素早く収束する。一方、最初の手法は、数値的に安定しているが、２番目の手法は、そうではない（標準フーリエ基底下で）。シグモイドの場合で、両方の性質を同時に得ることができることを示す。
【００３３】
第２の貢献は、浮動小数点表示およびマスキングである。マスキングを用いたマルチパーティ計算プロトコルへの典型定な取り組みは、固定小数点値を有限群に埋め込み、一様なマスキングおよび秘密分散を使用することである。それにより、演算回路が、例えば、事前計算済み乗算数字マスキングデータおよび以下のＢｅａｖｅｒ法［４］を使用して、評価され得る。この考えは、［１３］および［１２］においてうまく使用されている。この方法は、相関または線形回帰［１７］のような低乗算深さ回路にうまく働くが、通常、必要とされる群サイズが、乗算深さに従って指数関数的に大きくなる。［２５］において、この指数関数的成長は、２パーティ丸め解法によって弱められるが、この技法は、最上位ビットにおけるオーバーフローが起こる可能性がある、３つ以上のパーティには及ばない。本発明では、固定小数点値が（場合によってはマルチビット）浮動小数点を使用して直接分散されるという代替の分散法を紹介し、また乗算するたびにシェアサイズを縮小する技法を提示する。この技法は、任意の数の参加者にも難なく及ぶ。
【００３４】
第３の貢献は、通信時間の大幅な短縮である。本明細書では、［２５］に見られるのと同じ手法に従い、大規模行列乗算、システム解決、またはシグモイドの紛失評価など、高位命令に専用の数字マスキングデータを定義する。この手法は、ＳＰＤＺにおいて見られるようなマスキング下位命令ほど一般的ではないが、大きな要素によって通信およびメモリの要件を緩くすることを可能にする。マスクおよび演算では、ベクトル次元または行列次元の型が分かっており、上位演算のベクトル性質から利を得る。例えば、２つの行列の乗算では、コンパイラのバッチング品質に応じて、係数単位の手法には、最高Ｏ（ｎ３）ではなく、一回の通信で足りる。さらに、基本演算ごとにではなくイミュータブル変数ごとに、マスキングが定義されるので、この方法全体を通して、定数行列をマスクするのが１回のみで済む。非自明局所演算と組み合わせると、これらの数字マスキングデータを使用して、ただ環の加法または乗算よりも一層多くのことを実現することができる。簡単に言うと、通信量が、同じマスクを再使用する結果として減り、通信回数が、行列や他の大きな構造体を直接マスクする結果として減る。したがって、総通信時間が、計算費用に比べてごくわずかになる。
【００３５】
第４の貢献は、ｎ参加者まで拡張可能なｈｏｎｅｓｔ  ｂｕｔ  ｃｕｒｉｏｕｓオフライン段階用の新しいプロトコルである。高い効率を維持しながら、一般的な人数ｎの参加者にまで難なく拡張可能であるｈｏｎｅｓｔ−ｂｕｔ−ｃｕｒｉｏｕｓモデルにおいてオフライン段階を実行する際の新しいプロトコルを紹介する。これを実現するのに、ピアツーピア通信の代わりに同報通信チャネルを使用して、通信回数における二次急増を避ける。このモデルにおけるｎ＞３参加者用のこれまでのプロトコルのいずれも効率的ではなかったので、これは、重要な貢献である。［１７］では、例として、信頼できるディーラモデルにおける非常に効率的な方法を提案するが、まだ紛失通信プロトコルの実行時間は、極めて遅い。
【００３６】
２  記号および前置き
Ｐ１、．．．、Ｐｎは、個々の計算パーティ（参加者）であると仮定する。本明細書に必要とされるいくつかの基本概念をマルチパーティ計算から想起する。
【００３７】
２．１  秘密分散およびマスキング
（Ｇ、●）を群とし、ｘ∈Ｇを群要素とする。
2020532771.tif 000005
（若干の記号濫用による）によって示されるｘの秘密シェアは、ｘ＝ｘ１●・・・●ｘｎであるようなタプル（ｘ１、．．．、ｘｎ）∈Ｇｎである。（Ｇ、＋）がアーベルであれば、秘密シェアｘ１、．．．、ｘｎ加法的秘密シェアを呼び出す。いずれか２つの要素ｘ、ｙ∈Ｇについて、シェアの狭義サブタプル
2020532771.tif 000006
が見分けが付かない場合、秘密分散法は、計算上安全である。Ｇが一様分布を許す場合、情報−理論的セキュア秘密分散法は、一様に無作為にｘ１、．．．、ｘｎ−１を描き、
2020532771.tif 000007
を選ぶことから成る。Ｇがコンパクトではない場合、統計上または計算上の区別性に対して条件を緩めることができる。
【００３８】
密接に関わる概念は、群マスキングの概念である。Ｇの部分集合Ｘを与えると、マスキングＸの目標は、ｘ∈Ｘの場合のｘ●Ｄの分布がすべて見分けが付かないようなＧ上の分布Ｄを見付けることである。当然、このような分布を使用して、秘密シェアを作り出すことができ、λ←Ｄを標本抽出し、ある参加者にλ−１を与え、他の参加者にｘ●λを与えることができる。またマスキングを使用して、結果が準同型（例えば、Ｂｅａｖｅｒの三つ組乗算技法［４］に見られるような）によって密かに非マスク化されるとすぐに、マスク済みデータにわたって非線形演算を明確に評価することができる。
【００３９】
２．２  マスキングによる秘密シェアを用いた算術
和ｘ＋ｙ（または、（Ｇ、＋）が加群構造を有する場合は一次結合）に向けた秘密シェアの計算は、ｘおよびｙの対応するシェアを加えることにより、各参加者によって非対話式に行われ得る。積に向けた秘密シェアの計算は、より厄介なものである。これを行う１つの方法は、事前計算され、秘密分散された乗法的数字マスキングデータに基づくＢｅａｖｅｒの考えを用いることである。一般的な視点から、（Ｇ１、＋）、（Ｇ２、＋）、および（Ｇ３、＋）を３つのアーベル群とし、π：Ｇ１×Ｇ２→Ｇ３を双線形写像とする。
【００４０】
２つの元ｘ∈Ｇ１およびｙ∈Ｇ２について加法的秘密シェア
2020532771.tif 000008
を仮定し、元π（ｘ、ｙ）∈Ｇ３に対して秘密シェアを計算したいと思う。Ｂｅａｖｅｒの方法では、参加者は、λ∈Ｇ１およびμ∈Ｇ２について事前計算された使い捨ての無作為数字マスキングデータ
2020532771.tif 000009
を採用し、次にそれを使用して、ａ＝ｘ＋λおよびｂ＝ｙ＋μをマスクし、また明かす必要がある。次に、参加者は、以下のようにπ（ｘ、ｙ）について秘密シェアを計算する：
−参加者１が、ｚ１＝π（ａ、ｂ）−π（ａ、μ１）−π（λ１、ｂ）＋（π（λ、μ））１を計算する、
−参加者ｉ（ｉ＝２、．．．、ｎ）が、ｚｉ＝−π（ａ、μｉ）−π（λｉ、ｂ）＋（π（λ、μ））ｉを計算する。
【００４１】
計算済みｚ１、．．．、ｚｎは、π（ｘ、ｙ）の加法的シェアである。所与のλの使用で、１つだけしか変数をマスクすることができないので、オフライン段階の間（すなわち、参加者に使用可能なデータが作られる前）、乗算のたびに１つの三つ組（より一般的に言えば、数字マスキングデータセット）を事前計算する必要がある。適切な群でインスタンス化され、この抽象的な方式は、環における積だけではなく、ベクトル内積、行列−ベクトル積、または行列−行列積を求めることを可能にする。
【００４２】
２．３  実数値連続関数のＭＰＣ評価
様々な用途で（例えば、以下の６節のロジスティック回帰）、秘密分散型データにわたって連続実数値関数を計算する必要がある。非線形関数（例えば、指数、対数、ベキ、余弦、正弦、シグモイドなど）に対しては、本文献に様々な方法が提案されている。
【００４３】
単純な手法は、完全浮動小数点演算の枠組を実装することと［６、１２］、浮動小数点にわたって関数を評価するデータ−紛失法をコンパイルすることから成る。これは、例えば、ＳｈａｒｅｍｉｎｄおよびＳＰＤＺが使用するものの場合である。しかし、これら２つの一般的な方法は、浮動小数点関数を何百万回も評価する必要がある場合、法外な実行時間につながる。
【００４４】
第２の手法は、この関数を計算しやすい近似値に置き換えることであり、例えば、［２５］は、ガーブル化回路を使用して、固定小数点比較および絶対値を求め、次に、ロジスティック回帰におけるシグモイド関数を区分線形関数に置き換える。そうでなければ、［２４］は、シグモイドを固定した次数の多項式で近似し、この多項式をホーナー法で評価するが、それにより、その次数に比例した通信回数を必要とする。
【００４５】
ＳＰＤＺ［１３］が有限体で逆関数を計算する方法に近い別の方法は、乗法的マスキングによる多項式評価に基づいており、形式
2020532771.tif 000010
の事前計算済み数字マスキングデータを使用して、参加者は、ｕ＝ｘλを明かし、かつ一次結合
2020532771.tif 000011
を出力することによって、
2020532771.tif 000012
を評価することができる。
【００４６】
ただし、乗法的マスキングは、ある漏洩を伴い、すなわち、有限体において、ｘがゼロであるか否かを明かす。この状況は、有限環においていっそう悪くなり、そこでは、ｘの乗算軌道が開示され（例えば、行列環で階数が明かされる可能性がある）、
2020532771.tif 000013
にわたって、ｘの桁が明かされる可能性がある。
【００４７】
実数値多項式の場合、変数ｘを範囲［１、２］に入るように変換し、再スケーリングすることによって、漏洩が減らされる可能性がある。しかし、通常、この変換された関数を近似する多項式の係数が、激増し、それにより、深刻な数値上の問題が起こる。
【００４８】
２．４  フル閾値ｈｏｎｅｓｔ−ｂｕｔ−ｃｕｒｉｏｕｓプロトコル
本発明の目標が、実数値連続関数の効率的な評価および良質なロジスティック回帰などの新しい機能性に重点を置くことにあるので、参加者全員が何の誤りも持ち込むことなく、プロトコルに従うというシナリオを考えることが多い。ただし、参加者は、全取引履歴を記録し、データについての違法情報を知ろうとする可能性がある。オンライン段階中、ｎのうち多くてｎ−１の参加者のどのような結託によっても、合法的かつ明確に明かされた集計結果以外のデータのいずれの意味的性質も見分けることができないことをセキュリティモデルが課す。これを実現する際、信頼できるディーラと呼ばれるただ１つのエンティティによって、Ｂｅａｖｅｒ三つ組（数字マスキングデータとも呼ばれ、参加者の秘密シェアをマスクするのに使用される）が生成され、分散され得る。この場合、多くてｎ−１の参加者が提携しても、平文数字マスキングデータ情報に対して計算上の利益を何ら得るはずはない。しかし、ディーラ自身が平文数字マスキングデータを知り、それにより、データ全体を知ることは、いくつかの外部委託のユースケースでのみ意味を成す。以下の５節では、この時点でディーラとの双方向通信を伴う、同じ数字マスキングデータを生成するための代替のｈｏｎｅｓｔ−ｂｕｔ−ｃｕｒｉｏｕｓ（またはｓｅｍｉ−ｈｏｎｅｓｔ）プロトコルを示す。この場合、事前計算済み行列を生成するために、ディーラと参加者とがオフライン段階の間協力するが、彼らのうちの誰も平文数字マスキングデータ全体にアクセスしない。これは、ディーラがいずれの参加者とも結託せず、少なくとも１人の参加者が他の参加者と結託しない限り、意味が通っている。今後の研究に向けて積極的にセキュアなプロトコルの構想を残しておく。
【００４９】
３  統計的マスキングおよび秘密シェア縮小
この節では、固定小数点演算用の本発明のマスキング技法を提示し、実数値連続関数のＭＰＣ評価用の方法を提供する。具体的には、ＭＰＣにおいてｐビットの数値精度を得るには、τが固定セキュリティパラメータであるｐ＋２τ−ビット浮動小数点を持てば十分であることを示す。
【００５０】
本発明で考察する秘密シェアは、実数である。本発明では、浮動小数点数を使用して、これらのシェアをマスクしたいと思う。まだ、
2020532771.tif 000014
上の一様分布がないので、実数にわたってマスキング分布を加えても、任意の入力を完全に隠すことはできない。秘密シェアがある程度分かっている数値精度範囲に属する場合、マスク済み値が入力についての情報を計算上何も漏らさないように、精度範囲に応じて、マスキング分布を慎重に選ぶことが可能である。分布が十分に大きな標準偏差であれば、その役割を果たすことができ、本明細書の以下では、この種類のマスキングを「統計的マスキング」と呼ぶ。実際には、標準偏差σ＝２４０の正規分布を選ぶ。
【００５１】
一方、このようなマスキングを使用することによって、Ｂｅａｖｅｒの技法により乗算を評価するたびに、秘密シェアのサイズが大きくなることが分かる（２．２節）３．３節では、各秘密シェアの最上位ビットを捨てることによって（秘密シェアの和がまだそれらのサイズよりも相当に小さいという事実を使用して）、秘密シェアサイズを縮小することを可能にする技法を導入することによって、この問題に取り組む。
【００５２】
３．１  浮動小数点、固定小数点、および区間精度
Ｂが整数であり、ｐが非負整数（ビット数）であると仮定する。ベキ指数Ｂおよび数値精度ｐの固定小数点数のクラスは、
2020532771.tif 000015
である。
【００５３】
各クラスＣ（Ｂ、ｐ）は、有限であり、２Ｐ＋１＋１個を含む。それらをリスケールし、（ｐ＋２）−ビット整数として格納してもよい。代替として、小数点表示が少なくともｐビットの対小数を有するという条件では、個数ｘ∈Ｃ（Ｂ、ｐ）は、浮動小数点値ｘでも表され得る。この場合、同じ数値精度のクラスにわたる数の加法および乗算は、浮動小数点演算に自然に写像される。これらのクラスにおける主要な算術演算は：
−無損失加法：Ｃ（Ｂ１、ｐ１）×Ｃ（Ｂ２、ｐ２）→Ｃ（Ｂ２、ｐ）、式中、Ｂ＝最大（Ｂ１、Ｂ２）＋１、およびｐ＝Ｂ−最小（Ｂ１−ｐ１、Ｂ２−ｐ２）、
−無損失乗法：Ｃ（Ｂ１、ｐ１）×Ｃ（Ｂ２、ｐ２）→Ｃ（Ｂ、ｐ）、式中、Ｂ＝Ｂ１＋Ｂ２、およびｐ＝ｐ１＋ｐ２、
−丸め：Ｃ（Ｂ１、ｐ１）→Ｃ（Ｂ、ｐ）、これは、ｘを２Ｂ−ｐ
2020532771.tif 000016
におけるその最も近い元に写像する。
【００５４】
無損失演算では、ｐが乗算深さにおいて指数関数的に大きくなることを必要とするが、固定精度演算では、最終丸めを適用することによって、ｐが一定のままである。最後に、ベキ指数Ｂが、加法の結果を格納するように増分される必要があるが、Ｂが固定小数点演算におけるユーザ定義のパラメータであることに留意されたい。ユーザがＢを変えないでおくことを無理やり選んだ場合、いずれの結果｜ｘ｜＞２Ｂも出力ドメインに表わすことができなくなる（この種のオーバーフローを平文オーバーフローとする）。
【００５５】
３．２  浮動小数点表示
セキュリティパラメータτを与えると、対抗者は、Ｃ（Ｂ、ｐ）において２つの平文ｍ０、ｍ１を選び、挑戦者は、ｂ∈｛０、１｝およびα∈Ｓを一様ランダムに選び取り、ｃ＝ｍｂ＋αを対抗者に送信する、という区別可能性ゲームが、アドバンテージ≧２−τでは勝つことができない場合、集合ＳがクラスＣ（Ｂ、ｐ）に対するτ−セキュアマスキング集合であると言える。対抗者は、ｂを言い当てる必要がある。
2020532771.tif 000017
へのこのような区別アドバンテージの上昇では、少なくとも２τの標本を攻撃者に与えることが必要になる可能性があるので、実際には、τ＝４０で十分であることに留意されたい。
【００５６】
命題１。
2020532771.tif 000018
は、Ｃ（Ｂ、ｐ）についてのτ−セキュアマスキング集合である。
【００５７】
証明。ａ、ｂ∈Ｃ（Ｂ、ｐ）およびＵがＣ（Ｂ、ｐ、τ）上の一様分布ならば、ａ＋Ｕとｂ＋Ｕとの間の統計上の距離は、（ｂ−ａ）・２ｐ−Ｂ／＃Ｃ（Ｂ、ｐ、τ）≦２−πである。この距離は、いずれの計算上のアドバンテージにも上限を付ける。
【００５８】
また、クラスＣ（Ｂ、ｐ、τ）＝Ｃ（Ｂ＋τ、ｐ＋τ）がｐ＋τ−ビットの対小数の浮動小数点数に適合するので、それらを使用して、数値精度ｐで固定小数点数をしっかりとマスクすることができる。さらに、Ｃ（Ｂ、ｐ）についてのすべての加法的シェアは、Ｃ（Ｂ、ｐ、τ）で取られることになる。
【００５９】
ここで、Ｂｅａｖｅｒのプロトコルを使用して、２つの平文、ｘ∈Ｃ（Ｂ１、ｐ）とｙ∈（Ｂ２、ｐ）とを掛け合わせると、何が起こるかを分析する。マスク済み値ｘ＋λ、ｙ＋μは、それぞれ、
2020532771.tif 000019
によって境界される。また、マスクλが
2020532771.tif 000020
によって境界され、マスクμが
2020532771.tif 000021
によって境界されるので、ｘ・ｙの計算済み秘密シェアは、
2020532771.tif 000022
によって境界されることになる。そのため、無損失乗算は、Ｃ（Ｂ、ｐ、τ）に代わって、Ｂ＝Ｂ１＋Ｂ２であるＣ（Ｂ１、ｐ、τ）×Ｃ（Ｂ２、ｐ、τ）→Ｃ（Ｂ、２ｐ、２τ）を送信する。ｐを縮小することは、単に丸めの問題であり、浮動小数点表示によって自動的に行われる。ただし、出力秘密シェアが２Ｂ＋τによって境界されるようにτを小さくするための方法がまだ必要である。
【００６０】
３．３  秘密シェア縮小方法
提案するこの方法は、２つの補助パラメータに左右され、これらの補助パラメータは、２ηが絶対値における望ましい限界であるようにη＝Ｂ＋τと定義された切り捨てと、参加者人数より大きな補助パラメータＭ＝２κである。
【００６１】
中心となる考えは、初期シェアが、合計で小さな秘密分散型値ｚになる大きな構成要素ｚ１、．．．、ｚｎを含むということである。それに加え、切り捨て位置を越えるシェアの最上位ビット（例えば、
2020532771.tif 000023
）は、データに関する何の情報も含まず、明かしても全く安全である。シェアの和（すなわち、データのＭＳＢ）がゼロであることも分かっているので、シェアのＭＳＢの和は、非常に小さい。シェア縮小方法は、この和を計算し、それを参加者間に均一に分配し直すだけで済む。和が小さいことが約束されるので、大きな整数においてではなくＭを法として計算が行われる。より正確に言えば、ｉ＝１、．．．、ｎに対して切り捨てパラメータηを使用して、参加者ｉは、ｚの自分の秘密シェアｚｉを、
2020532771.tif 000024
およびｕｉ∈［−２η−１、２η−１］である、ｚｉ＝ｕｉ＋２ηｖｉとして書き込む。次に、参加者ｉは、ｖｉ  ｍｏｄ  Ｍを同報通信して、各参加者が和を計算するようにする。個々のシェアは、必要に応じて、ν＝０  ｍｏｄ  Ｍである事前計算済みシェア
2020532771.tif 000025
を使用して、再ランダム化され得る。
2020532771.tif 000026
が−Ｍ／２〜Ｍ／２の範囲にあることが約束されるので、Ｍを法とするその表現から復元され得る。それにより、各参加者は、同じ和を元のシェアとして構築することによって得るが、２ηによって境界付けられるｕｉ＋２ηｗ／ｎとして、自分のシェアをローカルに更新する。
【００６２】
３．４  マスク縮小方法
以下の方法は、上の３．３節に記述したような、秘密シェアのサイズを縮小するための一実施形態の詳細である。この手順は、浮動小数点に関わる古典的なＭＰＣ乗算の中で使用され得る。
入力：
2020532771.tif 000027
および１つの数字マスキングデータセット
2020532771.tif 000028
、ν＝０  ｍｏｄ  Ｍ。
出力：シェアの絶対値を小さくした、同じ値ｚに対する秘密シェア。
１：各参加者Ｐｉが、ｚｉ＝ｕｉ＋２ηｖｉであるような、ｕｉ∈［−２η−１、２η−１］および
2020532771.tif 000029
を計算する。
２：各参加者Ｐｉは、ｖｉ＋νｉ  ｍｏｄ  Ｍを他の参加者に同報通信する。
３：参加者は、
2020532771.tif 000030
を計算する。
４：各参加者Ｐｉは、ｚの新しいシェアを
2020532771.tif 000031
として計算する。
【００６３】
４  フーリエ近似
フーリエ理論により、特定の周期関数を三角多項式で近似することを可能にする。この節の目的は、２つあり、ＭＰＣにおいて三角多項式をどのように評価するかを示すことと、同時に、いくつかの近似結果の非周期関数への拡張を再検討し、示すことである。
【００６４】
４．１  ＭＰＣにおける三角多項式またはフーリエ級数の評価
複雑な三角多項式は、
2020532771.tif 000032
であるａｍ＋ｉｂｍに等しい、形式
2020532771.tif 000033
の有限和であることを思い出してみる。各三角多項式は、周期２πを有する周期関数である。すべての
2020532771.tif 000034
について
2020532771.tif 000035
であるならば、ｔは、実数値であり、よりなじみのあるコサイン分解
2020532771.tif 000036
に対応する。ここで、ＭＰＣ背景において三角多項式をどのように評価するかを説明し、それが、普通の多項式よりも優れている理由を説明する。
【００６５】
すべてのｍについて、ｔの係数ａｍおよびｂｍが公然とアクセス可能であり、かつ０≦ａｍ、ｂｍ≦１であると仮定する。ｔが２π周期であるので、２πを法とする入力に対してそれを評価することができる。
2020532771.tif 000037
は、一様分布の余地があることから、一様マスクキングを使用することができ、この方法は、乗法的マスキングによる古典的な多項式の評価に関連している漏洩問題を完全に片付ける、ということを言っておく。一方、この評価の出力は、まだ
2020532771.tif 000038
にあり、この場合、前の節で説明した統計的マスキングを使用して、先に進む。この入力は、内密に分散され、加法的にマスクされるが、分かりやすくするために、２πを法とする加法から実数上の古典的な加法を区別するのに、２πを法とする加法を一時的に
2020532771.tif 000039
で表すことにする。同様に、２πを法とする加法に関する加法的秘密シェアを
2020532771.tif 000040
と表す。次に、２πを法としてシェアを自明に縮小することによって、
2020532771.tif 000041
への遷移がもたらされ得る。
【００６６】
次に、秘密分散型入力
2020532771.tif 000042
に対してｔを評価する方法は、
2020532771.tif 000043
を
2020532771.tif 000044
に変換し、それを分散型マスキング
2020532771.tif 000045
で加法的にマスクし、次に
2020532771.tif 000046
を明かし、標的
2020532771.tif 000047
を
2020532771.tif 000048
として書き換えることである。当然、
2020532771.tif 000049
が明かされるので、係数
2020532771.tif 000050
が明確に計算され得る。まとめると、
2020532771.tif 000051
などの事前計算済み三角多項式またはフーリエ級数マスキングデータを前提とし、
2020532771.tif 000052
が明かされているという事実によると、多項式ｔ全体を一回の通信で評価することができる。
【００６７】
また、絶対値１の複素数を用いて作業すると、普通の多項式におけるベキ関数に比べて、この方法が数値的に安定することが分かる。これが、本発明の背景において、三角多項式の評価がより良いソリューションである理由である。
【００６８】
４．２  非周期関数の近似
非周期関数ｆを一様に近似することに関心がある場合（所与の区間、例えば［−π／２、π／２］における三角多項式を用いて）、フーリエ係数を単純に使用することはできない。当然、この関数が解析的である場合でも、そのフーリエ級数は、ギブス現象に起因して終点近くに一様に収束する必要はない。
【００６９】
４．２．１  Ｃ∞−拡張による近似
この問題を打開する１つのやり方は、より広い区間へのこの関数の周期拡張を探し、その拡張に対するフーリエ級数の収束性に着目することである。指数関数的収束を得るには、そのことがめったに保証されないという条件で、拡張も解析的である必要がある。言い換えれば、古典的なホイットニー拡張定理［２８］は、同時に周期的でもある解析的な拡張をもたらすことはめったにない。微分可能関数を拡張するための建設的な手法が、より一般的にＨｅｓｔｅｎｅｓ［２０］およびＦｅｆｆｅｒｍａｎ［１６］によって与えられている。これに一番期待できることは、この関数をＣ∞−関数（解析的ではない）に拡張することである。［８］、［９］で説明しているように、このような拡張は、よくても指数関数的ではないスーパー代数的近似をもたらすに過ぎない。
【００７０】
４．２．２  最小二乗近似
三角多項式で非周期関数を近似するための代替の手法は、元の関数と近似との間のＬ２−距離の制約（元の区間に対する）が最小限に抑えられているようなより広い区間（例えば、［−π、π］）において、これらの関数を探すことである。この方法は、最初に［７］によって提案されたが、標準フーリエ基底に関する係数が、基底関数の個数を増やすのに従って発散する（最適解で）という意味において、この係数が数値的に不安定であることが確認されている。［２１］の方法は、最適解の係数が数値的に安定するようになる第一種および第二種のいくつかの半範囲チェビシェフ多項式の異なる正規直交基底を使用することによってこの問題を打開することを可能にする。さらに、ガウス求積則を使用して、これらの係数を数値的に計算することができる。
【００７１】
４．２．２．１  半周期にわたる三角多項式による関数の近似
ｆを、必ずしも滑らかまたは周期的とは限らない、区間［−π／２、π／２］における自乗可積分関数とする。
【００７２】
４．２．２．１．１  近似問題
２π−周期関数の集合
2020532771.tif 000053
および問題
2020532771.tif 000054
を考えてみる。
【００７３】
［７］で確認したように、この単純な基底を使用して最適解を書く場合、関数ｇｎのフーリエ係数は、非有界であり、それにより数値的な不安定をもたらす。［２１］では、第一種および第二種のチェビシェフ多項式に密接に関係する直交多項式の２つの族の観点から、どのように最適解を記述するかについて説明されている。より重要なことには、この最適解が、スーパー代数的にではなく指数関数的にｆに収束することが証明され、これらの基数の観点から最適解ｇｎ（ｘ）をどのように数値的に評価するかが示されている。
【００７４】
ここで［２１］の方法を要約することにする。以下とし、
2020532771.tif 000055
Ｃｎをこれらの関数が及ぶ
2020532771.tif 000056
（偶関数の部分空間）とする。同様に、以下とし、
2020532771.tif 000057
ＳｎをＳｎの
2020532771.tif 000058
（奇関数の空間）とする。ＣｎＵＳｎがＧｎに対する基数であることに留意されたい。
【００７５】
４．２．２．１．２  第一種および第二種のチェビシェフの多項式
ｙ∈［−１、１］の場合のＴｋ（ｙ）を第一種の第ｋチェビシェフ多項式、すなわち、すべてのθについてＴｋ（ｃｏｓθ）＝ｃｏｓｋθを満たし、Ｔｋ（１）＝１（Ｔｋは、次数ｋを有する）であるように正規化された、多項式とする。ｋが変わるにつれて、この多項式は、重み関数
2020532771.tif 000059
に関して直交する。同様に、ｙ∈［−１、１］の場合のＵｋ（ｙ）を第二種の第ｋチェビシェフ多項式、すなわち、ＵＫ（ｃｏｓθ）＝ｓｉｎ（（ｋ＋１）θ）／ｓｉｎθを満たし、Ｕｋ（１）＝ｋ＋１であるように正規化された、多項式とする。多項式｛Ｕｋ（ｙ）｝は、重み関数
2020532771.tif 000060
に関して直交する。
【００７６】
［２１、定理３．３］では、偶関数の空間に対して正規直交基底を形成する半範囲チェビシェフ多項式の数列
2020532771.tif 000061
をどのように定義するかを説明している。同様に、［２１、定理３．４］は、奇関数に対して正規直交基底
2020532771.tif 000062
をもたらす（第二種の半範囲チェビシェフ多項式）。［２１、定理３．７］に従って、上記の問題に対する最適解ｇｎが、以下によって得られ、
2020532771.tif 000063
ここで、
2020532771.tif 000064
また、
2020532771.tif 000065
である。
【００７７】
標準フーリエ基底において最適解ｇｎを表すことは、数値的に不安定であるが、正規直交基底
2020532771.tif 000066
の観点からそれらを表すことは、安定している。さらに、［２１、定理３．１４］では、収束が指数関数的であることを示している。係数ａｋおよびｂｋを数値的に計算する際、［２１、§５］で説明しているようなガウス求積則を使用する。
【００７８】
４．２．３  シグモイド関数の近似
ここで、あるＢ＞０の場合の区間［−Ｂ／２、Ｂ／２］にわたるシグモイド関数の場合に限って説明する。［−π／２、π／２］にわたりｇ（ｘ）＝ｓｉｇｍｏ（Ｂｘ／π）を近似するように変数をリスケールすることができる。ｇを鏡映条件ｇ（ｘ）＝ｇ（π−ｘ）で区間［π／２、３π／２］まで反周期性（奇数−偶数）によって拡張した場合、連続２π−周期区分Ｃ１関数を得る。ディリクレの大域的な定理によって、ｇのフーリエ級数が、
2020532771.tif 000067
で一様に収束するので、すべてのε＞０について、
2020532771.tif 000068
であるような、次数Ｎおよび三角多項式ｇＮが存在する。秘密分散型ｔにわたりｓｉｇｍｏ（ｔ）を計算するには、最初に、変数（ＭＰＣにおいて評価しやすい）のアフィン変化を適用して、対応するｘ∈［−π／２、π／２］を得て、次に、フーリエ数字マスキングデータを使用して三角多項式ｇＮ（ｘ）を評価する。１０項しかない多項式で２４ビットの精度を得るには、この方法で十分であるが、漸進的に、収束率は、ｇの導関数における不連続性により、θ（ｎ−２）だけである。言い換えれば、ｇをλビットの精度で近似するには、次数２λ／２の三角多項式を評価する必要がある。好都合にも、シグモイド関数の特殊な場合、区間全体［−π、π］で（半区間ではない）リスケール済みシグモイドに指数関数的に近い２π−周期の解析関数を明示的に構築することによって、この次数の多項式を計算することができる。それ以外にも、三角多項式の係数の幾何級数的減衰は、完全な数値的安定性を確実にする。以下の定理に、この構造をまとめる。
【００７９】
定理１。Ｘ∈（−π、π）に対してｈα（ｘ）＝１／（１＋ｅ−αｘ）−ｘ／２πとする。ε＞０ごとに、ｈαが２π−周期の解析関数ｇから一定の距離ε／２にあるようなα＝Ｏ（ｌｏｇ（１／ε）が存在する。ｇのフーリエ級数の第Ｎ項がｇのε／２の距離にあり、したがって、ｈαから≦εの距離にあるような、Ｎ＝Ｏ（ｌｏｇ２（１／ε））が存在する。
【００８０】
ここで、以下の方法論を用いて定理１を証明する。まず、微分方程式を使用して、シグモイド関数の連続導関数に限界を設ける。次に、シグモイドの最初の導関数が指数関数的にすぐに減衰することから、２πを法としていずれのｘに対しても、その値のすべてを合計し、［−π、π］上で元の関数を厳密に近似するＣ∞周期関数を構成することができる。最後に、連続導関数における限界が、フーリエ係数の幾何級数的減少の直接の証明となる。
【００８１】
証明。最初に、
2020532771.tif 000069
のσ（ｘ）＝１／（１＋ｅ−ｘ）のシグモイド関数を考えてみる。σは、微分方程式σ’＝σ−σ２を満たす。ｎ回微分することによって、
2020532771.tif 000070
を得る。（ｎ＋１）！で割ると、以下の式が得られる。
2020532771.tif 000071
そこから、すべてのｎ≧に対する、またすべての
2020532771.tif 000072
に対するそれを、帰納法によって導き出し、それがｎで減少するので、すべての≧１に対し、
2020532771.tif 000073
となる。
【００８２】
図１は、リスケール済みシグモイドの奇数−偶数周期拡張のグラフを示す。リスケール済みシグモイド関数ｇ（αｘ）は、
2020532771.tif 000074
に、反周期性によって拡張される。このグラフは、α＝１、３、５の場合の拡張された関数を示す。対称性によって、出力関数のフーリエ級数は、奇数正弦項：
2020532771.tif 000075
となる。α＝２０／πに対して、最初のフーリエは、素早く２４ビットの精度をもたらす、［６．１２ｅ−１、１．５１ｅ−１、５．３７ｅ−２、１．９９ｅ−２、７．４１ｅ−３、２．７５ｅ−３、１．０３ｅ−３、３．８２ｅ−４、１．４４ｅ−４、５．１４ｅ−５、１．８７ｅ−５、．．．｝の素早く減少する数列を形成する。しかし、この数列は、
2020532771.tif 000076
における導関数の不連続性により、Ｏ（ｎ−２）において漸近的に減少するので、この方法は、指数関数的に都合の良い近似を得るのに好適ではない。
【００８３】
図２は、定理１によるシグモイドの漸近近似を示す。αが大きくなるにつれて、リスケール済みシグモイド関数
2020532771.tif 000077
の不連続性が消え、そのフーリエ係数が幾何級数的にすぐに減少する、解析的な周期関数に指数関数的に近づく。この方法は、数値的に安定しており、多項式時間において任意の精度でシグモイドを評価することができる。
【００８４】
ここで、ｈαの導関数に非常に近いはずである周期関数を構成し、
2020532771.tif 000078
を考えることにする。幾何級数の総和により、ｇαは、
2020532771.tif 000079
のうまく定義された無限に導出可能な２π−周期関数である。すべてのｘ∈（−π、π）について、差
2020532771.tif 000080
が
2020532771.tif 000081
によって境界付けされるので、
2020532771.tif 000082
を選ぶことにより、この差を
2020532771.tif 000083
より小さくすることができる。
【００８５】
ここで、αが一定であると仮定し、ｇαが解析的であることを、すなわち、そのフーリエ係数が指数関数的に素早く減少することを証明する。定義により、
2020532771.tif 000084
であるので、すべてのｐ∈Ｎについて、
2020532771.tif 000085
であるので、
2020532771.tif 000086
である。これは、第ｎフーリエ係数ｃｎ（ｇα）が
2020532771.tif 000087
であることを証明する。
2020532771.tif 000088
では、この最小値に達し、｜ｃｎ（ｇα）｜＝Ｏ（ｅ−ｎ／α）が得られる。
【００８６】
最後に、これは、
2020532771.tif 000089
を選ぶことによって、ｇαのフーリエ級数の第Ｎ項が、ｇαの≦εの距離に、したがって
2020532771.tif 000090
から≦εの距離にあることを証明する。この境界は、区間（−π、π）全体にわたってシグモイドの望ましい近似を生み出す三角多項式を積分することによって守られる（この定理からのｇは、ｇａの原始関数である）。
【００８７】
５  Ｈｏｎｅｓｔ  ｂｕｔ  Ｃｕｒｉｏｕｓモデル
これまでの節では、乗算、累乗、およびフーリエ数字マスキングデータのシェアを定義しているが、どのようにそれらを生成するかを説明していなかった。もちろん、全参加者（ＴＤモデル）によって認められただ１つの信頼できるディーラが、必要なシェアのすべてを生成し、それを参加者に分配する可能性がある。信頼できるディーラがすべてのマスク、したがってすべてのデータを知っているので、ＴＤモデルは、いくつかの計算外部委託シナリオに対してのみ合法的である。
【００８８】
ここで、より従来型のｈｏｎｅｓｔ−ｂｕｔ−ｃｕｒｉｏｕｓ（ＨＢＣ）モデルにおいて、どのように効率的に同じ数字マスキングデータを生成するかを説明する。そのようにするには、対話型プロトコルにおいて、数字マスキングデータを生成するのに加わるが、マスク済み情報しか見ない、ディーラとも呼ばれる外部エンティティを抱えておく。ＨＢＣモデルとＴＤモデルとで数字マスキングデータが、同様なので、オンライン段階は、変わらずにいる。このＨＢＣモデルではディーラが秘密シェアにアクセスしない場合でも、ディーラがまだ参加者よりも力をもつことに留意されたい。実際には、参加者のうちの１人が秘密データに関する情報を得たいと思う場合、その参加者は、他のすべての参加者と結託する必要があるが、ディーラは、参加者のうちのただ１人と協力するだけで済む可能性がある。
【００８９】
５．１  ｈｏｎｅｓｔ−ｂｕｔ−ｃｕｒｉｏｕｓ通信チャネル
以下では、オフライン段階中、各参加者とディーラとの間にプライベートチャネルが存在すると仮定する。ＨＢＣディーラの場合、また、追加のプライベート同報通信チャネル（ディーラがアクセスしないチャネル）が、全参加者間に存在すると想定する。後で、オンライン段階は、参加者間の公開同報通信チャネルのみ必要とする。実際には、根底にある暗号化のために、プライベートチャネル（例えば、ＳＳＬ接続）は、公開チャネル（普通のＴＣＰ接続、通常、クラウドインスタンス間で１００〜１０００ＭＢ／ｓ）よりも情報処理量が低い（通常、
2020532771.tif 000091
）。
【００９０】
この節に提示している図は、信頼できるディーラモデルおよびｈｏｎｅｓｔ  ｂｕｔ  ｃｕｒｉｏｕｓモデル両方における参加者とディーラとの間の通信チャネルを表す。２種類の通信チャネルが使用され、１つは、実際にはＳＳＬチャネルに対応するプライベートチャネル（通常、＜２０ＭＢ／ｓ）で、もう１つは、実際にはＴＣＰ接続に対応する公開チャネル（通常、１００ＭＢ〜１ＧＢ／ｓ）である。この図では、プライベートチャネルは、破線で表され、公開チャネルは、普通の線で表されている。
【００９１】
図３は、一実施形態による、ＭＰＣプロトコルのオフライン段階中の接続の概略図を示す。この図は、オフライン段階中に使用される、信頼できるディーラモデル（左）とｈｏｎｅｓｔ  ｂｕｔ  ｃｕｒｉｏｕｓモデル（右）とにおける通信チャネルを示す。最初のモデルでは、ディーラが、数字マスキングデータを、プライベートチャネルを介して各参加者に送信する。２番目のモデルでは、参加者が、参加者の全員の間で共有している、プライベート同報通信チャネルにアクセスし、各参加者は、追加のプライベートチャネルをディーラと共有する。プライベートチャネルは、破線で示されている。この図は、３人の参加者を表しているが、各モデルは、任意の人数ｎの参加者に及ぶことができる。ＴＤモデルでは、ディーラは、すべての事前計算済みデータを生成する唯一の者である。このディーラは、プライベートチャネルを使用して、数字マスキングデータの自分のシェアを、各参加者に送信する（一方向矢印）。ＨＢＣモデルでは、参加者が、数字マスキングデータの生成に協力する。これを行うには、参加者は、ディーラがアクセスできない、追加のプライベート同報通信チャネルを参加者間に必要とする。
【００９２】
図４は、一実施形態による、オンライン段階中の参加者間の通信チャネルの概略図を示す。この図は、オンライン段階中に使用される通信チャネルを示す。参加者は、公開同報通信チャネルを介してマスク済み値を送受信する（公開チャネルは、普通の線で示されている）。この例では３人に限定されている参加者の人数は、一般的な参加者人数ｎに難なく広げることができる。オンライン段階は、ＴＤモデルとＨＢＣモデルとで同じであり、そこにディーラはいない。
【００９３】
５．２  Ｈｏｎｅｓｔ  ｂｕｔ  ｃｕｒｉｏｕｓ法
本文献において提案しているＨＢＣプロトコルの大半は、２人しか参加者がいないシナリオを提示する。［１１］および［３］では、参加者が３人であるモデルにおいて高速ＭＰＣ乗算を行うのに使用され得る効率的なＨＢＣプロトコルについて説明されている。この２つの方式では、パーティが正しくプトロコルに従い、２人の参加者が結託しないことを前提とする。［１１］で提案している方式は、３つよりも多いパーティ向けにスケールするには非常に複雑である一方、［３］におけるプロトコルは、一般的な参加者人数に及ぶことができるが、平方数のプライベートチャンネルを必要とする（参加者ペアごとに１つ）。参加者の人数ｎが何人であっても効率的であるＨＢＣシナリオにおいて、乗法的数字マスキングデータを生成するための異なるプロトコルを提案する。本発明のシナリオでは、ディーラが、参加者によって作成されたマスク済みデータにわたって、数字マスキングデータ生成時において非線形部分を評価し、次に、マスク済みシェアを分散させる。マスクは、すべての参加者にとってありふれたものであり、参加者が共有するプライベート同報通信チャネルのおかげで作り出される。最後に、各参加者は、ディーラから受信した事前計算済みデータをアンマスクすることによって自分の数字マスキングデータを作り出す。
【００９４】
ここで、ｈｏｎｅｓｔ−ｂｕｔ−ｃｕｒｉｏｕｓシナリオにおいて２つのモデルを詳細に提示し、最初のモデルは、乗法的なＢｅａｖｅｒの数字マスキングデータの生成用であり、２番目のモデルは、ベキ関数の計算に使用される数字マスキングデータの生成用である。両方の方法では、数字マスキングデータの生成にディーラと参加者とが協力し、両者のいずれも情報全体にアクセスしないことになっている。大まかに言えば、参加者が自分の秘密シェア（最初のケースでは、λおよびμの秘密シェア、２番目のケースではλのみの秘密シェア）を生成し、各自が秘密を守る。参加者はまた、参加者が同報通信チャネルを介して互いの間で分散させるが、ディーラには秘密のままである、ありふれたマスクの秘密シェアを生成する。次に、参加者は、自分の秘密シェアをありふれたマスクでマスクし、それをディーラに送信し、ディーラは、その非線形部分を評価する（最初の方法では積、２番目の方法では累乗）。ディーラは、この結果に対して新しい加法的シェアを生成し、プライベートチャネルを介して、これらの値を各参加者に返信する。このように、参加者は、各他者のシェアは分からない。最後に、ありふれたマスクが分かっている参加者は、他と無関係に、自分の秘密シェアをアンマスクし、したがってディーラに知られることのない数字マスキングデータの自分の最終シェアを得ることができる。
【００９５】
Ｈｏｎｅｓｔ  ｂｕｔ  ｃｕｒｉｏｕｓ数字マスキングデータ生成方法
出力：シェア
2020532771.tif 000092
、ｚ＝λμ
１：各参加者Ｐｉがａｉ、ｂｉ、λｉ、μｉを生成する（一致する分布から）。
２：各参加者Ｐｉが他の参加者全員とａｉ、ｂｉを分け合う。
３：各参加者が、ａ＝ａ１＋・・・＋ａｎ、およびｂ＝ｂ１＋・・・＋ｂｎを計算する。
４：各参加者Ｐｉが、ａｉ＋λｉおよびｂｉ＋μｉをディーラに送信する。
５：ディーラが、ａ＋λ、ｂ＋μ、およびｗ＝（ａ＋λ）（ｂ＋μ）を計算する。
６．ディーラが、
2020532771.tif 000093
を作り出し、ｗｉを、ｉ＝１、．．．、ｎである参加者Ｐｉに送信する。
７：参加者Ｐ１が、ｚ１＝ｗ１−ａｂ−ａμ１−ｂλ１を計算する。
８：ｉ＝２、．．．、ｎである参加者Ｐｉが、ｚｉ＝ｗｉ−ａμｉ−ｂλｉを計算する。
【００９６】
ベキ関数メソッドの場合のＨｏｎｅｓｔ  ｂｕｔ  ｃｕｒｉｏｕｓ数字マスキングデータ生成
出力：シェア
2020532771.tif 000094
。
１：各参加者Ｐｉが、λｉ、ａｉを生成する（一致する分布から）。
２：各参加者Ｐｉが、他の参加者全員とａｉを分け合う。
３：各参加者が、ａ＝ａ１＋・・・＋ａｎを計算する。
４：各参加者Ｐｉが、
2020532771.tif 000095
であるようなｚｉを生成する。
５：各参加者Ｐｉが、ｚｉ＋ａλｉをディーラに送信する。
６：ディーラが、μλおよびｗ＝（μλ）−αを計算する。
７．ディーラが、
2020532771.tif 000096
を作り出し、ｗｉをｉ＝１、．．．、ｎである参加者Ｐｉに送信する。
８：各参加者Ｐｉが、ｗｉとμαとを右乗法して、（λ−α）ｉを得る。
【００９７】
ここで、ＨＢＣシナリオにおいて、三角多項式の評価に使用される数字マスキングデータの生成用の３番目の方法を提示する。
出力：シェア
2020532771.tif 000097
。
１：各参加者Ｐｉが、λｉ、ａｉを生成する（２πを法として一様に）。
２：各参加者Ｐｉが他の全参加者にａｉを同報通信する。
３：各参加者が、ａ＝ａ１＋・・・＋ａｎ  ｍｏｄ  ２πを計算する。
４：各参加者Ｐｉが、ｚｉ＋ａλｉ  ｍｏｄ  ２πをディーラに送信する。
５：ディーラが、λ＋ａ  ｍｏｄ  ２π、および
2020532771.tif 000098
を計算する。
６：ディーラが、
2020532771.tif 000099
を作り出し、ｗ（１）＝、．．．、ｗ（Ｎ）を参加者Ｐｉに送信する。
７：各参加者Ｐｉが、全ｊ∈［１、Ｎ］について、各
2020532771.tif 000100
を掛け、
2020532771.tif 000101
を得る。
【００９８】
６  ロジスティック回帰への適用
分類問題では、ここでは行列
2020532771.tif 000102
によって表す、訓練セットとも呼ばれるデータセットと、訓練ベクトルｙ∈｛０、１｝Ｎが与えられる。データセットは、ｋ特徴ごとのＮ入力ベクトルから成り、ベクトルｙの座標ｙｉは、データセットの第ｉ元が属するクラス（０または１）に対応する。形式上、目標は、入力として、ｋ特徴を含むベクトルｘを取り、かつ対応する出力値であるｙをかなりうまく予測するｈθ（ｘ）を出力する、関数
2020532771.tif 000103
を確定することである。
【００９９】
ロジスティック回帰では、
2020532771.tif 000104
、およびｘ０＝１である、形式ｈθ（ｘ）＝ｓｉｇｍｏ（θＴｘ）の仮定関数
2020532771.tif 000105
を通常、使用する。モデルとも呼ばれるベクトルθは、確定される必要があるパラメータである。このため、データ点（ｘ、ｙ）におけるモデルの品質を測定する凸性費用関数Ｃｘ、ｙ（θ）は、
2020532771.tif 000106
と定義される。
【０１００】
データセット全体に掛かる費用は、したがって
2020532771.tif 000107
として計算される。全体的な目標は、その費用関数ができる限り０に近いモデルθを確定することである。これを達成する一般的な方法は、Ｃｘ、ｙ（θ）が費用関数の勾配であり、α＞０が学習率と呼ばれる定数である、
θ：＝θ−α▽Ｃｘ、ｙ（θ）
としてモデルθを絶えず更新することから成るいわゆる勾配降下である。最適なαを選ぶことは、データセットの品質に大きく左右され、αが大きすぎる場合、この方法が逸れる可能性があり、αが小さすぎる場合、最小値に達するのに膨大な反復回数が必要になる。残念ながら、このパラメータをチューニングするのには、データに関する情報を明かすか、または、プライベートＭＰＣ計算では必ずしも実現可能ではない、公開虚偽訓練セットにアクセスすることが必要になる。このステップは、本文献では黙って無視されることが多い。同様に、特徴スケーリングなどの前処理技法、または直交化技法は、データセットを改善することができ、学習率を大幅に上げることを可能にする。しかしまた、入力データが分散される場合、また相関情報を内密にしておかなくてはいけない場合、これらの技法を簡単に実施することはできない。
【０１０１】
本研究では、十分な浮動小数点精度を有するという条件では、特徴スケーリングを必要とせず、学習率１でうまくいき、かつそれほど多くない反複で収束するＩＲＬＳ法［５、§４．３］を実施することを選ぶ。この場合、モデルは以下のように、更新される：
θ：＝θ−Ｈ（θ）−１・Ｃｘ、ｙ（θ）、
式中、Ｈ（θ）は、ヘッセ行列である。
【０１０２】
６．１  実施結果および実験結果
Ｃ＋＋においてロジスティック回帰法のＭＰＣ概念実証を実施した。１２８ビット浮動小数点数でＣ（Ｂ、ｐ）クラスにおける数を表し、マスキングセキュリティパラメータをτ＝４０ビットに設定した。１２８ビット数が１１３ビットの精度を備え、乗算方法が２τ＝８０ビットのマスキングを必要とすることから、計算全体を通して自由に使える３３ビットの精度がまだ保たれる。本発明のベンチマークが普通のｘ８６＿６４ＣＰＵ上で行われることから、１２８−ビット浮動小数点演算がＧＣＣのｑｕａｄｍａｔｈライブラリを使用してエミュレートされるが、この演算をネイティブサポートするつい最近のハードウェア（例えば、ＩＢＭの次世代ＰＯＷＥＲ９プロセッサ）において、さらなるスピードアップがもたらされる可能性がある。本発明の概念実証では、主たる焦点は、オンライン段階の実行時間、浮動小数点精度、および通信複雑度を改善することにあったので、信頼できるディーラシナリオの場合のみオフライン段階を実施し、ｈｏｎｅｓｔ  ｂｕｔ  ｃｕｒｉｏｕｓディーラの異型は、今後の研究として残しておいた。
【０１０３】
以下に、ＩＲＬＳ法を活用するモデル訓練メソッドを提示する。最初に、平文実装形態に対して、この方法を以下に記述する。ＭＰＣインスタンス化では、各参加者が、変数ごとに秘密シェアを得る。２節の双一次公式を使用して、あらゆる積が評価され、４節のフーリエメソッドを使用してシグモイドが評価される。
モデル訓練メソッド：Ｔｒａｉｎ（Ｘ、ｙ）
入力：データセット
2020532771.tif 000108
、および訓練ベクトル  ｙ∈｛０、１｝Ｎ
出力：ＣｏｓｔＸ、ｙ（θ）を最小化する、モデル
2020532771.tif 000109
１：
2020532771.tif 000110
、ｉ∈［０、Ｎ−１］
２：θ←［０、．．．、０］∈ＲＫ
３：ｆｏｒ  ｉｔｅｒ＝１  ｔｏ  ＩＲＬＳ＿ＩＴＥＲＳ  ｄｏ／／Ｉｎ  ｐｒａｃｔｉｃｅ  ＩＲＬＳ＿ＩＴＥＲＳ＝８
４：ａ←Ｘ・θ
５：ｐ←［ｓｉｇｍｏ（ａ０）、．．．、ｓｉｇｍｏ（ａＮ−１）］
６：ｐｍｐ←［ｐ０（１−ｐ０）、．．．、ｐＮ−１（１−ｐＮ−１）］
７：ｇｒａｄ←ＸＴ（ｐ−ｙ）
８：Ｈ←ｐｍｐ・Ｐｒｏｄｓ
９：θ−Ｈ−１・ｇｒａｄ
１０：ｅｎｄ  ｆｏｒ
１１：ｒｅｔｕｒｎθ
【０１０４】
このメソッドで記述されるロジスティック回帰モデル訓練を実施した。メインループを繰り返すたびに、その時の位置θにおける勾配（ｇｒａｄ）およびヘッセ行列（Ｈ）を評価し、ヘッセ行列システム（行７）を解いて、次の位置を見付ける。計算ステップの大半は、大きな行列またはベクトルにおいて双一次であり、計算ステップの各々は、ただ一回の通信でＢｅａｖｅｒ三つ組（数字マスキングデータ）を介して評価される。ステップ５において、シグモイド関数が、区間全体で２０ビットの精度をもたらす、次数２３の奇数三角多項式によって近似される（並行して）。したがって、４節で説明したように、フーリエ数字マスキングデータのベクトルを使用する。ヘッセ行列システム（ステップ９）が左右の２つの（一様ランダム）正規直交行列によってマスクされ、明かされるので、平文において解くことができる。このメソッドは、勾配のノルム（どのみち予測可能である）を明かすが、その方向は完全に隠し、これは、最終モデルを確実に内密にしておくのに十分である。最後に、入力データが必ずしも特徴スケールされるわけではないので、無作為な位置ではなく、ゼロ位置から始めることが推奨され（ステップ２）、それは、最初の入力データがＩＲＬＳ収束領域にあることが約束されているからである。
【０１０５】
このメソッドのＭＰＣ評価をビルドするのに、小さなコンパイラを書き込み、この高水準リストを前処理し、すべてのｆｏｒ  ｌｏｏｐを公開し、それをイミュータブル変数上の一連の命令（影響を受けると読み取り専用になる）に変える。より重要なことには、コンパイラが、１つの加法的マスクλＵをこれらのイミュータブル変数Ｕのそれぞれに関連付ける。これにより、これまでの節で見てきた２つの重要な問題が解消され、まず、このメソッド全体を通して再使用される巨大な行列用のマスキング情報が、プトロコル全体を通して１度だけ送信される（この最適化は、すでに［２５］に示されているが、本発明では、それは、定数入力行列、および全ＩＲＬＳ反復で再使用されるそれらの事前計算積に大きな影響を与える）。それはまた、攻撃者が同じ分布から決して２つの標本を得ることがないことから、そのマスク済み分布を平均化することによって、情報を引き出す可能性のある攻撃を弱める。これは、マスキングに対する４０ビットのセキュリティの選択の根拠となる。
【０１０６】
オフライン段階中、信頼できるディーラは、イミュータブル変数ごとに１つの無作為なマスク値を生成し、これらのマスクを秘密分散させる。いずれか２つのイミュータブル変数ＵとＶとの行列−ベクトル積または行列−行列積のすべてに対し（上記のモデル訓練メソッドの行１、４、６、７、および８からの）、信頼できるディーラはまた、ＵのマスクλＵ、およびＶのλＶを使用して、特定の乗算三つ組を生成する。より正確に言えば、信頼できるディーラは、λＵ・λＶとともに、分散縮小段階での積と同じ次元の整数ベクトル／行列に対して加法的シェアを生成し、配分する。これらの整数係数は、効率の面から２５６を法として取られる。
【０１０７】
６．２  結果
Ｘｅｏｎ  Ｅ５−２６６６  ｖ３プロセッサを備えるＡＷＳプラットフォームおよびＡｚｕｒｅプラットフォームの両方でクラウドインスタンスを使用して、説明した方法のすべてを実施し、２つのパーティと３つのパーティを対象に本発明のコードをテストした。本出願では、各インスタンスは、その公開ＩＰアドレスを介して通信する。また、ｚｅｒｏＭＱライブラリを使用して、参加者間の低レベル通信を処理する（ピアツーピア、同報通信、中央節など．．．）。
【０１０８】
図５は、ｎ＝３参加者を対象にした実験中に得た様々な測定値をまとめた本発明の実施の結果表を示す。それぞれ８、１２、または２０の特徴を有する１００００〜１５０００００点を含むデータセットを考えた。もたらされる結果では、ほとんどのデータセットで完全な収束に達するのに十分である８にＩＲＬＳ反復回数を固定し、ＭＰＣ計算が平文反復の場合のモデルと同じモデルを出力することを実験により実証した。１５００００点のデータセットでは、オンライン段階の総実行時間が、１〜５分であることが分かる。この実行時間は、エミュレートされた４倍精度浮動小数点演算の使用に大部分起因するものであり、このＭＰＣ計算は、同じ１２８ビットの浮動小数点を使用してそれを実施した場合、同じデータセットにおける平文ロジスティック回帰のせいぜい１／２０の速さである（しかし、もちろん、ネイティブな２倍精度型は、ずっと速い）。より興味深いことには、数字マスキングデータの総体の全体サイズおよびオンライン通信量が少ないことが分かり、例えば、８特徴を有する１５００００点におけるロジスティック回帰は、参加者当たり、わずか７５６ＭＢの数字マスキングデータで済み、そのうち、参加者当たり、わずか２０５ＭＢのデータが、オンライン段階中に同報通信される。これは、フーリエ数字マスキングデータが、マスクされ交換される値よりもかなり大きいという事実に起因する。このことから、通信時間は、普通のＷＡＮ帯域幅の場合でも、全実行時間に比べてわずかである。
【０１０９】
最後に、特徴スケールされることが入力データに約束されている場合、全体時間、メモリ、および通信の複雑度を、古典的な勾配降下反複を３回行い、続いて、８回のＩＲＬＳ反復に代わって５回のＩＲＬＳ反復を行うことによって、約３０％改善することができる。平文およびＭＰＣ版の両方に対しこの最適化をテストし、使用した方法に応じて、ロジスティック回帰中の費用関数の開方、またＦ−スコアの開方を示す。
【０１１０】
図６は、８特徴および０．５％の合格率の場合で、１５００００標本のテストデータセットにおいて、ロジスティック回帰中の費用関数の開方を反復回数の関数として示す。黄色は、最適な学習率の標準勾配降下であり、赤は、シグモイド関数の区分線形近似を使用する勾配降下であり（［２５］で見られるような）、緑は、本発明のＭＰＣモデル（ＩＲＬＳ法に基づく）である。ＭＰＣ  ＩＲＬＳ法（および平文ＩＲＬＳ法）は、標準勾配法の場合の５００反復に対して、８未満の反復で収束する。予測通りに、この近似法は、最小費用には達しない。
【０１１１】
図７は、同じロジスティック回帰の最中のＦ−スコアの開方を反復回数の関数として示す。標準勾配降下と本発明のＭＰＣとは、０．６４の限界Ｆ−スコアで、同じモデルを生み出す。しかし、区分線形近似によっては何もはっきりした標本が検出されず、ｎｕｌｌＦ−スコアにつながる。しかし、この３つのケースで、正確さ（紫）は、１回目からほぼ１００％である。
【０１１２】
銀行業界から提供されたデータセットにおいて本発明のプラットフォームをテストした。秘密保持上、これらのデータセットを明かすことはできない。ただし、本明細書に記載の挙動は、例えばガウス分布を用いて、ランダムデータセットを生成し、合格閾値を０．５％に設定し、かついくつかのラベルを無作為に交換することにより何らかのノイズを加えることによって、再現され得る。
【０１１３】
未解決問題。第１の重要な未解決問題は、本発明のノイズ低減法後の分布の区別性である。より基本的なレベルでは、標準フーリエ基底とは対照的に、付属資料に定義されている半範囲チェビシェフ多項式の基底を使用して、マスキング方法を見つけたいと思うであろう。指数近似とともに、このような方法により、Ｌ２［−１、１］におけるいずれの関数も評価することが可能になるであろう（ＭＰＣにおいて）。
【０１１４】
７  参考文献
１．Ｍ．Ａｂａｄｉ，Ａ．Ｃｈｕ，Ｉ．Ｇｏｏｄｆｅｌｌｏｗ．Ｈ．Ｂｒｅｎｄａｎ  ＭｃＭａｈａｎ，Ｉ．Ｍｉｒｏｎｏｖ，Ｋ．Ｔａｌｗａｒ，ａｎｄ  Ｌ．Ｚｈａｎｇ．Ｄｅｅｐ  ｌｅａｒｎｉｎｇ  ｗｉｔｈ  ｄｉｆｆｅｒｅｎｔｉａｌ  ｐｒｉｖａｃｙ．ＣｏＲＲ，  ａｂｓ／１６０７．００１３３，２０１６．
２．Ｙ．Ａｏｎｏ，Ｔ．Ｈａｙａｓｈｉ，Ｌ．Ｔｒｉｅｕ  Ｐｈｏｎｇ，ａｎｄ  Ｌ．Ｗａｎｇ．Ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  ｌｏｇｉｓｔｉｃ  ｒｅｇｒｅｓｓｉｏｎ  ｗｉｔｈ  ｄｉｓｔｒｉｂｕｔｅｄ  ｄａｔａ  ｓｏｕｒｃｅｓ  ｖｉａ  ｈｏｍｏｍｏｒｐｈｉｃ  ｅｎｃｒｙｐｔｉｏｎ．ＩＥＩＣＥ  Ｔｒａｎｓａｃｔｉｏｎｓ，９９−Ｄ（８）：２０７９−２０８９，２０１６．
３．Ｔ．Ａｒａｋｉ，Ｊ．Ｆｕｒｕｋａｗａ，Ｙ．Ｌｉｎｄｅｌｌ，Ａ．Ｎｏｆ，ａｎｄ  Ｋ．Ｏｈａｒａ．Ｈｉｇｈ−ｔｈｒｏｕｇｈｐｕｔ  ｓｅｍｉｈｏｎｅｓｔ  ｓｅｃｕｒｅ  ｔｈｒｅｅ−ｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ  ｗｉｔｈ  ａｎ  ｈｏｎｅｓｔ  ｍａｊｏｒｉｔｙ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２０１６  ＡＣＭ  ＳＩＧＳＡＣ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ，Ｖｉｅｎｎａ，Ａｕｓｔｒｉａ，Ｏｃｔｏｂｅｒ  ２４−２８，２０１６，ｐａｇｅｓ  ８０５−８１７，２０１６．
４．Ｄ．Ｂｅａｖｅｒ．    Ｅｆｆｉｃｉｅｎｔ  Ｍｕｌｔｉｐａｒｔｙ  Ｐｒｏｔｏｃｏｌｓ  Ｕｓｉｎｇ  Ｃｉｒｃｕｉｔ  Ｒａｎｄｏｍｉｚａｔｉｏｎ．Ｉｎ  ＣＲＹＰＴＯ  ’９１，ｖｏｌｕｍｅ  ５７６  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，ｐａｇｅｓ  ４２０−４３２．Ｓｐｒｉｎｇｅｒ，１９９２．
５．Ａ．Ｂｊｏｒｃｋ．Ｎｕｍｅｒｉｃａｌ  Ｍｅｔｈｏｄｓ  ｆｏｒ  Ｌｅａｓｔ  Ｓｑｕａｒｅｓ  Ｐｒｏｂｌｅｍｓ．Ｓｉａｍ  Ｐｈｉｌａｄｅｌｐｈｉａ，１９９６．
６．Ｄ．Ｂｏｇｄａｎｏｖ，Ｓ．Ｌａｕｒ，ａｎｄ  Ｊ．Ｗｉｌｌｅｍｓｏｎ．Ｓｈａｒｅｍｉｎｄ：Ａ  ｆｒａｍｅｗｏｒｋ  ｆｏｒ  ｆａｓｔ  ｐｒｉｖａｃｙ  ｐｒｅｓｅｒｖｉｎｇ  ｃｏｍｐｕｔａｔｉｏｎｓ．Ｉｎ  ＥＳＯＲＩＣＳ  ２００８，ｐａｇｅｓ  １９２−２０６．Ｓｐｒｉｎｇｅｒ，２００８．
７．Ｊ．Ｂｏｙｄ．Ａ  ｃｏｍｐａｒｉｓｏｎ  ｏｆ  ｎｕｍｅｒｉｃａｌ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｆｏｕｒｉｅｒ  ｅｘｔｅｎｓｉｏｎ  ｏｆ  ｔｈｅ  ｆｉｒｓｔ，ｓｅｃｏｎｄ，ａｎｄ  ｔｈｉｒｄ  ｋｉｎｄｓ．Ｊ．Ｃｏｍｐｕｔ．Ｐｈｙｓ．，１７８（１）：１１８−１６０，Ｍａｙ  ２００２．
８．Ｊ．Ｂｏｙｄ．Ｆｏｕｒｉｅｒ  ｅｍｂｅｄｄｅｄ  ｄｏｍａｉｎ  ｍｅｔｈｏｄｓ：Ｅｘｔｅｎｄｉｎｇ  ａ  ｆｕｎｃｔｉｏｎ  ｄｅｆｉｎｅｄ  ｏｎ  ａｎ  ｉｒｒｅｇｕｌａｒ  ｒｅｇｉｏｎ  ｔｏ  ａ  ｒｅｃｔａｎｇｌｅ  ｓｏ  ｔｈａｔ  ｔｈｅ  ｅｘｔｅｎｓｉｏｎ  ｉｓ  ｓｐａｔｉａｌｌｙ  ｐｅｒｉｏｄｉｃ  ａｎｄ  ｃ∞．Ａｐｐｌ．Ｍａｔｈ．Ｃｏｍｐｕｔ．，１６１（２）：５９１−５９７，Ｆｅｂｒｕａｒｙ  ２００５．
９．Ｊ．Ｂｏｙｄ．Ａｓｙｍｐｔｏｔｉｃ  ｆｏｕｒｉｅｒ  ｃｏｅｆｆｉｃｉｅｎｔｓ  ｆｏｒ  ａ  Ｃ  ｉｎｆｉｎｉｔｙ  ｂｅｌｌ  （ｓｍｏｏｔｈｅｄ−”ｔｏｐ−ｈａｔ”）＆  ｔｈｅ  ｆｏｕｒｉｅｒ  ｅｘｔｅｎｓｉｏｎ  ｐｒｏｂｌｅｍ．Ｊ．Ｓｃｉ．Ｃｏｍｐｕｔ．，２９（１）：１−２４，２００６．
１０．Ｋ．Ｃｈａｕｄｈｕｒｉ  ａｎｄ  Ｃ．Ｍｏｎｔｅｌｅｏｎｉ．Ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  ｌｏｇｉｓｔｉｃ  ｒｅｇｒｅｓｓｉｏｎ．Ｉｎ  Ｄａｐｈｎｅ  Ｋｏｌｌｅｒ，Ｄａｌｅ  Ｓｃｈｕｕｒｍａｎｓ，Ｙｏｓｈｕａ  Ｂｅｎｇｉｏ，ａｎｄ  Ｌｅｏｎ  Ｂｏｔｔｏｕ，ｅｄｉｔｏｒｓ，Ａｄｖａｎｃｅｓ  ｉｎ  Ｎｅｕｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｙｓｔｅｍｓ  ２１，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｔｗｅｎｔｙ−Ｓｅｃｏｎｄ  Ａｎｎｕａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｎｅｕｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｙｓｔｅｍｓ，Ｖａｎｃｏｕｖｅｒ，Ｂｒｉｔｉｓｈ  Ｃｏｌｕｍｂｉａ，Ｃａｎａｄａ，Ｄｅｃｅｍｂｅｒ  ８−１１，２００８，ｐａｇｅｓ  ２８９−２９６．Ｃｕｒｒａｎ  Ａｓｓｏｃｉａｔｅｓ，Ｉｎｃ．，２００８．
１１．Ｒ．Ｃｒａｍｅｒ，Ｉ．Ｄａｍａｒｄ，ａｎｄ  Ｊ．Ｂ．Ｎｉｅｌｓｅｎ．Ｓｅｃｕｒｅ  Ｍｕｌｔｉｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ  ａｎｄ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ．Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，２０１５．
１２．Ｉ．Ｄａｍａｒｄ，Ｖ．Ｐａｓｔｒｏ，Ｎ．Ｓｍａｒｔ，ａｎｄ  Ｓ．Ｚａｋａｒｉａｓ．Ｍｕｌｔｉｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ  ｆｒｏｍ  ｓｏｍｅｗｈａｔ  ｈｏｍｏｍｏｒｐｈｉｃ  ｅｎｃｒｙｐｔｉｏｎ．Ｉｎ  Ｒｅｉｈａｎｅｈ  Ｓａｆａｖｉ−Ｎａｉｎｉ  ａｎｄ  Ｒａｎ  Ｃａｎｅｔｔｉ，ｅｄｉｔｏｒｓ，Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  ＣＲＹＰＴＯ  ２０１２  ３２ｎｄ  Ａｎｎｕａｌ  Ｃｒｙｐｔｏｌｏｇｙ  Ｃｏｎｆｅｒｅｎｃｅ，Ｓａｎｔａ  Ｂａｒｂａｒａ，ＣＡ，ＵＳＡ，Ａｕｇｕｓｔ１９−２３，２０１２．Ｐｒｏｃｅｅｄｉｎｇｓ，ｖｏｌｕｍｅ７４１７  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，ｐａｇｅｓ６４３−６６２．Ｓｐｒｉｎｇｅｒ，２０１２．
１３．Ｉ．Ｄａｍａｒｄ，Ｖ．Ｐａｓｔｒｏ，Ｎ．Ｐ．Ｓｍａｒｔ，ａｎｄ  Ｓ．Ｚａｋａｒｉａｓ．ＳＰＤＺ  Ｓｏｆｔｗａｒｅ．ｗｗｗ．ｃｓ．ｂｒｉｓ．ａｃ．ｕｋ／Ｒｅｓｅａｒｃｈ／ＣｒｙｐｔｏｇｒａｐｈｙＳｅｃｕｒｉｔｙ／ＳＰＤＺ／
１４．Ｄａｔａｓｅｔ．Ａｒｃｅｎｅ  Ｄａｔａ  Ｓｅｔ．ａｒｃｈｉｖｅ．ｉｃｓ．ｕｃｉ．ｅｄｕ／ｍｌ／ｄａｔａｓｅｔｓ／Ａｒｃｅｎｅ．
１５．Ｄａｔａｓｅｔ．ＭＮＩＳＴ  Ｄａｔａｂａｓｅ．ｙａｎｎ．ｌｅｃｕｎ．ｃｏｍ／ｅｘｄｂ／ｍｎｉｓｔ／．
１６．Ｃ．Ｆｅｆｆｅｒｍａｎ．Ｉｎｔｅｒｐｏｌａｔｉｏｎ  ａｎｄ  ｅｘｔｒａｐｏｌａｔｉｏｎ  ｏｆ  ｓｍｏｏｔｈ  ｆｕｎｃｔｉｏｎｓ  ｂｙ  ｌｉｎｅａｒ  ｏｐｅｒａｔｏｒｓ．Ｒｅｖ．Ｍａｔ．Ｉｂｅｒｏａｍｅｒｉｃａｎａ，２１（１）：３１３−３４８，２００５．
１７．Ａ．Ｇａｓｃｏｎ，Ｐ．Ｓｃｈｏｐｐｍａｎｎ，Ｂ．Ｂａｌｌｅ，Ｍ．Ｒａｙｋｏｖａ，Ｊ．Ｄｏｅｒｎｅｒ，Ｓ．Ｚａｈｕｒ，ａｎｄ  Ｄ．Ｅｖａｎｓ．    Ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  ｄｉｓｔｒｉｂｕｔｅｄ  ｌｉｎｅａｒ  ｒｅｇｒｅｓｓｉｏｎ  ｏｎ  ｈｉｇｈ−ｄｉｍｅｎｓｉｏｎａｌ  ｄａｔａ．Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｎ  Ｐｒｉｖａｃｙ  Ｅｎｈａｎｃｉｎｇ  Ｔｅｃｈｎｏｌｏｇｉｅｓ，４：２４８−２６７，２０１７．
１８．Ｒ．Ｇｉｌａｄ−Ｂａｃｈｒａｃｈ，Ｎ．Ｄｏｗｌｉｎ，Ｋ．Ｌａｉｎｅ，Ｋ．Ｅ．Ｌａｕｔｅｒ，Ｍ．Ｎａｅｈｒｉｇ，ａｎｄ  Ｊ．Ｗｅｒｎｓｉｎｇ．Ｃｒｙｐｔｏｎｅｔｓ：Ａｐｐｌｙｉｎｇ  ｎｅｕｒａｌ  ｎｅｔｗｏｒｋｓ  ｔｏ  ｅｎｃｒｙｐｔｅｄ  ｄａｔａ  ｗｉｔｈ  ｈｉｇｈ  ｔｈｒｏｕｇｈｐｕｔ  ａｎｄ  ａｃｃｕｒａｃｙ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ３３ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ，ＩＣＭＬ  ２０１６，Ｎｅｗ  Ｙｏｒｋ  Ｃｉｔｙ，ＮＹ，ＵＳＡ，Ｊｕｎｅ  １９−２４，２０１６，ｐａｇｅｓ  ２０１−２１０，２０１６．
１９．Ｉ．Ｇｏｏｄｆｅｌｌｏｗ，Ｙ．Ｂｅｎｇｉｏ  ａｎｄ  Ａ．Ｃｏｕｒｖｉｌｌｅ．    Ｄｅｅｐ  Ｌｅａｒｎｉｎｇ．ＭＩＴ  Ｐｒｅｓｓ，２０１６．ｗｗｗ．ｄｅｅｐｌｅａｒｎｉｎｇｂｏｏｋ．ｏｒｇ．
２０．Ｍ．Ｒ．Ｈｅｓｔｅｎｅｓ．Ｅｘｔｅｎｓｉｏｎ  ｏｆ  ｔｈｅ  ｒａｎｇｅ  ｏｆ  ａ  ｄｉｆｆｅｒｅｎｔｉａｂｌｅ  ｆｕｎｃｔｉｏｎ．Ｄｕｋｅ  Ｍａｔｈ．Ｊ．，８：１８３−１９２，１９４１．
２１．Ｄ．Ｈｕｙｂｒｅｃｈｓ．Ｏｎ  ｔｈｅ  ｆｏｕｒｉｅｒ  ｅｘｔｅｎｓｉｏｎ  ｏｆ  ｎｏｎｐｅｒｉｏｄｉｃ  ｆｕｎｃｔｉｏｎｓ．ＳＩＡＭＪ．Ｎｕｍｅｒｉｃａｌ  Ａｎａｌｙｓｉｓ，４７（６）：４３２６−４３５５，２０１０．
２２．Ａ．Ｊａｓｃｈｋｅ  ａｎｄ  Ｆ．Ａｒｍｋｎｅｃｈｔ．Ａｃｃｅｌｅｒａｔｉｎｇ  ｈｏｍｏｍｏｒｐｈｉｃ  ｃｏｍｐｕｔａｔｉｏｎｓ  ｏｎ  ｒａｔｉｏｎａｌ  ｎｕｍｂｅｒｓ．Ｉｎ  ＡＣＮＳ  ２０１６，ｖｏｌｕｍｅ  ９６９６  ｏｆ  ＬＮＣＳ，ｐａｇｅｓ  ４０５−４２３．Ｓｐｒｉｎｇｅｒ，２０１６．
２３．Ｙ．Ｌｉｎｄｅｌｌ  ａｎｄ  Ｂ．Ｐｉｎｋａｓ．Ｐｒｉｖａｃｙ  ｐｒｅｓｅｒｖｉｎｇ  ｄａｔａ  ｍｉｎｉｎｇ．Ｉｎ  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  ＣＲＹＰＴＯ  ２０００，２０ｔｈ  Ａｎｎｕａｌ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｒｙｐｔｏｌｏｇｙ  Ｃｏｎｆｅｒｅｎｃｅ，Ｓａｎｔａ  Ｂａｒｂａｒａ，Ｃａｌｉｆｏｒｎｉａ，ＵＳＡ，Ａｕｇｕｓｔ  ２０−２４，２０００，Ｐｒｏｃｅｅｄｉｎｇｓ，ｐａｇｅｓ  ３６−５４，２０００．
２４．Ｒ．Ｌｉｖｎｉ，Ｓ．Ｓｈａｌｅｖ−Ｓｈｗａｒｔｚ，ａｎｄ  Ｏ．Ｓｈａｍｉｒ．Ｏｎ  ｔｈｅ  ｃｏｍｐｕｔａｔｉｏｎａｌ  ｅｆｆｉｃｉｅｎｃｙ  ｏｆ  ｔｒａｉｎｉｎｇ  ｎｅｕｒａｌ  ｎｅｔｗｏｒｋｓ．Ｉｎ  Ｚｏｕｂｉｎ  Ｇｈａｈｒａｍａｎｉ，Ｍａｘ  Ｗｅｌｌｉｎｇ，Ｃｏｒｉｎｎａ  Ｃｏｒｔｅｓ，Ｎｅｉｌ  Ｄ．Ｌａｗｒｅｎｃｅ，ａｎｄ  Ｋｉｌｉａｎ  Ｑ．Ｗｅｉｎｂｅｒｇｅｒ，ｅｄｉｔｏｒｓ，Ａｄｖａｎｃｅｓ  ｉｎ  Ｎｅｕｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｙｓｔｅｍｓ  ２７：Ａｎｎｕａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｎｅｕｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｙｓｔｅｍｓ  ２０１４，  Ｄｅｃｅｍｂｅｒ  ８−１３  ２０１４，Ｍｏｎｔｒｅａｌ，Ｑｕｅｂｅｃ，Ｃａｎａｄａ，ｐａｇｅｓ  ８５５−８６３，２０１４．
２５．Ｐ．Ｍｏｈａｓｓｅｌ  ａｎｄ  Ｙ．Ｚｈａｎｇ．ＳｅｃｕｒｅＭＬ：    Ａ  ｓｙｓｔｅｍ  ｆｏｒ  ｓｃａｌａｂｌｅ  ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  ｍａｃｈｉｎｅ  ｌｅａｒｎｉｎｇ．Ｉｎ  ２０１７  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ，ＳＰ  ２０１７，Ｓａｎ  Ｊｏｓｅ，ＣＡ，ＵＳＡ，Ｍａｙ  ２２−２６，２０１７，ｐａｇｅｓ  １９−３８．ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ，２０１７．
２６．Ｖ．Ｎｉｋｏｌａｅｎｋｏ，Ｕ．Ｗｅｉｎｓｂｅｒｇ，Ｓ．Ｉｏａｎｎｉｄｉｓ，Ｍ．Ｊｏｙｅ，Ｄ．Ｂｏｎｅｈ，ａｎｄ  Ｎ．Ｔａｆｔ．Ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  ｒｉｄｇｅ  ｒｅｇｒｅｓｓｉｏｎ  ｏｎ  ｈｕｎｄｒｅｄｓ  ｏｆ  ｍｉｌｌｉｏｎｓ  ｏｆ  ｒｅｃｏｒｄｓ．Ｉｎ  ２０１３  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ，ＳＰ  ２０１３、Ｂｅｒｋｅｌｅｙ，ＣＡ，ＵＳＡ，Ｍａｙ  １９−２２，２０１３，ｐａｇｅｓ  ３３４−３４８．ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ，２０１３．
２７．Ｌ．Ｔｒｉｅｕ  Ｐｈｏｎｇ，Ｙ．Ａｏｎｏ，Ｔ．Ｈａｙａｓｈｉ，Ｌ．Ｗａｎｇ，ａｎｄ  Ｓ．Ｍｏｒｉａｉ．Ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  ｄｅｅｐ  ｌｅａｒｎｉｎｇ：Ｒｅｖｉｓｉｔｅｄ  ａｎｄ  ｅｎｈａｎｃｅｄ．Ｉｎ  Ｌｙｎｎ  Ｂａｔｔｅｎ，Ｄｏｎｇ  Ｓｅｏｎｇ  Ｋｉｍ，Ｘｕｙｕｎ  Ｚｈａｎｇ，ａｎｄ  Ｇａｎｇ  Ｌｉ，ｅｄｉｔｏｒｓ，Ａｐｐｌｉｃａｔｉｏｎｓ  ａｎｄ  Ｔｅｃｈｎｉｑｕｅｓ  ｉｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ−８ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ，ＡＴＩＳ  ２０１７，Ａｕｃｋｌａｎｄ，Ｎｅｗ  Ｚｅａｌａｎｄ，Ｊｕｌｙ  ６−７，２０１７，Ｐｒｏｃｅｅｄｉｎｇｓ，ｖｏｌｕｍｅ  ７１９  ｏｆ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｃｉｅｎｃｅ，ｐａｇｅｓ  １００−１１０．    Ｓｐｒｉｎｇｅｒ，２０１７．
２８．Ｈ．Ｗｈｉｔｎｅｙ．Ａｎａｌｙｔｉｃ  ｅｘｔｅｎｓｉｏｎｓ  ｏｆ  ｄｉｆｆｅｒｅｎｔｉａｂｌｅ  ｆｕｎｃｔｉｏｎｓ  ｄｅｆｉｎｅｄ  ｉｎ  ｃｌｏｓｅｄ  ｓｅｔｓ．Ｔｒａｎｓ．ＡｍｅｒＭａｔｈ．Ｓｏｃ．，３６（１）：６３−８９，１９３４．
２９．Ｓ．Ｗｕ，Ｔ．Ｔｅｒｕｙａ，Ｊ．Ｋａｗａｍｏｔｏ，Ｊ．Ｓａｋｕｍａ，ａｎｄ  Ｈ．Ｋｉｋｕｃｈｉ．Ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖａｔｉｏｎ  ｆｏｒ  ｓｔｏｃｈａｓｔｉｃ  ｇｒａｄｉｅｎｔ  ｄｅｓｃｅｎｔ  ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ｓｅｃｕｒｅ  ｌｏｇｉｓｔｉｃ  ｒｅｇｒｅｓｓｉｏｎ．Ｔｈｅ  ２７ｔｈ  Ａｎｎｕａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｆ  ｔｈｅ  Ｊａｐａｎｅｓｅ  Ｓｏｃｉｅｔｙ  ｆｏｒ  Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ，２７：１−４，２０１３．
【０１１５】
ＩＩ．フーリエスプラインおよび多項式スプラインによる実数値関数の高精度プライバシ保護評価
１  概要
多項式スプラインおよびフーリエスプラインは、機械学習において様々な関数を近似するのに役立つ多項式級数またはフーリエ級数によって定義される区分関数（三角関数）である。
【０１１６】
ハイブリッドマルチパーティ計算解法に基づくこのようなスプラインの高精度プライバシ保護関数評価のための方法を開示する。この方法は、秘密分散法によるフーリエ級数および多項式評価を、ガーブル化回路による境界の確認と組み合わせる。上記「Ｉ  高精度プライバシ保護実数値関数評価」節に開示した技法を使用する、ある区間におけるフーリエ関数および多項式関数のプライバシ保護高精度評価である（［３］も参照）。
【０１１７】
最後に、公開入力に対して秘密関数を評価する回路に、古典的なガーブル化回路（秘密入力に対して公開関数が評価されている）を二重化することによる、ガーブル化オートマトンとして知られる新しい概念を提示する。これにより、比較演算子など、ガーブル化回路設定時の評価の一部をスピードアップすることが可能になる。
【０１１８】
２  紛失通信の場合のガーブル化回路の使用
まず、様々な最適化とともに紛失通信の場合の基本的なガーブル化回路プロトコルを思い出してみる。論理合成技法が回路を最適化するのに使用され、以下に詳しく述べられる。次に、加法的秘密シェアをカーブル化回路秘密シェアに変換し、確認を行ってから加法的秘密シェアに戻す標準技法を説明する。
【０１１９】
２．１  ガーブル化回路の背景
一般的なガーブル化回路では、（公開）関数が、ＡＮＤゲートおよびＸＯＲゲートから成るブール回路として記述される。Ｙａｏの「Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  Ｓｅｃｕｒｅ  Ｃｏｍｐｕｔａｔｉｏｎｓ」，ＩＥＥＥ，１９８２によって説明されているプロトコルの基本版は、３つの段階：１）ガーブル化段階、２）通信段階、３）評価段階、から成る。ここで、それぞれ個々の段階の説明を思い出してみる。
【０１２０】
２．１．１  ガーブル化段階
各論理ゲート（ＡＮＤまたはＸＯＲ）は、２つの入力線（通常、ａとｂとで示される）および１つの出力線（通常、ｃで示される）を有する。Ｗ∈｛ａ、ｂ、ｃ｝で、ガーブラは、２つの可能な値に対応する、ラベル
2020532771.tif 000111
（｛０、１｝Ｋにおける）を選ぶ。図８は、真理値表例と対応する暗号化真理値表（暗号化表）を示す。各行を使用して、対応する入力線には２つのキーを使用して、出力線に対応するラベルを対称的に暗号化する。次に、ガーブラは、暗号化表の行を無作為に並べ替えて、評価器に送られる（ゲートごとに）カーブル化表を得る。
【０１２１】
２．１．２  通信段階
それにより、ガーブラと評価器が、それぞれ、
2020532771.tif 000112
とで示されるそれらのプライベートな入力ビットを持つ。ここで、各ビットｕｉまたはｖｉは、他のパーティに明かされてはならない｛０．１｝におけるプライベートな値を持つ。
【０１２２】
ガーブラがそのビットのラベルを評価器に送信するのは簡単である（対応するラベル
2020532771.tif 000113
を送るだけ）。評価器は、これらのビットの内密な値をガーブラに明かすことなく、その対応するラベル
2020532771.tif 000114
を得る必要がある。これは、１−ｏｕｔ−ｏｆ−２型紛失通信−評価器が、ｂ∈｛０、１｝が対応する値である、  
2020532771.tif 000115
を各
2020532771.tif 000116
で求めることを経て行われる。ＯＴにより、ガーブラがｂについて何も覚えず、評価器が
2020532771.tif 000117
について何も覚えないことが約束される。
【０１２３】
２．１．３  評価段階
評価段階では、受信した自分のキー
2020532771.tif 000118
（ＯＴを介して）およびガーブラのキー
2020532771.tif 000119
を有する評価器は、続いてブール回路を評価し始める。所与のゲートで、評価器が入力線ＫａおよびＫｂ用のラベルをすでに確定しているとの前提で、評価器は、出力線用のラベルであるＫｃの復号がうまく行くまで、対応するガーブル化表への登録事項をＫａＫｂで復号しようとする。
【０１２４】
２．２  最適化
２．２．１  Ｐｏｉｎｔ−ａｎｄ−ｐｅｒｍｕｔｅ
評価器は、４行すべてではなくガーブル化表の１行を簡単に復号することができる。これは、無作為選択のビットに基づき、その表をソートすることに起因する。詳しくは［８］を参照のこと。
【０１２５】
２．２．２  Ｆｒｅｅ  ＸＯＲ
この最適化は、ＸＯＲゲートではなく、ＡＮＤゲートの個数のみによって決まる、データ転送量、ならびに暗号化および復号の回数をもたらす。この技法は、［７］で紹介されている。
【０１２６】
考察１．ガーブラは、グローバルオフセットＲ（ガーブラだけが知っており、回路全体にわたって有効な）を選ぶ。真偽論理値のラベル（２つの色に相当する）は、ＸＯＲをとってＲになる。「グローバル」オフセットの範囲が、ＸＯＲゲートによって接続されている線までに限られ得ることが、ＦｌｅＸＯＲ［５］において確認された。これは、回路をＸＯＲ−エリアに分け、Ｒは、ＸＯＲエリアごとに一意でありさえすればよい。非ブール回路（例えば、線の論理値が、２を法としてではなくＢを法とする数）でうまくいく場合、オフセット
2020532771.tif 000120
を＋ｘ．Ｒ  ｍｏｄ  Ｂに取り替えるだけでよい。
【０１２７】
２．２．３  固定キーＡＥＳ
この方法により、より費用が嵩む暗号学的ハッシュ関数の代わりに固定キーＡＥＳを使用することによってＡＮＤゲートをガーブル化し、評価することが可能になる［２］。より正確に言えば、  
2020532771.tif 000121
である、
2020532771.tif 000122
が、ゲート（ゲート数）ごとの公開微調整である。
【０１２８】
２．２．４  行の還元
この最適化は、４行から３行にガーブル化表のサイズを縮小する。出力線のラベルが、入力ラベルの関数として生成される。ガーブル化表の１行目は、それが完全に０から成り、かつ送られる必要がないように生成される。詳しくは［９］を参照のこと。
【０１２９】
２．２．５  半ゲート
半ゲート法は、３行から２行への行の還元後にガーブル化表のサイズを縮小する。この最適化は、ＡＮＤゲートに当てはまる。
【０１３０】
図９は、様々なガーブル化最適化に対するカーブル化時間、ガーブル化サイズ、および評価時間が載せられる表を示す。ガーブル化時間および評価時間は、ゲート当たりのハッシュ数（ＡＥＳ）であり、ガーブル化サイズは、ゲート当たりの１２８−ビット暗号文数である。詳しくは［１０］を参照のこと。
【０１３１】
２．２．６  順序回路ガーブル化
順序回路は、従来のゲート、グローバルクロック、およびシフトレジスタを備える回路である。線における論理値は、一定ではなく、クロックチック間でバラツキがあり、それらを一連の値として表すことができる。クロックおよびシフトレジスタが何の秘密も伴わないので、ＭＰＣ回路およびＦＨＥ回路は、それらをネイティブに扱うことができる。
【０１３２】
メモリの面から言えば、回路は、よりコンパクトであり（記述がより少ない）、評価中の所与の時点で、２つの連続する時間スタンプのみを記憶するだけで足りる（それほどメモリがいらない）。しかし、それは、純粋な組合せ回路に比べて、総実行時間、ＯＴ送信、または事前計算済みデータサイズを縮小することはない。
【０１３３】
２．３  秘密分散法としてのガーブル化回路
直観的に言えば、Ｐ１（評価器）が、関数（ブール回路として表される）の出力のビット用のラベルを復号した後、Ｐ１がガ−ブラ（Ｐ０）と結託していれば、Ｐ１は、その出力を計算することができる。まだ、Ｐ０とＰ１とが結託していなければ、それらのどれも、その出力について何も知ることがなく、まだ出力が秘密分散されている。
【０１３４】
この単純な所見は、ｆｒｅｅ−ＸＯＲ最適化［７］およびｐｏｉｎｔ−ａｎｄ−ｐｅｒｍｕｔｅ最適化［８］の両方を使用して、ガーブル化回路プロトコルの背景において形式化され得る。
2020532771.tif 000123
が最下位ビット１を有するバイナリ列であると想定する。この場合、所与の線ｗに対応するキーは、
2020532771.tif 000124
であり、線ｗ用の順列ビットは、
2020532771.tif 000125
の最下位ビットである。
【０１３５】
プライベートな入力ｘに対して、分散型値は、
2020532771.tif 000126
となる。
分散プロトコルは、以下のように記述される：
2020532771.tif 000127
：ここで、Ｐ０（ガ−ブラ）は、秘密ビットｘを持っている。Ｐ０は、無作為な秘密
2020532771.tif 000128
を生成し、
2020532771.tif 000129
をＰ１に送信する。
2020532771.tif 000130
：ここで、Ｐ１（評価器）は、秘密ビットｘを持っている。秘密分散を行う際、プロトコルは、相関ＯＴを使用することができる［１］。Ｐ０（送信側）は、（相関）関数
2020532771.tif 000131
を入力し、
2020532771.tif 000132
を受信する。Ｐ１（受信側）は、
2020532771.tif 000133
を気付かずに受信する。
【０１３６】
２．４  分散法の変換
加法的秘密分散とＧＣ分散との間の基本的な変換法を思い出してみる。［４、§ＩＩＩ−ＩＶ］に詳細がまとめられている。
【０１３７】
入力ｙに対し、Ｓｈａｒｅ０（ｙ）をガーブラ標本
2020532771.tif 000134
と定義し、
2020532771.tif 000135
を計算する。それにより、ガーブラは、ｋｘを評価器に送信する。
【０１３８】
２．４．１  加法的秘密分散⇒ＧＣ分散
2020532771.tif 000136
がその群、すなわち
2020532771.tif 000137
の中で加法的に秘密分散されると仮定する。この変換は、標準的であり、ブール加算回路をセキュアに評価することによって行われ得る（詳しくは［６］を参照）。次に、ＧＣ秘密シェアが、
2020532771.tif 000138
と定義され、ここで、
2020532771.tif 000139
である。
【０１３９】
２．４．２  ＧＣ分散⇒加法的秘密分散
2020532771.tif 000140
がＧＣ秘密分散型値と想定する。加法的秘密シェアに次のように移行することができ、ガーブラが無作為なγを生成し、ＧＣがそれを秘密分散し、すなわち、Ｓｈａｒｅ０（γ）を計算する。それにより、２つのパーティが
2020532771.tif 000141
を計算することができる。つぎに、Ｐ１がｄを再構成し、この算術式シェアが
2020532771.tif 000142
と定義される。その際、再構築プロトコル
2020532771.tif 000143
を呼び出す必要がある。
【０１４０】
代替として、最初にブール秘密シェアを経て、次にブールを演算に変換することによって、移行することができることが［４、§ＩＶ．Ｆ］に示唆されている。
【０１４１】
３  信頼できるディーラを介したガーブル化回路の使用
信頼できるディーラ（ＴＤ：Ｔｒｕｓｔｅｄ  Ｄｅａｌｅｒ）が、ガーブラであり（すなわち、ガーブラも、秘密分散に向けて数字マスキングデータを生成する）、計算パーティが評価器である、信頼できるディーラモデルを導入する。
【０１４２】
この場合、秘密分散された（様々なパーティＰ１、．．．Ｐｎ−評価器の間で）ｙの符号を計算することを、ガーブラＰ０がパーティ間で秘密分散されているｙに対してマスクλを生成する、という視点から見ることができる。マスク済み値ｘ＝ｙ＋λがＰ１、．．．Ｐｎ間で明かされると（ただし、ｘは、ガーブラには知られないまま）、各Ｐｉ、ｉ＝１、．．．、ｎは、Ｐ０でガーブル化回路プロトコルを実行し、ｘ＜λであるか否か（符号（ｙ）＝−１であるか否かと等価）を確認することができる。
【０１４３】
このモデル下では、紛失通信プロトコル（通常、ガーブル化回路プロトコルのオンライン段階で実行する）をオフライン段階時の秘密分散プロトコルに取り替える必要があることに留意されたい。実際には、これは、オンライン段階からガーブラを完全に締め出す必要があることを意味する。
【０１４４】
４  シグモイド関数への適用
ここで、どのように非有界シグモイドを高精度で評価するかを示す。
【０１４５】
４．１  シグモイド関数の高精度評価
シグモイド関数
2020532771.tif 000144
を考え、固定有界区間［−Ｂ、Ｂ］（例えば、［−１０、１０］）におけるフーリエ級数によってこの関数の十分に良い近似を有すると仮定する。まだ、フーリエ級数は、この区間の補集合においてこの関数を近似する必要はない。実際には、フーリエ級数は、この区間の外側に発散し、それにより、［−Ｂ、Ｂ］の外側のｘに対するσ（ｘ）の数値精度における大きな低下をもたらすように見られる。
【０１４６】
この問題を解消するために、精度ｐ、ｘおよびσ（ｘ）を所与として、最初にσ（−Ｂ）＜ｐおよびσ（Ｂ）＞１−ｐであるように区間［−Ｂ、Ｂ］を定め、次いで、０を戻すことで、実際のシグモイドを計算したいと思う。同様に、あらゆるｘ＞Ｂで、１を戻す。そうでなければ、フーリエ近似法によって計算したσ（ｘ）を戻す。フーリエベースの評価は、［３］に記載の補助マスキングデータを用いて秘密ＭＰＣによって行われる。比較演算は、ガーブル化回路によって行われる。
【０１４７】
大筋として、境界Ｂを所与として、関数σＦｏｕｒ（ｘ）を、区間［−Ｂ、Ｂ］における関数σ（ｘ）を一様に近似する調和関数の一次結合と定義する。σＦｏｕｒ（ｘ）が、［３］に提示されているＢｅａｖｅｒ数字マスキングデータを用いて秘密分散プロトコルによって評価されたＭＰＣとすることができることに留意されたい。
【０１４８】
しかし、この区間の外側では、２つの関数が、通常素早く発散するので、σ（ｘ）をσＦｏｕｒ（ｘ）に簡単に取り替えることができない。理想的には、加法的に秘密分散されている入力ｘにおいて、関数
2020532771.tif 000145
、
を評価することを望む。
【０１４９】
考え方としては、ｘが加法的に秘密分散される場合、２．４節の変換技法を使用して、ｘをＧＣ秘密シェアに変換する、というものである。次に、ガーブル化ブール回路を評価し（次の節に提示）、ｘが位置する区間を気付かずに見付けるようになる（すなわち、ｘが（−∞、−Ｂ）にあるか、［−Ｂ、Ｂ］にあるか、または（Ｂ、＋∞）にあるか）。
【０１５０】
４．２  ブール比較回路および加算回路
どのように加法的秘密シェアからＧＣ秘密シェアに変換するかが分かっているので、２つの比較をすでにガーブル化し、評価することができる。これを行う際、それぞれｎビットの２つの数を比較するのに陽的ブール回路を必要とする。
【０１５１】
４．２．１  比較回路
図１０は、以下のように、比較回路例を示す：
入力：評価器に知られているｘ（場合によっては、ガーブラだけに知られている色でマスクされている）
入力λ：ガーブラに知られているλ
出力：ｘ＜λ（場合によっては、ガーブラだけに知られている色でマスクされている）
図示の回路では、半ゲート技法から恩恵を受ける可能性があることが分かる。
【０１５２】
４．２．２  秘密加算回路
図１１は、以下のように、秘密加算回路例を示す：
入力：評価器に知られているｘ（場合によっては、ガーブラだけに知られている色でマスクされている）、入力λ：ガーブラに知られているλ
出力：ｘ＋λ（場合によっては、ガーブラだけに知られている色でマスクされている）
この場合もまた、半ゲート技法から恩恵を受ける可能性があることが分かる。
【０１５３】
５  カーブル化オートマトン
ガーブル化回路をマスキング技法と組み合わせていることから、別の見方ができる。普通のカーブル化回路では、各線には、２つの可能な論理状態があり（それらの真理値は０、１）、ゲートは、これらの状態間の推移を符号化する。
【０１５４】
５．１  ガーブル化ＧＣ秘密分散の二重化
ここで、有限状態オートマトンの背景において有用になってくる古典的なガーブル化回路法における二重の見方について説明する。
【０１５５】
５．１．１  明かされた値に対する秘密演算
図１２は、関数の２つの例の図を示す。（秘密）出力ｚをもたらす２つの秘密入力ｘおよびｙに対して公開関数Ｆを有する、すなわち、ｚ＝Ｆ（ｘ、ｙ）と想定する。例えば、Ｆは、古典的なガーブル化回路の意味ではブールゲートと考えられ得、ｘおよびｙは、プライベートな入力と考えられ得る。ｘおよびｙが、２．３節に説明されている意味で、ガーブラと評価器との間で秘密分散されていると想定すると、この方式の代替の考え方は、マスクキングの視点からであり、すなわち、ガーブラが、ｘとｙとに対してそれぞれ、マスクλとμとを生成しており、同様に出力ｚ＝Ｆ（ｘ、ｙ）に対してマスクνを生成している。ＵＦが、この図を可換性にするような、明かされた値ａおよびｂに働く関数Ｇを探すことにする。
【０１５６】
例えば、Ｂｅａｖｅｒ乗算では、Ｆ＝ｘ、およびｍａｓｋλ＝＋λであるので、
ＵＦ（ａ、ｂ）＝（ａ−λ）×（ｂ−μ）＋νであると難なく判断する。（１）
これから分かるように、この関数は、ガーブラ（マスクλ、μ、およびνを知っている唯一のパーティである）だけに知られている。したがって、それは、秘密関数と考えられ得る。
【０１５７】
ここで、演算ｍａｓｋλ：Ｄ→Ｒを、２つの集合、Ｄ−変数ｘの領域と、Ｒ−マスクされた／明かされた値の集合との（秘密）全単射として見る（厳密に言えば、記号λは必要とされず、必要なのは、単に各線に関連付けられた関数マスクである）。ｕｎｍａｓｋλ：Ｒ→Ｄを使用して、逆写像を表す。セキュリティの面から、ｍａｓｋλ（ｘ）を知ることで、ｘまたは全単射マスクλについての情報が明かされてはならない。
【０１５８】
考察２  マスクがＤとＲとの間の一様に無作為な全単射である必要がないことに留意されたい。これは、例えば、［３］に記載の統計的マスキングの場合である。
【０１５９】
５．１．２  ラベル付け
考えられるマスク済み値ａ＝ｍａｓｋλ（ｘ）ごとに、Ｘａを与えると、誰もが簡単にａを引き出すことができるが、ａを与えると、評価器がＸａを確定することができないような、ラベルＸａを定義する。
【０１６０】
５．１．３  ガーブル化表
ガーブラは、以下のようにガーブル化表を作り出す：表の行は、以下であり、
2020532771.tif 000146
式中、ａ、ｂは、対応する明かされた集合の順番で（自然順と呼ばれる）列挙される。
【０１６１】
５．２  二重視点によるガーブル化オートマトン
図１３は、ｎ個の文字を処理する状態機械の概略図を示す。状態機械は、以下のように記述され得る：
●反復のたびに、状態機械は、状態
2020532771.tif 000147
を呈する。領域Ｑｉは、公開されているが、ｑｉは、普通は内密にされる（ガーブラにも評価器にも知られていない、ということを意味する）。ここで、ｑ０は、初期状態であり、評価したいと思う関数に応じて、公開されているかまたは内密であるかのいずれかであり得る。
●反復のたびに、状態機械は、アルファベットΣｉから文字αｉを読み取る。アルファベットΣｉは、公開されており、反復のたびに異なる可能性がある。本発明のモデルでは、文字は、評価器には知られているが、ガーブラには知られていない。
●各反復間で、状態が、決定論的な遷移関数
2020532771.tif 000148
によって結び付けられる。図１２の図によってＴｉに関連付けられた関数
2020532771.tif 000149
は、ガーブラ（ｑｉ−１のマスキング値λｉ−１およびαｉのマスキング値μｉを知っている唯一の者である）だけに知られている。まだ、この関数の定義域は、公開されている（例えば、関数Ｕｉは、（１）における関数である可能性がある）。
【０１６２】
５．２．１  ガーブル化段階
各状態Ｑｉに対し、ガーブラは、Ｑｉの置換と考えられる、すなわち、ｍａｓｋλｉ：Ｑｉ→Ｒｉ（ここで、Ｒｉは、明かされた値を表す）である、ｍａｓｋλｉを選ぶ。ここで、Ｒｉ＝（γｉ、１、．．．、γｉ、ｊ、．．．）が得られ、ガーブラを除き、値γｉ、ｊは、状態ｑｉ、ｊ＝ｕｎｍａｓｋλｉ（γｉ、ｊ）について何も明かさない。
【０１６３】
マスキングｍａｓｋλｉおよびｍａｓｋμｉから、ガーブラは、ガーブル化表Ｔｉを定義することもできる。Ｘｉ、ｊを使用して、γｉ、ｊのラベルを表し、また、確実にＸｉ、ｊからｊ（それにより、γｉ、ｊ）を推定することができるようにする（例えば、ラベルの最上位ビットがｊに等しい可能性がある）。ガーブラはまた、すべての考えられる文字
2020532771.tif 000150
に対してマスキング値ｍａｓｋｉ、ｊを選び出すが、この時、順番に対して何のプライバシ要件もない（インデックスｊは、この文字を公に明かすことができるか、または文字と等しいものでさえあり得る）。
【０１６４】
反複ｉのたびに、各文字
2020532771.tif 000151
に対し、ガーブラは、
2020532771.tif 000152
暗号文一覧から成る遷移関数
2020532771.tif 000153
を暗号化する。より正確に言えば、ガーブラは、Ｑｉ−１に対するマスクｍａｓｋλ−１およびΣｉに対するマスクｍａｓｋλ−１、ならびにプライベート関数
2020532771.tif 000154
を使用して、５．１．３節に見られるように定義されたガーブル化表Ｔｉを計算する。
【０１６５】
行の還元：ラベルは必ず、各遷移関数（例えば、Ｃｉ、α、０）の最初の暗号文が必ず０であり、伝達される必要のないように、選ばれ得る。
【０１６６】
５．２．２  評価段階
評価器は、ｎ個の文字αｉに対するラベルｙｉ、および初期状態の初期ラベルｘ０を受信している（ＯＴを介して、またはマスキングを介して）（それにより、評価器は、その色ｊ０を推定する）。ｉ＝１〜ｎに対し、評価器は、
2020532771.tif 000155
を復号し、次のラベルｊｉを推定する。
【０１６７】
最後の状態のラベルは、その回路の結果である。結果が内密にされるべきか、マスクされるべきか、または公開されるべきかに応じて、ガーブラによって、写像用ｕｎｍａｓｋが提供され得る。
【０１６８】
５．３  例
ここで、オートマトンの視点が役立つ可能性があり、より一般的なオートマトンを考えると、実際にいくつかのプロトコルのスピードアップを促進する、いくつかの例を示すことにする。
【０１６９】
５．３．１  ビット単位比較オートマトンの場合の例
加法的に分散された１２８−ビット数ｘの符号を計算する必要があると仮定する。ガーブラが、ｍａｓｋλを選ぶ（オンライン段階中、ａ＝ｘ＋λが明かされるようになる）。ｑｕｅｓｔｉｏｎ  ｘ≦０が、ａ≦λに等価であるので、ガーブラは、以下のように、「ラムダに匹敵する」オートマトンを符号化する：
ａおよびλのｉ最下位ビットの比較の結果を、ｑｉで表す。（略式に、（ａ  ｍｏｄ  ２ｉ）≦（λ  ｍｏｄ  ２ｉ））。定義として、
●初期状態：ｑ０：＝１
●遷移：ａｉ＝λｉであれば、ｑｉ：＝ｑｉ−１、さもなければλｉ
●出力：ｑ１２８は、ａ≦λに対する答えである。
●すべてのｉに対して
2020532771.tif 000156
。
●ガーブル化段階：１２８×２×２＝５１２暗号化、１２８×３＝３８４暗号文（行の還元）
●評価段階：１２８×１復号
オートマトン手法は、すべての知られている最適化（半ゲート、ｐｏｉｎｔ−ａｎｄ−ｐｅｒｍｕｔｅ）を含むように見える。
【０１７０】
５．３．２  基底４比較オートマトンの場合の例
これは、基底４において比較を行うことを除いて、上記の基底２比較オートマトンと同じである。状態Ｑｉは、まだブールの意味を有するが、アルファベットΣｉ＝０、１、２、３である。また、ａとλとのｉ最下位ビットの比較の結果をｑｉで表示する。（略式に、（ａ  ｍｏｄ  ２ｉ）≦（λ  ｍｏｄ  ２ｉ））。定義として、
●ｑ０：＝１
●ａｉ＝λｉであれば、ｑｉ：＝ｑｉ−１、さもなければ（ａｉ≦λｉ）
●ｑ６４は、ａ≦λに対する答えである。
●すべてのｉに対して
2020532771.tif 000157
。
●ガーブル化段階：６４×４×２＝５１２暗号化、６４×７＝４４８暗号文（行の還元）
●評価段階：６４×１復号
基底−４オートマトンは、すべての知られている最適化（半ゲート、ｐｏｉｎｔ−ａｎｄ−ｐｅｒｍｕｔｅ）を備える従来のガーブル化回路よりずっと良い。
【０１７１】
５．３．３  秘密整数加算の場合の例
入力として、整数（ａ０、．．．、ａｎ）が、リトルエンディアン順序の０〜９までの数字である（例えば、基底Ｂにおける）、ａ（公開されたまたはマスクされた）を取る。λがガーブラだけに知られているａ＋λを計算したいと思う。この場合、オートマトンを使用して、キャリービットを計算し、古典的なｆｒｅｅ−ｘｏｒ技法を使用して、そのキャリービットと入力とのｘｏｒをとり、最終結果を得ることになる。
●ｑ０：＝０
●
2020532771.tif 000158
。
●すべてのｉに対して
2020532771.tif 000159
。
●
2020532771.tif 000160
（ｆｒｅｅ−ｘｏｒ  ｍｏｄ  Ｂを使用）
【０１７２】
参考文献
１．Ｇ．Ａｓｈａｒｏｖ，Ｙ．Ｌｉｎｄｅｌｌ，Ｔ．Ｓｃｈｎｅｉｄｅｒ，ａｎｄ  Ｍ．Ｚｏｈｎｅｒ．Ｍｏｒｅ  ｅｆｆｉｃｉｅｎｔ  ｏｂｌｉｖｉｏｕｓ  ｔｒａｎｓｆｅｒ  ａｎｄ  ｅｘｔｅｎｓｉｏｎｓ  ｆｏｒ  ｆａｓｔｅｒ  ｓｅｃｕｒｅ  ｃｏｍｐｕｔａｔｉｏｎ．Ｉｎ  Ａｈｍａｄ−Ｒｅｚａ  Ｓａｄｅｇｈｉ，Ｖｉｒｇｉｌ  Ｄ．Ｇｌｉｇｏｒ，ａｎｄ  Ｍｏｔｉ  Ｙｕｎｇ，ｅｄｉｔｏｒｓ，２０１３  ＡＣＭ  ＳＩＧＳＡＣ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｅｃｕｒｉｔｙ，ＣＣＳ’１３，Ｂｅｒｌｉｎ，Ｇｅｒｍａｎｙ，Ｎｏｖｅｍｂｅｒ  ４−８，２０１３，ｐａｇｅｓ  ５３５−５４８．ＡＣＭ，２０１３．
２．Ｍ．Ｂｅｌｌａｒｅ，Ｖ．Ｈｏａｎｇ，Ｓ．Ｋｅｅｌｖｅｅｄｈｉ，ａｎｄ  Ｐ．Ｒｏｇａｗａｙ．Ｅｆｆｉｃｉｅｎｔ  ｇａｒｂｌｉｎｇ  ｆｒｏｍ  ａ  ｆｉｘｅｄ−ｋｅｙ  ｂｌｏｃｋｃｉｐｈｅｒ．Ｉｎ  ２０１３  ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｐｒｉｖａｃｙ，ＳＰ  ２０１３、Ｂｅｒｋｅｌｅｙ，ＣＡ，ＵＳＡ，Ｍａｙ  １９−２２，２０１３，ｐａｇｅｓ  ４７８−４９２．ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ，２０１３．
３．Ｃ．Ｂｏｕｒａ，Ｉ．Ｃｈｉｌｌｏｔｔｉ，Ｎ．Ｇａｍａ，Ｄ．Ｊｅｔｃｈｅｖ，Ｓ．Ｐｅｃｅｎｙ，ａｎｄ  Ａ．Ｐｅｔｒｉｃ．Ｈｉｇｈ−ｐｒｅｃｉｓｉｏｎ  ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  ｒｅａｌ−ｖａｌｕｅｄ  ｆｕｎｃｔｉｏｎ  ｅｖａｌｕａｔｉｏｎ．Ｃｒｙｐｔｏｌｏｇｙ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ，Ｒｅｐｏｒｔ  ２０１７／１２３４，２０１７．ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１７／１２３４．
４．Ｄ．Ｄｅｍｍｌｅｒ，Ｔ．Ｓｃｈｎｅｉｄｅｒ，ａｎｄ  Ｍ．Ｚｏｈｎｅｒ．ＡＢＹ−Ａ  ｆｒａｍｅｗｏｒｋ  ｆｏｒ  ｅｆｆｉｃｉｅｎｔ  ｍｉｘｅｄ−ｐｒｏｔｏｃｏｌ  ｓｅｃｕｒｅ  ｔｗｏ−ｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ．Ｉｎ  ２２ｎｄ  Ａｎｎｕａｌ  Ｎｅｔｗｏｒｋ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍ  Ｓｅｃｕｒｉｔｙ  Ｓｙｍｐｏｓｉｕｍ，ＮＤＳＳ  ２０１５，Ｓａｎ  Ｄｉｅｇｏ，Ｃａｌｉｆｏｒｎｉａ，ＵＳＡ，Ｆｅｂｒｕａｒｙ  ８−１１，２０１５．Ｔｈｅ  Ｉｎｔｅｒｎｅｔ  Ｓｏｃｉｅｔｙ，２０１５．
５．Ｖ．Ｋｏｌｅｓｎｉｋｏｖ，Ｐ．Ｍｏｈａｓｓｅｌ，ａｎｄ  Ｍ．Ｒｏｓｕｌｅｋ．Ｆｌｅｘｏｒ：Ｆｌｅｘｉｂｌｅ  ｇａｒｂｌｉｎｇ  ｆｏｒ  ＸＯＲ  ｇａｔｅｓ  ｔｈａｔ  ｂｅａｔｓ  ｆｒｅｅ−ｘｏｒ．Ｉｎ  Ｊ．Ｇａｒａｙ  ａｎｄ  Ｒ．Ｇｅｎｎａｒｏ，ｅｄｉｔｏｒｓ，Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ  ２０１４−３４ｔｈ  Ａｎｎｕａｌ  Ｃｒｙｐｔｏｌｏｇｙ  Ｃｏｎｆｅｒｅｎｃｅ，Ｓａｎｔａ  Ｂａｒｂａｒａ，  ＣＡ，ＵＳＡ，Ａｕｇｕｓｔ  １７−２１，２０１４，Ｐｒｏｃｅｅｄｉｎｇｓ，Ｐａｒｔ  ＩＩ，ｖｏｌｕｍｅ  ８６１７  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，ｐａｇｅｓ  ４４０−４５７．Ｓｐｒｉｎｇｅｒ，２０１４．
６．Ｖ．Ｋｏｌｅｓｎｉｋｏｖ，Ａ．Ｓａｄｅｇｈｉ，ａｎｄ  Ｔ．Ｓｃｈｎｅｉｄｅｒ．Ａ  ｓｙｓｔｅｍａｔｉｃ  ａｐｐｒｏａｃｈ  ｔｏ  ｐｒａｃｔｉｃａｌｌｙ  ｅｆｆｉｃｉｅｎｔ  ｇｅｎｅｒａｌ  ｔｗｏ−ｐａｒｔｙ  ｓｅｃｕｒｅ  ｆｕｎｃｔｉｏｎ  ｅｖａｌｕａｔｉｏｎ  ｐｒｏｔｏｃｏｌｓ  ａｎｄ  ｔｈｅｉｒ  ｍｏｄｕｌａｒ  ｄｅｓｉｇｎ．    Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｅｃｕｒｉｔｙ，２１（２）：２８３−３１５，２０１３．
７．Ｖ．Ｋｏｌｅｓｎｉｋｏｖ  ａｎｄ  Ｔ．Ｓｃｈｎｅｉｄｅｒ．Ｉｍｐｒｏｖｅｄ  ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔ：    Ｆｒｅｅ  ＸＯＲ  ｇａｔｅｓ  ａｎｄ  ａｐｐｌｉｃａ−ｔｉｏｎｓ．Ｉｎ  Ｌｕｃａ  Ａｃｅｔｏ，Ｉｖａｎ  Ｄａｍａｒｄ，Ｌｅｓｌｉｅ  Ａｎｎ  Ｇｏｌｄｂｅｒｇ，Ｍａｇｎｕｓ  Ｍ．Ｈａｌｌｄｏｒｓｓｏｎ，Ａｎｎａ  Ｉｎｇｏｌｆｓｄｏｔｔｉｒ，ａｎｄ  Ｉｇｏｒ  Ｗａｌｕｋｉｅｗｉｃｚ，ｅｄｉｔｏｒｓ，Ａｕｔｏｍａｔａ，Ｌａｎｇｕａｇｅｓ  ａｎｄ  Ｐｒｏｇｒａｍｍｉｎｇ，３５ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｌｌｏｑｕｉｕｍ，ＩＣＡＬＰ  ２００８  Ｒｅｙｋｊａｖｉｋ，Ｉｃｅｌａｎｄ，Ｊｕｌｙ  ７−１１，２００８，Ｐｒｏｃｅｅｄｉｎｇｓ，Ｐａｒｔ  ＩＩ−Ｔｒａｃｋ  Ｂ：Ｌｏｇｉｃ，Ｓｅｍａｎｔｉｃｓ，ａｎｄ  Ｔｈｅｏｒｙ  ｏｆ  Ｐｒｏｇｒａｍｍｉｎｇ＆Ｔｒａｃｋ  Ｃ：Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｆｏｕｎｄａｔｉｏｎｓ，ｖｏｌｕｍｅ  ５１２６  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，ｐａｇｅｓ  ４８６−４９８．Ｓｐｒｉｎｇｅｒ，２００８．
８．Ｄ．Ｍａｌｋｈｉ，Ｎ．Ｎｉｓａｎ，Ｂ．Ｐｉｎｋａｓ，ａｎｄ  Ｙ．Ｓｅｌｌａ．Ｆａｉｒｐｌａｙ−ｓｅｃｕｒｅ  ｔｗｏ−ｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ  ｓｙｓｔｅｍ．Ｉｎ  Ｍａｔｔ  Ｂｌａｚｅ，ｅｄｉｔｏｒ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １３ｔｈ  ＵＳＥＮＩＸ  Ｓｅｃｕｒｉｔｙ  Ｓｙｍｐｏｓｉｕｍ，Ａｕｇｕｓｔ  ９−１３，２００４，Ｓａｎ  Ｄｉｅｇｏ，ＣＡ，ＵＳＡ，ｐａｇｅｓ  ２８７−３０２．ＵＳＥＮＩＸ，２００４．
９．Ｍ．Ｎａｏｒ，Ｂ．Ｐｉｎｋａｓ，ａｎｄ  Ｒ．Ｓｕｍｎｅｒ．Ｐｒｉｖａｃｙ  ｐｒｅｓｅｒｖｉｎｇ  ａｕｃｔｉｏｎｓ  ａｎｄ  ｍｅｃｈａｎｉｓｍ  ｄｅｓｉｇｎ．Ｉｎ  ＥＣ，ｐａｇｅｓ  １２９−１３９，１９９９．
１０．Ｓ．Ｚａｈｕｒ，Ｍ．Ｒｏｓｕｌｅｋ，ａｎｄ  Ｄ．Ｅｖａｎｓ．Ｔｗｏ  ｈａｌｖｅｓ  ｍａｋｅ  ａ  ｗｈｏｌｅ−ｒｅｄｕｃｉｎｇ  ｄａｔａ  ｔｒａｎｓｆｅｒ  ｉｎ  ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔｓ  ｕｓｉｎｇ  ｈａｌｆ  ｇａｔｅｓ．    Ｉｎ  Ｅ．Ｏｓｗａｌｄ  ａｎｄ  Ｍ．Ｆｉｓｃｈｌｉｎ，ｅｄｉｔｏｒｓ，Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＥＵＲＯＣＲＹＰＴ  ２０１５−３４ｔｈ  Ａｎｎｕａｌ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  ｔｈｅ  Ｔｈｅｏｒｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｔｅｃｈｎｉｑｕｅｓ，Ｓｏｆｉａ，Ｂｕｌｇａｒｉａ，Ａｐｒｉｌ  ２６−３０，２０１５，Ｐｒｏｃｅｅｄｉｎｇｓ，Ｐａｒｔ  ＩＩ，ｖｏｌｕｍｅ  ９０５７  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，ｐａｇｅｓ  ２２０−２５０．Ｓｐｒｉｎｇｅｒ，２０１５．
【０１７３】
ＩＩＩ．プライバシ保護プログラムをコンパイルするための方法
０  概要
プライバシ保護プログラムをコンパイルするための方法を開示し、このプログラムでは、ドメイン特化プログラミング言語（ＤＳＬ：Ｄｏｍａｉｎ−Ｓｐｅｃｉｆｉｃ  ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅ）により、データアナリストが、その入力データがいくつかのプライベートなデータソースに格納されるプライバシ保護計算の際、コードを書き込むことができる。プライバシ保護計算それ自体は、「高精度プライバシ保護実数値関数評価」の見出しで上記Ｉ節に開示されている方法を使用して行われ得る。
【０１７４】
ＤＳＬコードは、個々のプライベートなデータソースまたはパーティに特有の複数のコンピューティングシステムノードによって実行され得る低レベル仮想マシンコードに、マルチパーティ計算向けの専用コンパイラによってコンパイルされ得る。
【０１７５】
プログラミング言語は、関数および関数呼び出し、限られた反復回数（コンパイル時に分かる）のｆｏｒ  ｌｏｏｐ、ならびに公開条件による条件文をサポートすることができる。この言語は、スコープド変数をサポートすることができる。最後に、変数を型付けすることでき、型は、ユーザ入力から、またはコンパイラによって推定された、ある種の統計的パラメータを有することができる。
【０１７６】
以下に、ＤＳＬコンパイラおよび専用コンパイラ両方の実施形態のより詳細な説明を示す。
【０１７７】
１  ＤＳＬ、コンパイルおよび実行時間アーキテクチャ
一実施形態において、ＤＳＬコードは、関数定義を含み得る。１つの関数定義は、エントリポイントであり得る（実引数なしのｖｏｉｄ  ｍａｉｎ（）関数）。ＤＳＬのレベルにおいて、関数の内容は、構文上、ステートメントツリー：ブロック、ｐｕｂｌｉｃ  ｉｆ−ｔｈｅｎ−ｅｌｓｅ、ｐｕｂｌｉｃ  ｂｏｕｎｄｅｄ  ｆｏｒ、およびＭＰＣ計算時にサポートされる他の特定のステートメント、であり得る。ステートメントには、子ステートメントとともに他のパラメータが含まれ得る。以下に、特定のステートメントについて、一実施形態に従って述べる。
【０１７８】
ブロックは、オフライン評価時、オンライン評価時両方で、連続して評価される子ステートメントリストである。例えば：
｛
／＊ａ  ｓｅｑｕｅｎｃｅ  ｏｆ  ｃｈｉｌｄ  ｓｔａｔｅｍｅｎｔｓ＊／
．．．
｝
スコープド変数は、ステートメントに、または最上位で宣言された変数である（グローバル変数）。ｐｕｂｌｉｃ  ｉｆ−ｔｈｅｎ−ｅｌｓｅは、スコープド変数、および２つの子ステートメントによってパラメータ化される。オフライン段階中、両方の子ステートメントが、同じ入力バインディングから評価され、オンライン段階中、その条件の公開値に応じて、これらの子ステートメントのうちの１つのみが評価される。ｂｏｕｎｄｅｄ  ｆｏｒ  ｌｏｏｐは、Ｎ値の公開整数域で反復するスコープド変数、１つの子命令、ｂｒｅａｋ条件によってパラメータ化される。オフライン段階中、子命令は、Ｎ回連続して繰り返される。オンライン段階中、ｂｒｅａｋ条件が、公に真と評価されない限り、子命令が繰り返され、この場合、ｆｏｒ  ｌｏｏｐが終了する。ｂｒｅａｋ条件がない場合、それは、初期設定で偽である。例えば：
ｆｏｒ  ｉ  ｉｎ  ｒａｎｇｅ（０、１０）｛
／＊ｓｅｑｕｅｎｃｅ  ｃｈｉｌｄ  ｉｎｓｔｒｕｃｔｉｏｎｓ＊／
ｂｒｅａｋｉｆ  ｅｘｐｒｅｓｓｉｏｎ；
｝
イミュータブルは、オフライン実行時のある時点における、スコープド変数のある特定の出現に対応する。各イミュータブルは、大域的な連続するインデックスを得る。したがって、専用コンパイラは、スコープド変数をイミュータブルに解決する。
【０１７９】
コンパイラは、ＤＳＬコードを命令ツリーおよびイミュータブル宣言に変換する（ステートメント、例えばブロックは、１つより多い命令またはイミュータブル宣言を含み得る）。次に、このツリーは、「高精度プライバシ保護実装値関数評価」の見出しで上記のＩ節に説明した方法によって、各パーティコンピューティングシステム上で進行する低レベル仮想マシンコードに変換され得る。
【０１８０】
同じプログラムを二通りに評価することができ、１つは、少なくとも１回各命令を走り抜けるオフライン評価で、もう１つは、オフライン評価の部分集合であるオンライン評価である（例えば、以下の「ｐｕｂｌｉｃ  ｉｆ−ｔｈｅｎ−ｅｌｓｅ」参照）。
【０１８１】
１．１  オフライン命令インデックス
オフライン評価の最中の命令の各実行で、大域的な連続するインデックスである命令インデックスが得られる。ｆｏｒ  ｌｏｏｐおよび関数呼び出しの場合には、構文的な命令が、複数のオフラインインデックスを有することがある。ほとんどのオフラインインデックスは、条件付きジャンプが起こり得るｉｆ−ｔｈｅｎ−ｅｌｓｅまたはｆｏｒ  ｌｏｏｐｓを除き、オンライン段階中に連続して実行される。
【０１８２】
１．２  スコープド変数
変数のスコープは、変数が定義される命令のオフライン評価の持続期間である。各変数は、それがオフライン評価中に現れるのに従って、大域的な一意の連続するインデックスｖａｒｉａｂｌｅＩｄｘを得る。
｛
／＊ｖａｒｉａｂｌｅｓ  ａｒｅ  ｎｏｔ  ａｃｃｅｓｓｉｂｌｅ  ｂｅｆｏｒｅ  ｔｈｅｉｒ  ｄｅｃｌａｒａｔｉｏｎ＊／
ＭＰＣＲｅａｌ  ｘ；／＊ｄｅｃｌａｒａｔｉｏｎ  ｗｉｔｈｉｎ  ａ  ｂｌｏｃｋ＊／
／＊ｓｅｑｕｅｎｃｅ  ｏｆ  ｉｎｓｔｒｕｃｔｉｏｎｓ＊／
／＊ｔｈｅ  ｓｃｏｐｅ  ｏｆ  ｘ  ｉｓ  ｌｉｍｉｔｅｄ  ｔｏ  ｔｈｉｓ  ｂｌｏｃｋ＊／
｝
【０１８３】
上の例では、ｘのスコープは、上に表示したブロックに限られる。したがって、変数のスコープを記述する際、変数が宣言されるブロックの経過を追う必要がある。
【０１８４】
１．３  型
擬似コードでは、各変数を使用する前に宣言しておく必要があり、ユーザは、例えば、変数が、行列、ベクトル、または数を含むように意図されている場合、（部分的な）型情報を指定することの選択肢を有する。ユーザによって提供された情報に基づき、コンパイラは、統計電卓として知られている構成要素を使用して完全な型推定を行う。関数実引数、またはそれらの代入による即値宣言では、ユーザは、ｖａｒ型またはａｕｔｏ型しか提供することができず、これは、コンパイラが完全な推定を行うようになることを意味する。これに加え、コンパイラは、推定した型を使用して、関数または演算子を固有分解能にする必要がある。例えば、以下のコード片を持っていると仮定する：
／＊ａ、ｂ  ｈａｖｅ  ｂｅｅｎ  ｄｅｆｉｎｅｄ  ｐｒｅｖｉｏｕｓｌｙ，ｃ  ｉｓ  ｄｅｃｌａｒｅｄ  ａｎｄ  ｉｔ’ｓ  ｔｙｐｅ  ｉｓ  ｄｅｄｕｃｅｄ＊／
ａｕｔｏ  ｃ＝ａ＋ｂ；
．．．
【０１８５】
コンパイラは、型確認を行う必要がある。これは、抽象構文木（ＡＳＴ：Ａｂｓｔｒａｃｔ  Ｓｙｎｔａｘ  Ｔｒｅｅ）がビルドされた後行われるようになる（変数がイミュータブルに解決され、型確認が行われる間）。この段階で、コンパイラは、ａおよびｂの型に基づき、使用する必要のある演算子「＋」がどれかを判断し、ｃの完全な型を推定する。
【０１８６】
【０１８７】
１．４  ブロックＩＤ
一実施形態において、ＭＰＣプログラムをコンパイルすることができるようにするためには、各ブロックが実行される最高回数を分かるしかない（この情報は、オフライン段階に必要とされる）。したがって、各ブロックステートメントは、指定のｂｌｏｃｋＩｄを持つことができる。
【０１８８】
１．５  関数呼び出し
ＭＰＣにおいて、以下のような関数を持っていると仮定する；
ｄｅｆ  ｆｏｏ（）｛
／＊ｆｕｎｃｔｉｏｎ  ｃｏｄｅ＊／
＜ＭＰＣＴｙｐｅ  ｘ；
｝
ここでの課題は、コンパイル時に、何回関数が呼び出されるかが正確に分からず、それにより、何回値ｘをマスクしなければならないか（言い換えれば、何種類のイミュータブルがｘに対応しなければならないか）がはっきり分からないことである。すべてが明らかになって初めて、コンパイラは、コンパイル時にスタックオーバーフローを検出することができるようになる。一実施形態において、コンパイラが関数呼び出し最高回数を確定することができ、またコンパイラが関数を明らかにすることができるという制約の下、関数および関数呼び出しがサポートされる。
【０１８９】
１．６  イミュータブル
一実施形態において、各イミュータブルは、大域的な連続するインデックス−ｉｍｍｕｔａｂｌｅＩｄｘを得る。イミュータブルは、コンパイル時に確定されるパラメータ化型（ＭＰＣＴｙｐｅ）を有する。初期化されると、イミュータブルの論理値は、一定になる。一実施形態において、イミュータブルは、マスキング型当たり多くても１つのマスクにしか対応しておらず、したがって、マスキング型当たり多くても１つのマスク済み値しか持たない。イミュータブルの実際の値（表現）は、オンライン評価中にだらだらと計算され、それ自体の入れ物に各参加者によって格納される。これらの値には、例えば、以下を含めることができる：
●公開値（論理値に等しい）、全参加者で同じ（公開値がある場合、それは、他のすべての表現に優先する）
●秘密分散型値（秘密分散法による）、参加者により異なる
●マスク済み値（マスキング型による）、全参加者で同じ
例えば、ＤＳＬの以下の抜粋は、
／＊ｘ  ｉｓ  ａｎ  ＭＰＣＴｙｐｅ＊／
＜ＭＰＣＴｙｐｅ  ｘ；
ｘ：＝ｘ＋ｙ；
ｘ：＝ｘ＊ｘ；
イミュータブルを伴う以下の中間コードに解決する必要があり、
／＊  ｘ  ｉｓ  ａｎ  ＭＰＣＴｙｐｅ  ＊／
ＭＰＣＴｙｐｅ  ｘ１；
ｘ２：＝ｘ１＋ｙ；
ｘ３：＝ｘ２＊ｘ２；
式中、×１、×２、×３は、ＭＰＣ変数ｘにすべてが対応するイミュータブルである。
【０１９０】
１．７  Ｐｕｂｌｉｃ  ｉｆ−ｔｈｅｎ−ｅｌｓｅ
一般的なｐｕｂｌｉｃ  ｉｆ−ｔｈｅｎ−ｅｌｓｅは、以下の構成である：
ｉｆ  （／＊ｐｕｂｌｉｃ  ｃｏｎｄｉｔｉｏｎ＊／）  ｔｈｅｎ  ｛
／＊ａｄｄ  ｙｏｕｒ  ｃｏｄｅ  ｈｅｒｅ＊／
｝  ｅｌｓｅ  ｛
／＊ａｄｄ  ｙｏｕｒ  ｃｏｄｅ  ｈｅｒｅ＊／
｝
一例として、以下のソースコード抜粋を考察する：
／＊ｘ，  ｙ  ｈａｖｅ  ｂｅｅｎ  ｄｅｃｌａｒｅｄ  ａｓ  ａ  ｓｅｃｒｅｔ  ｓｈａｒｅｄ  ＭＰＣ  ｔｙｐｅ＊／
ｉｆ  （／＊ｐｕｂｌｉｃ  ｃｏｎｄｉｔｉｏｎ＊／）  ｔｈｅｎ  ｛
ｘ：＝２＊ｘ；
｝  ｅｌｓｅ  ｛
ｘ：＝ｘ＋ｙ；
ｘ：＝２＊ｘ；
｝
ｚ：＝ｘ＊ｘ；
ここで、イミュータブルの集まりによって内部的に表されるようになるＭＰＣ変数ｘを有する。実際には、コンパイラが、以下のように、スコープド変数ｘを複数のイミュータブルに取り替える以下のコードに、上記のステートメントを変換する可能性がある：
／＊ｘｉ，ｙｉ  ａｒｅ  ｔｈｅ  ｉｍｍｕｔａｂｌｅｓ  ｃｏｒｒｅｓｐｏｎｄｉｎｇ  ｔｏ  ｘ  ａｎｄ  ｙ
／＊Ｎｏｔｅ  ｔｈａｔ  ｘ５  ｉｓ  ａｎ  ａｕｘｉｌｉａｒｙ  ｉｍｍｕｔａｂｌｅ  ｗｉｔｈ  ｔｈｅ  ｍａｘｉｍｕｍ  ｏｆ  ｔｈｅ  ｐａｒａｍｅｔｅｒｓ  ｆｏｒ  ｘ２  ａｎｄ  ｘ４．
＊／
ｉｆ  （／＊ｐｕｂｌｉｃ  ｃｏｎｄｉｔｉｏｎ＊／）  ｔｈｅｎ  ｛
ｘ２：＝２＊ｘ１；
ｘ５：＝ｘ２；
｝  ｅｌｓｅ  ｛
ｘ３：＝ｘ１＋ｙ１；
ｘ４：＝２＊ｘ３；
ｘ５：＝ｘ４；
｝
【０１９１】
ここで、ｘ５は、２つのブロックを同期させる働きをする。ｘが現れるたびにそれを異なるイミュータブルに取り替えた。各段階において、ｘは、あるイミュータブルの出現に関連付けられる。各イミュータブルがパラメータ化ＭＰＣＴｙｐｅであることから、各ｘｉは、特定のパラメータおよびマスキングデータを持つようになる。ｘが、ｉｆに対しても、ｔｈｅｎブロックに対しても局所的ではないことから、イミュータブルｘ２とｘ４とは、条件ブロックの後に同期される必要がある。これは、コンパイラに、それらのブロックのいずれかの結果をコピーするｘに対応する臨時の補助イミュータブルｘ５を作り出すことを要求する。
【０１９２】
すべての場合で、ブール条件の値は、オンライン段階中に公に明かされるが、コンパイラの視点から見ると、２つのケースが、公開中に起こる可能性がある。
●条件が、コンパイラに知られている即値ブールであり、この場合、コンパイラが、計算済みブール値に応じて、ｔｈｅｎブロック、またはｅｌｓｅブロックを生成する。
●条件は、コンパイル時には知られていないデータによって決まってくる。この場合、コンパイラは、ｔｈｅｎブロックおよびｅｌｓｅブロックの両方用のコードを生成し、両ブロック間でイミュータブルインデックスを同期させる。オンライン段階中、ブール条件値が公に明かされ、実行がｔｈｅｎに飛ぶか、またはｅｌｓｅが始まる。コンパイラは、その条件のブール値のみを明かし、このブールを計算するための中間ステップは明かさず、例えば、この条件がｙ＜３であれば、プライバシ保護様式で、比較が評価される（ｙは秘密のまま）。ｙの値が理に適っていない場合、ユーザは、ｙの値を公に明かした後、公開比較を行うｒｅｖｅａｌ（ｙ）＜３を書き込むことによって、成果を挙げることができる。
【０１９３】
一実施形態において、コンパイラが、公開条件を即値に解決する場合、それのｂｒｅａｋｉｆコードが完全に省かれると言った、副作用を公開条件に含めることはできない。例えば、
ｂｏｏｌｅａｎ  ｗｅｉｒｄｏｓ（ａｕｔｏ＆ｘ）｛
ｘ＝ｘ＋１；  
ｒｅｔｕｒｎ  ｔｒｕｅ；
｝
．．．
ｉｆ（ｗｅｉｒｄｏｓ（ｘ））｛
／＊ｉｎｓｔｒｕｃｔｉｏｎｓ＊／
｝
【０１９４】
１．８  Ｐｕｂｌｉｃ  Ｂｏｕｎｄｅｄ  ｆｏｒ  Ｌｏｏｐｓ
一実施形態において、ｐｕｂｌｉｃ  ｂｏｕｎｄｅｄ  ＭＰＣ  ｆｏｒ  ｌｏｏｐは、以下の構成である：
ｆｏｒ  （ｉ  ｉｎ  ｒａｎｇｅ  （０，１０））｛
／＊ｙｏｕｒ  ｃｏｄｅ  ｈｅｒｅ＊／
ｂｒｅａｋｉｆ  ｃｏｎｄｉｔｉｏｎ；／／ｏｐｔｉｏｎａｌ  ｐｕｂｌｉｃ  ｂｒｅａｋ  ｃｏｎｄｉｔｉｏｎ，ｉｎ  ｔｈｅ  ｅｎｄ
｝
一実施形態において、コンパイラが、公開条件を即値に解決する場合、それのｂｒｅａｋｉｆコードが完全に省かれると言った、副作用を公開条件に含めることはできない。例えば、
ｂｏｏｌｅａｎ  ｗｅｉｒｄｏｓ（ａｕｔｏ＆ｘ）｛
ｘ＝ｘ＋１；
ｒｅｔｕｒｎ  ｆａｌｓｅ；
｝
．．．
Ｆｏｒ（ｉ  ｉｎ  ｒａｎｇｅ（０，５））｛
ｂｒｅａｋｉｆ  ｗｅｉｒｄｏｓ（ｘ）；
｝
再び、コンパイラは、すべての実行に対するコードを連続して生成し、ｂｒｅａｋｉｆ条件を反復のたびに評価しようとする。この条件のうちの１つが、ｉｍｍｅｄｉａｔｅ  ｔｒｕｅである場合、ｆｏｒ  ｌｏｏｐが、反復するたびに必ず中断するという、警告が発せられる。すべての条件がｉｍｍｅｄｉａｔｅ  ｆａｌｓｅである場合（または、ｂｒｅａｋｉｆがない場合）、すべてのブロックのコードが連続して生成される。その他に、コンパイラは、すべてのアクセス可能な反復に対するコードを生成し、ｎｏｎ−ｉｍｍｅｄｉａｔｅ条件が終わるたびに各変数を同期させる。ｐｕｂｌｉｃ  ｉｆ−ｔｈｅｎ−ｅｌｓｅ構造の場合と全く同じように、ここでも、何回ループしたかに従って、変数を同期させる必要がある。
【０１９５】
２  ＤＳＬ、中間言語および機械語
図１４は、一実施形態によるコンパイルを行うための方法を示す。コンパイルプロセスを行うためには、コンパイラが、まず、ＤＳＬコードを、様々な種類の確認を行い、変数をイミュータブルに置き換えるとともに、ｂｏｕｎｄｅｄ  ｆｏｒ  ｌｏｏｐ、ｐｕｂｌｉｃ  ｉｆ−ｔｈｅｎ−ｅｌｓｅ、関数、および関数呼び出しを解決する、即値表現に変換する。２つの即値表現：即値表現１（ＩＲ１）と即値表現２（ＩＲ２）がある。抽象構文木（ＡＳＴ）は、意味解析および型確認の第１の段階を行うことによってＩＲ１に変換されるが、まだ、この段階では、イミュータブルに解決される変数はない。ここで、部分的な型が確定されるが、完全な型は、まだ実証されない（統計的型パラメータは、この段階ではまだ計算されない）。次に、変数をイミュータブルに取り替え、ｆｏｒ  ｌｏｏｐを公開して同期させ、ｉｆ−ｔｈｅｎ−ｅｌｓｅ文を同期させ、関数呼び出しを公開し、そして最も重要なことには、統計的型パラメータを計算することにより完全な型を確定することによって、表現ＩＲ１がＩＲ２に変換される。後者は、ユーザ入力パラメータおよび／またはコンパイラの統計電卓によって成し遂げられる。
【０１９６】
２．１  ＤＳＬ文法定義
ＤＳＬ文法は、文（これは、ブロック、ｉｆ−ｔｈｅｎ−ｅｌｓｅ、ｂｏｕｎｄｅｄ  ｆｏｒ、関数本体、代入などを含む）および式を含むようになる。文とは違って、式は、評価され得る。式は、特殊な式である算術式を含む。
【０１９７】
２．２  中間表現１（ＩＲ１）
中間表現１（ＩＲ１）は、ＤＳＬの部分的な意味解析の結果である中間言語である。考え方としては、意味解析が二段階で行われ、１つは、変数導出および型パラメータ計算の前の段階（意味段階１、すなわちＳＰ１）であり、もう１つは、変数がイミュータブルに取り替えられ、完全な型が、型パラメータを推定することによって決定される段階（意味段階２、すなわちＳＰ２）である。二段階に分ける一番の理由は、ＩＲ１（ＳＰ１の結果）が、直列化可能になり、したがって、ＩＲ１においてプリコンパイル済みライブラリを定義することができる点である。ＩＲ２以外は、入力データの統計値によって決まってくるので、予めコンパイルすることができない（したがって、これが、意味解析をＳＰ１とＳＰ２とに分ける理由である）。
【０１９８】
中間言語ＩＲ１は、独自の抽象構文木（ＡＳＴ−ＩＲ１）を有する。この時点では、変数は、まだイミュータブルに取り替えられておらず、まだ、ＩＲ１は、以下のコンプライヤ特性およびコンプライヤ確認を遂行する。
●一連の標準演算子が式に取って代わる：
ｒｅｓ＝ａ＋ｂ＊ｃ；
／＊ｒｅｐｌａｃｅｄ  ｂｙ＊／  
ｔｍｐ＝ｂ＊ｃ；
ｒｅｓ＝ａ＋ｔｍｐ；
／＊ｏｒ＊／
ｒｅｓ＝ｆｏｏ（ｕ＋ｖ＊ｔ，ｂａｒ（ｗ））
／＊ｒｅｐｌａｃｅｄ  ｂｙ＊／
ｔ１＝ｖ＊ｔ；
ｔ２＝ｕ＋ｔ１；
ｔ３＝ｂａｒ（ｗ）；
ｒｅｓ＝ｆｏｏ（ｔ２，ｔ３）；
●この時点で、未宣言変数が報告される。
●戻り値のないｎｏｎ−ｖｏｉｄ関数またはその逆
ＭＰＣＲｅａｌ  ｆｏｏ（ＭＰＣＲｅａｌ  ｕ，  ＭＰＣＲｅａｌ  ｖ）｛
ＭＰＣＲｅａｌ  ｒ＝ｕ＋ｖ；
｝
●部分的な型チェックエラーが報告される−例えば：
ＭＰＣＲｅａｌ  ｒ；
ＭＰＣＭａｔｒｉｘ  Ｍ；
ＭＰＣＲｅａｌ  ｒｅｓ＝ｒ＋Ｍ；
●ｂｏｕｎｄｅｄ  ｆｏｒ  ｌｏｏｐｓにおけるｂｒｅａｋｉｆ文を解決する：
ｓ＝０；
ｆｏｒ  ｉ  ｉｎ  ｒａｎｇｅ（０，１０）｛
ｓ＝ｓ＋ｉ；
ｂｒｅａｋｉｆ（ｓ＞＝１０）；
｝
代替として、完全な型を確定した後のＳＰ２用に後者を取っておくことができる。演算子レベル節に焦点を絞り（例えば、代入および戻り値が部分的に導出される）、変数名の部分的な導出を行い、まだ、関数定義および関数呼び出しをそのままにしておく。
【０１９９】
２．３  中間表現２（ＩＲ２）
中間表現２（ＩＲ２）は、最終コンパイル済みプログラムで、ほとんど全単射で、コンパイルされ、公開されたプログラムである。この表現では、すべてのｌｏｏｐおよび関数呼び出しが公開され、即値定数が実行全体にわたって伝播され、すべての変数が、その型が完全修飾されているイミュータブルとして完全に解決される。同じことが、三つ組およびマスキングデータにも言える。結果として、関数定義節はもうなくなり、すべての関数呼び出しが単一のツリーとして展開される（関数呼び出しは、もう葉ではなく、内部節である）。ユーザに報告する考えられるエラー：
●再帰エラーが検出され、このステップにおいて報告される（スタックオーバーフロー）
●型エラー（または、関連パラメータを見付けることが不可能）。
プライバシ保護計算プロトコルのオフライン段階で使用される補助数字マスキングデータ（三つ組）の観点から、この表現は、以下を含む：
●補助データの大域インデックス
●完全修飾ＭＰＣ型。
以下を含むイミュータブルも完全修飾される：
●イミュータブルの大域インデックス
●完全修飾ＭＰＣ型（統計的型パラメータを含む）。
【０２００】
３  コンパイル段階
一実施形態において、コンパイル方法には、以下の段階がある：
●字句解析
●意味解析／パーシング＝＞ＡＳＴ生成
●意味解析段階１（ＳＰ１）ＡＳＴ＝＞ＩＲ１
●意味解析段階２（ＳＰ２）ＩＲ１＝＞ＩＲ２
これらの段階のそれぞれについて、以下に詳しく説明する。
【０２０１】
３．１  字句解析段階およびパーシング段階
これらの段階は、ごく標準的なものであり、使用されているプライバシ保護方法とは無関係である。字句アナライザは、ソースコードを走査し、語彙素（トークン）を生み出す。次に、このトークンが、ＤＳＬ文法用の規則の正確な記述を使用して、抽象構文木（ＡＳＴ）を作り出すようにパーサに渡される。トークンの範疇には、例えば、識別子、キーワード、リテラル、演算子、区切り文字を含めることができる。
【０２０２】
３．２  意味段階１（ＳＰ１）
この意味解析段階は、プライバシ保護計算方法に極めて特有である。
【０２０３】
３．２．１  深さ優先探索走査法
ＳＰ１用の主要方法では、グラフＡＳＴ上で深さ優先探索（ＤＦＳ：Ｄｅｐｔｈ−Ｆｉｒｓｔ−Ｓｅａｒｃｈ）を行なう。この考え方としては、ＡＳＴを走査するＤＦＳによって、ＡＳＴ−ＩＲ１節を確定し、これらの節のそれぞれに対し、ノードコンテキスト（この定義については次節を参照）をポピュレートできる、ということである。この手法により、未宣言変数または互換性のない部分的な型を検出することができるか、またはｎｏｎ−ｖｏｉｄ関数が互換性のない型を戻すか否かを検出することができる。
【０２０４】
３．２．２  算術式の単調化
ＤＦＳ走査法の最中、単調化算術式も必要になる（後者は、ＤＳＬ文法の意味に取られる）。例えば：
ｒｅｓ＝ｕ＋ｆｏｏ（ｖ＊ｗ）；
以下へ解決する必要がある
ｔｍｐ１＝ｖ＊ｗ；
ｔｍｐ２＝ｆｏｏ（ｔｍｐ１）；
ｒｅｓ＝ｕ＋ｔｍｐ２；
スロットの利点としては、すべての補助変数に対し識別子を導入する必要がなく、むしろ、該当するスロットに単調化式の根を挿入するだけで済む点である、ということに留意されたい。したがって、入力として算術式（ＡＳＴの節としての）を取り、スロット形式において単調化式を出力する、再帰的手続きを考察する。
【０２０５】
３．２．３  ノードコンテキスト（一時的シンボル表）
このシンボル表は、単に一時的なものであり、ＡＳＴ−ＩＲ１を生成するのに使用される。この一時的な表の表現は、前後関係を各節に対応付ける（ノードコンテキスト）。この前後関係は、所与の節に対応するすべての宣言およびスロットを含む。ＡＳＴ−ＩＲ１グラフの各節は、この節に対するすべての変数宣言と、その変数の（部分的な）型とを含むノードコンテキストを有するようになる。変数が宣言されているかどうかを確認するために、その節から根に走査し、各節の環境を確認する。これは、優先度が高い宣言の最初の出現である。例えば：
ｖｏｉｄ  ｍａｉｎ（）｛
／＊ｂｌｏｃｋ  ｃｏｒｒｅｓｐｏｎｄｉｎｇ  ｔｏ  ｎｏｄｅ１＊／
ＭＰＣＲｅａｌ  ｒ＝１；
／＊ｕ  ｉｓ  ｄｅｃｌａｒｅｄ  ａｌｒｅａｄｙ  ｉｎ  ｔｈｉｓ  ｃｏｎｔｅｘｔ＊／
｛
／＊ｂｌｏｃｋ  ｃｏｒｒｅｓｐｏｎｄｉｎｇ  ｔｏ  ｎｏｄｅ２＊／
ＭＰＣＲｅａｌ  ｒ＝０；
｛
／＊ｂｌｏｃｋ  ｃｏｒｒｅｓｐｏｎｄｉｎｇ  ｔｏ  ｎｏｄｅ３＊／
ｒ＋＝ｕ；
｝
｝
｝
この例では、変数ｒは、主機能のブロック（節１）において定義され、次に子ブロック（節２）において再定義される。最も内側のブロック（節３）には代入がある。ＳＰ１の最中、コンパイラが、最初に、節２である節３の親の前後関係を確認し、次にｒの宣言および代入があることを検出する。この宣言／代入に対応するスロットは、節２のノードコンテキストに、それまでには現れている（ＡＳＴを走査するのに使用される深さ優先探索法のせいで）。
【０２０６】
３．３  意味段階２（ＳＰ２）
この意味解析段階は、プライバシ保護計算方法に極めて特有である。
【０２０７】
３．３．１  即値の伝播
この方法でこれまでに使用されているイミュータブルのすべてのその時のインデックスを保ち、この意味段階を２回通過する。
１回目の通過（ＡＳＴ深さ優先探索）
●即値の伝播
●関数の公開
●ｂｏｕｎｄｅｄ  ｆｏｒ文の公開
●ｐｕｂｌｉｃ  ｉｆ−ｔｈｅｎ−ｅｌｓｅ文の公開
●変数をイミュータブルで解決する（ｉｆ−ｔｈｅｎ−ｅｌｓｅ、ｂｏｕｎｄｅｄ  ｆｏｒ  およびｒｅｔｕｒｎの文を同期させる）
２回目の通過
●  統計電卓を作動させ、イミュータブルの完全な型を確定する
【０２０８】
３．３．２  解決済み文
解決済み文は、関数呼び出しが解決され（ブロックに取って代わられる）、変数が、イミュータブルに取って代わられ、変数連結がポピュレートされている（変数からイミュータブルへの写像、またその逆の写像）文である。解決済み文は、ツリー形式である可能性があるが、最終コンパイル済みプログラムは、一連の命令にすぎない。
【０２０９】
３．３．３  統計電卓
さらに、型が確認され、型パラメータが、統計電卓と呼ばれる、コンパイラの特殊な構成要素によって計算された。この構成要素の主機能は、すべての命令を連続して受け、その命令に対する入力変数の型パラメータが設定されているとの前提で、出力変数に対する型パラメータを計算することである。仮想マシンの命令が、陽数学関数に対応しているので、コンパイラは、出力の統計分布を計算することができ、それにより、完全な型を推定することができる（それらがユーザによって規定されていない限り）。
【０２１０】
４  本節の用語解説
以下は、本節ＩＩＩに使用されている用語の解説である。ここでの説明は、単に、読み手が開示された実施形態を理解しやすいようにとの目的で提供し、請求項に係る発明に制限を設けるものではない。
ＡＳＴ１：ＤＳＬから直接生み出された抽象構文木
ＡＳＴ２：算術式がＭＰＣ最適化されているＡＳＴ１から導出された抽象構文木（初めは、ＡＳＴ１とＡＳＴ２とが同じものであると想定する）。
ＡＳＴ−ＩＲ１：中間言語１（ＩＬ１）に対応している抽象構文木
ブロック：スコープを定義するのに使用される基本文
式：評価され得る文法構造
ＩＲ１：中間表現１
ＩＲ２：中間表現２
イミュータブル：特定の変数の１回の代入（各変数は、対応するイミュータブル集合を持つことができる。）
スコープド変数：特定のブロック（スコープ）にしか見ることができない変数
意味段階１（ＳＰ１）：型パラメータおよびイミュータブルとは無関係な部分的な意味解析
意味段階２（ＳＰ２）：コンパイル済みプライバシ保護プログラムをもたらす完全な意味解析
文：文法構造（ブロック、ｉｆ−ｔｈｅｎ−ｅｌｓｅ、ｂｏｕｎｄｅｄ  ｆｏｒ  ｌｏｏｐ、関数本体など）
統計電卓：ＳＰ２において、命令を経て、型パラメータを推定するコンパイラ構成要素
【０２１１】
ＶＩ．コンピュータ実装形態
本明細書に開示されている実施形態の構成要素は、方法、プロセス、アプリケーション、プログラム、モジュール、エンジン、機能などと呼ばれる場合があり、非一時的コンピュータ可読媒体に命令として具体化された専用ソフトウェアを使用して、１つ以上のコンピュータまたはコンピュータシステムを構成することによって実装され得る。１つ以上のコンピュータまたはコンピュータシステムは、ネットワーク化コンピュータシステムとしての有線ネットワークおよび／または無線ネットワークを通して、必要に応じてネットワーク化され得る、スタンドアローンコンピュータ、クライアントコンピュータおよび／またはサーバコンピュータとすることができるか、またはそれらを含むことができる。
【０２１２】
図１５は、様々な実施形態による、開示されている構成要素を実装するように適宜構成され得る一般的なコンピュータアーキテクチャ１５００を示す。コンピューティングアーキテクチャ１５００は、コンピュータ１５０１、ネットワーク１５１８、および１つ以上のリモートコンピュータ１５３０など、様々なよくあるコンピューティング要素を含み得る。ただし、本明細書に開示されている実施形態は、この一般的なコンピューティングアーキテクチャ１５００による実装に限られるものではない。
【０２１３】
図１５について言えば、コンピュータ１５０１は、例えば、サーバ、ディスクトップコンピュータ、ラップトップコンピュータ、タブレットコンピュータ、またはモバイルコンピューティングデバイスなど、様々な汎用コンピュータのいずれかとすることができる。コンピュータ１５０１は、処理ユニット１５０２、システムメモリ１５０４、およびシステムバス１５０６を含み得る。
【０２１４】
処理ユニット１５０２は、互いに独立して作動することができる、１つ以上の処理コアを含み得る様々な市販のコンピュータプロセッサのいずれかとすることができる。コンピュータには、グラフィックスプロセッシングユニット１５０３などの付加的共処理ユニットも備わっていることがある。
【０２１５】
システムメモリ１５０４は、動的ランダムアクセスメモリ（ＤＲＡＭ：Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）または他のランダムアクセスメモリ素子など、揮発性素子を含み得る。システムメモリ１５０４は、読み取り専用メモリまたはフラッシュメモリなど、不揮発性素子も含み得るか、または代替として、それらを含み得る。
【０２１６】
コンピュータ１５０１は、ディスクドライブ、ソリッドステートディスク、またはメモラブルメモリカードなど、ローカル不揮発性二次記憶域１５０８を含み得る。ローカル記憶域１５０８は、１つ以上のリムーバブル記憶ユニットおよび／または非リムーバブル記憶ユニットを含み得る。ローカル記憶域１５０８は、コンピュータ上で実行する様々なアプリケーションを起動し、管理するオペレーティングシステムを格納するのに使用され得る。ローカル記憶域１５０８は、本明細書に開示されている実施形態の構成要素を実装するように構成され、またオペレーティングシステム下で１つ以上のアプリケーションとして実行され得る、専用ソフトウェアを格納するのにも使用され得る。
【０２１７】
コンピュータ１５０１は、通信デバイス１５１２も含み得、この通信デバイス１５１２を通して、コンピュータ１５０１は、有線および／または無線のコンピュータネットワーク１５１８上で、１つ以上のリモートコンピュータ１５３０などの他のデバイスと通信する。通信デバイス１５１２は、例えば、有線コンピュータネットワーク上でデータを伝達するためのネットワークインタフェースを含み得る。通信デバイス１５１２は、例えば、Ｗｉ−Ｆｉ、Ｂｌｕｅｔｏｏｔｈ（登録商標）、および／または移動電話網上の通信向けの１つ以上の無線送信機を含み得る。
【０２１８】
コンピュータ１５０１は、コンピュータネットワーク１５１８を通してネットワーク記憶域１５２０にアクセスすることもできる。ネットワーク記憶域は、例えば、ローカルネットワークに位置するネットワークアタッチドストレージ素子、または１つ以上のリモートデータセンタでホストされるクラウドベース記憶域を含み得る。オペレーティングシステムおよび／または専用ソフトウェアは、代替として、ネットワーク記憶域１５２０に格納され得る。
【０２１９】
コンピュータ１５０１は、キーボード、マウス、タッチスクリーン、カメラ、マイク、加速度計、温度計、磁気計、または任意の他のセンサなど、様々な入力デバイス１５１４を備え得る。ディスプレイ、スピーカ、プリンタ、偏心回転質量振動モータなどの出力デバイス１５１６も含まれ得る。
【０２２０】
様々な記憶域１５０８、通信デバイス１５１２、出力デバイス１５１６、および入力デバイス１５１４は、コンピュータのハウジング内に統合され得るか、またはコンピュータ上の様々な入力／出力インタフェースデバイスを通して接続され得、この場合、整理番号１５０８、１５１２、１５１４、および１５１６は、場合によって、デバイスへの接続用のインタフェースを示すか、またはデバイスそのものを示すことがある。
【０２２１】
以上の態様のいずれも、コンピュータシステムとして、このようなコンピュータシステムによって行われるプロセスとして、このようなコンピュータシステムのいずれかの個々の構成要素として、または、コンピュータプログラム命令が格納されるコンピュータ記録域を含む製造品として、１つ以上のインスタンスにおいて具体化され得、コンピュータプログラム命令は、１つ以上のコンピュータによって処理されると、このようなコンピュータシステムまたはこのようなコンピュータシステムのいずれかの個々の構成要素を提供するように、１つ以上のコンピュータを構成する。サーバ、コンピュータサーバ、ホスト、またはクライアントデバイスはそれぞれ、コンピュータまたはコンピュータシステムとして具体化され得る。コンピュータシステムは、通信ネットワークを通してつなげられる複数のコンピュータによって作業が行われる、分散型コンピューティング環境において実施され得る。分散型コンピューティング環境では、コンピュータプログラムは、ローカルおよびリモート両方のコンピュータ記憶媒体に置かれ得る。
【０２２２】
本明細書に記載したものなどの、また１つ以上のコンピュータ上で働く、コンピュータシステムの各構成要素は、コンピュータの１つ以上の処理ユニットと、１つ以上の処理ユニットによって処理される１つ以上のコンピュータプログラムとを使用して実装され得る。コンピュータプログラムは、命令がコンピュータ内の１つ以上の処理ユニットによって処理される、プログラムモジュールなどのコンピュータ実行可能命令および／またはコンピュータ解釈式命令を含む。通常、このような命令は、処理ユニットによって処理されると、処理ユニットに、データに対して作業を行うように命令するか、または、様々な構成要素もしくはデータ構造を実装するようにプロセッサまたはコンピュータを構成する、ルーチン、プログラム、オブジェクト、構成要素、データ構造などを定義する。
【０２２３】
モジュール、エンジン、プロセス、機能などと呼ばれることがある本明細書に開示されている実施形態の構成要素は、例えば、専用ハードウェアロジックコンポーネントを使用することによって、専用ソフトウェアを用いて汎用コンピューティングリソースを構成することによって、または、専用ハードウェアと構成済み汎用コンピューティングリソースとの組合せによって、ハードウェアにおいて実装され得る。使用され得る図示の種類のハードウェアロジックコンポーネントは、例えば、フィールドプログラマブルゲートアレイ（ＦＰＧＡ：Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）、特定用途向け集積回路（ＡＳＩＣ：Ａｐｐｌｉｃａｔｉｏｎ−Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、特定用途向け標準製品（ＡＳＳＰ：Ａｐｐｌｉｃａｔｉｏｎ−Ｓｐｅｃｉｆｉｃ  Ｓｔａｎｄａｒｄ  Ｐｒｏｄｕｃｔ）、システムオンチップシステム（ＳＯＣ：Ｓｙｓｔｅｍ−ｏｎ−ａ−ｃｈｉｐ  ｓｙｓｔｅｍ）、および複雑なプログラマブルロジックデバイス（ＣＰＬＤ：Ｃｏｍｐｌｅｘ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｌｏｇｉｃ  Ｄｅｖｉｃｅ）を含む。
【０２２４】
Ｖ．  結論
特定の実施形態に関して本発明の対象を説明したが、当業者には、本明細書に示されている様々な特徴および利点を提供することもしないこともある実施形態を含む他の実施形態が、上記の開示に照らして見えてくるであろう。上記の具体的な実施形態は、単に例として開示され、本特許の主題の範囲は、以下の特許請求の範囲によって規定される。
【０２２５】
特許請求の範囲では、「ｂａｓｅｄ  ｕｐｏｎ（〜に基づく）」という用語は、結果または影響をもたらす際、直接かつ／または間接的に、また場合によっては他の要因と合わせて、ある要因が考慮されるという状況を含むものとする。特許請求の範囲では、一部分というのは、あるもののうちの１つもないよりも大きく、あるものの全部までを含むもととし、あるものの暗号化は、そのものの一部分の暗号化を含むものとする。特許請求の範囲では、いずれの参照文字も単に説明の便宜上使用され、方法を行う際の特定の順番を示すものではない。
【図１】
2020532771.tif 000161
【図２】
2020532771.tif 000162
【図３】
2020532771.tif 000163
【図４】
2020532771.tif 000164
【図５】
2020532771.tif 000165
【図６】
2020532771.tif 000166
【図７】
2020532771.tif 000167
【図８】
2020532771.tif 000168
【図９】
2020532771.tif 000169
【図１０】
2020532771.tif 000170
【図１１】
2020532771.tif 000171
【図１２】
2020532771.tif 000172
【図１３】
2020532771.tif 000173
【図１４】
2020532771.tif 000174
【図１５】
2020532771.tif 000175
【図１６】
2020532771.tif 000176
【手続補正書】
【提出日】令和2年5月25日(2020.5.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
個々のパーティによって与えられた入力データのプライバシを保護しながら、セキュアマルチパーティ計算を行って、結果を出すための方法であって、前記方法が、
ディーラコンピューティングシステムが、複数の関連数字マスキングデータ成分セットを作り出すことであって、関連数字マスキングデータ成分セットごとに、前記セットの各成分が、スカラ、ベクトル、および行列のうちの１つである、作り出すことと、
前記ディーラコンピューティングシステムが、複数のパーティコンピューティングシステム間で、前記複数の関連数字マスキングデータ成分セットの各セットの各成分を秘密分散させることと、
前記複数のパーティコンピューティングシステムのパーティコンピューティングシステムごとに、前記パーティコンピューティングシステムが、
前記ディーラコンピューティングシステムから、前記複数の数字マスキングデータ成分セットの各セットの各成分のそれぞれの秘密シェアを受信し、少なくとも１つの入力データセットに対し、前記入力データセットの秘密シェアを受信することと、
前記パーティコンピューティングシステムに、１つ以上のマルチパーティ計算を行わせて、計算済み秘密分散型データの１つ以上のインスタンスを作り出させる、プログラム命令セットを実行することであって、インスタンスごとに、各パーティコンピューティングシステムが、入力データセットの少なくとも１つの秘密シェアか、または計算済み秘密分散型データの別のインスタンスの少なくとも１つの秘密シェアに基づき、前記インスタンスの秘密シェアを計算し、数字マスキングデータ成分の受信した秘密シェアが、前記計算中に伝えられたデータをマスクするのに使用され、前記計算が、
（ａ）複数の確定済みフーリエ級数から、前記入力データセットか、または計算済み秘密分散型データの前記別のインスタンスに基づき、選択されたフーリエ級数を使用して連続関数の値を近似することであって、前記複数の確定済みフーリエ級数の各々が、前記連続関数の定義域の対応する部分区間に対して前記連続関数を近似するように構成されている、近似すること、
（ｂ）計算され、浮動小数点表示で格納された秘密分散型データのインスタンスを、計算済み秘密分散型データの同等な、同等に正確で、かつ同等にセキュアなインスタンスに変換する秘密シェア縮小であって、前記変換は、少なくとも、
前記複数のコンピューティングシステムの各パーティコンピューティングシステムが、
所定の切り捨て位置を越える秘密シェアの最上位桁集合を選択し、
前記切り捨て位置までに、前記秘密シェアの最下位桁集合を保持し、
前記複数のコンピューティングシステムにわたって、選択した最上位桁集合で表される値の和を確定し、かつ
前記複数のパーティコンピューティングシステムの前記秘密シェアの保持した最下位桁集合にわたって、確定した和を分配することによって、行われる、秘密シェア縮小、および
（ｃ）前記入力データセットか、または計算済み秘密分散型データの前記別のインスタンスに対して、フーリエ級数評価の秘密シェアを確定することであって、少なくとも、
前記入力データセット、または計算済み秘密分散型データの前記別のインスタンスの秘密シェアを、数字マスキングデータ成分の前記秘密シェアでマスクし、
マスク済み秘密シェアに相当する値を確定して、明かし、
前記マスク済み秘密シェアに相当する確定値に基づき、フーリエ級数基底評価の値を計算し、かつ
前記フーリエ級数基底関数の計算値、および数字マスキングデータ成分の前記秘密シェアに基づき、前記フーリエ級数評価の前記秘密シェアを計算すること、によって行われる、確定することと、のうちの少なくとも１つを含む、実行することと、
前記複数のパーティコンピューティングシステムのパーティコンピューティングシステムごとに、前記パーティコンピューティングシステムが、前記複数のパーティコンピューティングシステムのうちの１つ以上の他のシステムに、計算済み秘密分散型データのインスタンスの秘密シェアを送信することと、
前記複数のパーティコンピューティングシステムの少なくとも１つのパーティコンピューティングシステムでは、前記パーティコンピューティングシステムが、
前記複数のパーティコンピューティングシステムのうちの１つ以上の他のシステムから、計算済み秘密分散型データのインスタンスの１つ以上の秘密シェアを受信し、かつ
計算済み秘密分散型データの前記インスタンスの前記受信した秘密シェアを結合して、前記結果を出すことと、を含む、方法。
【請求項２】
前記計算が、（ａ）および（ｂ）を含む、請求項１に記載の方法。
【請求項３】
前記計算が、（ａ）を含む、請求項１に記載の方法。
【請求項４】
前記連続関数の定義域の一部分を複数の部分区間に分割することと、
前記複数の部分区間の部分区間ごとに、
前記部分区間において前記関数のフーリエ級数近似値を確定することと、をさらに含む、請求項３に記載の方法。
【請求項５】
前記マルチパーティ計算が、ガーブル化回路および紛失選択のうちの少なくとも１つを使用して、対応する部分区間を選択することをさらに含む、請求項３に記載の方法。
【請求項６】
前記近似値が、前記連続関数の一様近似値である、請求項３に記載の方法。
【請求項７】
前記連続関数が、機械学習活性化関数である、請求項３に記載の方法。
【請求項８】
前記機械学習活性化関数が、シグモイド関数である、請求項７に記載の方法。
【請求項９】
前記機械学習活性化関数が、双曲線正接関数である、請求項７に記載の方法。
【請求項１０】
前記機械学習活性化関数が、ニューラルネットワーク向けの整流器活性化関数である、請求項７に記載の方法。
【請求項１１】
前記連続関数が、前記シグモイド関数である、請求項３に記載の方法。
【請求項１２】
前記計算が、（ｂ）を含む、請求項１に記載の方法。
【請求項１３】
前記複数のコンピューティングシステムにわたって前記選択した最上位桁集合に相当する値の和を確定することが、
前記和がゼロになる数字マスキングデータ成分セットを確定することと、
前記パーティコンピューティングシステムの各々に、確定済みセットの１つの項を分配することと、
各パーティコンピューティングシステムが、前記確定済みセットのそれぞれの項を受信することと、
各パーティコンピューティングシステムが、受信した項を、その秘密シェアのその選択した最上位桁集合に加え、マスク済み最上位桁集合を得ることと、
前記マスク済み最上位集合を合計することと、を含む、請求項１２に記載の方法。
【請求項１４】
前記結果が、ロジスティック回帰分類モデルの係数集合である、請求項１に記載の方法。
【請求項１５】
前記方法が、ロジスティック回帰分類器を実装し、前記結果が、前記入力データに基づく前記ロジスティック回帰分類器の予測である、請求項１に記載の方法。
【請求項１６】
前記ディーラコンピューティングシステムが、信頼できるディーラコンピューティングシステムであり、前記パーティコンピューティングシステム間の通信が、前記信頼できるディーラコンピューティングシステムにはアクセス不能である、請求項１に記載の方法。
【請求項１７】
前記ディーラコンピューティングシステムが、ｈｏｎｅｓｔ−ｂｕｔ−ｃｕｒｉｏｕｓディーラコンピューティングシステムであり、前記パーティコンピューティングシステム間の通信が前記ｈｏｎｅｓｔ−ｂｕｔ−ｃｕｒｉｏｕｓディーラコンピューティングシステムによってアクセスされ得るか否かに関わらず、前記パーティコンピューティングシステムのうちの１つ以上によって与えられた秘密分散型入力データのプライバシが保護される、請求項１に記載の方法。
【請求項１８】
少なくとも１つの入力データセットに対し、前記入力データセットにおいて統計解析を行って、入力データセット統計値を確定することと、
前記入力データセット統計値を使用して、ソースコード命令セットの事前実行を行い、１つ以上の変数型の各々に対して統計的型パラメータを生成することと、
統計的型パラメータ集合に基づいて、前記ソースコード命令セットをコンパイルして、前記プログラム命令セットを生成することと、をさらに含む、請求項１に記載の方法。
【請求項１９】
前記事前実行が、
反復回数が確定可能である前記ソースコード命令セットにおいてｌｏｏｐを公開することと、
前記ソースコード命令セットにおいて関数呼び出しを公開することと、に続いて行われる、請求項１８に記載の方法。
【請求項２０】
少なくとも１つの関連数字マスキングデータ成分セットが、３つの成分から成り、前記３つの成分が、前記成分のうちの１つが前記成分のうちの残りの２つの乗算積に等しいという関係性を有する、請求項１に記載の方法。
【請求項２１】
少なくとも１つの関連数字マスキングデータ成分セットが、数字と、前記数字に対して評価されたフーリエ基底関数の１つ以上の対応値集合と、を含む、請求項１に記載の方法。
【請求項２２】
前記計算が、（ｃ）を含む、請求項１に記載の方法。
【請求項２３】
前記フーリエ級数評価の前記秘密シェアを前記計算することが、式に基づき行われ、
2020532771.tif 000177
式中、ｘは、前記入力データセット、または計算済み秘密分散型データの前記別のインスタンスを表し、λは前記マスキングデータを表し、ｍは整数を表し、記号
2020532771.tif 000178
は、個数ｎの加法的秘密シェアを示し、前記記号
2020532771.tif 000179
は、２πを法とする加法を示す、請求項２２に記載の方法。
【請求項２４】
前記計算が、（ａ）（ｂ）、および（ｃ）を含む、請求項１に記載の方法。
【請求項２５】
前記計算が、（ａ）および（ｃ）を含む、請求項１に記載の方法。
【請求項２６】
前記結果が、前記結果の平文計算に関して所定の精度を有する、請求項１〜２５のいずれか一項に記載の方法。
【請求項２７】
前記複数のパーティコンピューティングシステムのうちの少なくとも１つが、前記複数のパーティコンピューティングシステム間で、それぞれの入力データセットを秘密分散させることをさらに含む、請求項１〜２５のいずれか一項に記載の方法。
【請求項２８】
複数のコンピューティングシステムを備えるシステムであって、前記複数のコンピューティングシステムが、請求項１〜２５のいずれか一項に記載の方法を行うように構成されている、システム。
【請求項２９】
請求項１〜２５のいずれか一項に記載のプログラム命令セットで符号化された非一時的コンピュータ可読媒体。
【請求項３０】
複数のコンピュータシステムによって実行されると、前記複数のコンピュータシステムに、請求項１〜２５のいずれか一項に記載の方法を行わせる、コンピュータコードで符号化された非一時的コンピュータ可読媒体。
【国際調査報告】
2020532771.tif 000180
2020532771.tif 000181
2020532771.tif 000182
2020532771.tif 000183