Efficient Completely Non-Malleable Public Key Encryption

Non-malleable encryption schemes make it infeasible for adversaries provided with an encryption of some plaintext m to compute another ciphertext encrypting a plaintext m that is related to m. At ICALP'05, Fischlin suggested a stronger notion, called complete nonmalleability, where non-malleability should be preserved against adversaries attempting to compute encryptions of related plaintexts under newly generated public keys. This new notion applies to systems where on-line certificate authorities are available and users can issue keys on-the-fly. It was originally motivated by the design of non-malleable commitments from public key encryption (i.e., extractable commitments), for which the usual flavor of non-malleability does not suffice. Completely non-malleable encryption schemes are known not to exist w.r.t. black-box simulation in the standard model (although constructions are possible in the random oracle model). One of the original motivations of Fischlin's work was to have non-malleable commitments without preconditions. At PKC'08, Ventre and Visconti investigated complete non malleability as a general notion suitable for protocol design, and departed from only considering it as a tool for commitment schemes without preconditions. Indeed, if one allows members of a community to generate public keys "on the fly", then considering the notion is justified: For example, if a bidder in an auction scheme can, in the middle of the auction process, register a public key which is malleable with respect to a scheme used in an already submitted bid, he may produce a slightly higher bid without even knowing the already submitted bid. Only when the latter is opened he may be able to open its bid. In this more general context, Ventre and Visconti showed that completely non malleable schemes do exist in the standard model; in fact in the shared random string model as well as in the interactive setting. Their non-interactive scheme is, however, inefficient as it relies on the generic NIZK approach. They left the existence of efficient schemes in the common reference string model open. In this work we describe the first efficient constructions that are completely non-malleable in this standard model.