Search

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]