Publications
JOURNAL (DOMESTIC) 完全準同型暗号上での差分プライベートパーティショニングアルゴリズムの高速化
牛山 翔二郎 (早稲田大学), 髙橋 翼, 工藤 雅士 (早稲田大学), 山名 早人 (早稲田大学)
情報処理学会論文誌データベース（TOD） 16 (3) (IPSJ-TOD)
July 21, 2023
本研究では，複数のデータ所有者から収集した生データに対して，クラウド上でレンジクエリ処理を行う際の，差分プライバシと完全準同型暗号を用いたプライバシ保護に取り組む．具体的には，データ所有者，計算サーバ，復号サーバ，クエリ応答システムを使用するデータ解析者の4パーティから構成されるモデルを想定し，生データのプライバシをクラウドサーバ，データ解析者から保護する．プライバシ保護を実現する手法として，2020年のChowdhuryらによる提案と同様に，生データから差分プライバシ適用済インデックスの生成までを準同型暗号上で行うモデルを採用する．レンジクエリを対象とした場合，個々のカウント値に差分プライバシを適用する代わりに，ヒストグラムをパーティショニングした後で差分プライバシを適用することにより，差分プライバシ適用後の誤差を小さくできることが知られている．しかし，同処理を準同型暗号上で行う場合，データ数に対して計算量が指数的に増加し，実用的ではない．この問題に対し，本研究では，計算量を線形増加に抑えたプライバシ保護パーティショニングアルゴリズムを提案する．提案手法は，隣接するデータ間の差分と閾値との比較のみによりデータ分割点を決定する．Nettraceをはじめとする7種類のデータセットを用いた評価実験の結果，従来のデータ依存パーティショニングアルゴリズムと同等の精度を保つことができること，および，データ数に比例した実行時間で処理できることを確認した．
Paper :
完全準同型暗号上での差分プライベートパーティショニングアルゴリズムの高速化
(external link)