Searchable Encryption with Secure and Efficient Updates

論文タイトル Searchable Encryption with Secure and Efficient Updates
著者（所属） Florian Hahn (SAP, Karlsruhe Germany), Florian Kerschbaum (SAP, Karlsruhe Germany)
論文PDF／ランディングページへのリンク http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.720.130&rep=rep1&type=pdf
論文まとめ（落合フォーマット準拠）
- どんなもの？ Dynamic Searchable Encryption（暗号化データベースに後からデータを追加したり削除したりできる）において，安全かつ効率的なデータの追加や削除が行える手法を提案．
- 先行研究と比べてどこがすごい？先行研究では，決定性暗号を用いることで，効率よくアップデートを行うもの（ただし，安全性は低下）や，安全性の高いもの（ただし，ストレージと検索時間のオーバヘッドが大きい）があるが，両方を実現している手法はない．この論文では，その両方を実現する手法が提案される．
- 技術や手法のキモはどこ？一度検索に用いたトークンをハッシュテーブルで保存しておき，次に同じトークンが与えられた時は，定数時間で検索を可能とする．トークンに紐づいている暗号化されたキーワードの情報（アクセスパターン）は漏洩するが，キーワードの内容までは知られない．独自のリーク関数を定義し，新しく安全性の定義を提案している．（既存のものよりも厳しい）←しっかりと読めていない
- どうやって有効だと検証した？ 300,000のキーワードとドキュメントに対して平均70ミリ秒で検索できた．
- 議論はある？アクセスパターンも非表示にしたい
- 次に読むべき論文は？ E. Stefanov, C. Papamanthou, and E. Shi. Practical dynamic searchable symmetric encryption with small

tsukuba-kde / papers

Searchable Encryption with Secure and Efficient Updates #23