Computer Science Colloquia
Monday, May 7, 2012
Advisor: abhi shelat
Attending Faculty: Gabriel Robins, Chair; Westley Weimer, Andrei Rapinchuk, and Steven Myers
9:00 AM, Rice Hall, Rm. 242
PhD Proposal Presentation
New Designs of Encryption Schemes
A quintessential cryptographic primitive for which many basic questions remain is encryption which is the most widely used and oldest notion of cryptography. Encryption schemes are used to ensure secure communication between parties where the means of communication might be controlled by an untrusted party. Encryption is the process of transforming a piece of data that needs to be hidden or the plaintext into a bit string or ciphertext that sounds meaningless unless one has access to data called the key. The key can be used later to decrypt the ciphertext. Encryption schemes are being widely used to preserve the privacy of data in many systems. A report by the Computer Security Institute shows that the companies surveyed encrypted 66.2% of data in transit and 59.8% of data in storage. An encryption scheme is non-malleable if the adversary cannot transform an encryption of a message under a randomly selected key into an encryption of a related message under the same key. Notice that the basic security definition for an encryption scheme does not prevent this attack. Depending on the timing of the adversary's access to the decryption oracle during the attack, the non-malleable encryption schemes can be categorized further; NM-CCA1 and CCA2 secure encryption schemes. In the first type, the adversary has access to the decryption oracle before seeing the ciphertext she wants to maul, whereas in the second type the adversary has access to the decryption oracle throughout the entire experiment. In this proposal, we study the design and application of several encryption schemes. In particular, we first propose how to build an NM-CCA1 encryption scheme from the weakest possible general assumptions. Second we propose how to extend the result to design encryption schemes which security falls between NM-CCA1 and CCA2 security. Next, we further study a key component in our construction, namely the family of extractable complexity assumptions. We show that although these assumptions are defined in different forms, they are equivalent in real world applications. Next, we propose two new CCA2 secure encryption schemes that are intuitive and efficient. Finally, we consider new applications for encryption schemes that are the opposite of non-malleable, i.e. fully homomorphic. We show that using fully homomorphic encryption schemes, we can construct black-box protocols for secure multiparty computation with low communication complexity.