The task of privacy amplification, in which Alice holds some partially secret information with respect to an adversary Eve and wishes to distill it until it is completely secret, is known to be solvable almost optimally in both the classical and quantum worlds. Unfortunately, when considering an adversary who is limited only by nonsignaling constraints such a statement cannot be made in general. We here consider systems which violate the chained Bell inequality and prove that under the natural assumptions of a time-ordered nonsignaling system, which allow past subsystems to signal future subsystems (using the device's memory for example), superpolynomial privacy amplification by any hashing is impossible. This is of great relevance when considering practical device-independent key-distribution protocols which assume a superquantum adversary.
The task of privacy amplification, in which Alice holds some partially secret information with respect to an adversary Eve and wishes to distill it until it is completely secret, is known to be solvable almost optimally in both the classical and quantum worlds. Unfortunately, when considering an adversary who is limited only by nonsignaling constraints such a statement cannot be made in general. We here consider systems which violate the chained Bell inequality and prove that under the natural assumptions of a time-ordered nonsignaling system, which allow past subsystems to signal future subsystems (using the device's memory for example), superpolynomial privacy amplification by any hashing is impossible. This is of great relevance when considering practical device-independent key-distribution protocols which assume a superquantum adversary.
In the past few years there was a growing interest in proving the security of cryptographic protocols, such as key distribution protocols, from the sole assumption that the systems of Alice and Bob cannot signal to each other. This can be achieved by making sure that Alice and Bob perform their measurements in a space-like separated way (and therefore signalling is impossible according to the non-signalling postulate of relativity theory) or even by shielding their apparatus. Unfortunately, it was proven in [E. Haenggi, R. Renner, and S. Wolf. The impossibility of non-signaling privacy amplification] that, no matter what hash function we use, privacy amplification is impossible if we only impose non-signalling conditions between Alice and Bob and not within their systems. In this letter we reduce the gap between the assumptions of Haenggi et al. and the physical relevant assumptions, from an experimental point of view, which say that the systems can only signal forward in time within the systems of Alice and Bob. We consider a set of assumptions which is very close to the conditions above and prove that the impossibility result of Haenggi et al. still holds.
We study the problem of "privacy amplification": key agreement between two parties who both know a weak secret w, such as a password. (Such a setting is ubiquitous on the internet, where passwords are the most commonly used security device.) We assume that the key agreement protocol is taking place in the presence of an active computationally unbounded adversary Eve. The adversary may have partial knowledge about w, so we assume only that w has some entropy from Eve's point of view. Thus, the goal of the protocol is to convert this non-uniform secret w into a uniformly distributed string R that is fully secret from Eve. R may then be used as a key for running symmetric cryptographic protocols (such as encryption, authentication, etc.).
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 problem of “privacy amplification”: key agreement between two parties who both know a weak secret w, such as a password. (Such a setting is ubiquitous on the internet, where passwords are the most commonly used security device.) We assume that the key agreement protocol is taking place in the presence of an active computationally unbounded adversary Eve. The adversary may have partial knowledge about w, so we assume only that w has some entropy from Eve’s point of view. Thus, the goal of the protocol is to convert this non-uniform secret w into a uniformly distributed string R that is fully secret from Eve. R may then be used as a key for running symmetric cryptographic protocols (such as encryption, authentication, etc.). Because we make no computational assumptions, the entropy in R can come only from w. Thus such a protocol must minimize the entropy loss during its execution, so that R is as long as possible. The best previous results have entropy loss of Θ(κ 2), where κ is the security parameter, thus requiring the password to be very long even for small values of κ. In this work, we present the first protocol for information-theoretic key agreement that has entropy loss linear in the security parameter. The result is optimal up
For pt. II see ibid., vol.49, no.4, p.832-38 (2003). Here, we consider the special case where the legitimate partners already share a mutual string which might, however, be partially known to the adversary. The problem of generating a secret key in this case has been well studied in the passive-adversary model - for instance, in the context of quantum key agreement - under the name of privacy amplification. We consider the same problem with respect to an active adversary and propose two protocols, one based on universal hashing and one based on extractors, allowing for privacy amplification secure against an adversary whose knowledge about the initial partially secret string is limited to one third of the length of this string. Our results are based on novel techniques for authentication secure even against adversaries knowing a substantial amount of the "secret" key.
This paper examines classical privacy amplification using a universal family of hash functions. In quantum key distribution, the adversary's measurement can wait until the choice of hash functions is announced, and so the adversary's information may depend on the choice. Therefore the existing result on classical privacy amplification, which assumes the independence of the choice from the other random variables, is not applicable to this case. This paper provides a security proof of privacy amplification which is valid even when the adversary's information may depend on the choice of hash functions. The compression rate of the proposed privacy amplification can be taken to be the same as that of the existing one with an exponentially small loss in secrecy of a final key.