美歩 三宅
近年, 情報技術はさまざまな分野で使用されている. 特に企業では, 顧客や社会のニーズに応えるために人工知能などの先端技術や自社のデータの有効活用などが重要視されている. しかし, 顧客のパーソナルデータや企業の独自技術といった機密情報の利活用には, 情報漏洩や不正利用など安全面に課題がある. そこで, データを秘匿化したまま任意の計算が可能な秘密計算(secure multi-party computation, MPC) と呼ばれる暗号技術が注目されている. MPC とは, n人の入力x1, . . . , xn を持つパーティP₁, . . . , Pn が, 入力を秘匿したまま関数f(x1, . . . , xn) を共同計算する暗号技術である. MPC に関するほとんどの先行研究では, 全てのパーティが他の全てのパーティと通信できることが前提となっている. このようなプロトコルでは, プロトコルの実行中, 全てのパーティが常にオンラインである必要があり, これは現実的な設定ではない. 例えば, 無線通信では無線機器間の物理的距離によって直接通信ができない可能性がある. そのため, パーティ間の通信が制限されたMPC を考える必要がある. Halevi, Lindell, Pinkas はこの問題に対して, 全てのパーティが同時にオンラインであるという制約をなくしたプロトコルを提案した. また, Beimel らとGoldwasser らは, 各パーティが独立してメッセージをサーバへ送信し, サーバが関数の出力を計算するプロトコルを提案した. その後, Halevi らがこれらを一般化し, 相互通信パターン(interaction pattern)という概念を導入したMPC プロトコルを提案した. 相互通信パターンは, 各パーティが送信するメッセージの依存関係を表す有向非巡回グラフによって与えられる. 彼らのプロトコルは事前計算モデルであり, パーティ間で通信を行う前に, 各パーティに相関乱数 を与えることで任意の相互通信パターンを持つMPC プロトコルを実現している. また, 彼らは対称関数に対してチェーン型の相互通信パターンを持つ情報理論的に安全なプロトコルを提案している. このプロトコルでは, 相関乱数はn(n +1)²ビット, 総通信量は高々n(n +1)²ビットである. 本研究では, 対称関数に対応したアーベルプログラムに対するチェーン型と木状相互通信パターンを持つプロトコルを提案する. 提案プロトコルでは, 相関乱数はO(n log n) ビット, 総通信量はO(n log n) ビットである. アーベルプログラムとは, 入力はアーベル群G上の要素であり, 関数f : G → {0, 1}を用いてh(x1, . . . , xn) = f(Σi∈[n] xi) で表される関数である. 入力領域をG = Zn+1 とすることで, 対称関数が表現できる. 対称関数は出力が入力のハミング重みにのみ依存する関数であり, 具体的には, OR, AND, 多数決関数などの実用的な関数がある. また, 木状相互通信パターンを持つプロトコルは有用である. 通信ネットワーク上のルーティングは木構造となっている. そのため, 木状相互通信パターンを持つプロトコルを提案することで, パーティ間の通信が任意に制限されている通信ネットワーク上でのMPC を実現可能とする.
•Mar 1, 2023•0 citations