Revision History for: Privacy Amplification Subroutines
- 2026-06-07 at 17:46 by Mina Doosti
Introduction
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.
Outline
The subroutine can be described abstractly as follows.
- Input. The honest party or parties hold a classical string $X$. In a two-party setting, Alice and Bob hold reconciled strings $X_A$ and $X_B$, ideally satisfying $X_A=X_B$.
- Entropy estimate. The protocol estimates or lower-bounds the amount of secrecy remaining in $X$ against the adversary’s side information $E$. This is often expressed using conditional min-entropy.
- Choice of extractor. The parties agree on a family of hash functions. A public random seed $R$ is used to select a particular hash function $h_R$.
- Compression. The parties compute a shorter output string by applying the selected hash function to the reconciled string.
- Output. The output is a shorter key $K$. The subroutine succeeds if $K$ is close to uniformly random and independent of the adversary’s information, except with a small security error.
- Abort condition. If the estimated entropy is too small to extract a key of the desired length, the protocol outputs abort.
Assumptions
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.
Notation
- $X$ denotes the raw or reconciled classical string held by the honest party. In a two-party setting, Alice and Bob hold strings $X_A$ and $X_B$.
- $E$ denotes the adversary’s side information. In quantum security analyses, $E$ may be a quantum system correlated with $X$.
- $R$ denotes the public random seed used to select a hash function $h_R$ from a family $\\\mathcal{H}$.
- $\\\ell$ is the desired output length. The privacy-amplified key is denoted by $K \\\in {0,1}^{\\\ell}$.
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$.
Properties
- Secrecy amplification. The subroutine transforms a partially secret string into a shorter string with stronger secrecy guarantees.
- Compression. Privacy amplification necessarily shortens the input string. The output length must be chosen according to the amount of entropy remaining against the adversary.
- Public seed. The hash seed can be announced publicly. The seed must be independent of the input string and the adversary’s side information, but it does not need to be secret.
- Composable security. In modern security definitions, the output key should be close to an ideal key that is uniform and independent of the adversary. This allows the key to be safely used in later cryptographic tasks.
- Robustness to quantum side information. In quantum cryptography, the adversary may hold quantum information. The quantum leftover hash lemma gives security guarantees for privacy amplification in this setting [2,3].
- Dependence on leakage. Any public information revealed during earlier steps, especially error correction, reduces the entropy available for extraction.
- Abort possibility. If the estimated entropy is too low, the subroutine should output abort rather than produce an insecure key.
Technical description
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.
Further information
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.
References
- R. Renner and R. König, “Universally composable privacy amplification against quantum adversaries,” in Theory of Cryptography Conference, TCC 2005, Lecture Notes in Computer Science, vol. 3378, Springer, 2005.
- M. Tomamichel, C. Schaffner, A. Smith, and R. Renner, “Leftover Hashing Against Quantum Side Information,” IEEE Transactions on Information Theory, vol. 57, no. 8, pp. 5524–5535, 2011.
- C. H. Bennett, G. Brassard, and J.-M. Robert, “Privacy Amplification by Public Discussion,” SIAM Journal on Computing, vol. 17, no. 2, pp. 210–229, 1988.
- C. H. Bennett, G. Brassard, C. Crépeau, and U. M. Maurer, “Generalized Privacy Amplification,” IEEE Transactions on Information Theory, vol. 41, no. 6, pp. 1915–1923, 1995.
- 2026-04-15 at 13:11 by Mina Doosti
Introduction
To be added later
Outline
To be added later
Assumptions
To be added later
Notation
No content has been added to this section, yet!
Properties
No content has been added to this section, yet!
Technical description
To be added later
Further information
No content has been added to this section, yet!
References
No refs