AppLicAtions of MalleaBIlity in Cryptography – ALAMBIC

Cryptography is a crucial and ubiquitous component of information security. It permits to deal with basic computer security needs, related to e.g. confidentiality, privacy, integrity or authentication, but also more unconventional ones. For instance, the basic goal of an encryption scheme is to guarantee the confidentiality of data. However, when encryption schemes are deployed in more complex environments, the demands for security of encryption grow beyond just the basic confidentiality requirement. In 1991, Dolev, Dwork and Naor defined the notion of non-malleability. This ensures that it is infeasible for an adversary to modify ciphertexts into other ciphertexts of messages which are related to the decryption of the first ones. The notion of non-malleability was then applied successfully to various cryptographic primitives such as commitments, zero-knowledge proofs or multi-party computation.

On the other hand, it has been realized that, in specific settings, malleability in cryptographic protocols can actually be a very useful feature. The notion of homomorphic encryption allows specific types of computations to be carried out on ciphertexts and generate an encrypted result which, when decrypted, matches the result of operations performed on the plaintexts. Until recently, all the homomorphic encryption schemes were able to perform only one type of operation (addition or multiplication) on ciphertexts. In 2009, Gentry proposed the first fully homomorphic encryption scheme. His scheme (and subsequent improvements) supports both addition and multiplication and therefore any circuit can be homomorphically evaluated on ciphertexts. The homomorphic property can be used to create secure voting systems, collision-resistant hash functions, private information retrieval schemes, and -- for fully homomorphic encryption -- enables widespread use of cloud computing by ensuring the confidentiality of processed data. Recently, it has been shown that malleability is an interesting feature for other primitives (such as, counter-intuitively, signatures or proof systems) and it is the main goal of this research project to investigate further theoretical and practical AppLicAtions of MalleaBIlity in Cryptography.

In order to reach an accurate analysis that covers a spectrum of study as large as possible, this research proposal focuses on three different aspects: secure computation outsourcing and server-aided cryptography, homomorphic encryption and applications and ``paradoxical'' applications of malleability. More generally, the main objectives of the proposal are the following:
- Define theoretical models for ``malleable'' cryptographic primitives that captures strong practical attacks (in particular, in the settings of secure computation outsourcing, server-aided cryptography, cloud computing and cryptographic proof systems);
- Analyze the security and efficiency of primitives and constructions that rely on malleability;
- Conceive novel cryptographic primitives and constructions (for secure computation outsourcing, server-aided cryptography, multi-party computation, homomorphic encryption and their applications);
- Implement these new constructions in order to validate their efficiency and effective security.