Biblio

Blockchain technology has attracted much attention due to the great success of the cryptocurrencies. Owing to its immutability property and consensus protocol, blockchain offers a new solution for trusted storage and computation services. To scale up the services, prior research has suggested a hybrid storage architecture, where only small meta-data are stored onchain and the raw data are outsourced to off-chain storage. To protect data integrity, a cryptographic proof can be constructed online for queries over the data stored in the system. However, the previous schemes only support simple key-value queries. In this paper, we take the first step toward studying authenticated range queries in the hybrid-storage blockchain. The key challenge lies in how to design an authenticated data structure (ADS) that can be efficiently maintained by the blockchain, in which a unique gas cost model is employed. By analyzing the performance of the existing techniques, we propose a novel ADS, called GEM2-tree, which is not only gas-efficient but also effective in supporting authenticated queries. To further reduce the ADS maintenance cost without sacrificing much the query performance, we also propose an optimized structure, GEM2*-tree, by designing a two-level index structure. Theoretical analysis and empirical evaluation validate the performance of the proposed ADSs.

As cloud storage and computing gains popularity, data entrusted to the cloud has the potential to be exposed to more people and thus more vulnerable to attacks. It is important to develop mechanisms to protect data privacy and integrity so that clients can safely outsource their data to the cloud. We present a method for ensuring data completeness which is one facet of the data integrity problem. Our approach converts a standard database to a Completeness Protected Database (CPDB) by inserting some semantic fake data before outsourcing it to the cloud. These fake data are initially produced using our generating function which uses Order Preserving Encryption, which allows the user to be able to regenerate these fake data and match them to fake data returned from a range query to check for completeness. The CPDB is innovative in the following ways: (1) fake data is deterministically generated but is semantically indistinguishable from other existing data; (2) since fake data is generated by deterministic functions, data owners do not need to locally store the fake data that have been inserted, instead they can re-generate fake data using the functions; (3) no costly data encryption/signature is used in our scheme compared to previous work which encrypt/sign the entire database.

Searchable Symmetric Encryption is a mechanism that facilitates search over encrypted data that are outsourced to an untrusted server. SSE schemes are practical as they trade nicely security for efficiency. However, the supported functionalities are mainly limited to single keyword queries. In this paper, we present a new efficient SSE scheme, called REX, that supports range queries. REX is a no interactive (single round) and response-hiding scheme. It has optimal communication and search computation complexity, while it is much more secure than traditional Order Preserving Encryption based range SSE schemes.