Passive secure AND from password identification
ProvedQAlgorithms.Papers.Independent.Intakenext100.P14.passive_and_reductionLet an identification execution have correctness error at most and passive statistical privacy error at most . A local view includes the publicly announced accept/reject decision. Privacy means that at a fixed local password, the views for any two different, unequal other passwords have trace distance at most . Choose three distinct passwords . Alice encodes input by or ; Bob encodes by or , respectively. Both output the identification decision . Then
The two players have the same output law. For Alice, any two input pairs with the same and the same ideal AND output have local views at trace distance at most ; the corresponding statement holds for Bob at fixed . Thus the executed reduction preserves passive correctness and statistical privacy. The input maps are prescribed; this statement makes no claim about malicious deviations.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P14
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P14
open scoped Matrix ComplexConjugate
open QAlgorithms.Papers.Independent.Dependency50.P47 (Law)
open QAlgorithms.Papers.Independent.Gap48.P11 (blockMatrix cqDistance)
open QAlgorithms.Papers.Independent.Claimed50.P31 (bb84Vector)
open QAlgorithms.Papers.Independent.Advance50.P05 (RectangularInstrument)
attribute [local instance] Classical.propDecidable
attribute [local instance] Classical.decEq
/-- Positive list length and inhabited fibers supply the tagged union's inhabitant.
This derived instance adds no hypothesis to Lemma 2.2. -/
local instance {m : ℕ} [NeZero m] {A : Fin m → Type*}
[∀ i, Nonempty (A i)] : Nonempty (Sigma A) :=
⟨⟨0, Classical.choice (inferInstance : Nonempty (A 0))⟩⟩
/-- PDF p.3, unnumbered passive AND reduction. Both parties receive the
identification decision. Correctness and full-view privacy are preserved for
the prescribed maps; no malicious-security claim is made. -/
theorem passive_and_reduction
{W EA EB : Type*} [Fintype EA] [Fintype EB]
(P : PassiveExecution W EA EB) (wzero wzeroOther wone : W)
(hzero : wzero ≠ wzeroOther) (hleft : wzero ≠ wone)
(hright : wzeroOther ≠ wone) (delta epsilon : ℝ)
(hsecurity : PassiveEqualitySecurity P delta epsilon) :
(∀ a b : Bool,
blockMass (P.bob (andPassword wzero wone a)
(andPassword wzeroOther wone b)) (a && b) ≥ 1 - delta ∧
∀ t, blockMass (P.alice (andPassword wzero wone a)
(andPassword wzeroOther wone b)) t =
blockMass (P.bob (andPassword wzero wone a)
(andPassword wzeroOther wone b)) t) ∧
(∀ a b c : Bool, (a && b) = (a && c) →
cqDistance (P.alice (andPassword wzero wone a) (andPassword wzeroOther wone b))
(P.alice (andPassword wzero wone a) (andPassword wzeroOther wone c)) ≤ epsilon) ∧
(∀ b a c : Bool, (a && b) = (c && b) →
cqDistance (P.bob (andPassword wzero wone a) (andPassword wzeroOther wone b))
(P.bob (andPassword wzero wone c) (andPassword wzeroOther wone b)) ≤ epsilon) := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P14
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be any type, let be finite types, and let supply Boolean-indexed matrix families and on these respective spaces. For such a family , let be the block diagonal matrix with blocks , let , and let . Choose three pairwise distinct elements , and real numbers . Assume ; every is positive semidefinite of trace ; their Boolean masses agree; ; whenever ; and whenever . Define if is true and otherwise, and if is true and otherwise. Then, for all Boolean ,
Moreover, for all Boolean , equality implies ; and for all Boolean , equality implies . These implications include cases where the two compared input pairs are identical.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.