In public-key encryption (PKE), ciphertexts received by a receiver may be possibly correlated and the security of a PKE relies on honestly generated system parameters. Security against selective opening attacks (SOA) for PKE guarantees that even when an attacker has broken into a subset of honestly generated ciphertexts and opened them (i.e., seeing plaintexts and random bits), the unopened ciphertexts remain secure. While security against parameter subversion attacks (PSA) for PKE requires that even when the public system parameters are maliciously generated, a PKE scheme should be secure. In this paper, we initiate the study of PKE secure against both SOA and PSA. To capture SOA and PSA simultaneously, we formulate a new security notion called indistinguishability under selective opening attacks and parameter subversion attacks (IND-SO-PSA). Further, we define the lossy trapdoor function and all-but-many lossy trapdoor function in the presence of PSA (LTF-PSA and ABM-LTF-PSA correspondingly) and propose an instantiation with the efficiently-embeddable group (EG). Applying these new primitives, we construct a PKE scheme that is proven to be IND-SO-PSA secure.
In public-key encryption (PKE), ciphertexts received by a receiver may be possibly correlated and the security of a PKE relies on honestly generated system parameters. Security against selective opening attacks (SOA) for PKE guarantees that even when an attacker has broken into a subset of honestly generated ciphertexts and opened them (i.e., seeing plaintexts and random bits), the unopened ciphertexts remain secure. While security against parameter subversion attacks (PSA) for PKE requires that even when the public system parameters are maliciously generated, a PKE scheme should be secure. In this paper, we initiate the study of PKE secure against both SOA and PSA. To capture SOA and PSA simultaneously, we formulate a new security notion called indistinguishability under selective opening attacks and parameter subversion attacks (IND-SO-PSA). Further, we define the lossy trapdoor function and all-but-many lossy trapdoor function in the presence of PSA (LTF-PSA and ABM-LTF-PSA correspondingly) and propose an instantiation with the efficiently-embeddable group (EG). Applying these new primitives, we construct a PKE scheme that is proven to be IND-SO-PSA secure.
Security against selective opening attack (SOA) for receivers requires that in a multi-user setting, even if an adversary has access to all ciphertexts, and adaptively corrupts some fraction of the users to obtain the decryption keys corresponding to some of the ciphertexts, the remaining (potentially related) ciphertexts retain their privacy. In this paper, we study simulation-based selective opening security for receivers of public key encryption (PKE) schemes under chosen-ciphertext attacks (RSIM-SO-CCA). Concretely, we first show that some known PKE schemes meet RSIM-SO-CCA security. Then, we introduce the notion of master-key SOA security for identity-based encryption (IBE), and extend the Canetti–Halevi–Katz transformation to show generic PKE constructions achieving RSIM-SO-CCA security. Finally, we show how to construct an IBE scheme achieving master-key SOA security.
We provide the first public key encryption schemes proven secure against selective opening attack (SOA). This means that if an adversary obtains a number of ciphertexts and then corrupts some fraction of the senders, obtaining not only the corresponding messages but also the coins under which they were encrypted then the security of theothermessagesisguaranteed. Whetherornotschemeswith this property exist has been open for many years. Our schemes are based on a primitive we call lossy encryption. Our schemes have short keys (public and secret keys of a fixed length suffice for encrypting an arbitrary number of messages), are stateless, are non-interactive, and security does not rely on erasures. The schemes are without random oracles, proven secure under standard assumptions (DDH, Paillier’s DCR, QR, lattices), and even efficient. We are able to meet both an indistinguishability
In the first part of this work, Chapter 3 we present new and general constructions of lossy encryption schemes.
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 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.
In the second part of this work, Chapter 4, we focus on constructing lossy trapdoor functions.
Lossy trapdoor functions (LTDFs) were introduced by Peikert and Waters in STOC '08. Since their introduction, lossy trapdoor functions have found many uses in cryptography. In the work of Peikert and Waters, lossy trapdoor functions were used to give an efficient construction of a chosen-ciphertext secure (IND-CCA2) cryptosystem. Lossy trapdoor functions were then shown to imply deterministic encryption by Boldyreva, Fehr and O'Neill in CRYPTO '08. In TCC '09, Rosen and Segev showed that lossy trapdoor functions are correlated product secure, meaning that they remain one-way even when evaluated on correlated inputs.
In this section we extend the notion of smooth hash proof systems as defined by Cramer and Shoup in Eurocrypt '02, to include an additional homomorphic property. We call this primitive smooth homomorphic hash proof systems . We show that smooth homomorphic projective hash proof systems include all Diverse Group Systems, as defined by Cramer and Shoup. Using this definition, we show that · Smooth homomorphic hash proof systems imply LTDFs. · Diverse group systems as defined in [CS02] imply LTDFs. These are the first known generic constructions of LTDFs. · Applying our generic construction the specific constructions of smooth hash proof systems given by Cramer and Shoup, we obtain the first construction of fully lossy trapdoor functions from the quadratic residuosity (QR) assumption. We also obtain a novel construction of LTDFs from Paillier's decisional composite residuosity (DCR) assumption. · Applying the black-box separation results of Rosen and Segev, we show that there is a black-box separation between smooth homomorphic hash proof systems and one-way trapdoor permutations.
In the third part of this work, Chapter 5, we examine in what situations we can construct lossy trapdoor functions from the seemingly weaker primitive lossy encryption.
Injective one-way trapdoor functions are one of the most fundamental cryptographic primitives. In this section we give a novel construction of injective trapdoor functions based on oblivious transfer for long strings. Our main result is to show that any 2-message statistically sender-private semi-honest oblivious transfer (OT) for strings longer than the sender randomness implies the existence of injective one-way trapdoor functions. This is perhaps surprising given the black box separation of injective one-way trapdoor functions from many common cryptographic protocols, e.g. IND-CCA encryption. As a tool for creating injective one-way trapdoor functions, we define a new notion of security for a public key encryption scheme called Randomness Dependent Message (RDM) security, and use it as a stepping stone for creating injective one-way trapdoor functions. (Abstract shortened by UMI.)
This paper provides the first efficient, standard-model, fully-secure schemes for some related and challenging forms of public-key encryption (PKE), namely deterministic and hedged PKE. These forms of PKE defend against subversion of random number generators, an end given new urgency by recent revelations on the nature and extent of such subversion. We resolve the (recognized) technical chal-lenges in reaching these goals via a new paradigm that combines UCEs (universal computational extractors) with LTDFs (lossy trapdoor functions). Crucially, we rely only on a weak form of UCE, namely security for statistically (rather than computationally) unpredictable sources. We then de-fine and achieve unique-ciphertext PKE as a way to defend against implementation subversion via
Functional encryption (FE) has more fine-grained control to encrypted data than traditional encryption schemes. The well-accepted security of FE is indistinguishability-based security (IND-FE) and simulation-based security (SIMFE), but the security is not sufficient.For example, if an adversary has the ability to access a vector of ciphertexts and can ask to open some information of the messages, such as coins used in the encryption or secret key in multikey setting, whether the privacy of the unopened messages is guaranteed.This is called selective opening attack (SOA).In this paper, we propose a stronger security of FE which is secure against SOA (we call SO-FE) and propose a concrete construction of SO-FE scheme in the standard model.Our scheme is a non-adaptive IND-FE which satisfies selective opening secure in the simulation sense.In addition, the scheme can encrypt messages of any bit length other than bitwise and it is secure against SOA-C and SOAK simultaneously while the two attacks were appeared in different model before.According to the different functionality f, our scheme can specialize as IBE, ABE and even PE schemes secure against SOA.
Receiver selective opening (RSO) attack for public key encryption (PKE) captures a situation where one sender sends messages to multiple receivers, an adversary can corrupt a set of receivers and get their messages and secret keys. Security against RSO attack for a PKE scheme ensures confidentiality of other uncorrupted receivers' ciphertexts. Among all of the RSO security notions, simulation-based RSO security against chosen ciphertext attack (SIM-RSO-CCA security) is the strongest notion. In this paper, we explore constructions of SIM-RSO-CCA secure PKE from various computational assumptions. Toward this goal, we show that a SIM-RSO-CCA secure PKE scheme can be constructed based on an IND-CPA secure PKE scheme and a designated-verifier non-interactive zero-knowledge (DV-NIZK) argument satisfying one-time simulation soundness. Moreover, we give the first construction of DV-NIZK argument satisfying one-time simulation soundness. Consequently, through our generic construction, we obtain the first SIM-RSO-CCA secure PKE scheme under the computational Diffie-Hellman (CDH) or learning parity with noise (LPN) assumption.