In this work we challenge the common misconception that information-theoretic (IT) privacy is too impractical to be used in the real-world: we propose to build simple and reusable IT-encryption solutions whose only efficiency penalty (compared to computationally-secure schemes) comes from a large secret key size, which is often a rather minor inconvenience, as storage is cheap. In particular, our solutions are stateless and locally computable at the optimal rate, meaning that honest parties do not maintain state and read only (optimally) small portions of their large keys with every use. Moreover, we also propose a novel architecture for outsourcing the storage of these long keys to a network of semi-trusted servers, trading the need to store large secrets with the assumption that it is hard to simultaneously compromise too many publicly accessible ad-hoc servers. Our architecture supports everlasting privacy and post-application security of the derived one-time keys, resolving two major limitations of a related model for outsourcing key storage, called bounded storage model. Both of these results come from nearly optimal constructions of so called doubly-affine extractors: locally-computable, seeded extractors Ext(X,S) which are linear functions of X (for any fixed seed S), and protect against bounded affine leakage on X. This holds unconditionally, even if (a) affine leakage may adaptively depend on the extracted key R = Ext(X,S); and (b) the seed S is only computationally secure. Neither of these properties are possible with general-leakage extractors.
In this work we challenge the common misconception that information-theoretic (IT) privacy is too impractical to be used in the real-world: we propose to build simple and reusable IT-encryption solutions whose only efficiency penalty (compared to computationally-secure schemes) comes from a large secret key size, which is often a rather minor inconvenience, as storage is cheap. In particular, our solutions are stateless and locally computable at the optimal rate, meaning that honest parties do not maintain state and read only (optimally) small portions of their large keys with every use. Moreover, we also propose a novel architecture for outsourcing the storage of these long keys to a network of semi-trusted servers, trading the need to store large secrets with the assumption that it is hard to simultaneously compromise too many publicly accessible ad-hoc servers. Our architecture supports everlasting privacy and post-application security of the derived one-time keys, resolving two major limitations of a related model for outsourcing key storage, called bounded storage model. Both of these results come from nearly optimal constructions of so called doubly-affine extractors: locally-computable, seeded extractors Ext(X,S) which are linear functions of X (for any fixed seed S), and protect against bounded affine leakage on X. This holds unconditionally, even if (a) affine leakage may adaptively depend on the extracted key R = Ext(X,S); and (b) the seed S is only computationally secure. Neither of these properties are possible with general-leakage extractors.
We address the problem of the-security of cryptographic protocols in face of future advances in computing technology and algorithmic research. The problem stems from the fact may be deemed that computations which at a given point in time may be deemed infeasible, can, in the course of years or decades, be made possible with improved hardware and/or breakthroughs in code-breaking algorithms. In such cases, the security of historical , but nonetheless highly confidential data may be in jeopardy. We present a scheme for efficient secure two-party communication with provable everlasting security. The security is guaranteed in face of any future technological advances, given the current state of of the art. Furthermore, the security of the messages is also guaranteed even if the secret encryption/decryption key is revealed in the future, The scheme is based on the bounded storage model and provides information-theoretic security in this model. The bounded storage model postulates an adversary who is computationally unbounded, and is only bounded in the amount of storage (not computation space) available to store the output of his computation. The bound on the storage can be arbitrarily large (e.g., 100 Tbytes), as long as it is fixed. Given this storage bound, our protocols guarantee that even a computationally all powerful adversary gains no information about a message (except with a probability that is exponentially small in the security parameter k). The bound on storage space need only hold at the time of the message transmission. Thereafter, no additional storage space or, computational power can help the adversary in deciphering the message. We present two protocols. The first protocol, which elaborates on the autoregressive (AR) protocol of Aumann and Rabin (see Advances in Cryptology-Crypto '99, p. 65-79, 1999), employs a short secret key whose size is independent of the length of the message, but uses many public random bits. The second protocol uses an optimal number of public random bits, but employs a longer secret key. Our proof of security utilizes a novel linear algebraic technique.
We study the classical problem of privacy amplification, where two parties Alice and Bob share a weak secret X of min-entropy k, and wish to agree on secret key R of length m over a public communication channel completely controlled by a computationally unbounded attacker Eve. Despite being extensively studied in the literature, the problem of designing “optimal ” efficient privacy amplification protocols is still open, because there are several optimization goals. The first of them is (1) minimizing the entropy loss L = k−m (it is known that the optimal value for L = O(λ), where ε = 2−λ is the desired security of the protocol). Other important considerations include (2) minimizing the number of communication rounds, (3) maintaining security even after the secret key is used (this is called post-application robustness), and (4) ensuring that the protocol P does not leak some “useful information ” about the source X (this is called source privacy). Additionally, when dealing with a very long source X, as happens in the so-called Bounded Retrieval Model (BRM), extracting as long a key as possible is no longer the goal. Instead, the goals are (5) to touch as little of X as possible (for efficiency), and (6) to be able to run the protocol many times on the same X, extracting multiple secure keys.
We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Since standard symmetrickey primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which Alice and Bob use W to agree on a nearly uniform key R, by communicating over a public channel controlled by an active adversary Eve. We study this question in the information theoretic setting where the attacker is computationally unbounded. We show that single-round (i.e. one message) protocols do not work when k ≤ n 2, and require poor parameters even when n 2 < k ≪ n. On the other hand, for arbitrary values of k, we design a communication efficient two-round (challenge-response) protocol extracting nearly k random bits. This dramatically improves the previous construction of Renner and Wolf [RW03], which requires Θ(λ + log(n)) rounds where λ is the security parameter. Our solution takes a new approach by studying and constructing “non-malleable” seeded randomness extractors — if an attacker sees a random seed X and comes up with an arbitrarily related seed X ′, then we bound the relationship between R = Ext(W;X) and R ′ = Ext(W;X ′). We also extend our two-round key agreement protocol to the “fuzzy ” setting, where Alice and Bob share “close ” (but not equal) secrets WA and WB, and to the Bounded Retrieval Model (BRM) where the size of the secret W is huge.
Motivated by applications in cryptography, we consider a generalization of randomness extraction and the related notion of privacy amplification to the case of two correlated sources. We introduce the notion of correlation extractors, which extract nearly perfect independent instances of a given joint distribution from imperfect, or "leaky," instances of the same distribution. More concretely, suppose that Alice holds a and Bob holds b, where (a, b) are obtained by taking n independent samples from a joint distribution (X, Y) and letting a include all X instances and b include all Y instances. An adversary Eve obtains partial information about (a, b) by choosing a function L with output length t and learning L(a, b). The goal is to design a protocol between Alice and Bob which may use additional fresh randomness, such that for every L as above the following holds. In the end of the interaction, Alice outputs a' and Bob outputs b' such that (a', b') are statistically indistinguishable from m independent instances of (X, Y) even when conditioned on Eve's view, and even when conditioned on the joint view of Eve together with either Alice or Bob. The standard questions of privacy amplification and randomness extraction correspond to the case where X and Y are identical random bits. In this work we address this question for other types of correlations. A central special case is that of OT extractors, which are correlation extractors for the correlation (X, Y) corresponding to the cryptographic primitive of oblivious transfer. Our main result is that for any finite joint distribution (X, Y) there is an explicit correlation extractor which extracts m = ?(n) instances using O(n) bits of communication, even when t = ?(n) bits of information can be leaked to Eve. We present several applications which motivate the concept of correlation extractors and our main result. These include: ? Protecting certain cryptographic protocols against sidechannel attacks. ? A protocol which realizes m instances of oblivious transfer by communicating only O(m) bits. The security of the protocol relies on a number-theoretic intractability assumption. ? A constant-rate unconditionally secure construction of oblivious transfer (for semi-honest parties) from any nontrivial channel. This establishes constant-rate equivalence of any two nontrivial finite channels.
Consider a sender 𝒮 and a group of n recipients. 𝒮 holds a secret message 𝗆 of length l bits and the goal is to allow 𝒮 to create a secret sharing of 𝗆 with privacy threshold t among the recipients, by broadcasting a single message 𝖼 to the recipients. Our goal is to do this with information theoretic security in a model with a simple form of correlated randomness. Namely, for each subset 𝒜 of recipients of size q, 𝒮 may share a random key with all recipients in 𝒜. (The keys shared with different subsets 𝒜 must be independent.) We call this Broadcast Secret-Sharing (BSS) with parameters l, n, t and q. Our main question is: how large must 𝖼 be, as a function of the parameters? We show that (n-t)/q l is a lower bound, and we show an upper bound of ((n(t+1)/(q+t)) -t)l, matching the lower bound whenever t = 0, or when q = 1 or n-t. When q = n-t, the size of 𝖼 is exactly l which is clearly minimal. The protocol demonstrating the upper bound in this case requires 𝒮 to share a key with every subset of size n-t. We show that this overhead cannot be avoided when 𝖼 has minimal size. We also show that if access is additionally given to an idealized PRG, the lower bound on ciphertext size becomes (n-t)/q λ + l - negl(λ) (where λ is the length of the input to the PRG). The upper bound becomes ((n(t+1))/(q+t) -t)λ + l. BSS can be applied directly to secret-key threshold encryption. We can also consider a setting where the correlated randomness is generated using computationally secure and non-interactive key exchange, where we assume that each recipient has an (independently generated) public key for this purpose. In this model, any protocol for non-interactive secret sharing becomes an ad hoc threshold encryption (ATE) scheme, which is a threshold encryption scheme with no trusted setup beyond a PKI. Our upper bounds imply new ATE schemes, and our lower bound becomes a lower bound on the ciphertext size in any ATE scheme that uses a key exchange functionality and no other cryptographic primitives.
Web-servers are a dominant medium of modern communication and thus process vast amounts of highly sensitive, private data. Social networks, online auctions, and all kinds of cloud services constitute popular examples of online services complying with this paradigm. Due to many alarming scandals regarding the misuse of private data, IT security solutions protecting this sensitive data (for example by hiding it through encryption) are indispensable. Ideally, web-servers should be able to compute on private data without seeing it - we refer to this as the "Secure Outsourcing of Computation". Most notably, the cryptographic primitive of Homomorphic Encryption (HE) enables the web-servers to process data in the encrypted domain, which thereby hides/protects all private data as it is never available in the clear. More precisely, HE is a type of encryption that allows for the computation of certain functionalities on encrypted data without knowledge of the decryption key. Depending on the HE scheme, various functionalities can be evaluated in the encrypted domain, ranging from additions or multiplications only (Group Homomorphic Encryption, GHE), to virtually any computable functionality (Fully Homomorphic Encryption, FHE). We provide a clean foundational framework for HE that permits security characterizations for a large class of HE schemes and shows strong similarities between GHE and FHE. We study these characterizations in order to assess the limits of HE, and show that GHE is obsolete in the quantum world, meaning that any GHE scheme can be broken by a quantum computer. Together with our newly constructed universal blueprint that encompasses virtually any GHE scheme, we know exactly how these schemes must be designed and what the underlying hardness assumptions must look like. To some extent, this rounds off the topic of GHE both in the standard and quantum model of computation. In the standard model (which is presently assumed to be the most realistic model of computation), GHE is still highly attractive as it provides very efficient solutions to a variety of practical problems. On the basis of our foundational framework, we construct new GHE schemes with unique features and show their employability in practical applications. Most importantly, we use the special features of one of these schemes and develop a novel technique to achieve a practically efficient solution to the problem of securely outsourcing computations. Our construction allows multiple users to send encryptions of their private data under their own keys to a distrusted web-server that can then, on behalf of the users, evaluate any dynamically chosen computable function on these inputs in the encrypted domain (even across encryptions under different public keys) without learning anything at all, and without interacting with the users.