We propose a general cryptographic primitive called lossy trapdoor functions (lossy TDFs), and we use it to develop new approaches for constructing several important cryptographic tools, including (injective) trapdoor functions, collision-resistant hash functions, oblivious transfer, and chosen ciphertext-secure cryptosystems (in the standard model). All of these constructions are simple, efficient, and black-box. We realize lossy TDFs based on a variety of cryptographic assumptions, including the hardness of the decisional Diffie–Hellman (DDH) problem and the hardness of the “learning with errors” problem (which is implied by the worst-case hardness of various lattice problems). Taken together, our results resolve some long-standing open problems in cryptography. They give the first injective TDFs based on problems not directly related to integer factorization and provide the first chosen ciphertext-secure cryptosystem based solely on worst-case complexity assumptions.
We propose a general cryptographic primitive called lossy trapdoor functions (lossy TDFs), and we use it to develop new approaches for constructing several important cryptographic tools, including (injective) trapdoor functions, collision-resistant hash functions, oblivious transfer, and chosen ciphertext-secure cryptosystems (in the standard model). All of these constructions are simple, efficient, and black-box. We realize lossy TDFs based on a variety of cryptographic assumptions, including the hardness of the decisional Diffie–Hellman (DDH) problem and the hardness of the “learning with errors” problem (which is implied by the worst-case hardness of various lattice problems). Taken together, our results resolve some long-standing open problems in cryptography. They give the first injective TDFs based on problems not directly related to integer factorization and provide the first chosen ciphertext-secure cryptosystem based solely on worst-case complexity assumptions.
Lossy trapdoor functions (LTFs) were first introduced by Peikert and Waters (STOC’08). Since their introduction, lossy trapdoor functions have found numerous applications. They can be used as tools to construct important cryptographic primitives such as injective one-way trapdoor functions, chosen-ciphertext-secure public key encryptions, deterministic encryptions, et al. In this paper, we focus on the lossy trapdoor functions in the presence of continuous leakage. We introduce the new notion of updatable lossy trapdoor functions (ULTFs) and give their formal definition and security properties. Based on these, we extend the security model to the LTFs against continuous leakage when the evaluation algorithm is leakage resilient. Under the standard DDH assumption and DCR assumption, respectively, we show two explicit lossy trapdoor functions against continuous leakage in the standard model. In these schemes, using the technology of matrix kernel, the trapdoor can be refreshed at regular intervals and the adversaries can learn unbounded leakage information on the trapdoor along the whole system life. At the same time, we also show the performance of the proposed schemes compared with the known existing continuous leakage resilient lossy trapdoor functions.
Lossy Trapdoor Functions (LTFs) was introduced by Peikert and Waters in 2008. The importance of the LTFs was justified by their numerous cryptographic applications, like the construction of injective one-way trapdoor functions, CCA-secure public-key encryption, etc. However, little research on application of LTFs to key-leakage resilient public-key encryption was done. In this article we introduce a new variant of LTFs featuring leakage-resilience, namely lrLTFs and give a realization of lrLTFs with leakage rate 1/Θ(κ) (where κ is the security parameter) under the Decisional Diffie-Hellman (DDH) assumption. We further improve the leakage rate to 1-o(1) over a composite-order group in which the Decisional Composite Residuosity (DCR) assumption holds. We also introduce a new notion of key-leakage attacks, which we call weak key-leakage attacks, for bridging the adaptive and non-adaptive key-leakage attacks in the setting of public-key cryptosystem. In this model, the leakage adversary only gets a part of public key before accessing to a leakage oracle. We show that lrLTFs imply public-key encryption schemes secure against chosen-ciphertext weak key-leakage attacks in a black-box sense.
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.)
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.
Inspired by the no-cloning theorem in quantum theory, a variety of quantum cryptographic primitives with unclonable functionalities, such as secure key leasing and copy protection, have been proposed and attracted significant attention. However, trapdoor functions (TDFs), fundamental primitives in public-key cryptography, have not been extensively studied in these areas. In this work, we initiate a study of TDFs in both secure key leasing and copy protection settings. We first introduce the definition of TDFs with secure key leasing (TDF-SKL), which enables leasing and deleting of quantum trapdoors. We formalize TDF-SKL both with and without domain sampler, and give a construction of TDF-SKL without domain sampler based on the LWE assumption and a construction of TDF-SKL with domain sampler based on any standard PKE schemes combined with hinting pseudorandom generators [Koppula and Waters, CRYPTO 2019]. Next, we define TDFs with copy protection (TDF-CP), where the inversion functionality is copy protected by a quantum trapdoor. We establish a construction of TDF-CP assuming indistinguishability obfuscation and the LWE assumption, following a modular framework of copy protection proposed by Ananth and Behera [CRYPTO 2024]. We also present applications of TDF-SKL and TDF-CP. Existing constructions of public-key encryption with secure key leasing (PKE-SKL) and single-decryptor encryption (SDE) suffer from a critical vulnerability: quantum decryption keys may be destroyed after decrypting maliciously chosen ciphertexts. We construct PKE-SKL schemes and SDE schemes with robust quantum decryption keys that remain reusable after decrypting arbitrary ciphertexts from TDF-SKL and TDF-CP, respectively.
We show how to construct a variety of "trapdoor" cryptographic tools assuming the worst-case hardness of standard lattice problems (such as approximating the length of the shortest nonzero vector to within certain polynomial factors). Our contributions include a new notion of trapdoor function with preimage sampling, simple and efficient "hash-and-sign" digital signature schemes, and identity-based encryption. A core technical component of our constructions is an efficient algorithm that, given a basis of an arbitrary lattice, samples lattice points from a discrete Gaussian probability distribution whose standard deviation is essentially the length of the longest Gram-Schmidt vector of the basis. A crucial security property is that the output distribution of the algorithm is oblivious to the particular geometry of the given basis.