Paper 2016/180

Public-Key Encryption with Simulation-Based Selective-Opening Security and Compact Ciphertexts

Dennis Hofheinz, Tibor Jager, and Andy Rupp

Abstract

In a selective-opening (SO) attack on an encryption scheme, an adversary A gets a number of ciphertexts (with possibly related plaintexts), and can then adaptively select a subset of those ciphertexts. The selected ciphertexts are then opened for A (which means that A gets to see the plaintexts and the corresponding encryption random coins), and A tries to break the security of the unopened ciphertexts. Two main flavors of SO security notions exist: indistinguishability-based (IND-SO) and simulation-based (SIM-SO) ones. Whereas IND-SO security allows for simple and efficient instantiations, its usefulness in larger constructions is somewhat limited, since it is restricted to special types of plaintext distributions. On the other hand, SIM-SO security does not suffer from this restriction, but turns out to be significantly harder to achieve. In fact, all known SIM-SO secure encryption schemes either require O(|m|) group elements in the ciphertext to encrypt |m|-bit plaintexts, or use specific algebraic properties available in the DCR setting. In this work, we present the first SIM-SO secure PKE schemes in the discrete-log setting with compact ciphertexts (whose size is O(1) group elements plus plaintext size). The SIM-SO security of our constructions can be based on, e.g., the k-linear assumption for any k. Technically, our schemes extend previous IND-SO secure schemes by the property that simulated ciphertexts can be efficiently opened to arbitrary plaintexts. We do so by encrypting the plaintext in a bitwise fashion, but such that each encrypted bit leads only to a single ciphertext bit (plus O(1) group elements that can be shared across many bit encryptions). Our approach leads to rather large public keys (of O(|m|2) group elements), but we also show how this public key size can be reduced (to O(|m|) group elements) in pairing-friendly groups.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. TCC 2016-B
Keywords
Public-key encryptionselective-opening securitylossy encryptionmatrix assumptions.
Contact author(s)
andy rupp @ kit edu
History
2019-01-26: last of 2 revisions
2016-02-22: received
See all versions
Short URL
https://ia.cr/2016/180
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/180,
      author = {Dennis Hofheinz and Tibor Jager and Andy Rupp},
      title = {Public-Key Encryption with Simulation-Based Selective-Opening Security and Compact Ciphertexts},
      howpublished = {Cryptology ePrint Archive, Paper 2016/180},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/180}},
      url = {https://eprint.iacr.org/2016/180}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.