ShuntaIshihara
commented
4 years ago - 論文タイトル Mitigating Leakage in Secure Cloud-Hosted Data Structures: Volume-Hiding for Multi-Maps via Hashing
- 著者（所属） Sarvar Patel(Google LLC), Giuseppe Persiano(Università di Salerno), Kevin Yeo(Google LLC), Moti Yung(Google LLC),
- 論文PDF／ランディングページへのリンク https://dl.acm.org/doi/pdf/10.1145/3319535.3354213
- 論文まとめ（落合フォーマット準拠）
- どんなもの？ 漏洩プロファイルのリスクを軽減するために，ボリュームを隠す暗号化MultiMap（EMM）スキームの概念が導入された．このスキームにより，単一のキーに関連付けられた値の数（ボリューム）が攻撃者に漏洩すること防ぐことができる． この研究では，ボリュームを非表示にするEMMの分野で，概念とアルゴリズムの両方に貢献している．特に，ボリューム非表示EMM(dprfMM)の正式な定義の提示と差分プライベートなボリューム非表示EMM(dpMM)の概念を紹介する．さらに，両方のタイプのEMMの効率的な構造を提示する． また，プライバシーと効率性の間のバランスを調整できる差分プライベート非表示暗号化MultiMap(dpMM)も提案する．
- 先行研究と比べてどこがすごい？ 先行研究のスキームでは，一般的なマルチマップの多くの情報を失い，ストレージのオーバーヘッドが大きくなるか，十分に調査されていない計算の前提が必要か，または，我々の構造よりもはるかに大きなクエリオーバーヘッドが必要となる．一方で，この研究で提案している構造では，マルチマップの情報を失うことなく，サーバーストレージとクエリのオーバーヘッドを大幅に削減できている．さらに，差分プライベートボリューム非表示構造では，わずかに多くのサーバーストレージを使用しながら，クエリのオーバーヘッドを大幅に削減できる．
- 技術や手法のキモはどこ？ オーバーヘッドの少ないボリューム非表示MultiMapを構成するために，cuckoo hashingを使う．サーバーには２つのテーブルがあり，キーkに関連づけられている値がいずれかのテーブルに保存されるようになっている．各テーブルの空いている場所には，ダミー値を入れて，両方のテーブルとも全ての値に対して暗号化されている．クライアンは２つのテーブルそれぞれに対する2l 個（lはキーに関連づけられている値の数の最大値）のハッシュ値(キー)を送り，そしてサーバーは，全部で2l個の暗号化された値をテーブルから返します．実際の値が入力されているかダミーの値が入力されているかをサーバーが認識していないため，この構造はボリューム非表示である． また，通信コストの改善として，１つのハッシュ値から2l個のハッシュ値に安全に拡張できるようにすることでクライアントからサーバーに送るハッシュ値の個数を削減することができる． 差分プライベートボリューム非表示MultiMapについては，クライアントからのハッシュ値の数をl(k)+Xとすることで実現する．ここで，l(k)はキーkに関連付けられた値の数で，Xはラプラシアン分布に従う確率変数とする．問題となるのは，ラプラシアン分布から生成されるXが負の値を取ることであり，その結果，損失を起こしてしまう．そこで，ラプラシアン分布で生成されるXの値がf（λ）より小さい確率が最大でも2^-λの確率になるように，いくつかのパブリックパラメーターf（λ）を選択する．十分な大きさのλとf（λ）=ω（logλ）を選択することで，実際に観測されない小さな確率を除いて，構造が非損失であることを保証できます。
- どうやって有効だと検証した？ dprfMMは，プレーンテキストで1〜67 MBを占め，合計値が2^16〜2^22のそれぞれのMultiMapについて暗号化する実験を行ったときに、クエリの通信コストを先行研究[32]の構造よりも10〜16倍改善できた． dpMMについても同じように，プレーンテキストで1〜67 MBを占める2^16〜2^22の合計値を持つMultiMapを暗号化するときに，先行研究[32]の平均クエリオーバーヘッドを150〜240倍に大幅に改善できている．
- 議論はある？ （個人的に） 検索のみなので，使えるアプリケーションはそんなに多くないのかも
- 次に読むべき論文は？
構造化暗号(STE)
- [16] Melissa Chase and Seny Kamara. 2010. Structured encryption and controlled disclosure. In EUROCRYPT ’10. Springer, 577–594. 暗号化マルチマップ(EMM)
- [17] RezaCurtmola,JuanGaray,SenyKamara,andRafailOstrovsky.2011.Searchable symmetric encryption: improved definitions and efficient constructions. Journal of Computer Security (2011).
- [32] Seny Kamara and Tarik Moataz. 2019. Computationally Volume-Hiding Struc- tured Encryption. In EUROCRYPT 2019, Yuval Ishai and Vincent Rijmen (Eds.). 183–213.