Search

In this paper, we propose the notion of adaptive all-but-one lossy trapdoor functions (aABO-LTFs), a variant of all-but-one lossy trapdoor functions. An aABO-LTF is parameterised by a set of branches. Given the lossy branch, the function statistically loses the information of its inputs. Given injective branches, the function is injective, and there is a trapdoor that enables efficient function inversion. What differentiates an aABO-LTF and an ABO-LTF is that for an aABO-LTF, the lossy branch is indistinguishable from the other branches even if the adversary gets to ask for function inversions on any injective branches apart from the lossy branch. We demonstrate the usefulness of the adaptivity of aABO-LTFs by providing generic and efficient constructions of an adaptively chosen-ciphertext secure (CCA-secure) public-key encapsulation mechanism (KEM) and an adaptive deterministic public-key encryption (DPKE) without random oracles using aABO-LTFs in a very simple black-box way. Our constructions are direct in the sense of that it avoids generic transformations using one-time signatures or message authentication codes typically found in standard model CCA-secure constructions. Moreover, we show that aABO-LTFs can be instantiated generically by lossy trapdoor primitives, including lossy trapdoor functions (LTFs) and identity-based (lossy) trapdoor functions (IB-LTFs). We also demonstrate that the lattice-based ABO-LTFs proposed by Alwen et al. (CRYPTO'13) are aABO-LTFs. Several existing CCA-secure KEM and DPKE schemes can be described by our generic constrictions. Therefore, our work unifies these seemingly unrelated schemes and explains the design principles behind these schemes. [ABSTRACT FROM AUTHOR]

We study how to make any deterministic encryption scheme probabilistic and secure against adaptively chosen ciphertext attacks. A new transpositional padding encryption scheme is proposed, with which we construct a universal scheme, namely, a transpositional padding encryption scheme, which has three novel attributes: 1) it can pad a given plaintext into several different values once the randomness is chosen while the previous padding schemes only pad a given plaintext into a fixed value; 2) it introduces the randomness into a ciphertext without employing hash function or random oracle, and; 3) it enables the encrypted message to contain more useful information that may exceed the upper limit of plaintext space. Then, we give this encryption scheme an instantiation of RSA, which is proven to be indistinguishable under adaptively chosen ciphertext attacks without random oracle that assumes a variant of the standard RSA problem. The variant problem is a novel arithmetic problem, and it is weaker than the standard RSA problem.

Cloud and remote storage, which has become the preferred method for reducing the security risk and safeguarding our data, is widely used for backups or outsourcing. Thus, for effective utilization of data, it is desirable to perform keyword queries directly over the encrypted data. In the single-data owner architecture, it is common to use symmetric encryption cryptography and allows only the holder who has the secret key to create searchable ciphertexts and trapdoors. In the multi-data owner (MDO) architecture, the scheme uses asymmetric encryption cryptography and allows anyone to create searchable ciphertexts under the public key, while the corresponding private key creates the trapdoors. In the real world, the data come from different providers. Thus, the MDO architecture may meet more applications. However, the existing solutions, in the MDO architecture, do not guarantee security for the trapdoors and provide only linear time search. In this paper, we present a comprehensive study of searching over encrypted data in the MDO architecture, and we propose a novel scheme that supports the inverted index structure, complex search, and dynamic update. After extensive analysis and several experiments, the results indicate that our proposed method is both efficient and secure. We believe that this is the first work that achieves trapdoor security and logarithmic time pairing free search over encrypted data in the MDO architecture.

Bellare, Boldyreva, and O’Neill (CRYPTO ’07) initiated the study of deterministic public-key encryption as an alternative in scenarios where randomized encryption has inherent drawbacks. The resulting line of research has so far guaranteed security only for adversarially chosen-plaintext distributions that are independent of the public key used by the scheme. In most scenarios, however, it is typically not realistic to assume that adversaries do not take the public key into account when attacking a scheme. We show that it is possible to guarantee meaningful security even for plaintext distributions that depend on the public key. We extend the previously proposed notions of security, allowing adversaries to adaptively choose plaintext distributions after seeing the public key, in an interactive manner. The only restrictions we make are that: (1) plaintext distributions are unpredictable (as is essential in deterministic public-key encryption), and (2) the number of plaintext distributions from which each adversary is allowed to adaptively choose is upper bounded by 2p, where p can be any predetermined polynomial in the security parameter and plaintext length. For example, with p=0 we capture plaintext distributions that are independent of the public key, and with p=O(slogs) we capture, in particular, all plaintext distributions that are samplable by circuits of size s. Within our framework we present both constructions in the random oracle model based on any public-key encryption scheme, and constructions in the standard model based on lossy trapdoor functions (thus, based on a variety of number-theoretic assumptions). Previously known constructions heavily relied on the independence between the plaintext distributions and the public key for the purposes of randomness extraction. In our setting, however, randomness extraction becomes significantly more challenging once the plaintext distributions and the public key are no longer independent. Our approach is inspired by research on randomness extraction from seed-dependent distributions. Underlying our approach is a new generalization of a method for such randomness extraction, originally introduced by Trevisan and Vadhan (FOCS ’00) and Dodis (Ph.D. Thesis, MIT, ’00). [ABSTRACT FROM AUTHOR]

Motivated by applications in large storage systems, we initiate the study of incremental deterministic public-key encryption. Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O'Neill (CRYPTO '07), provides an alternative to randomized public-key encryption in various scenarios where the latter exhibits inherent drawbacks. A deterministic encryption algorithm, however, cannot satisfy any meaningful notion of security for low-entropy plaintexts distributions, but Bellare et al. demonstrated that a strong notion of security can in fact be realized for relatively high-entropy plaintext distributions. In order to achieve a meaningful level of security, a deterministic encryption algorithm should be typically used for encrypting rather long plaintexts for ensuring a sufficient amount of entropy. This requirement may be at odds with efficiency constraints, such as communication complexity and computation complexity in the presence of small updates. Thus, a highly desirable property of deterministic encryption algorithms is incrementality: Small changes in the plaintext translate into small changes in the corresponding ciphertext. We present a framework for modeling the incrementality of deterministic public-key encryption. Our framework extends the study of the incrementality of cryptography primitives initiated by Bellare, Goldreich and Goldwasser (CRYPTO '94). Within our framework, we propose two schemes, which we prove to enjoy an optimal tradeoff between their security and incrementality up to lower-order factors. Our first scheme is a generic method which can be based on any deterministic public-key encryption scheme, and, in particular, can be instantiated with any semantically secure (randomized) public-key encryption scheme in the random-oracle model. Our second scheme is based on the Decisional Diffie-Hellman assumption in the standard model. The approach underpinning our schemes is inspired by the fundamental 'sample-then-extract' technique due to Nisan and Zuckerman (JCSS '96) and refined by Vadhan (J. Cryptology '04), and by the closely related notion of 'locally computable extractors' due to Vadhan. Most notably, whereas Vadhan used such extractors to construct private-key encryption schemes in the bounded-storage model, we show that techniques along these lines can also be used to construct incremental public-key encryption schemes. [ABSTRACT FROM AUTHOR]

We give generic constructions of several fundamental cryptographic primitives based on a new encryption primitive that combines circular security for bit encryption with the so-called reproducibility property (Bellare et al. in Public key cryptography-PKC 2003, vol. 2567, pp. 85-99, Springer, 2003). At the heart of our constructions is a novel technique which gives a way of de-randomizing reproducible public-key bit encryption schemes and also a way of reducing one-wayness conditions of a constructed trapdoor function family (TDF) to circular security of the base scheme. The main primitives that we build from our encryption primitive include k-wise one-way TDFs (Rosen and Segev in SIAM J Comput 39(7):3058-3088, 2010), chosen-ciphertext-attack-secure encryption and deterministic encryption. Our results demonstrate a new set of applications of circularly secure encryption beyond fully homomorphic encryption and symbolic soundness. Finally, we show the plausibility of our assumptions by showing that the decisional Diffie-Hellman-based circularly secure scheme of Boneh et al. (Advances in cryptology-CRYPTO 2008, vol. 5157, Springer, 2008) and the subgroup indistinguishability-based scheme of Brakerski and Goldwasser (Advances in cryptology-CRYPTO 2010, vol. 6223, pp. 1-20, Springer, 2010) are both reproducible. [ABSTRACT FROM AUTHOR]

with the rapid change in the technology and innovation in the last decade, big data analysis has gone for an exponential and tremendous growth and will most probably continue to perform spectacular developments due to the emergence of innovative trends and new interactive multimedia applications and the use of highly integrated systems driven by the rapid growth in information services and microelectronic devices. Up to yet, large no. of the existing mobile systems is mainly targeted to voice communications with low transmission rates. Big-Data has always been a part of our lives knowingly or unknowingly [7]. This is a particular review on known big-data systems that contain a set of tools and technique to load, extract and process and improve dissimilar datasets while leveraging the immensely and most parallel processing power to perform the idiosyncratic transformations and analysis. Big-Data" technology faces a list of technical challenges. [ABSTRACT FROM AUTHOR]

This paper addresses deterministic public-key encryption schemes (DE), which are designed to provide meaningful security when only source of randomness in the encryption process comes from the message itself. We propose a general construction of DE that unifies prior work and gives novel schemes. Specifically, its instantiations include: The security proofs for these schemes are enabled by three tools that are of broader interest: We also extend our result about computational entropy to the average case, which is useful in reasoning about leakage-resilient cryptography: leaking λ bits of information reduces the quality of computational entropy by a factor of 2 and its quantity by λ. [ABSTRACT FROM AUTHOR]

Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O'Neill (CRYPTO '07), provides an alternative to randomized public-key encryption in various scenarios where the latter exhibits inherent drawbacks. A deterministic encryption algorithm, however, cannot satisfy any meaningful notion of security when the plaintext is distributed over a small set. Bellare et al. addressed this difficulty by requiring semantic security to hold only when the plaintext has high min-entropy from the adversary's point of view. In many applications, however, an adversary may obtain auxiliary information that is related to the plaintext. Specifically, when deterministic encryption is used as a building block of a larger system, it is rather likely that plaintexts do not have high min-entropy from the adversary's point of view. In such cases, the framework of Bellare et al. might fall short from providing robust security guarantees. We formalize a framework for studying the security of deterministic public-key encryption schemes with respect to auxiliary inputs. Given the trivial requirement that the plaintext should not be efficiently recoverable from the auxiliary input, we focus on hard-to-invert auxiliary inputs. Within this framework, we propose two schemes: the first is based on the d-linear assumption for any d≥1 (including, in particular, the decisional Diffie-Hellman assumption), and the second is based on a rather general class of subgroup indistinguishability assumptions (including, in particular, the quadratic residuosity assumption and Paillier's composite residuosity assumption). Our schemes are secure with respect to any auxiliary input that is subexponentially hard to invert (assuming the standard hardness of the underlying computational assumptions). In addition, our first scheme is secure even in the multi-user setting where related plaintexts may be encrypted under multiple public keys. Constructing a scheme that is secure in the multi-user setting (even without considering auxiliary inputs) was identified by Bellare et al. as an important open problem. [ABSTRACT FROM AUTHOR]