完全準同型暗号上での差分プライベートパーティショニングアルゴリズムの高速化

• Item type: Trans(1)
• 公開日: 2023-07-21
• タイトル: 完全準同型暗号上での差分プライベートパーティショニングアルゴリズムの高速化
• タイトル / 言語: en
• タイトル: Acceleration of a Differentially Private Partitioning Algorithm over Homomorphic Encryption
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [研究論文] 差分プライバシ，完全準同型暗号，TFHE，パーティショニング
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 早稲田大学
• 著者所属: LINE株式会社
• 著者所属: 早稲田大学
• 著者所属: 早稲田大学
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者所属(英): en
• 著者所属(英): LINE Corporation
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者名: 牛山, 翔二郎; 髙橋, 翼; 工藤, 雅士; 山名, 早人
• 著者名(英): Shojiro, Ushiyama; Tsubasa, Takahashi; Masashi, Kudo; Hayato, Yamana
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本研究では，複数のデータ所有者から収集した生データに対して，クラウド上でレンジクエリ処理を行う際の，差分プライバシと完全準同型暗号を用いたプライバシ保護に取り組む．具体的には，データ所有者，計算サーバ，復号サーバ，クエリ応答システムを使用するデータ解析者の4パーティから構成されるモデルを想定し，生データのプライバシをクラウドサーバ，データ解析者から保護する．プライバシ保護を実現する手法として，2020年のChowdhuryらによる提案と同様に，生データから差分プライバシ適用済インデックスの生成までを準同型暗号上で行うモデルを採用する．レンジクエリを対象とした場合，個々のカウント値に差分プライバシを適用する代わりに，ヒストグラムをパーティショニングした後で差分プライバシを適用することにより，差分プライバシ適用後の誤差を小さくできることが知られている．しかし，同処理を準同型暗号上で行う場合，データ数に対して計算量が指数的に増加し，実用的ではない．この問題に対し，本研究では，計算量を線形増加に抑えたプライバシ保護パーティショニングアルゴリズムを提案する．提案手法は，隣接するデータ間の差分と閾値との比較のみによりデータ分割点を決定する．Nettraceをはじめとする7種類のデータセットを用いた評価実験の結果，従来のデータ依存パーティショニングアルゴリズムと同等の精度を保つことができること，および，データ数に比例した実行時間で処理できることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this study, we tackle the privacy protection of raw data provided by multiple data owners by combining differential privacy and fully homomorphic encryption, when targeting range queries on the cloud. We assume a query processing system consisting of four entities: 1) data owners, 2) the computation server, 3) the decryption server, and 4) data analysts who submit range queries. In the system, we protect the privacy of raw data against both the cloud servers and data analysts by constructing a differentially private index from the raw data over homomorphic encryption. Although the model to construct a differentially private index is similar to the model proposed by Chowdhury et al. in 2020, we need to adopt an efficient partitioning algorithm to achieve accurate query responses. When targeting range queries, applying differential privacy after partitioning histograms is known to achieve accurate query responses compared to applying differential privacy to each count. However, adopting partitioning over ciphertexts is not practical because its computational complexity increases exponentially with the input histogram size. To solve the above problem, we propose a new privacy-preserving partitioning algorithm that reduces the computational complexity to a linear increase. The proposed method merges adjacent data having close values in the histogram if the difference between the adjacent data is less than a threshold. Experimental evaluation with 7 actual datasets including Nettrace confirmed that the accuracy of the proposed method was equivalent to the state-of-the-art partitioning algorithm and the execution time of the proposed algorithm increased linearly with the input histogram size.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 16, 号 3, p. 1-16, 発行日 2023-07-21
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会