Privacy-Preserving Approximate k-Nearest-Neighbors Search that Hides Access, Query and Volume Patterns
Privacy-Preserving Approximate k-Nearest-Neighbors Search that Hides Access, Query and Volume Patterns
复制标题
DOI：
10.2478/popets-2021-0084
复制
发表时间：
2021-07
影响因子：
--
通讯作者：
A. Boldyreva;Tianxin Tang
中科院分区：
文献类型：
--
作者：
A. Boldyreva;Tianxin Tang
摘要研究了在外包环境下的隐私保护近似KNN搜索问题--客户端将加密数据发送到不可信的服务器，然后可以执行安全的近似KNN搜索和更新。我们设计了一个安全模型，并提出了一种基于位置敏感散列、对称加密和不经意映射的通用结构。该结构提供了非常强大的安全保障，不仅隐藏了有关数据的信息，还隐藏了访问、查询和卷模式。我们实现了两种基于不经意的AVL树和不经意的BSkiplist的具体方案，并对其进行了效率评估和性能比较。
Abstract We study the problem of privacy-preserving approximate kNN search in an outsourced environment — the client sends the encrypted data to an untrusted server and later can perform secure approximate kNN search and updates. We design a security model and propose a generic construction based on locality-sensitive hashing, symmetric encryption, and an oblivious map. The construction provides very strong security guarantees, not only hiding the information about the data, but also the access, query, and volume patterns. We implement, evaluate efficiency, and compare the performance of two concrete schemes based on an oblivious AVL tree and an oblivious BSkiplist.