Abstract Lossy trapdoor functions (LTFs), introduced by Peikert and Waters (STOC’08), have already been found to be a very useful tool in constructing complex cryptographic primitives in a black-box manner, such as one-way trapdoor functions, deterministic public-key encryption, CCA-secure public-key encryption, etc. Due to the existence of the side-channel attack, the leakage of trapdoor information in lossy trapdoor function systems can lead to the impossibility of provable security. Recently, Zhang et al. introduced a model of consecutive and continual leakage-resilient and updatable lossy trapdoor functions (ULTFs) and provided a concrete construction to achieve the security. Meanwhile, they proposed a consecutive and continual leakage-resilient public-key encryption scheme. However, in this paper, we demonstrate that the correctness of injective function can not be satisfied. Furthermore, the attacker can easily distinguish the evaluation key of ULTFs generated by the challenger according to the security model. Finally, we show two new constructions based on the continual leakage-resilient public-key encryption scheme of Brakerski et al. (FOCS 2010) and demonstrate the security of our scheme in the consecutive and continual leakage model.
Abstract Lossy trapdoor functions (LTFs), introduced by Peikert and Waters (STOC’08), have already been found to be a very useful tool in constructing complex cryptographic primitives in a black-box manner, such as one-way trapdoor functions, deterministic public-key encryption, CCA-secure public-key encryption, etc. Due to the existence of the side-channel attack, the leakage of trapdoor information in lossy trapdoor function systems can lead to the impossibility of provable security. Recently, Zhang et al. introduced a model of consecutive and continual leakage-resilient and updatable lossy trapdoor functions (ULTFs) and provided a concrete construction to achieve the security. Meanwhile, they proposed a consecutive and continual leakage-resilient public-key encryption scheme. However, in this paper, we demonstrate that the correctness of injective function can not be satisfied. Furthermore, the attacker can easily distinguish the evaluation key of ULTFs generated by the challenger according to the security model. Finally, we show two new constructions based on the continual leakage-resilient public-key encryption scheme of Brakerski et al. (FOCS 2010) and demonstrate the security of our scheme in the consecutive and continual leakage model.
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.
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.
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.
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.)
Injective one-way trapdoor functions are one of the most fundamental cryptographic primitives. In this work 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 semihonest oblivious transfer (OT) for strings longer than the sender randomness implies the existence of injective one-way trapdoor functions. This is perhaps surprising given 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. Our main result has a number of interesting corollaries: • Applying the results of Mol and Yilek (PKC ’10), we also show that Lossy Encryption with long plaintexts implies correlated product secure functions and INDCCA secure encryption. • Lossy encryption with long plaintexts implies a weak form of RDM security. In addition, Hemenway, Libert, Ostrovsky and Vergnaud (ePrint ’09) showed that statistically-hiding 2-round Oblivious Transfer (OT) is equivalent to Lossy Encryption, where if OT uses randomness shorter than the message so does Lossy Encryption and vice versa. Thus, our main result also implies an injective one-way trapdoor function from any lossy encryption with short randomness. This is somewhat surprising since injective trapdoor functions are deterministic and, given the trapdoor, allow recovery of a complete inverse, while public-key encryptions are probabilistic and recover only the plaintext and not necessarily the randomness used in the encryption process. Our result corroborates the previous result of Bellare, Halevi, Sahai and Vadhan (CRYPTO ’98) showing that IND-CPA secure encryption implies injective one-way trapdoor permutations in the random oracle model. We stress that in our work we do not make use of a random oracle.