Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§4.2: ideal KD has perfect equality, uniformity and privacy

Proved
QAlgorithms.Papers.Independent.Support50.P27.idealKD_perfect

by Goku · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let MMM be a public random key length with finite support, chosen with any distribution by the adversarial interface. Conditional on M=mM=mM=m, let ρ~m\widetilde\rho_mρ​m​ be Eve's normalized residual state. Ideal key distribution samples a fresh uniform mmm-bit string KKK, gives the same string to Alice and Bob, and leaves Eve's state equal to ρ~m\widetilde\rho_mρ​m​, independently of KKK. The value m=0m=0m=0 denotes abort and gives the unique empty key. If pideal(m)(a,b)=2−m1a=bp_{\mathrm{ideal}}^{(m)}(a,b)=2^{-m}\mathbf1_{a=b}pideal(m)​(a,b)=2−m1a=b​, then the equality-and-uniformity defect and conditional accessible information both vanish:

∑mPr⁡(M=m) ∥pideal(m)−pideal(m)∥1=0,∑mPr⁡(M=m) Iacc(KAKB:E∣M=m)=0.\sum_m\Pr(M=m)\,\lVert p_{\mathrm{ideal}}^{(m)}-p_{\mathrm{ideal}}^{(m)}\rVert_1=0, \qquad \sum_m\Pr(M=m)\,I_{\mathrm{acc}}(K_AK_B:E\mid M=m)=0.m∑​Pr(M=m)∥pideal(m)​−pideal(m)​∥1​=0,m∑​Pr(M=m)Iacc​(KA​KB​:E∣M=m)=0.

Because KA=KB=KK_A=K_B=KKA​=KB​=K, the second expression is exactly the privacy requirement for KKK in Eq. (5), optimized over measurements. Independence is conditional on the announced length, which Eve may know or control. This gives the perfect reference resource against which QKD output is compared.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P27
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Support50.P27

open scoped BigOperators Matrix ComplexConjugate ComplexOrder

open QAlgorithms.Papers.Independent.Dependency50.P07
  (CQData ensembleMean ensembleInformation accessibleInformation)

open QAlgorithms.Papers.Independent.Dependency50.P24 (Key)

open QAlgorithms.Papers.Independent.Dependency50.P47 (cqMatrix)

attribute [local instance] Classical.decEq Classical.propDecidable

/-- PDF p.10, Section 4.2: ideal KD has zero equality/uniformity defect and
zero accessible information about its identical keys, conditional on length.
The pair of keys determines the same random variable as K in Eq.(5).
Devil may choose the length law and cause abort; unconditional independence
of Eve and the publicly announced length is not asserted. -/
theorem idealKD_perfect {L : ℕ} {E : Type} [Fintype E] [Nonempty E]
    (D : KeyData L E) :
    equalityUniformityDefect D.lengthProb (idealBranch D) = 0 ∧
      (∑ m, D.lengthProb m * accessibleInformation (idealBranch D m)) = 0 := by sorry

end QAlgorithms.Papers.Independent.Support50.P27

end
Source
The Universal Composable Security of Quantum Key Distribution, arXiv:quant-ph/0409078v1, PDF p. 10, §4.2: ideal KD has perfect equality, uniformity and privacy
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

For every natural number LLL, finite nonempty type EEE, and data DDD comprising nonnegative weights w0,…,wLw_0,\ldots,w_Lw0​,…,wL​ summing to 111, probability laws pmp_mpm​ on {0,…,2m−1}2\{0,\ldots,2^m-1\}^2{0,…,2m−1}2, and positive semidefinite, trace-one matrices ρm,a,b\rho_{m,a,b}ρm,a,b​ on EEE, define ωm=∑a,bpm(a,b)ρm,a,b\omega_m=\sum_{a,b}p_m(a,b)\rho_{m,a,b}ωm​=∑a,b​pm​(a,b)ρm,a,b​ and um(a,b)=2−mu_m(a,b)=2^{-m}um​(a,b)=2−m when a=ba=ba=b, and 000 otherwise. The ideal branch at length mmm assigns probability um(a,b)u_m(a,b)um​(a,b) and the same state ωm\omega_mωm​ to every pair. The statement asserts both

∑m=0Lwm∑a,b∣um(a,b)−um(a,b)∣=0,∑m=0Lwm Amideal=0.\sum_{m=0}^{L}w_m\sum_{a,b}|u_m(a,b)-u_m(a,b)|=0, \qquad \sum_{m=0}^{L}w_m\,\mathcal A_m^{\mathrm{ideal}}=0.m=0∑L​wm​a,b∑​∣um​(a,b)−um​(a,b)∣=0,m=0∑L​wm​Amideal​=0.

Here Amideal\mathcal A_m^{\mathrm{ideal}}Amideal​ is the real supremum over all finite families Mt⪰0M_t\succeq0Mt​⪰0 with at least one outcome and ∑tMt=I\sum_tM_t=I∑t​Mt​=I, of H(um)+H(q)−H(J)H(u_m)+H(q)-H(J)H(um​)+H(q)−H(J), where J((a,b),t)=um(a,b)Re⁡tr⁡(Mtωm)J((a,b),t)=u_m(a,b)\operatorname{Re}\operatorname{tr}(M_t\omega_m)J((a,b),t)=um​(a,b)Retr(Mt​ωm​), q(t)=∑a,bJ((a,b),t)q(t)=\sum_{a,b}J((a,b),t)q(t)=∑a,b​J((a,b),t), and H(v)=−∑iv(i)log⁡2v(i)H(v)=-\sum_i v(i)\log_2v(i)H(v)=−∑i​v(i)log2​v(i) with zero summands interpreted as 000. Length 000, zero length weights, and zero branch probabilities are allowed.

Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me