Big Data Processing with Compressed Secure Computation

・ソートアルゴリズムの通信量の削減ソート（データを小さい順に並び替える）はデータの処理において最も重要な処理と言ってよく，多くの計算の内部で使われる．本研究で開発したソートアルゴリズムは，基数ソート (radix sort) に基づいている．これは，数を2進数で表現した際に，まず最下位のビットに基づきソートを行い，次に下から2番目のビットに基づきソートし，というように桁ごとにソートを行うものである．これをそのまま実行すると W ビットの数のソートは W 回のラウンドを必要とする．これを高速化するには1回のラウンドで複数ビットを処理する必要がある．1回に L ビットに基づきソートを行えばラウンド数は W/L に削減される．しかし秘匿計算においては，複数ビットに基づくソートを行う際には問題が生じる．それは，1回のラウンドあたりの通信量が増大してしまうという点である．既存手法では，1ラウンドあたり O(2^L N log N) ビットのオンライン通信量が必要であったが，これを O(NL) ビットに削減した．・秘匿接尾辞ソーティング本研究では，入力文字列の全ての接尾辞をソートするアルゴリズムを開発した．通常の計算モデルでは，長さ n の文字列に対し線形（O(n)）時間で接尾辞をソートすることができるが，秘匿計算モデルでは効率的な（O(n^2） よりも高速な)アルゴリズムは存在しなかった．本研究では O(n log^2 n) 時間の秘匿計算アルゴリズムを与えた．ラウンド数は O(log^2 n), 通信量は O(n log^3 n) ビットである．このアルゴリズムは，平文計算における接尾辞ソートアルゴリズムの中でもダブリングという手法に基づくアルゴリズムを用いており，これは秘匿計算と親和性が高く，効率的なアルゴリズムの開発が可能となった．

・ソートアルゴリズムの通信量の削減ソート（データを小さい順に並び替える）はデータの処理において最も重要な処理と言ってよく，多くの計算の内部で使われる．本研究で開発したソートアルゴリズムは，基数ソート (radix sort) に基づいている．これは，数を2進数で表現した際に，まず最下位のビットに基づきソートを行い，次に下から2番目のビットに基づきソートし，というように桁ごとにソートを行うものである．これをそのまま実行すると W ビットの数のソートは W 回のラウンドを必要とする．これを高速化するには1回のラウンドで複数ビットを処理する必要がある．1回に L ビットに基づきソートを行えばラウンド数は W/L に削減される．しかし秘匿計算においては，複数ビットに基づくソートを行う際には問題が生じる．それは，1回のラウンドあたりの通信量が増大してしまうという点である．既存手法では，1ラウンドあたり O(2^L N log N) ビットのオンライン通信量が必要であったが，これを O(NL) ビットに削減した．・秘匿接尾辞ソーティング本研究では，入力文字列の全ての接尾辞をソートするアルゴリズムを開発した．通常の計算モデルでは，長さ n の文字列に対し線形（O(n)）時間で接尾辞をソートすることができるが，秘匿計算モデルでは効率的な（O(n^2） よりも高速な)アルゴリズムは存在しなかった．本研究では O(n log^2 n) 時間の秘匿計算アルゴリズムを与えた．ラウンド数は O(log^2 n), 通信量は O(n log^3 n) ビットである．このアルゴリズムは，平文計算における接尾辞ソートアルゴリズムの中でもダブリングという手法に基づくアルゴリズムを用いており，これは秘匿計算と親和性が高く，効率的なアルゴリズムの開発が可能となった．