Cryptography for efficiency: New directions in . . .

Cloud computing has emerged as an important new computational and storage medium and is increasingly being adopted both by companies and individuals as a means of reducing operational and maintenance costs. However, remotely-stored sensitive data may be lost or modified and third-party computations may not be performed correctly due to errors, op-portunistic behavior, or malicious attacks. Thus, while the cloud is an attractive alternative to local trusted computational resources, users need integrity guarantees in order to fully adopt this new paradigm. Specifically, they need to be assured that uploaded data has not been altered and outsourced computations have been performed correctly. Tackling the above problems requires the design of protocols that, on the one hand, are provably secure and at the same time remain highly efficient, otherwise the main purpose of adopting cloud computing, namely efficiency and scalability, is defeated. It is therefore essential that expertise in cryptography and efficient algorithmics be combined to achieve these goals. This thesis studies techniques allowing the efficient verification of data integrity and computations correctness in such adversarial environments. Towards this end, several new authenticated data structures for fundamental algorithmics and computation problems, e.g., hash table queries and set operations, are proposed. The main novelty of this work lies in employing advanced cryptography such as lattices and bilinear maps, towards achieving high efficiency, departing from traditional hash-based primitives. As such, the proposed techniques lead to efficient solutions that introduce minimal asymptotic overhead and at the same time enable highly-desirable features such as optimal verification mechanisms and par-allel authenticated data structures algorithms. The small asymptotic overhead does translate into significant practical savings, yielding efficient protocols and system prototypes