Theorem 6 — Transposition differential
OpenAddXnor.Supplement.theorem_6add-xnorcryptographyp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let two operator strings agree except that an adjacent pair is replaced by . For uniform independent -bit operands,
The formula holds for every common prefix and suffix and therefore does not depend on the transposed pair's position.
Differences from the source:
- encoding: positions → a natural index with , corresponding to the paper's position ; reason: Lean operator indices are 0-based
- encoding: probability over uniform operands → exact finite uniform probability over
(Fin (q+1) → BitVec m); reason: finite-type encoding with identical uniform weights
Preamble
import Mathlib import Definitions.Def_AddXnor_Supplement_core set_option autoImplicit false
Formal statement
namespace AddXnor.Supplement
/-- **Theorem 6 (Transposition differential)** (Wang, Lv, Shen, Zhang,
*Add/XNOR Chains*, manuscript, sha256 405d6dda..., Theorem 6, pp.19--20
(PDF pp.19--20)).
Lean uses the 0-based position `p`; it is the paper's position `p+1`. The hypotheses say that
`x'` replaces exactly the adjacent `(+,XNOR)` pair by `(XNOR,+)` and agrees on the whole common
prefix and suffix. Since the value below is independent of `p`, the position-independence clause
is part of the quantified identity. -/
theorem theorem_6 (q m p : ℕ) (hq : 2 ≤ q) (hm : 1 ≤ m) (hp : p + 1 < q)
(x x' : Fin q → Bool)
(hpair : x ⟨p, by omega⟩ = false ∧ x ⟨p + 1, hp⟩ = true)
(hpair' : x' ⟨p, by omega⟩ = true ∧ x' ⟨p + 1, hp⟩ = false)
(hcommon : ∀ i : Fin q, (i : ℕ) ≠ p → (i : ℕ) ≠ p + 1 → x' i = x i) :
collisionProb (m := m) x x' =
2 * (5 / 8 : ℝ) ^ (m - 1) - (2 : ℝ) ^ (-(m - 1 : ℤ)) := by sorry
end AddXnor.Supplement
Source
Wang, Lv, Shen, Zhang, manuscript (sha256 405d6dda…), Theorem 6, pp.19–20 (PDF pp.19–20)