The Emulatable Key Agreement Protocol. We now describe an emulatable key agreement protocol for a wiretap channel F C with γ < δ, that is, for which the channel to the eavesdropper Eve is more reliable than the channel to Bob. ∈ This is a small modification of a key agreement protocol from [Mau93, V]. For each γ, δ, the protocol specifies numbers s, A, n N, to be determined below. In addition, A = 2m + 1 is an odd number. The protocol consists of three phases: advantage distillation, information reconciliation and privacy amplification. − − ∈ J ƒ∈ J J ⊆ { } { } The goal of the advantage distillation step is to create a conceptual channel between Xxxxx and Xxx which is more reliable than the one between Xxxxx and Xxx. In our protocol, this step proceeds as follows. Xxxxx samples n random bits bi and encodes each bit b as a bitstring v in 0, 1 A by selecting uniformly at random a set 1, . . . , A of size m and setting the j-th coordinate of v to be 1 b if j and b if j . Note that this means m + 1 of the bits of the encoding equal b while the other m bits equal 1 b. Now, if for a given sent bit b, Bob receives a message of the form (c, c, . . . , c) for some c, we say Bob accepts the bit b and c is his guess about b. Now Xxxxx creates the bitstring bi1 bi2 . . . bis given by the first s bits accepted by Bob and Bob creates the bitstring ci1 ci2 . . . cis of his guesses. They both disregard the remaining bits. Alternatively, one can see Xxxxx’s encoding process as first encoding her bit with the repetition code and then introducing errors in exactly m positions. As we discuss in Section 3.2, the protocol is similar to that in [Mau93, V], except that the global error introduced here is of fixed weight m, rather than flipping each bit with certain probability. In Section 3.2 below, we discuss why we need this to introduce this modification. Yet, from the point of view of advantage distillation, the intuition why this protocol works is the same as in [Mau93]: namely, even though Xxx has more information over messages sent over the wiretap channel than Bob has, she has less information about the ones accepted by Bob; in other words, the probability that Bob decodes those bits correctly is higher than that of Xxx’s. We formalize this later. The information reconciliation step is carried out over the public channel. After this step, Xxxxx and Xxx will share a common bitstring with overwhelming probability, and Xxx is still guaranteed to have some uncertainty about it. In the description below, we use the...
