キー・バリュー型データベースにおける利用者のプライバシを考慮した範囲問合せの実現手法

Abstract

本論文では，キー・バリュー型データベースを対象に，利用者のプライバシを考慮した範囲問合せ手法を提案する．従来議論されてきたプライバシを考慮した情報検索 （PIR; private information retrieval） の枠組みでは，単独では範囲問合せが行えず，また検索用キー属性の値に重複が認められないという制限がある．提案手法では，キー属性の値と問合せそれぞれに摂動を加え暗号化を施すことで，これらの制限を設けることなく問合せへの頻度分析攻撃を防ぐ範囲問合せを実現する． In this paper, we introduce a new private range query method in key-value type database.Existing PIR (Private Information Retrieval) approaches have two limitations: it supports only equal queries but range queries;the key attribute used to query processing must be unique.Our approach, on the other hands, guarantees private range queries and allows tuples having a same value of the key attribute against frequency analysis attacks.For these properties, we add perturbations to both key attributes and queries, and encrypt them.