秘匿計算上の一括写像アルゴリズム

摘要

本論文では，秘匿計算上でルックアップテーブルの参照を複数のデータに対して一括で行う，一括写像アルゴリズムを提案する.秘匿計算は暗号化されたデータを入力とし，データを一度も復号することなく任意の計算を行う技術である.秘匿計算はデータ提供者のプライバシーを守りながらデータ処理を行う技術として注目されているが，通常の計算機に比べて実行速度が非常に遅いという課題がある.その原因ーのがつは，通常の計算機上で用いられる多くのアルゴリズムはそのまま秘匿計算上で適用しょうとすると計算量が大きくなつてしまうことである.そこで我々は，事前に計算の結果をルックアップテーブルと呼ばれる表に保存しておき，実行時には計算を表の参照に置き換えて処理を効率化する技法を，秘匿計算で実現するアルゴリズムを提案する.提案アルゴリズムは大きさmの表を参照する処理をn個の入力データに対して一括で行う.パーティ数と環の大きさを定数と見たとき，処理時間はラウンド数がO(logn)，通信量が乗算換算でO((m+n)log(m+n))である.