Exact privacy-amplification exponent under relative-entropy security
- Field
- Topics
Problem
What is the optimal exponential rate of decay of relative-entropy insecurity achievable by two-universal hashing against quantum side information at every positive extraction rate below the conditional entropy? Let \(\rho_{AE}=\sum_{a\in\mathcal A}p_a\lvert a\rangle\langle a\rvert\otimes\rho_E^a\) be a fixed finite-dimensional classical–quantum state, with \(\rho_E=\sum_a p_a\rho_E^a\). All logarithms are base two. Write \(S(\sigma)=-\operatorname{Tr}\sigma\log_2\sigma\) and \(H(A|E)_\rho=S(\rho_{AE})-S(\rho_E)\).
For \(n\) independent copies, choose a public random hash \(F_n:\mathcal A^n\to\{1,\ldots,M_n\}\), independently of the source. Two-universality means
For a realized function \(f\), let \(\rho^f_{Z_nE^n}\) be the state obtained by applying \(f\) to the classical register of \(\rho_{AE}^{\otimes n}\), and put \(\tau_{M_n}=I_{Z_n}/M_n\). With \(D(\omega\|\sigma)=\operatorname{Tr}\omega(\log_2\omega-\log_2\sigma)\), define
where the supremum ranges over sequences satisfying Eq. (1) and \(n^{-1}\log_2 M_n\to R\), and \(-\log_2 0=+\infty\). The hash family may depend on the fixed source state. Determine Eq. (2) for arbitrary \(\rho_{AE}\) and \(0<R<H(A|E)_\rho\), including the low-rate regime.
Source
Hayashi discusses the tightness question in Sections 8.14 and 8.21.4, pp. 434–435 and 461 [Hay17]. Li, Yao, and Hayashi formulate the exponent problem in Section IV and identify the unresolved low-rate regime in Section IV-B [LYH23]. Equation (2) preserves the supplied note’s optimization over two-universal families.
Progress
Reports do not certify correctness or automatically change the problem's status. Progress policy.
Define the fixed-marginal sandwiched conditional entropy by
\begin{equation} \widetilde H_{1+s}(A|E)_\rho=-\frac1s\log_2\operatorname{Tr}\!\left[\left((I_A\otimes\rho_E^{-s/(2(1+s))})\rho_{AE}(I_A\otimes\rho_E^{-s/(2(1+s))})\right)^{1+s}\right],\quad s>0, \tag{3} \end{equation}with inverses on the support and the continuous value \(H(A|E)_\rho\) at \(s=0\). Using Eq. (3), the known bounds are
\begin{equation} e_H(R):=\max_{0\leq s\leq1}s(\widetilde H_{1+s}(A|E)_\rho-R)\ \leq\ e_I(\rho_{AE},R)\ \leq\ \sup_{s\geq0}s(\widetilde H_{1+s}(A|E)_\rho-R). \tag{4} \end{equation}The upper bound in Eq. (4) holds even for the best deterministic hashes. Theorem 3 and Eq. (24) prove equality with \(e_H(R)\) when \(R\geq R_{\rm crit}:=\left.\frac{d}{ds}[s\widetilde H_{1+s}(A|E)_\rho]\right|_{s=1}\) [LYH23].
Section IV-B shows that the two bounds in Eq. (4) need not be tight at low rates [LYH23]. Thus the original suggestion that \(e_H\) is always exact has a negative answer; the remaining task is the exact exponent, rather than proving that suggestion.
Li, Qiu, and Zhang determine an exact exponent for sandwiched Rényi orders \(\alpha\geq2\) under independent uniform random binning; see Theorem 14 in Section 6.1 of their August 2026 v2 preprint. Their Section 7 explicitly leaves orders \(\alpha\in(0,2)\) open. This theorem concerns a specified ensemble and a different security divergence, so it does not determine Eq. (2) [LQZ26].
Comment
Audited on 2026-09-09 using the full source papers, including the August 2026 revision of [LQZ26]. The high-rate theorem does not solve the all-rate question. The reference state fixes the actual marginal \(\rho_E\); it is not optimized over an auxiliary state. The positive-rate restriction removes the degenerate choice \(M_n=1\), which has zero insecurity. Even at positive rates the exponent can be infinite: uniformly random balanced partitions of a uniform independent classical source can extract an exactly uniform key. A complete answer must accommodate such sources. The original unrestricted tightness suggestion is already false, while a general exact low-rate formula remains unknown. The statement concerns the relative-entropy criterion and optimization over two-universal families; neither a trace-distance exponent nor the exponent of a single prescribed family is an equivalent question.