Doctoral Thesis: On Deniable Computation and Sublinear Graph Algorithms

Saleet Mossel

Abstract:
This thesis studies deniable computation and sublinear time graph algorithms.
Deniable Computation. We define and construct Deniable Fully Homomorphic Encryption based on the Learning With Errors (LWE) polynomial hardness assumption. Deniable FHE enables storing encrypted data in the cloud to be processed securely without decryption, maintaining deniability of the encrypted data, as well the prevention of vote-buying in electronic voting schemes where encrypted votes can be tallied without decryption. Our constructions achieve compactness independently of the level of deniability- both the size of the public key and the size of the ciphertexts are bounded by a fixed polynomial, independent of the detection probability achieved by the scheme. The running time of our encryption algorithm depends on the inverse of the detection probability, thus the scheme falls short of achieving simultaneously compactness, negligible deniability and polynomial encryption time. Moreover, we introduce the notions of Encryption with Deniable Edits and Encryption with Invisible Edits and give constructions under minimal assumptions: in the public-key setting we only require the existence of standard public-key encryption and in the symmetric-key setting we only require the existence of one-way functions. An encryption scheme that supports deniable edits allows a user who owns a ciphertext c encrypting a large corpus of data m under a secret key sk, to generate an alternative but legitimate looking secret key sk_{c,e} that decrypts c to an “edited” version of the data. Whereas encryption with deniable edits enables a user to modify the meaning of a single ciphertext, the goal of encryption with invisible edits is to enable ongoing modifications of multiple ciphertexts.

Sublinear Graph Algorithms. We consider the problem of approximating the arboricity of a graph G= (V,E) which we denote by arb(G), in sublinear time in the adjacency lists model, where the arboricity of a graph is the minimal number of forests required to cover its edge set. We design a sublinear time algorithm that outputs an O(log^2 n) estimate of the arboricity, with high probability. Furthermore, we present a sublinear time algorithm in the adjacency list model that allows one to sample multiple edges independently from a distribution that is pointwise close to the uniform distribution over edges in the graph. If one knows the number of required samples q in advance, the overall cost of sampling q edges using our algorithm is sublinear in q, which is strictly preferable to the cost resulting from q invocations of the best algorithm for sampling a single edge.

Details

• Date: Thursday, June 30
• Time: 10:00 am
• Category: Thesis Defense

Additional Location Details:

Thesis Supervisor: Professor Shafi Goldwasser
Thesis Committee: Professors Ronitt Rubinfeld and Vinod Vaikuntanathan