Search

Publicly verifiable outsourced computation (PVC) allows devices with restricted resources to delegate computations to external servers, and to verify the correctness of results. Servers may be rewarded per computation, and so have an incentive to cheat rather than devote resources to a computation. Also, within an organisation, it is likely that individual user permissions will vary and so outsourced actions should be restricted accordingly. This gives rise to two interesting problems in the PVC setting addressed in this thesis: finding a method to revoke and punish cheating servers; and enforcing access control policies that restrict the computations each entity may outsource, compute or read the results of. In this thesis, we use primitives traditionally used to cryptographically enforce access control policies to construct secure PVC systems that meet these requirements. We first extend prior PVC schemes based on key-policy attribute-based encryption (ABE) to accommodate a broader system model where servers may compute multiple functions and be prevented from performing further computations if found cheating. We then show how a key assignment scheme can provide flexible access control over entities. Finally, we consider an alternative scenario in which input data is held by the server rather than the client, and construct a provably secure instantiation based on ciphertext-policy ABE. We conclude by showing that dual-policy ABE can accommodate both models of outsourced computation and provide a level of access control within a single system.

Since the early works of Ajtai (STOC’96) and Regev (STOC’05), lattice-based cryptography has proven to be a powerful building block in cryptography. My research focuses on further exploring the expressive power of lattice-based cryptography, as well as formal verification of lattice-based cryptographic schemes. Deniable encryption (Canetti et al. CRYPTO ’97) is an intriguing primitive that provides a security guarantee against not only eavesdropping attacks as required by semantic security, but also stronger coercion attacks performed after the fact. The concept of deniability has later demonstrated useful and powerful in many other contexts, such as leakage resilience, adaptive security of protocols, security against selective opening attacks and coercion resistance in voting systems. Despite its conceptual usefulness, our understanding of how to construct deniable primitives under standard assumptions is restricted. We construct a flexibly bi-deniable Attribute-Based Encryption (ABE) scheme for all polynomial-size Branching Programs from Learning With Errors assumption (Regev STOC’05). Attribute based encryption (ABE) is an advanced encryption system with a built-in mechanism to generate keys associated with functions which in turn provide restricted access to encrypted data. Most of the known candidates of attribute based encryption model the functions as circuits. This results in significant efficiency bottlenecks, especially in the setting where the function associated with the ABE key admits a RAM program whose runtime is sublinear in the length of the attribute. We study the notion of attribute based encryption for random access machines (RAMs), introduced in the work of Goldwasser, Kalai, Popa, Vaikuntanathan and Zeldovich (Crypto 2013) and present a construction satisfying sublinear decryption complexity assuming Learning With Errors. We then introduce a symbolic approach for proving security of cryptographic constructions based on the Learning With Errors assumption (Regev, STOC 2005). Such constructions are instances of lattice-based cryptography and are extremely important due to their potential role in post-quantum cryptography. Our approach combines a computational logic, deducibility problems, a standard tool for representing the adversary’s knowledge and the Dolev-Yao model. The computational logic is used to capture (indistinguishability-based) security notions and drive the security proofs whereas deducibility problems are used as side-conditions to control that rules of the logic are applied correctly. We then use AutoLWE, an implementation of the logic, to deliver very short or even automatic proofs of several emblematic constructions. The main technical novelty beyond AutoLWE is a set of (semi-)decision procedures for deducibility problems, using extensions of Grobner basis computations for subalgebras in the (non-)commutative setting (instead of ideals in the commutative setting). Our procedures cover the theory of matrices, which is required for lattice-based assumption, as well as the theory of non-commutative rings, fields, and Diffie-Hellman exponentiation, in its standard, bilinear and multilinear forms.

Attribute-based encryption is a promising cryptographic primitive that allows users to encrypt data according to specific policies on the credentials of the recipients. For example, a user might want to store data in a public server such that only subscribers with credentials of specific forms are allowed to access them. Encrypting the data once for each party is not only impractical but also raises important privacy issues. Therefore, it would be beneficial to be able to encrypt only once for all desired parties. This is achievable by attribute-based encryption schemes, which come into several types and are applicable to a wide range of settings. Several attribute-based encryption schemes have been proposed and studied with a wide range of characteristics. For example, initial constructions proved to be significantly more challenging than constructing traditional public-key encryption systems and they imposed restrictions on the expressiveness of the Boolean formulas used during encryption. For several proposed schemes the total number of attributes was fixed during setup, while others allowed any string to be used as attribute ("large universe" constructions), but with considerable weaker security guarantees. Furthermore, these first constructions, although polynomial time, were impractical for wide deployment. This thesis is motivated by two main goals for ABE schemes: robustness and efficiency. For robustness, we propose a novel construction that achieves strong security guarantees and at the same time augments the capabilities of previous schemes. More specifically, we adapt existing techniques to achieve leakage-resilient ABE schemes with augmented robustness features making no compromises on security. For the second direction, our goal is to create practical schemes with as many features as possible, such as "large universe" and multi-authority settings. We showcase these claims with working implementations, benchmarks, and comparisons to previous constructions. Finally, these constructions lead us to new directions that we propose and intend to investigate further.