Towards efficient proofs of storage and verifiable outsourced database in cloud computing

Abstract

Cloud computing is becoming an important topic in both industry and academic communities. While cloud computing provides many benefits, it also brings in new challenges in research, especially in information security. One of the main challenges is how to achieve a pair of apparently conflicting requirements simultaneously: efficiency in communication, storage and computation on both client and server sides, and security against outside and internal attackers. Security concerns consist of data confidentiality and data integrity.

This dissertation is devoted to efficiently verify integrity in cloud storage and outsourced database. The main strategy is to devise new homomorphic cryptographic methods.

For cloud storage, we propose three efficient methods that allow users to remotely check the integrity of their files stored in a potentially dishonest cloud storage server, without downloading their files. These three methods rely on three underlying homomorphic authentication methods, which we design with different techniques. All of these three underlying homomorphic authentication methods support linear homomorphism: Given a public key and a sequence of message-tag pairs, any third party can compute a valid authentication tag for a linear combination of these messages. Furthermore, the second and third authentication methods support an additional homomorphism: Given a public key and an authentication tag of a long message, any third party can compute a valid authentication tag for a short message, as long as the short message and the long message satisfy a predetermined predicate. We prove security properties of the proposed schemes under various cryptographic hard problem assumptions.

For outsourced database, we propose an efficient authentication method that allows users to query their database which is maintained by a potentially dishonest server, and verify the correctness and completeness of the query results returned by the server. Supported database queries include aggregate count/min/max/median query conditional on multidimensional rectangular range selection, and non-aggregate multidimensional rectangular range selection query. The proposed method relies on our newly constructed functional encryption scheme. This functional encryption scheme allows a third party, with a delegation key that is generated on the fly, to compute a designated function (the function is specified in the delegation key) value of the plaintext from the corresponding ciphertext, yet without knowing the value of the plaintext. We prove security properties of the proposed schemes under various cryptographic hard problem assumptions.