Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Weighted information implies the joint security criterion

Proved
QAlgorithms.Papers.Independent.Intakenext100.P77.weighted_information_security

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let TTT be a finite transcript alphabet, let wt≥0w_t\ge0wt​≥0 with ∑twt≤1\sum_t w_t\le1∑t​wt​≤1 be joint probabilities of passing and transcript ttt, and let Jt≥0J_t\ge0Jt​≥0 be the information in that transcript. For every threshold a>0a>0a>0,

a∑t:Jt≥awt≤∑twtJt.a\sum_{t:J_t\ge a}w_t\le\sum_t w_tJ_t.at:Jt​≥a∑​wt​≤t∑​wt​Jt​.

In particular, for α∈R\alpha\in\mathbb Rα∈R, β>0\beta>0β>0, and n∈Nn\in\mathbb Nn∈N, if ∑twtJt≤e2(α−βn)\sum_t w_tJ_t\le e^{2(\alpha-\beta n)}∑t​wt​Jt​≤e2(α−βn), then

Pr⁡[pass and J≥eα−βn]≤eα−βn.\Pr[\mathrm{pass}\ \text{and}\ J\ge e^{\alpha-\beta n}]\le e^{\alpha-\beta n}.Pr[pass and J≥eα−βn]≤eα−βn.

The exponential threshold is positive even when the weighted information is zero. The probabilities are not normalized conditional on passing.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P77
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P77

open scoped BigOperators ComplexConjugate ComplexOrder

open QAlgorithms

-- The repair instruction authorizes imports of pinned accepted definitions.
-- These are definitions only; no imported paper theorem is used here.

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

open QAlgorithms.Papers.Independent.Information100.P04 (Measurement)

open QAlgorithms.Papers.Independent.Information100.P27 (shannon)

open QAlgorithms.Papers.Independent.Information100.P39 (pushLaw)

open QAlgorithms.Papers.Independent.Support50.P16 (trivialMeasurement)

attribute [local instance] Classical.propDecidable Classical.decEq

/-- Appendix N, PDF pp.28--29, Eqs.(45),(46): Markov's bound for subnormalized
pass weights and its positive exponential-threshold specialization. No sqrt(W)
threshold is used at W=0. -/
theorem weighted_information_security {T : Type} [Fintype T]
    (p : PassWeights T) (info : T → ℝ) (hi : ∀ t, 0 ≤ info t) :
    (∀ a : ℝ, 0 < a →
      luckyProbability p info a * a ≤ ∑ t, p.weight t * info t) ∧
    ∀ (alpha beta : ℝ), 0 < beta → ∀ n : ℕ,
      (∑ t, p.weight t * info t) ≤ Real.exp (2 * (alpha - beta * n)) →
      luckyProbability p info (Real.exp (alpha - beta * n)) ≤
        Real.exp (alpha - beta * n) := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P77

end
Source
A Proof of the Security of Quantum Key Distribution, arXiv:quant-ph/9912053v1, PDF p. 28, Appendix N: weighted-information bound implies security criterion
Read-back

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

Let TTT be any finite type, let weights wt∈Rw_t\in\mathbb Rwt​∈R satisfy wt≥0w_t\ge0wt​≥0 for every ttt and ∑twt≤1\sum_tw_t\le1∑t​wt​≤1, and let I:T→RI:T\to\mathbb RI:T→R satisfy I(t)≥0I(t)\ge0I(t)≥0 for every ttt. Define L(a)=∑t: a≤I(t)wtL(a)=\sum_{t:\,a\le I(t)}w_tL(a)=∑t:a≤I(t)​wt​, so equality with the threshold is included. Then both of the following hold:

∀a>0,aL(a)≤∑twtI(t),\forall a>0,\qquad aL(a)\le\sum_tw_tI(t),∀a>0,aL(a)≤t∑​wt​I(t),

and, for every α,β∈R\alpha,\beta\in\mathbb Rα,β∈R with β>0\beta>0β>0 and every n∈Nn\in\mathbb Nn∈N,

∑twtI(t)≤exp⁡(2(α−βn))⟹L ⁣(exp⁡(α−βn))≤exp⁡(α−βn).\sum_tw_tI(t)\le \exp(2(\alpha-\beta n)) \quad\Longrightarrow\quad L\!\left(\exp(\alpha-\beta n)\right)\le\exp(\alpha-\beta n).t∑​wt​I(t)≤exp(2(α−βn))⟹L(exp(α−βn))≤exp(α−βn).

There is no sign restriction on α\alphaα, n=0n=0n=0 is included, and neither total weight one nor nonemptiness of TTT is required; for empty TTT, all the finite sums are zero.

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

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 31, 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