# Information-theoretically provable Privacy Amplification?

In Quantum Key Distribution, the distributed key is produced by Privacy Amplification (also known as key distillation). An ID Quantique whitepaper introduces it with a

Rudimentary Privacy Amplification Protocol
Let us consider a two-bit key shared by the emitter and the receiver and let us assume that it is 01. Let us further assume that the eavesdropper knows the first bit of the key but not the second one: 0?.
The simplest privacy amplification protocol consists in calculating the sum, without carry, of the two bits and to use the resulting bit as the final key. The legitimate users obtain 0 + 1 = 1. The eavesdropper does not know the second bit. For him, this operation could be either 0 + 0 = 0 or 0 + 1 = 1. He has no way to decide which one is the correct one. Consequently, he does not have any knowledge on the final key. There is a cost. This privacy amplification protocol shortens the key by 50%. In practice, more efficient protocols have obviously been developed.

Updated formal definition: In this question, Privacy Amplification aims at deterministically producing as much as possible nearly secret uniformly random and independent bits, rigorously bounding the advantage any distinguisher may give, when given as input

• $n$ partially secret bits, having been significantly and individually probed or/and influenced by an adversary, so that the remaining secret entropy is $\ge s\,n$ bit for some known $s\ll1$ (say $s=1/4$ );
• and optionally, some extra public uniformly random bits, assumed independent including of the partially secret bits;
• and optionally, as few as possible extra secret uniformly random bits, assumed independent including of the partially secret and extra public bits.

The classical cryptographer could use a hash and ignore the optional extras, but that relies on unproven mathematical hypothesis, that Quantum Cryptography aims at replacing with physical hypothesis. What provable methods does Information Theory bring to the rescue? Can we do without the optional extras?

Full disclosure: I'm trying to plug a hole at B.2 there.

Note: Extra public bits are used in Chi-Hang Fred Fung, Xiongfeng Ma, H. F. Chau Practical issues in quantum-key-distribution postprocessing (in Phys. Rev. A, 2010). Extra secret bits are a figment of my imagination.

• I think it's crucial to state precisely, what the evesdropper may know. The example to destill two bits into one works fine, and that's enough for a coin toss. But the difficult part is the generalization, when the output should be more than one bit and the evesdropper learns some bits at arbitrary positions. The output function would require a uniform distribution under all partitions of the input space by fixing some input bits. My intuition is, this goes more into the direction of high non-linearity and not information theoretic security. – tylo Sep 18 '17 at 13:37
• @tylo: in the use case in QKD, an adversary can have up to full knowledge on some input bits of his/her choice, but only at the price of increasing an error rate at an earlier step (Reconciliation). When we reach Privacy Amplification, it is known this error rate was small enough that, at a demonstrable and high confidence level (and under other hypothesis like quality of RNGs, and more), at least $n\,s$ bit worth of true entropy remains, spread over the $n$ bits in some unspecified, adversary-controlled way. – fgrieu Sep 18 '17 at 14:16