Privacy amplification is a nodal subroutine in which a party, or a set of honest parties, locally compress a partially secret classical string into a shorter string that is secure against an adversary. In quantum protocols, this subroutine usually appears after measurement and classical error correction. At that point, the honest parties may share identical or almost identical classical strings, but an adversary may still have partial classical or quantum side information about them.
The purpose of privacy amplification is to remove this residual information. The honest parties apply a publicly chosen randomness extractor, most commonly a universal hash function, to their reconciled string. The output is a shorter key that is close to uniform and close to independent of the adversary’s information.
This subroutine is widely used in quantum key distribution and secret-key agreement protocols. Its security is usually quantified by the trace distance between the real output key and an ideal uniformly random key independent of the adversary.
The subroutine can be described abstractly as follows.
The honest parties must share, or be able to agree on, the same reconciled string. In two-party protocols such as quantum key distribution, this is usually achieved by an earlier information-reconciliation or classical error-correction subroutine.
A common choice is a two-universal family of hash functions. A family $\\\mathcal{H}$ of functions from $\\\mathcal{X}$ to ${0,1}^{\\\ell}$ is two-universal if, for all distinct $x,x\’\\\in \\\mathcal{X}$,
$$
\\\Pr_{h\\\leftarrow \\\mathcal{H}}[h(x)=h(x\’)] \\\leq 2^{-\\\ell}.
$$
The conditional smooth min-entropy of $X$ given $E$ is denoted by
$$
H_{\\\min}^{\\\varepsilon}(X|E).
$$
This quantity measures how much randomness remains in $X$ from the point of view of an adversary holding $E$.
The goal is to compute a shorter string $K$ that is close to uniform and independent of $E$.
A public random seed $R$ is sampled and used to select a hash function
$$
h_R:\\\mathcal{X}\\\rightarrow {0,1}^{\\\ell}.
$$
The privacy-amplified key is
$$
K = h_R(X).
$$
In a two-party setting, Alice and Bob apply the same hash function to their reconciled strings:
$$
K_A = h_R(X_A),
$$
and
$$
K_B = h_R(X_B).
$$
If the preceding error-correction step was successful, then
$$
X_A = X_B,
$$
and therefore
$$
K_A = K_B.
$$
The security goal is that the joint state of the output key, the public seed, and the adversary’s side information is close to an ideal state in which the key is uniform and independent. This is commonly expressed as
$$ \\\frac{1}{2} |\\\rho_{KRE} – \\\tau_K \\\otimes \\\rho_{RE}| \\\leq \\\varepsilon_{\\\mathrm{sec}}$$
where $\\\tau_K$ is the fully mixed state on $\\\ell$-bit keys, $\\\rho_{KRE}$ is the real output state, and $\\\varepsilon_{\\\mathrm{sec}}$ is the secrecy error.
A standard sufficient condition is given by the leftover hash lemma. For a two-universal hash family, one may extract roughly
$$ \\\ell \\\leq H_{\\\min}^{\\\varepsilon_s}(X|E) – 2\\\log_2\\\left(\\\frac{1}{\\\varepsilon_{\\\mathrm{PA}}}\\\right) $$
bits, up to convention-dependent constants, with total secrecy error depending on the smoothing parameter $\\\varepsilon_s$ and the privacy-amplification error $\\\varepsilon_{\\\mathrm{PA}}$.
If public information $C$ was revealed during error correction, then the relevant entropy is the entropy conditioned on both the adversary’s side information and the public transcript:
$$
H_{\\\min}^{\\\varepsilon_s}(X|EC).
$$
Equivalently, if the public leakage is bounded by $\\\mathrm{leak}_{\\\mathrm{EC}}$ bits, one typically accounts for this by reducing the extractable length:
$$ \\\ell \\\lesssim H_{\\\min}^{\\\varepsilon_s}(X|E) – \\\mathrm{leak}{\\\mathrm{EC}} – 2\\\log_2\\\left(\\\frac{1}{\\\varepsilon{\\\mathrm{PA}}}\\\right). $$
The exact constants depend on the security convention and on the precise version of the leftover hash lemma used.
Common choices for privacy amplification include universal hashing, two-universal hashing, Toeplitz hashing, and other seeded randomness extractors. Toeplitz hashing is often used in practical QKD post-processing because it gives a universal hashing construction with efficient implementation.
Privacy amplification was introduced as a method for distilling a secret key from partially secret correlated data using public discussion [4,5]. It became a central component of quantum key distribution, where it is used after information reconciliation to remove any information that an eavesdropper may have gained.
In quantum cryptography, privacy amplification must remain secure even when the adversary holds quantum side information. This is captured by the quantum leftover hash lemma and by universally composable security definitions [2,3]. These results justify the use of two-universal hashing in QKD and related protocols.
Privacy amplification should be distinguished from classical error correction. Error correction aims to make honest parties’ strings agree. Privacy amplification aims to make the final agreed string secret. In QKD, these two subroutines usually appear in sequence: first information reconciliation, then privacy amplification.
To be added later
To be added later
To be added later
No content has been added to this section, yet!
No content has been added to this section, yet!
To be added later
No content has been added to this section, yet!
No refs