Linking Information Reconciliation and Privacy Amplification
Christian Cachin and Ueli Maurer
Information reconciliation and privacy amplification are important tools in cryptography and information theory. Reconciliation allows two parties knowing correlated random variables, such as a noisy version of the partner's random bit string, to agree on a shared string. Privacy amplification allows two parties sharing a partially secret string, about which an opponent has some partial information, to distill a shorter but almost completely secret key by communicating only over an insecure channel, as long as an upper bound on the opponent's knowledge about the string is known. The relation between these two techniques has not been well understood and it is the purpose of this paper to provide the missing link between these techniques. The results have applications in unconditionally secure key agreement protocols and in quantum cryptography.