A Unified Approach to Deterministic Encryption: New Constructions and a Connection to Computational Entropy

Date Added: Jan 2012
Format: PDF

Public-key cryptosystems require randomness: indeed, if the encryption operation is deterministic, the adversary can simply use the public key to verify that the ciphertext c corresponds to its guess of the plaintext m by encrypting m. However, such an attack requires the adversary to have a reasonably likely guess for m in the first place. Recent results on Deterministic public-key Encryption (DE) (building on previous work in the one-time, information-theoretic symmetric-key setting have studied how to achieve security when the randomness comes only from m itself. DE has a number of practical applications, such as efficient search on encrypted data and securing legacy protocols.