Achieving fully privacy-preserving private range queries over outsourced cloud data

With the prevalence of cloud computing, data owners are motivated to outsource their databases to the cloud server. However, to preserve data privacy, sensitive private data have to be encrypted before outsourcing, which makes data utilization a very challenging task. Existing work either focus on keyword searches and single-dimensional range query, or suffer from inadequate security guarantees and inefficiency. In this paper, we consider the problem of multidimensional private range queries over encrypted cloud data. To solve the problem, we systematically establish a set of privacy requirements for multidimensional private range queries, and propose a multidimensional private range query (MPRQ) framework based on private block retrieval (PBR), in which data owners keep the query private from the cloud server. To achieve both efficiency and privacy goals, we present an efficient and fully privacy-preserving private range query (PPRQ) protocol by using batch codes and multiplication avoiding technique. To our best knowledge, PPRQ is the first to protect the query, access pattern and single-dimensional privacy simultaneously while achieving efficient range queries. Moreover, PPRQ is secure in the sense of cryptography against semi-honest adversaries. Experiments on real-world datasets show that the computation and communication overhead of PPRQ is modest.     

Towards practical private processing of database queries over public data

Privacy is a major concern when users query public online data services. The privacy of millions of people has been jeopardized in numerous user data leakage incidents in many popular online applications. To address the critical problem of personal data leakage through queries, we enable private querying on public data services so that the contents of user queries and any user data are hidden and therefore not revealed to the online service providers. We propose two protocols for private processing of database queries, namely BHE and HHE. The two protocols provide strong query privacy by using Paillier’s homomorphic encryption, and support common database queries such as range and join queries by relying on the bucketization of public data. In contrast to traditional Private Information Retrieval proposals, BHE and HHE only incur one round of client server communication for processing a single query. BHE is a basic private query processing protocol that provides complete query privacy but still incurs expensive computation and communication costs. Built upon BHE, HHE is a hybrid protocol that applies ciphertext computation and communication on a subset of the data, such that this subset not only covers the actual requested data but also resembles some frequent query patterns of common users, thus achieving practical query performance while ensuring adequate privacy levels. By using frequent query patterns and data specific privacy protection, HHE is not vulnerable to the traditional attacks on k-Anonymity that exploit data similarity and skewness. Moreover, HHE consistently protects user query privacy for a sequence of queries in a single query session.     

基于可搜索加密机制的数据库加密方案

近年来,数据外包的日益普及引发了数据泄露的问题,云服务器要确保存储的数据具有足够的安全性,为了解决这一问题,亟需设计一套高效可行的数据库加密方案,可搜索加密技术可较好地解决面向非结构文件的查询加密问题,但是仍未较好地应用在数据库中,因此,针对上述问题,提出基于可搜索加密机制的数据库加密方案.本文贡献如下:第一,构造完整的密态数据库查询框架,保证了数据的安全性且支持在加密的数据库上进行高效的查询;第二,提出了满足IND-CKA1安全的数据库加密方案,在支持多种查询语句的前提下,保证数据不会被泄露,同时在查询期间不会降低数据库中的密文的安全性;第三,本方案具有可移植性,可以适配目前主流的数据库如MySQL、PostgreSQL等,本文基于可搜索加密方案中安全索引的构建思想,利用非确定性加密方案和保序加密方案构建密态数据库安全索引结构,利用同态加密以及AES-CBC密码技术对数据库中的数据进行加密,实现丰富的SQL查询,包括等值查询、布尔查询、聚合查询、范围查询以及排序查询等,本方案较BlindSeer在功能性方面增加了聚合查询的支持,本方案改善了CryptDB方案执行完成SQL查询后产生相等性泄露和顺序泄露的安全性问题,既保证了数据库中密文的安全性,又保证了系统的可用性,最后,我们使用一个有10000条记录的Student表进行实验,验证了方案框架以及算法的有效性,同时,将本方案与同类方案进行功能和安全性比较,结果表明本方案在安全性和功能性之间取得了很好的平衡.     

外包数据库查询完全性检验

在外包数据库中,查询完整性意味着从服务器返回给客户的结果集是正确的和完全的,即所有的记录都是来自数据拥有者且没有经过任何修改的,同时所有满足查询的记录都返回到客户端而没有遗漏。提出了一个称为“重复表”的新方法来检验查询完全性。在服务器端,每个表都有一个重复表,该表用不同的加密方法或加密密钥加密。从而,服务器不能从数据本身区分原始表和重复表。在查询时,客户分别查询原始表和重复表,得到两个结果集,然后判断是否所有满足查询的记录都出现在结果集中。实验结果表明该方法是有效的。     

Secure query processing against encrypted XML data using Query-Aware Decryption

Dissemination of XML data on the internet could breach the privacy of data providers unless access to the disseminated XML data is carefully controlled. Recently, the methods using encryption have been proposed for such access control. However, in these methods, the performance of processing queries has not been addressed. A query processor cannot identify the contents of encrypted XML data unless the data are decrypted. This limitation incurs overhead of decrypting the parts of the XML data that would not contribute to the query result. In this paper, we propose the notion of Query-Aware Decryption for efficient processing of queries against encrypted XML data. Query-Aware Decryption allows us to decrypt only those parts that would contribute to the query result. For this purpose, we disseminate an encrypted XML index along with the encrypted XML data. This index, when decrypted, informs us where the query results are located in the encrypted XML data, thus preventing unnecessary decryption for other parts of the data. Since the size of this index is much smaller than that of the encrypted XML data, the cost of decrypting this index is negligible compared with that for unnecessary decryption of the data itself. The experimental results show that our method improves the performance of query processing by up to six times compared with those of existing methods. Finally, we formally prove that dissemination of the encrypted XML index does not compromise security.     

基于敏感数据加密的分布式安全数据库服务研究*

针对目前基于数据加密技术的安全数据库服务不能有效平衡数据处理性能与数据隐私保护的不足,提出一种新的基于分布式安全数据库服务的隐私保护方法,通过引入准标志属性集的自动检测技术,采用对部分敏感属性加密和分解准标志属性集的方式实现数据的垂直分解,通过基于元数据的查询分解实现分布式查询处理。实验结果表明,该方法能较好地平衡查询性能与隐私保护之间的矛盾。     

Verifiable searchable symmetric encryption for conjunctive keyword queries in cloud storage

Searchable symmetric encryption (SSE) has been introduced for secure outsourcing the encrypted database to cloud storage, while maintaining searchable features. Of various SSE schemes, most of them assume the server is honest but curious, while the server may be trustless in the real world. Considering a malicious server not honestly performing the queries, verifiable SSE (VSSE) schemes are constructed to ensure the verifiability of the search results. However, existing VSSE constructions only focus on single-keyword search or incur heavy computational cost during verification. To address this challenge, we present an efficient VSSE scheme, built on OXT protocol (Cash et al., CRYPTO 2013), for conjunctive keyword queries with sublinear search overhead. The proposed VSSE scheme is based on a privacy-preserving hash-based accumulator, by leveraging a well-established cryptographic primitive, Symmetric Hidden Vector Encryption (SHVE). Our VSSE scheme enables both correctness and completeness verifiability for the result without pairing operations, thus greatly reducing the computational cost in the verification process. Besides, the proposed VSSE scheme can still provide a proof when the search result is empty. Finally, the security analysis and experimental evaluation are given to demonstrate the security and practicality of the proposed scheme.     

Paged similarity queries

An important feature of a database management systems (DBMS) is its client/server architecture, where managing shared memory among the clients and the server is always an tough issue. However, similarity queries are specially sensitive to this kind of architecture, since the answer sizes vary widely. Usually, the answers of similarity query are fully processed to be sent in full to the user, who often is interested in just parts of the answer, e.g. just few elements closer or farther to the query reference. Compelling the DBMS to retrieve the full answer, further ignoring its majority is at least a waste of server processing power. Paging the answer is a technique that splits the answer onto several pages, following client requests. Despite the success of paging on traditional queries, little work has been done to support it in similarity queries. In this work, we present a technique that not only provides paging in similarity range or k-nearest neighbor queries, but also supports them in two variations: the forward similarity query and the backward similarity query. They return elements either increasingly farther of increasingly closer to the query reference. The reported experiments show that, depending on the proportion of the interesting part over the full answer, both techniques allow answering queries much faster than it is obtained in the non-paged way.     

结构化加密图的最短路径查询

随着云计算的快速发展, 数据用户将大量图数据外包给云以节约存储和管理成本。然而, 外包数据的安全隐私问题是云计算面临的一大挑战。由于云是半诚实的, 为保护敏感信息的隐私安全, 数据拥有者希望在将图数据外包给云服务器之前对其加密, 同时保留对加密的图数据进行查询和处理的能力。最短路径查询查找图中给定两节点之间的最短路径, 是图应用中最基础的查询类型之一。目前已有许多研究者提出一系列高效的方案, 以支持加密图上近似或精确最短距离查询、约束最短距离查询和 top-k 最近关键字查询, 但支持最短路径查询的方案较少, 且已有方案的存储与时间开销较大。本文提出一种支持在加密图上进行两节点间最短路径查询的结构化加密图方案。在本方案中, 我们基于 2-Hop 标签技术构造支持有向图上最短路径查询的标签索引并加密, 然后将加密的标签外包给云服务器。 利用改进的保序编码算法编码距离值, 实现加法运算和值的比较, 提高最短路径查询的效率。在查询阶段, 通过递归式地计算两节点间最短路径上的第一条边和最后一条边, 最终输出完整的最短路径。安全性和性能分析证明本文方案是安全有效的, 能以较小的存储和较高的查询效率实现两节点间的最短路径查询并保护图数据的隐私。     

Efficient range query processing in metric spaces over highly distributed data

Similarity search in P2P systems has attracted a lot of attention recently and several important applications, like distributed image search, can profit from the proposed distributed algorithms. In this paper, we address the challenging problem of efficient processing of range queries in metric spaces, where data is horizontally distributed across a super-peer network. Our approach relies on SIMPEER (Doulkeridis et al. in Proceedings of VLDB, pp. 986–997, 2007), a framework that dynamically clusters peer data, in order to build distributed routing information at super-peer level. SIMPEER allows the evaluation of exact range and nearest neighbor queries in a distributed manner that reduces communication cost, network latency, bandwidth consumption and computational overhead at each individual peer. In this paper, we extend SIMPEER by focusing on efficient range query processing and providing recall-based guarantees for the quality of the result retrieved so far. This is especially useful for range queries that lead to result sets of high cardinality and incur high processing costs, while the complete result set becomes overwhelming for the user. Our framework employs statistics for estimating an upper limit of the number of possible results for a range query and each super-peer may decide not to propagate further the query and reduce the scope of the search. We provide an experimental evaluation of our framework and show that our approach performs efficiently, even in the case of high degree of distribution.     

Continuous aggregate nearest neighbor queries

This paper addresses the problem of continuous aggregate nearest-neighbor (CANN) queries for moving objects in spatio-temporal data stream management systems. A CANN query specifies a set of landmarks, an integer k, and an aggregate distance function f (e.g., min, max, or sum), where f computes the aggregate distance between a moving object and each of the landmarks. The answer to this continuous query is the set of k moving objects that have the smallest aggregate distance f. A CANN query may also be viewed as a combined set of nearest neighbor queries. We introduce several algorithms to continuously and incrementally answer CANN queries. Extensive experimentation shows that the proposed operators outperform the state-of-the-art algorithms by up to a factor of 3 and incur low memory overhead.     

一种安全高效的无人驾驶车辆地图更新方案

实时地图在无人驾驶车辆导航中发挥着至关重要的作用.和现有的地图更新方法相比,基于群智感知的实时地图更新方法成本更低且准确性更高.然而,此方法在地图更新过程中,会增加数据及用户身份泄露的风险.如何保证上传数据的机密性和用户的匿名性是实时地图更新中的一个挑战.提出了一种安全高效的无人驾驶车辆地图更新方案(secure and efficient map update scheme for AVs, SEMU).在SEMU方案中,利用签密和代理重加密技术,车辆用户对感知数据进行签密,将加密的数据存储在车辆雾节点中,当地图公司希望访问数据时,雾节点将加密的数据发送给云服务平台,云服务平台重新加密数据发送给地图公司,同时,云服务平台无法获得任何有关数据的明文信息.利用聚合签名技术,降低了计算开销.通过对车辆用户的信誉管理,提高了数据的可靠性.最后,安全性分析表明该方案实现了数据的机密性、完整性、可靠性、身份可验证性和不可否认性,保证了用户的匿名性和可追踪性.仿真验证了方案的激励性,并从计算开销方面证明了它的有效性.     

VKSE-MO: verifiable keyword search over encrypted data in multi-owner settings

Searchable encryption (SE) techniques allow cloud clients to easily store data and search encrypted data in a privacy-preserving manner, where most of SE schemes treat the cloud server as honest-but-curious. However, in practice, the cloud server is a semi-honest-but-curious third-party, which only executes a fraction of search operations and returns a fraction of false search results to save its computational and bandwidth resources. Thus, it is important to provide a results verification method to guarantee the correctness of the search results. Existing SE schemes allow multiple data owners to upload different records to the cloud server, but these schemes have very high computational and storage overheads when applied in a different but more practical setting where each record is co-owned by multiple data owners. To address this problem, we develop a verifiable keyword search over encrypted data in multi-owner settings (VKSE-MO) scheme by exploiting the multisignatures technique. Thus, our scheme only requires a single index for each record and data users are assured of the correctness of the search results in challenging settings. Our formal security analysis proved that the VKSE-MO scheme is secure against a chosen-keyword attack under a random oracle model. In addition, our empirical study using a real-world dataset demonstrated the efficiency and feasibility of the proposed scheme in practice.     

对加密电子医疗记录有效的连接关键词的搜索

随着云计算的发展,医院或医疗组织为了节省存储资源将加密的电子医疗记录的存储和管理外包给云服务器.尽管加密有助于保护用户数据的机密性,但是对加密的数据执行安全而有效的搜索是一个挑战性的问题.在这篇论文中,我们首先构造了被称为MCKS_I的简单的多域连接关键词搜索（MCKS）方案,该方案仅支持连接相等查询.为了实现更加灵活而复杂的多域关键词连接查询,例如子集查询和范围查询,我们又提出了被称为MCKS_II的提高方案.该方案利用了分层属性的矢量表示方法.这两个方案被证明能抵抗已知明文攻击.大量的分析和实验数据证明我们的方案是很实用的.     

基于秘密共享和压缩感知的通信高效联邦学习

深度学习技术的快速发展给我们带来了极大的便利,但同时也导致大量隐私数据的泄露.联邦学习允许客户端在只共享梯度的情况下联合训练模型,这看似解决了隐私信息泄露问题,但研究表明联邦学习框架中传输的梯度依然会导致隐私信息泄露.并且,联邦学习的高通信代价的特点难以适用于资源受限的环境.为此,提出了2个通信高效且安全的联邦学习算法,算法使用Top-K稀疏及压缩感知等技术以减少梯度传输造成的通信开销,另外利用安全多方计算中的加法秘密共享对重要的梯度测量值加密,以实现在减少通信开销的同时进一步增强其安全性.2个算法的主要区别是客户端与服务器通信时传递的分别为梯度测量值与梯度测量值的量化结果.在MNIST及Fashion-MNIST数据集上的实验表明,与其他算法相比,本文所提的算法在保证通信代价较低的情况下进一步增加了安全性,同时在模型准确性上也有较好的性能.     

分布式 LDAP 系统的引用研究

LDAP是轻量级目录访问协议的缩写。LDAP是X．500标准在TCP／IP上的实现,它采用树状层次存储结构,树的各层节点就是条目。分布式LDAP系统中,多个LDAP服务器构建不同的域,任何服务器上都可以查询到整个系统的数据。分布式LDAP系统使用引用机制在LDAP服务器间建立连接关系。客户端访问本地服务器查询条目,如果本地服务器发现查询条目不属于本域,它就会根据引用地址访问其他服务器,直至返回被查询条目的数据。但如果客户端查询的条目不在任何域内,则会导致引用死锁,客户端得不到响应,一直处于等待状态。针对上述问题,论文提出增加LDAPMessage字段的解决方案,并测试验证方案可行性。     

Private Keyword-Search for Database Systems Against Insider Attacks

The notion of searchable encrypted keywords introduced an elegant approach to retrieve encrypted data without the need of decryption. Since the introduction of this notion, there are two main searchable encrypted keywords techniques, symmetric searchable encryption (SSE) and public key encryption with keyword search (PEKS). Due to the complicated key management problem in SSE, a number of concrete PEKS constructions have been proposed to overcome it. However, the security of these PEKS schemes was only weakly defined in presence of outsider attacks; therefore they suffer from keyword guessing attacks from the database server as an insider. How to resist insider attacks remains a challenging problem. We propose the first searchable encrypted keywords against insider attacks (SEK-IA) framework to address this problem. The security model of SEK-IA under public key environment is rebuilt. We give a concrete SEK-IA construction featured with a constant-size trapdoor and the proposed scheme is formally proved to be secure against insider attacks. The performance evaluations show that the communication cost between the receiver and the server in our SEK-IA scheme remains constant, independent of the sender identity set size, and the receiver needs the minimized computational cost to generate a trapdoor to search the data from multiple senders.     

An efficient,robust method for processing of partial top-k/bottom-k queries using the RD-Tree in OLAP

Online analytical processing (OLAP) is a widely used technology for facilitating decision support applications. In the paper, we consider partial aggregation queries, especially for partial top-k/bottom-k, which retrieve the top/bottom-k records among the specified cells of the given query. For the efficient processing of partial ranking queries, this paper proposes a set of algorithms using the RD-Tree, which is a data structure previously proposed for partial max/min queries. Through experiments with real data, we show the efficiency, robustness, and low storage overhead of the proposed method.     

基于加密数据库的高效安全HW-PIR方案

在传统基于硬件的私有信息检索(HW-PIR)方案中,数据库明文记录容易被泄露.为解决该问题,提出基于加密数据库的HW-PIR方案.将数据库记录转化为(0,1)比特流后进行置换,并采用代理重加密算法,实现对密文数据库的查询,从而保证用户的查询隐私不会泄露给数据库服务器,还能防止用户的查询内容与数据库的隐私泄露给安全协处理器及恶意攻击者.效率分析结果表明,该方案的在线查询复杂度为O(1),同时安全处理器预处理阶段的计算量明显降低.     

DAS模式下基于密文分组索引的完整性验证

目前关于DAS模式下的全概率完整性验证方法主要是建立在明文数据上,并没有建立在密文数据上的完整性验证方法。提出一种建立在密文数据上的适用于动态数据库的完整性验证方法。分组索引是在DAS模式下的一种高效的密文索引,在密文数据分组索引的基础上,提出利用无碰撞增量式哈希生成完整性验证信息的方法。这是一种验证速度快(可并行计算)、维护代价小(对于增删改操作可增量式维护)的全概率验证方法,适用于动态数据库中完整性的验证。