Secret-key agreement over unauthenticated public channels-part I: definitions and a completeness result
IEEE Transactions on Information TheoryPublished 1 April 2003
Ueli Maurer, Stefan Wolf
Citations163
SJR quartileQ1
SJR score1.46
SNIP1.76
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The important special case where the legitimate partners as well as the adversary have access to the outcomes of many independent repetitions of a fixed tripartite random experiment is considered, and the result characterizing the possibility of secret-key agreement secure against active adversaries is of all-or-nothing nature.
Abstract
This is the first part of a three-part paper on secret-key agreement secure against active adversaries. In all three parts, we address the question whether two parties, knowing some correlated pieces of information X and Y, respectively, can generate a string S about which an adversary, knowing some information Z and having read and write access to the communication channel used by the legitimate partners, is almost completely ignorant. Whether such key agreement is possible, and if yes at which rate, is an inherent property of the joint probability distribution P/sub XYZ/. In this part, we first prove a number of general impossibility results. We then consider the important special case where the legitimate partners as well as the adversary have access to the outcomes of many independent repetitions of a fixed tripartite random experiment. In this case, the result characterizing the possibility of secret-key agreement secure against active adversaries is of all-or-nothing nature: either a secret key can be generated at the same rate as in the (well-studied) passive-adversary case, or such secret-key agreement is completely impossible. The exact condition characterizing the two cases is presented.
Keywords
Computer ScienceEngineering
IEEE Transactions on Information TheoryNew directions in cryptography
14,441 Citations1976Whitfield Diffie, Martin E. Hellman
Bell System Technical JournalCommunication Theory of Secrecy Systems*
9,330 Citations1949Claude E. Shannon
A theory of secrecy systems is developed on a theoretical level and is intended to complement the treatment found in standard works on cryptography.
Bell System Technical JournalThe Wire-Tap Channel
6,990 Citations1975A.D. Wyner
This paper finds the trade-off curve between R and d, assuming essentially perfect (“error-free”) transmission, and implies that there exists a Cs > 0, such that reliable transmission at rates up to Cs is possible in approximately perfect secrecy.
IEEE Transactions on Information TheoryBroadcast channels with confidential messages
3,378 Citations1978Imre Csiszár, János Körner
Given two discrete memoryless channels (DMC's) with a common input, a single-letter characterization is given of the achievable triples where R_{e} is the equivocation rate and the related source-channel matching problem is settled.
Journal of Computer and System SciencesUniversal classes of hash functions
2,573 Citations1979J.Lawrence Carter, Mark N. Wegman
An input independent average linear time algorithm for storage and retrieval on keys that makes a random choice of hash function from a suitable class of hash functions.
IEEE Transactions on Information TheorySecret key agreement by public discussion from common information
2,008 Citations1993Ueli Maurer
It is shown that such a secret key agreement is possible for a scenario in which all three parties receive the output of a binary symmetric source over independent binary symmetric channels, even when the enemy's channel is superior to the other two channels.
IEEE Transactions on Information TheoryGeneralized privacy amplification
1,379 Citations1995C. H. Bennett, Gilles Brassard +2 more
IEEE Transactions on Information TheoryCommon randomness in information theory and cryptography. I. Secret sharing
1,339 Citations1993Rudolf Ahlswede, Imre Csiszár
As the first part of a study of problems involving common randomness at distance locations, information-theoretic models of secret sharing (generating a common random key at two terminals, without letting an eavesdropper obtain information about this key) are considered.
SIAM Journal on ComputingPrivacy Amplification by Public Discussion
867 Citations1988Charles H. Bennett, Gilles Brassard +1 more
This paper investigates how the use of a channel with perfect authenticity but no privacy can be used to repair the defects of a channels with imperfect privacy but no authenticity.
Lecture notes in computer scienceInformation-Theoretic Key Agreement: From Weak to Strong Secrecy for Free
508 Citations2000Ueli Maurer, Stefan Wolf
This paper shows that not only secret-key agreement satisfying the strong secrecy condition is possible, but even that the achievable key-generation rates are equal to the previous weak notions of secrecy capacity and secret- key rate.
IEEE Transactions on Information TheoryUnconditionally secure key agreement and the intrinsic conditional information
275 Citations1999Ueli Maurer, Stefan Wolf
A new conditional mutual information measure is defined, the intrinsic conditional Mutual information between S and Y when given Z, denoted by I(X;Y/spl darr/Z), which is an upper bound on S(X, Y/spl par/Z).
IEEE Transactions on Information TheorySecret-key agreement over unauthenticated public channels-part III: privacy amplification
157 Citations2003Ueli Maurer, Stefan Wolf
This work considers the special case where the legitimate partners already share a mutual string which might, however, be partially known to the adversary, and proposes two protocols, one based on universal hashing and onebased 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.
Lecture notes in computer scienceUniversal hashing and authentication codes
153 Citations2007Douglas R. Stinson
IEEE Transactions on Information TheorySecret-key agreement over unauthenticated public channels-part II: the simulatability condition
100 Citations2003Ueli Maurer, Stefan Wolf
A new formalism, based on a mechanical model for representing the involved quantities, that allows for dealing with discrete joint distributions of random variables and their manipulations by noisy channels, is introduced and it is shown that this representation leads to a simple and efficient characterization of the possibility of secret-key agreement secure against active adversaries.
Lecture notes in computer scienceInformation-Theoretically Secure Secret-Key Agreement by NOT Authenticated Public Discussion
96 Citations1997Ueli Maurer
The goal of this paper is to investigate information-theoretic security even against active adversaries with complete control over the communication channel connecting the two parties who want to agree on a secret key.
Lecture notes in computer scienceCodes for Interactive Authentication
45 Citations2007Pete Gemmell, Moni Naor
This paper provides a single-round authentication protocol which requires log(n) + 5 log(1/p) bits of secrecy and introduces authentication protocols with more than one round of communication (multi-round protocols) and shows a lower bound of log(k)(n) on the number of shared random bits in a k-round protocol.
AlgorithmicaLinking Classical and Quantum Key Agreement: Is There a Classical Analog to Bound Entanglement?
37 Citations2002Gisin, Renner +1 more
It is proved that a quantum state between two parties is entangled if and only if the classical random variables resulting from optimal measurements provide some mutual classical information between the parties.
Lecture notes in computer scienceLinking Classical and Quantum Key Agreement: Is There “Bound Information”?
36 Citations2000Nicolas Gisin, Stefan Wolf
It is proved that a quantum state between two parties is entangled if and only if the classical random variables resulting from optimal measurements provide some mutual classical information between the parties.
Lecture notes in computer scienceTowards characterizing when information-theoretic secret key agreement is possible
29 Citations1996Ueli Maurer, Stefan Wolf
It is shown that secret key agreement is possible if and only if I(X;Y¦Z) >0, i.e., under the sole condition that X and Y have some (arbitrarily weak) statistical dependence when given Z.