Optimized Search-and-Compute Circuits and Their Application to Query Evaluation on Encrypted Data

FHEでDBに対するクエリ処理をした

Abstract

暗号化されたデータベース上でのプライベートクエリ処理
暗号化されたデータベースを利用して，ユーザの機密情報が漏洩しないようにデータを取得することができる．
暗号化されたデータベースからデータを取得することができます。
暗号化されたデータベースが与えられたとき，ユーザは通常，次のようなクエリ
以下のような例があります。1) 米国ドル以上の収入を得ている従業員は組織内に何人いるか？
2) 白血病にかかった工場労働者の平均年齢は何歳ですか？
2) 白血病の工場労働者の平均年齢は？これらの質問に答えるには
質問に答えるには、関連する暗号化されたデータセットを順に検索して
暗号化されたデータセットを順に検索し、計算する必要がある。この論文では
この論文では、完全に暗号化されたデータベース上で、両方の処理を必要とするクエリを
この論文では、完全に暗号化されたデータベース上で両方の処理を必要とするクエリを効率的に処理することに興味があります。
直近の解決策としては、複数の特殊な暗号化方式を同時に使用することが考えられますが、この方法では
しかし、この方法は、複数の暗号化コンテキストを維持するための高い計算コストを伴います。もう一つの解決策は、プライバシー・ホモモルフィック
スキームを使用することです。しかし、効率性の要求を満たす安全なソリューションは開発されていません。
効率化の要求を満たす安全なソリューションは開発されていない。本論文では
統一されたフレームワークを構築する。
を効率的かつ非公開に処理する統一的なフレームワークを構築する。この目的のために、まず
この目的のために、我々の研究の最初の部分では、暗号化されたデータに対するクエリのプリミティブとして
暗号化されたデータへの問い合わせのためのプリミティブとして、いくつかの回路を考案する。次に
2つの最適化技術を用いて
2つの最適化技術を用いています。1つ目の手法は
SIMD（single-instruction-multiple-data）技術を利用して
基本的な回路の動作を高速化します。一般的なSIMDの手法とは異なります。
私たちのSIMD実装は、一般的なSIMDアプローチとは異なり、1つの基本演算にも適用可能です。
基本的な演算にも適用できます。もうひとつの手法は、大きな整数
リング（例えば、Z2t）をバイナリフィールドではなく、メッセージ空間として使用することです。
k＞tのkビットの整数であっても、次数1の遅延回路を用いて加算を行うことができます。
次数1の回路を用いて、遅延キャリー演算を行うことができます。
最後に、クエリタイプなどのパラメータを変えて行った様々な実験を紹介します。
クエリの種類やタプルの数などのパラメータを変化させて
タプルを変化させて行った様々な実験を紹介します。