CryptoDB
Re-randomizable Encryption implies Selective Opening Security
| Authors: | |
|---|---|
| Download: | |
| Abstract: | In this paper, we present new general constructions of commitments and encryptions secure against a Selective Opening Adversary (SOA). Although it was recognized almost twenty years ago that SOA security was important, it was not until the recent breakthrough works of Hofheinz (H08) and Bellare, Hofheinz and Yilek (BHY09) 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 decommitments (or decryptions \emph{and} the randomness used to encrypt them). Do the unopened commitments (encryptions) remain secure? A protocol which achieves this type of security is called \emph{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- We formally define e-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. Applying our constructions to the known cryptosystems of El-Gamal, Paillier, and Goldwasser and Micali, we obtain IND-SO 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. Applying our general results to the Paillier Cryptosystem we demonstrate the first cryptosystem to achieve Semantic Selective Opening security from the DCR assumption. We give black-box constructions of Perfectly Binding SOA secure commitments, which is surprising given the negative results of Bellare, Hofheinz and Yilek. We define the notion of adaptive chosen ciphertext security (CCA-2) in the selective opening setting, and describe the first encryption scheme which is CCA-2 secure (and simultaneously SOA-secure). |
BibTeX
@misc{eprint-2009-18193,
title={Re-randomizable Encryption implies Selective Opening Security},
booktitle={IACR Eprint archive},
keywords={public-key cryptography / Public Key Encryption, Commitment, Selective Opening, Homomorphic Encryption, Chosen Ciphertext Security},
url={http://eprint.iacr.org/2009/088},
note={ bretth@math.ucla.edu 14295 received 19 Feb 2009},
author={Brett Hemenway and Rafail Ostrovsky},
year=2009
}