We introduce the concept of selectable knowledge, which models the information stored in an arbitrary (e.g., quantum mechanical) device. We then analyze a situation where an entity A holds selectable knowledge about some random variable X and quantify the information A has about the output H(X) of a randomly chosen function H applied to X. This generalizes the setting of privacy amplification by universal hashing. In particular, our result can be used to prove that privacy amplification remains secure even if the enemy possesses quantum instead of classical information.
We introduce the concept of selectable knowledge, which models the information stored in an arbitrary (e.g., quantum mechanical) device. We then analyze a situation where an entity A holds selectable knowledge about some random variable X and quantify the information A has about the output H(X) of a randomly chosen function H applied to X. This generalizes the setting of privacy amplification by universal hashing. In particular, our result can be used to prove that privacy amplification remains secure even if the enemy possesses quantum instead of classical information.
We address the question whether quantum memory is more powerful than classical memory. In particular, we consider a setting where information about a random n-bit string X is stored in s classical or quantum bits, for s<n, i.e., the stored information is bound to be only partial. Later, a randomly chosen predicate F about X has to be guessed using only the stored information. The maximum probability of correctly guessing F(X) is then compared for the cases where the storage device is classical or quantum mechanical, respectively. We show that, despite the fact that the measurement of quantum bits can depend arbitrarily on the predicate F, the quantum advantage is negligible already for small values of the difference n-s. Our setting generalizes the setting of Ambainis et al. who considered the problem of guessing an arbitrary bit (i.e., one of the n bits) of X. An implication for cryptography is that privacy amplification by universal hashing remains essentially equally secure when the adversary's memory is allowed to be quantum rather than only classical. Since privacy amplification is a main ingredient of many quantum key distribution (QKD) protocols, our result can be used to prove the security of QKD in a generic way.
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.
Privacy amplification is an indispensable step in the post-processing of quantum key distribution, which can be used to compress the redundancy of shared key and improve the security level of the key. The commonly used privacy amplification is based on the random selection of universal hash functions, which needs the help of an additional random source, while it does not exist in general. In this paper, we propose a privacy amplification scheme based on composite coding, which is an extension of quantum CSS codes to classical linear codes. Compared with the universal hashing function, the proposed scheme does not need other random sources, and the randomness can be completely provided by the qubit string. Furthermore, the information-theoretic bound for the extraction of the key is obvious in composite coding.
This is the third part of a three-part paper on se- cret-key agreement secure against active adversaries. Here, we con- sider 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 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 ac- tive adversary and propose two protocols, one based on universal hashing and one based on extractors, allowing for privacy ampli- fication secure against an adversary whose knowledge about the initial partially string is limited to one third of the length of this string. Our results are based on novel techniques for au- thentication secure even against adversaries knowing a substantial amount of the secret key. information about . From Eve's point of view, the length of can in this case be roughly equal to the Renyi entropy of . In this paper, we investigate the same problem under the as- sumption that the communication between Alice and Bob is not authenticated. Note that, in contrast to the model where many independent repetitions of the involved random variables are given (15), the same piece of information must be used here both for authentication and as the input for privacy amplifica- tion. Two problems that arise in this context are authentication with an only partially key, and the fact that this authenti- cation leaks information about , hence potentially also about , to the adversary. We show that for our purpose, a new, inter- active, authentication method is better than one-way authentica- tion by strongly universal hashing, and that so-called extractors, requiring fewer random bits (i.e., shorter messages to be com- municated), are a better technique for privacy amplification than
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.
Privacy amplification is the task by which two cooperating parties transform a shared weak secret, about which an eavesdropper may have side information, into a uniformly random string uncorrelated from the eavesdropper. Privacy amplification against passive adversaries, where it is assumed that the communication is over a public but authenticated channel, can be achieved in the presence of classical as well as quantum side information by a single-message protocol based on strong extractors. In 2009 Dodis and Wichs devised a two-message protocol to achieve privacy amplification against active adversaries, where the public communication channel is no longer assumed to be authenticated, through the use of a strengthening of strong extractors called non-malleable extractors which they introduced. Dodis and Wichs only analyzed the case of classical side information. We consider the task of privacy amplification against active adversaries with quantum side information. Our main result is showing that the Dodis-Wichs protocol remains secure in this scenario provided its main building block, the non-malleable extractor, satisfies a notion of quantum-proof non-malleability which we introduce. We show that an adaptation of a recent construction of non-malleable extractors due to Chattopadhyay et al. is quantum proof, thereby providing the first protocol for privacy amplification that is secure against active quantum adversaries. Our protocol is quantitatively comparable to the near-optimal protocols known in the classical setting.