Paper 2009/088

Lossy Encryption: Constructions from General Assumptions and Efficient Selective Opening Chosen Ciphertext Security

Brett Hemenway and Benoit Libert and Rafail Ostrovsky and Damien Vergnaud

Abstract

In this paper, we present new and general constructions of lossy encryption schemes. By applying results from Eurocrypt '09, we obtain new general constructions of cryptosystems secure against a Selective Opening Adversaries (SOA). Although it was recognized almost twenty years ago that SOA security was important, it was not until the recent breakthrough works of Hofheinz and Bellare, Hofheinz and Yilek that any progress was made on this fundamental problem. The Selective Opening problem is as follows: suppose an adversary receives $n$ commitments (or encryptions) of (possibly) correlated messages, and now the adversary can choose $n/2$ of the messages, and receive de-commitments (or decryptions and the randomness used to encrypt them). Do the unopened commitments (encryptions) remain secure? A protocol achieving this type of security is called secure against a selective opening adversary (SOA). This question arises naturally in the context of Byzantine Agreement and Secure Multiparty Computation, where an active adversary is able to eavesdrop on all the wires, and then choose a subset of players to corrupt. Unfortunately, the traditional definitions of security (IND-CPA, IND-CCA) do not guarantee security in this setting. In this paper: We formally define re-randomizable encryption and show that every re-randomizable encryption scheme gives rise to efficient encryptions secure against a selective opening adversary. (Very informally, an encryption is re-randomizable, if given any ciphertext, there is an efficient way to map it to an almost uniform re-encryption of the same underlying message). We define re-randomizable one-way functions and show that every re-randomizable one-way function family gives rise to efficient commitments secure against a selective opening adversary. We show that statistically-hiding 2-round Oblivious Transfer (OT) implies Lossy Encryption and so do smooth hash proof systems, as defined by Cramer-Shoup. Combining this with known results immediately shows that Private Information Retrieval and homomorphic encryption both imply Lossy Encryption, and thus Selective Opening Secure Public Key Encryption. Applying our constructions to well-known cryptosystems (such as Elgamal or Paillier), we obtain selective opening secure commitments and encryptions from the Decisional Diffie-Hellman (DDH), Decisional Composite Residuosity (DCR) and Quadratic Residuosity (QR) assumptions, that are either simpler or more efficient than existing constructions of Bellare, Hofheinz and Yilek. By applying our general results to the Paillier cryptosystem, we obtain the first cryptosystem to achieve simulation-based selective opening security from the DCR assumption. We provide (indistinguishability and simulation-based) definitions of adaptive chosen-ciphertext security (CCA2) in the selective opening setting and describe the first encryption schemes that provide security in the sense of this definition. In the indistinguishability-based model, we notably achieve short ciphertexts under standard number theoretic assumptions. In the simulation-based security chosen-ciphertext attack scenario, we handle non-adaptive (i.e., CCA1) adversaries and describe the first encryption scheme which is simultaneously CCA1 and SOA-secure.

Note: Removed erroneous IND-SO-CCA constructions. Added new (more efficient) IND-SO-CCA constructions based on the Canetti-Halevi-Katz paradigm.