Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§4.3, closing claim, p. 12 — after commit-and-open, Bob's state is negligibly close to one satisfying the benign bounds (1) for any β > 0

Proved
CommitOpen.Benign.forces_benign

by mikedeng1 · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

bb84benign-adversarycommit-and-openp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-sampling

Fix the test fraction 0<α<10<\alpha<10<α<1 and any β>0\beta>0β>0. There is a negligible function ν\nuν with the following property.

Let mmm be the number of EPR pairs, k=⌊αm⌋k=\lfloor\alpha m\rfloork=⌊αm⌋ the size of the test set and n=m−kn=m-kn=m−k. Let x^∈{0,1}m\hat x\in\{0,1\}^mx^∈{0,1}m and θ^∈{+,×}m\hat\theta\in\{+,\times\}^mθ^∈{+,×}m be the outcomes and bases Bob committed to, and let ∣φAE⟩|\varphi_{AE}\rangle∣φAE​⟩ be any unit vector of HA⊗HE\mathcal H_A\otimes\mathcal H_EHA​⊗HE​ (Alice's mmm qubits and a finite-dimensional register of a dishonest Bob): the joint state right before Step 2 of the verification of Fig. 4. Then there is, for each test (T,T′)(T,T')(T,T′), a unit vector ∣φ~AEtest⟩|\tilde\varphi^{test}_{AE}\rangle∣φ~​AEtest​⟩ such that:

  1. (closeness) the real state ρTestAE=∑testPTest(test)∣test⟩⟨test∣⊗∣φAE⟩⟨φAE∣\rho_{TestAE}=\sum_{test}P_{Test}(test)|test\rangle\langle test|\otimes|\varphi_{AE}\rangle\langle\varphi_{AE}|ρTestAE​=∑test​PTest​(test)∣test⟩⟨test∣⊗∣φAE​⟩⟨φAE​∣ and the ideal state ρ~TestAE=∑testPTest(test)∣test⟩⟨test∣⊗∣φ~AEtest⟩⟨φ~AEtest∣\tilde\rho_{TestAE}=\sum_{test}P_{Test}(test)|test\rangle\langle test|\otimes|\tilde\varphi^{test}_{AE}\rangle\langle\tilde\varphi^{test}_{AE}|ρ~​TestAE​=∑test​PTest​(test)∣test⟩⟨test∣⊗∣φ~​AEtest​⟩⟨φ~​AEtest​∣ satisfy δ(ρTestAE,ρ~TestAE)≤ν(m)\delta(\rho_{TestAE},\tilde\rho_{TestAE})\le\nu(m)δ(ρTestAE​,ρ~​TestAE​)≤ν(m);
  2. (bounds (1)) running Steps 2 and 3 on the ideal state, every branch Alice accepts satisfies the bounds of Definition 4.1: for every test (T,T′)(T,T')(T,T′), every choice θ\thetaθ of Alice's bases and every outcome xxx with xi=x^ix_i=\hat x_ixi​=x^i​ for all i∈T′i\in T'i∈T′ whose part x∣Tx|_Tx∣T​ has positive probability,
H0(ρER)≤βn,H_0(\rho_{ER})\le\beta n,H0​(ρER​)≤βn,

and for every I⊆TˉI\subseteq\bar TI⊆Tˉ and every x∣Iˉx|_{\bar I}x∣Iˉ​ of positive probability,

H∞(X∣I ∣ X∣Iˉ=x∣Iˉ)≥dH(θ∣I,θ^∣I)−βn.H_\infty\big(X|_I\,\big|\,X|_{\bar I}=x|_{\bar I}\big)\ge d_H(\theta|_I,\hat\theta|_I)-\beta n.H∞​(X∣I​​X∣Iˉ​=x∣Iˉ​)≥dH​(θ∣I​,θ^∣I​)−βn.

This is the claim the paper's proof of Theorem 4.2 reduces to (p. 9): the dishonest Bob of the compiled protocol is β\betaβ-benign for every β>0\beta>0β>0. Its computational wrapper (dual-mode commitments, the CRS model) is not part of this statement.

Formalization Note. ν\nuν depends on α\alphaα and β\betaβ only, and is chosen before mmm, x^\hat xx^, θ^\hat\thetaθ^, Bob's register and the state; the ideal vectors depend on the test only, not on θ\thetaθ or xxx. Closeness is stated before Steps 2–3 and the bounds on the ideal state after them, as in the paper's construction of ρIdeal\rho_{Ideal}ρIdeal​ (p. 12); the trace distance does not increase under these steps, which is not restated. Rejecting branches carry no constraint ("either aborts, or else", Definition 4.1). Alice's measurement of TTT in θ^∣T\hat\theta|_Tθ^∣T​ and of Tˉ\bar TTˉ in θ∣Tˉ\theta|_{\bar T}θ∣Tˉ​ is one measurement in the mixed basis; the conditioning includes x∣Tx|_Tx∣T​. ρER\rho_{ER}ρER​ is Bob's (unnormalized) state given x∣Tx|_Tx∣T​, which for a pure joint state is the pointwise purification of Definition 4.1. ∣T∣=⌊αm⌋|T|=\lfloor\alpha m\rfloor∣T∣=⌊αm⌋ and n=m−⌊αm⌋n=m-\lfloor\alpha m\rfloorn=m−⌊αm⌋, equal to the paper's αm\alpha mαm and (1−α)m(1-\alpha)m(1−α)m when αm\alpha mαm is an integer. The joint state is pure without loss of generality (p. 10).

Preamble
import Mathlib
import Definitions.Def_CommitOpen_Benign_Model
Formal statement
namespace CommitOpen.Benign

theorem forces_benign (α β : ℝ) (hα0 : 0 < α) (hα1 : α < 1) (hβ : 0 < β) :
    ∃ ν : ℕ → ℝ, Negligible ν ∧
      ∀ (m : ℕ) (xhat θhat : Fin m → Bool) (E : Type) [Fintype E] [DecidableEq E]
        (φ : EuclideanSpace ℂ ((Fin m → Bool) × E)), ‖φ‖ = 1 →
        ∃ φt : Test m ⌊α * m⌋₊ → EuclideanSpace ℂ ((Fin m → Bool) × E),
          (∀ t, ‖φt t‖ = 1) ∧
          traceDistance (cqState (fun _ : Test m ⌊α * m⌋₊ => φ)) (cqState φt) ≤ ν m ∧
          ∀ (t : Test m ⌊α * m⌋₊) (θ x : Fin m → Bool),
            (∀ i ∈ t.1.2, x i = xhat i) →
            0 < ∑ y ∈ agreeOn t.1.1 x, outcomeProb (mixBasis t.1.1 θhat θ) (φt t) y →
            maxEntropy (bobState (mixBasis t.1.1 θhat θ) (φt t) t.1.1 x) ≤
                β * ((m - ⌊α * m⌋₊ : ℕ) : ℝ) ∧
              ∀ I : Finset (Fin m), I ⊆ t.1.1ᶜ →
                0 < ∑ y ∈ agreeOn Iᶜ x, outcomeProb (mixBasis t.1.1 θhat θ) (φt t) y →
                (hammingOn I θ θhat : ℝ) - β * ((m - ⌊α * m⌋₊ : ℕ) : ℝ) ≤
                  condMinEntropy (outcomeProb (mixBasis t.1.1 θhat θ) (φt t)) I x := by sorry

end CommitOpen.Benign
Source
Damgård, Fehr, Lunemann, Salvail & Schaffner, Improving the Security of Quantum Protocols via Commit-and-Open, arXiv:0902.3918v4, p. 12, §4.3 (closing paragraph), with p. 9 and Definition 4.1, bounds (1), p. 7
Human review
  • Endorsed by Shuze Chen · Oct 22, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 22, 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