📝
【技術】MPCにおける基数ソート(Oblivious Radix Sort)の解説
目次
はじめに
この記事では、MPC によるソートの一つである、 Oblivious Radix Sort プロトコルを紹介します。原論文は以下のリンクから閲覧できます。また以下の論文で提案されている手法を、論文での名前をそのまま使い、この記事では Oblivious Radix Sort プロトコルと呼ぶことにします。
秘密計算において、キーまたはテーブル(表)の値を明らかにせずにソートをしたい場面は多く存在します。例えば最大・最小値や中央値を求めたり、何番目に大きいかであったり、i 番目に大きい値を知りたい等、データを分析する上でソートをして様々な値を求めたい場面などです。
,
例えば、上の例でソートするキーのベクトルを 、テーブル(表)を行列にしたものを とした場合、キー または の1列目の値(=キー )に従って並び替えて、以下のように並び替えるような操作に相当します。
,
このような操作はソートと呼ばれ、クイックソートやマージソート等の従来のアルゴリズムで実装することが可能です。しかし、上記のような一般のソートアルゴリズムは比較演算を多用するため、MPC で実現するには非常に多くの計算コストがかかってしまいます。そのため、MPC による秘密計算では特別に専用のプロトコルを用意する必要があります。
Oblivious Radix Sort プロトコルは、MPC における高速なソートプロトコルの一つであり、多くの論文で引用されています。そこで、本記事では Oblivious Radix Sort の具体的なプロトコルについて解説していきます。
記法の説明
本記事で出てくる記法を説明します。
- はプロトコルに参加している主体を表します（今後はパーティと呼びます）。各パーティは互いにセキュアなチャネルで結ばれているとします。
- をシーケンス (キーやテーブルの行数)とし、 をパーティの数とします。
- は を法とした素体を表します。また、 を のビット長とします。
- と書いた場合、 を意味します。
- は、全パーティの集合を表します。
- パーティ が保有する秘密情報 のシェアを と表します。加法的秘密分散法またはシャミア秘密分散法の両方が使用可能です。
- 全てのパーティが持つ秘密情報 のシェアをまとめて表記する場合に、 と表します。 ということです。
- 以外の別の素体でシェア値を使用することがあり、 と書きます。これを明示的に示すために、 のように上付きの添字を括弧をつけて示します。
- 大文字太字 を行列、小文字太字 をベクトルとし、 を行列の 行 列目の要素、 をベクトルの 行目の要素とします。
- や を、行列 やベクトル に対するパーティ のシェア行列やシェアベクトルを指します。
Oblivious Radix Sortプロトコルの内容
Oblivious Radix Sort プロトコルは、比較演算プロトコル本体と、そのプロトコル内で使用されている6つのサブプロトコルから構成されています。まず、サブプロトコルについて説明し、その後本体のプロトコルについて説明します。
サブプロトコル
Oblivious Radix Sort プロトコルを実装するにあたり、以下の6つのサブプロトコルが必要となります。
- Bit-Decomposition
- Shuffling
- Bit-field-conversion
- Revealing
- Destination computation
- Reveal sort
以下、それぞれのサブプロトコルについて順に説明します。
Bit-Decomposition
各 から を入力し、ビット分解して、 を出力します。
このプロトコルを以下のように表記します。
これを行う具体的なアルゴリズムについては、以下の論文を参照してください。
ここの処理の目的は、ある与えられた値を2進数表現に変換することです。つまり、 の時 となるように分解します。
例えば、 だったとします。この時、 とした場合に、このサブプロトコル実行後にどうなるかを見てみます。
つまり、 のように分解されます。2進数表示であることを考えれば、15 までは で十分でした。
Shuffling
各 から、 を入力し、各 に を出力します。これは、均一でランダムな置換 により、 のようになっています。このプロトコルを以下のように表記します。
これを行う具体的なアルゴリズムについては、以下の論文を参照してください。
ここでは、いわゆるランダム置換と呼ばれるもので、ベクトルや行列の各行の要素をランダムに並べ替えると言う操作をします。
ソートする時にキーの要素を公開するため、入力データと出力結果の対応関係を秘匿したい場合に使用します。逆に言えば、秘匿しなくてもいい場合は不要です。
Bit-field-conversion
各 から素体 上のシェア を入力し、別の体 上のシェア を各 に出力します。このプロトコルを以下のように表記します。
具体的なアルゴリズムは以下の論文を参照してください。
このアルゴリズムは、基本的にオーバーフローを防ぐために使用します。オーバーフローが発生しないような、適切な値の空間を最初から選択している場合は、気にする必要はありません。
Revealing
各 から を入力し、各 に を出力します。このプロトコルは、マルチパーティ設定での公開アルゴリズムとして機能します。 このプロトコルの実行は、次のように示されます。
このサブプロトコルではシェアを復号しています。Reveal Sort にシェアを復号するステップがあるので使用します。
Destination computation
まず、準備としてベクトル に対して、
のような 行列 を作成します。そして、各 から を入力し、
のようにソートされるような を計算し、 を生成し、最後に各 に を出力します。このプロトコルの実行を以下のように表記します。
プロトコル
0. 各パーティは、キーのシェアベクトル から、 を作成する。
ここの手順については後述します。
となるような を計算する。
となるような を計算する。
を計算する。
- を出力する。
例を見た方がわかりやすいので例示します。例では本質を見るために復号されたものを追っていきますが、実際はシェアに対して同じ作業をすることになります。
0.
として、
のような行列を作ります。one-hot-encoding のような操作です。しかし、注意として、シェアのままこのような作業を行うには one-hot-encoding のようなMPC アルゴリズムが必要になります。
それを回避する為に、ビット分解し をバイナリにするというBit-Decomposition があります。もし、 がバイナリだとすると、
として、
とすればよく、これはよく見ると、1列目は の否定、2列目は そのままを入れることで作ることができます。シェアのまま否定をすることは容易ですから、本体のプロトコルではバイナリに対してのみ適用することになります。
1.
より、
を作成します。 を1列目、2列目、3列目と言う順番で列方向に合計していって、その要素時点での合計値が になります。
2.
を作成します。
これは、 と の要素同士の掛け算で作成します。if文でやっても構いません。
3.
を作成します。
これは、 を行ごとに足し算することで得ることができます。そして、この値が の要素が何番目に小さいかと言うことを示します。同じ値同士は上から順になります。
4. を出力して終わりです。実際には上記の作業を全てシェアのまま行いますので、 を各 に出力します。
Reveal Sort
各 から を入力し、 の要素を公開し、
のようにソートされ、 を生成します。最後に各 に を出力します。このプロトコルの実行を以下のように表します。
プロトコル
- Shuffling プロトコルで をランダム置換し、 を作成します。全てのシェア、 で同じ置換を適用してください。 このShufflingプロトコルは、入力データと出力結果の対応関係を秘匿したい場合に使用します。逆に言えば、秘匿しなくてもいい場合は不要です。
- Reveal プロトコルで全てのキーの要素を復号し、公開します。
- に従って、バケットソート(基数ソート)をします。つまり、 の要素ごとに箱を作り、その行に対応する や を放り込み、小さい要素から拾っていきます。
ここで、 をソートするような表記にはなっていますが、実際には Destination computation で作成する に対してこのアルゴリズムを主に実行します。
本体プロトコル
ここからは、本体のソートプロトコルについて説明します。
Oblivious Radix Sort プロトコルは、大まかに分けて以下の4つのステップで成立します。
- キー をBit-Decomposition プロトコルにより、ビット分解する。
- ビット分解したキー に対して、Destination Computation プロトコルで、各桁の大小の順番 を計算する。
- 基数ソートを実行する。
- 実行結果を出力する。
しかし、このアルゴリズムではただの基数ソートではなく、Oblivious Radix Sort と呼ばれるソートアルゴリズムが用いられているので、2.と3.のプロセスは各ビットについて同じループ内で実行されます。
主なアイデアとしては、掛け算や比較演算等の通信を必要とする計算をできるだけ回避してソートを実行することで高速なソートを実行します。
以下で詳しいステップについて解説していきます。
プロトコル
- まず、全てのパーティは s.t. であることと、 のビット長が であることに合意します。
- ここで、BIt-Decomposition プロトコルでキー をビット分解します。
- ここで、Bit-Field-Conversion でオーバーフローしないような値の空間になるようにします。オーバーフローしないという意味を込めて右上に がつきます。
- を作成します。このベクトルはポインタのように使用される元の位置を格納するベクトルです。
- ループの為に以下のような置き換えをします。 ここで注意して欲しいのは、 は何度も作るのでコピーです。他はポインタ変数でもいいです。
- 以下のステップからビット分解したビットごとについてループに入ります。
- を から作成。 Destination computationのところで行った操作をします。バイナリであるため否定で作成できます。
- Destination computationを実行します。
- Reveal Sortを使って、まず を に従って並び替えます。 は前のループでどのように並び替えられたかと言う情報が入ります。1ループ目は何も起きません。これを使って少し変わった基数ソートをします。
- と を準備します。 は常に をコピーして持ってきます。 はラストループで が入ることに注意してください。
- ここで、 は列ベクトル と を水平方向に結合させたものです。 つまり、 に従って、 を同時に並び替えます。
- つまり、ソートされた行列 を返します。
例示
実際に例示した方がわかりやすいと思うので例を使って例示します。
本来はシェアの状態で行われるプロトコルですが、本質を見る為に元の値で実行してみます。本来はもちろんシェアのまま同様の計算を行い、必要に応じて必要な部分を復号することになります。
,
で表現できそうなので、
2. Bit-Decomposition で3つのベクトルに分解します。
3. でBit-Field-Conversion で変換します。しかし、この例ではビット長の最大値を考えないこととするため不要です。実際にはシェアの値によってオーバーフローの可能性がありますので、その時は適宜設定する必要はあるでしょう。
4. で を作ります。元の位置を格納するベクトルです。ここでは元の値で表現してるので
となります。
5. でコピーを作成します。つまり、ループの為に置き換えをします。
6.1
ここでループに入ります。以下では1回目のループを追います。
7.1 で を作成します。一列目は の否定、二列目はそのまま です。 であることに注意してください。これは前のループで並び替えられています。
となります。
8.1
ここでは、を集計した行列が であり、 の要素同士をかけたものが となります。そして、行で集計したものが です。
,
9.1
ここでは、1ループ目は何もしません。 がキーになっている以上1ループ目は は並び替えられることはありません。今回は特に意味のない作業です。
10.1 と を準備します。
,
11.1
ここで、
なので、公開されたキー に従い並べ替えます。 は整列されたものになっていると思います。(特に使用はしません)
,
6.2 次のループ（）に入ります。
7.2 を作ります。 という並び替えられた後のものを使うことに注意してください。
(なお、今回は並び替えられませんでした)
8.2 を作成します。
,
9.2
だったはずなので、 に従って並び替えます。
10.2 と を準備します。
,
11.2
,
6.3 最後の3ループ目（）に入ります。
7.3 を作ります。 という並び替えられた後のものを使うことに注意してください。
8.3 を作成します。
,
9.3
だったはずなので、 に従って並び替えます。
10.3 と を準備します。
ここでは、 であることに注意します。
,
11.3
,
13.
を出力します。
以上全ての操作をシェアのまま行います。そして、 を各パーティに出力します。あとは、分析に必要な部分のみ復号を行い様々な分析をすることになります。
負の数・小数への適用について
ここからは論文には書かれていない内容ですが、負の数・小数への適用について説明します。
ビット分解のところのアルゴリズムで、キー を符号付きで、固定小数点表現でビット分解してあげます。
固定小数点表現とは、小数部分と整数部分の桁数を決めて、ビット表現に直すことです。ここで、小数部分の桁数 、 整数部分の桁数 、最上位ビットに符号のビットで全 8 桁の表現だとします。
この時、例えば 3.25 という数であれば、以下のようにビット分解されると思います。 ですので、
のようになると思います。また、例えば、 - 5.5 という数であれば、2の補数表現を使って、 なので、
の補数表現、
のようにビット分解されます。このようにビット分解するプロトコルは、以下の論文に記載されています。
このように、固定小数点表現に直せたら、最上位ビットをみて、正の数と負の数に事前に分けます。同じ行に対して、シェアを取り出せばいいです。
その後、正の数はそのまま下位ビットからここで、書いてある Oblivious Radix Sort プロトコルでソートします。最上位ビットは無視していいです。正の数はこれで終わりです。
負の数は、補数表現の場合、そのまま並び替えれば、小さい順になります。つまり今の例だと、
と言う表現になっていて、
になってます。これを、下位ビットから Oblivious Radix Sort でそのまま並び替えれば、-15.875 が一番小さい数として認識され、上にきます。-0.125が一番大きい数とそのまま認識され、下にきます。つまり、負の数だけで並び替えれば、負の数も同じように小さい順になります。
最後に必要に応じて、分けた正の数と負の数のベクトルをくっつければ終わりです。このようにして、対応できます。
計算量について
まず、オーダーレベルで見ていくと、以下のようになります。
パーティの数 と素体ビット長 が一定であると仮定すると、忘却基数ソートは ラウンド、および 通信で、非常に効率的な計算量を示します。
: シーケンスの数
: パーティの数
: 基礎となる素体のビット長
計算量の具体的な値
破損許容度 t = 1 の (2,3) シャミアの秘密シェアスキームにソートアルゴリズムを実装し、パフォーマンスを向上させるために、semi-honest な敵対者に対して安全なプロトコルが実装されています。
すべての値は、素体 上の要素です。ここで、P は素数 であり、 を満たします。つまり、値は32ビットワードです。実験は、Intel Core i7-2640M 2.8 GHzCPU と 8GB の物理メモリを搭載した3台のラップトップマシンで実施されました。これらの3台のマシンは 1GbpsLAN に接続されていました。実装は C++ で記述され、コンパイルには g++ 4.6.3 が使用されました。ソートアルゴリズムの実行時間を表4に示し、グラフを図1に示します。結果は、Oblivious Radix Sort が上記の設定で既存のソートアルゴリズムよりも優れていることを示しています。
まとめ
本記事のまとめは以下の通りです。
- MPCにおける高速なソートプロトコルである Oblivious Radix Sort プロトコルについて説明しました。
- Oblivious Radix Sort プロトコルを使用すると、秘密分散をしたまま高速なソートをすることが可能になる。