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
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
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.
Abstract. Lossy Trapdoor Functions (LTDFs), introduced by Peikert and Waters (STOC 2008) have been useful for building many cryptographic primitives. In particular, by using an LTDF that loses a (1 − 1/ω(log n)) fraction of all its input bits, it is possible to achieve CCA security using the LTDF as a black-box. Unfortunately, not all candidate LTDFs achieve such a high level of lossiness. In this paper we drastically improve upon previous results and show that an LTDF that loses only a non-negligible fraction of a single bit can be used in a black-box way to build numerous cryptographic primitives, including oneway injective trapdoor functions, CPA secure public-key encryption (PKE), and CCA-secure PKE. We then describe a novel technique for constructing such slightly-lossy LTDFs and give a construction based on modular squaring.
In security proofs of cryptographic schemes, various kinds of assumptions have been used.Among those assumptions, the hardness of the factoring problem, called the factoring assumption, is one of the most reliable assumptions.In this dissertation, we study constructions of factoring-based cryptographic schemes.First we study a cryptographic primitive called a self-bilinear map.We define a relaxed version of a self-bilinear map, which we call a self-bilinear maps with auxiliary information (AI-SBM).We construct an AI-SBM based on the factoring assumption and the existence of indistinguishability obfuscation (iO).We also show that AI-SBM can be used for constructing cryptographic schemes including multiparty key exchange, broadcast encryption, attribute-based encryption and homomorphic signatures.As a side result, we construct a somewhat homomorphic encryption for NC 1 circuits based on the Φ-hiding assumption and the existence of iO.Second we study a cryptographic primitive called lossy trapdoor function (LTDF).We define a relaxed version of an LTDF which we call an adversary-dependent lossy trapdoor functions (ad-LTDF).Then we show that in many applications of LTDFs, we can replace LTDFs with ad-LTDFs.Moreover, we give a construction of ad-LTDFs based on the factoring assumption w.r.t.semi-smooth RSA subgroup moduli (SS moduli), which is a special type of RSA moduli introduced by Groth.As a result, we almost automatically obtain new constructions of a collision resistant hash function, CPA secure PKE scheme and DPKE scheme based on the same assumption.Especially, our DPKE scheme is the first scheme that satisfies the security notion called the PRIV security for block sources proposed by Boldyreva et al. solely based on the factoring assumption.Besides direct applications of ad-LTDFs, we construct a CCA secure PKE scheme based on the factoring assumption w.r.t.SS moduli whose ciphertext overhead is the shortest among schemes based on the same assumption.
Abstract Hedged public-key encryption (HPKE), introduced by Bellare et al. (ASIACRYPT 2009), provides useful security when the per-message randomness fails to be uniform due to faulty implementations or adversarial actions. The HPKE scheme achieves IND-CPA (chosen plaintext attack) security when the randomness they used is of high quality, but, when the randomness is poor quality, rather than breaking completely, it achieves a weaker but a useful notion of security called IND-CDA (chosen distribution attack) as long as the message and randomness together have sufficient min-entropy. However, little research on HPKE in the presence of key leakage was done. In this paper, we study HPKE featuring key leakage-resilience and formulate appropriate security notion for key leakage-resilient HPKE. We work in the continual key leakage model where the secret key is refreshed periodically and an adversary can learn arbitrary but bounded leakage on the secret key between the updates. We present two generic constructions of continual leakage-resilient HPKE in the standard model by using a continual leakage-resilient all-but-one lossy trapdoor function. Finally, we give an instantiation of leakage-resilient HPKE under the linear assumption in bilinear groups.
Public-key encryption (PKE) is an extremely useful cryptographic primitive, seeing constant use when browsing the internet. A PKE scheme is a simple way for users to communicate securely without exchanging any secret keys beforehand. However, PKE by itself only enables one-to-one communication. For example, in the simple setting of group messaging, where a user wishes to send a message to many other users simultaneously, vanilla PKE can become quite inefficient. In the decades following the introduction of PKE, numerous “advanced PKE” primitives were introduced. These include broadcast encryption, attributed-based encryption, functional encryption, threshold encryption, and many more. Such primitives typically achieve their additional functionality by assuming the existence of a central user who provides keys for the other users. Since this trust assumption is quite strong, there has been a recent line of work investigating the removal of such a trust assumption while still retaining the advanced functionality. Currently, these so-called trustless advanced PKE schemes can be constructed from pairing-based assumptions or strong tools like indistinguishability obfuscation and witness encryption. Notably, none of these schemes enjoy security from a reasonable post-quantum assumption. In this work, we make progress on filling this gap by constructing the first trustless advanced PKE schemes from simple lattice assumptions.