The New Security Bounds and Leakage-resilient Models for Encryption Schemes

Open Access
Zhang, Ye
Graduate Program:
Computer Science and Engineering
Doctor of Philosophy
Document Type:
Date of Defense:
May 06, 2015
Committee Members:
  • Adam Smith, Dissertation Advisor
  • Adam Smith, Committee Chair
  • Jason Ryder Morton, Committee Member
  • Trent Ray Jaeger, Committee Member
  • Martin Furer, Committee Member
  • PKCS #1
  • leakage-resilient encryption
  • pebbling games
One of the earliest and most important tasks in cryptography is to encode messages in a way that only authorized parties can read them. Encryption is the process of doing so. In an encryption scheme, an encryption key and a decryption key are first generated. Given the encryption key and a message $m$, the encryption scheme generates the encoded message: the ciphertext $C$. Given decryption key and a ciphertext $C$, the encryption scheme can recover the original message. In this thesis, we study some problems about security bounds and leakage-resilient models for encryption schemes, by showing tighter security bounds for encryption schemes, devising efficient constructions in the existing security models and proposing more powerful security models: PKCS \#1 v1.5 is a long-standing and a widely used standard that defines a set of encryption schemes. Ciphertext Indistinguishability under Chosen Plaintext Attack (IND-CPA) is one of the most popular security definitions for public key encryption. In this thesis, first, we show the encryption scheme in PKCS \#1 v1.5 is IND-CPA secure for messages of length roughly 8 times as long as in the previous work. Second, we consider securely updating encryption keys in a security co-processor where information could be leaked to an attacker periodically. We devise a leakage-resilient key evolution scheme to address the problem. Our construction can update keys in a near-linear time in $n$, where $n$ is the length of key. Previous work on this problem updates keys in time $\Theta(n^2)$. Our security analysis uses new results on the connectivity of random graphs. Third, we consider the \emph{ auxiliary input model}, which captures settings where the attacker has some information about the decryption key. Previous work only considered public-key encryption (PKE) in this model. In this thesis, we devise the first secure identity-based encryption (IBE) construction in this model. IBE is more flexible than PKE in the choice of public keys. This makes it much more useful, but harder to achieve. We also extend the auxiliary model to a stronger model by allowing the attackers to have some information about the randomness that is used to generate ciphertexts. This new model is important as in some cases (e.g., cloud computing), the randomness used by encryptors (e.g., data owners) is weak. We devise secure IBE and PKE constructions in this new model.