New Designs of Encryption Schemes
Mona Sergi · 2012
Encryption in Theory 3same key is used to either encrypt or decrypt data, while in the latter case the key for encryption (called public key) is different from the key for decryption (called private key).In general, Private Key Encryption is more efficient than Public Key Encryption.However, in many applications it is not feasible to give away the key that can decrypt ciphertexts.For example, consider a simple auction application where users encrypt their bids and broadcast them to the public.After everyone broadcasts the encryption of their bids, a trusted authority decrypts the bids and announces the winner.Clearly the bidders' privacy requires that their bids stay secret to the public.Hence the encryption and decryption key may not be the same and we need to use a Public Key Encryption Scheme.In this thesis we only focus on Public Key Encryption, and unless otherwise mentioned, we refer to Public Key Encryption Schemes as Encryption Schemes.The main goal of encryption is to guarantee the privacy of data meaning that a malicious user (or the adversary) cannot learn any information about encrypted data by analyzing its corresponding ciphertext (called the challenge ciphertext).The most basic security guarantee that encryption may provide is semantic security (or CPA security) first introduced by Goldwasser and Micali in [6].Intuitively, this form of security states that whatever the advisory may learn by analyzing the challenge ciphertext can be learned without access to the challenge ciphertext which roughly means that ciphertexts do not leak any unwanted information.However, an encryption scheme that satisfies CPA security might not necessarily preserve the privacy of data in some applications because of the (possibly) unrealistic restrictions of the adversary in the CPA security definition which do not necessarily match the restrictions of the malicious users in real world applications.For example, the adversary does not have access to the decryption oracle either before or after seeing the challenge ciphertext in the CPA security definition while a malicious user might have access to the decryption oracle before knowing the challenge ciphertext.In this case if the encryption scheme stays secure, we say the encryption scheme satisfies a stronger notion of security called CCA1 security which was first introduced and defined by Naor and Yung in [7] and intuitively implies that the decryption oracle does not leak the secret key by answering decryption queries.The encryption schemes in [8] are a few examples of Chapter 1 (Informal Theorem) There exists a black-box construction of NM-CCA1 encryption from plaintext awareness and weak simulatability.Refer to Chapter 3 for more details.Next we consider designing encryption schemes which security is strictly stronger than CCA1 security but weaker than CCA2 security (in the CCA2 security definition, the adversary has Chapter 1We say the adversary succeeds if Verify vkSig (m * , σ * ) = 1 but (m * , σ * ) = (m, σ) (assuming (m, σ) are defined).We stress that the adversary may succeed even if m * = m.Note that public key encryption implies strong one-time signature.This follows by combining the observations that public key encryption implies one-way functions, one-way functions imply universal one-way hash functions [22], and universal one-way hash functions imply strong onetime signature schemes [23,24].Thus, a strong one-time signature can be constructed given any encryption scheme.In this thesis, whenever we need to assume the existence of both encryption schemes and strong one-time signature schemes we only mention assuming the former since the former implies the latter.