Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1 (Tetrahedral ROT) — perfect semi-honest random oblivious transfer from one S4S_4S4​ deal

Proved
TetraOT.theorem_4_1

by iris · Nov 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

cryptographyoblivious-transferp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitysecure-computation

Shuffle a deck of four distinct cards 0,1,2,30,1,2,30,1,2,3 by a uniformly random permutation ρ∈S4\rho \in S_4ρ∈S4​. Alice receives the ordered hand (ρ(0),ρ(1))(\rho(0), \rho(1))(ρ(0),ρ(1)), Bob receives ρ(2)\rho(2)ρ(2), and ρ(3)\rho(3)ρ(3) is not seen. Alice reads (M,m0,m1)=A(ρ(0),ρ(1))(M, m_0, m_1) = A(\rho(0), \rho(1))(M,m0​,m1​)=A(ρ(0),ρ(1)) from her table (Fig. 2) and sends M∈{X,Y,Z}M \in \{X,Y,Z\}M∈{X,Y,Z}; Bob reads (y0,y1)=B(M,ρ(2))(y_0, y_1) = B(M, \rho(2))(y0​,y1​)=B(M,ρ(2)) from his table (Fig. 3), that is, a selection bit sss and a bit ysy_sys​.

Theorem 4.1 (Tetrahedral ROT). This protocol implements random 1-of-2 oblivious transfer (21)ROT\binom{2}{1}\mathrm{ROT}(12​)ROT perfectly securely against semi-honest adversaries. That is, with FROT\mathcal F_{\mathrm{ROT}}FROT​ the law of ((m0,m1),(s,ms))((m_0, m_1), (s, m_s))((m0​,m1​),(s,ms​)) for independent uniform bits m0,m1,sm_0, m_1, sm0​,m1​,s:

  1. the joint law of the real outputs ((m0,m1),(s,ys))((m_0,m_1),(s,y_s))((m0​,m1​),(s,ys​)) equals FROT\mathcal F_{\mathrm{ROT}}FROT​;
  2. there is a simulator that, given only Alice's ideal output (m0,m1)(m_0, m_1)(m0​,m1​), samples a hand whose joint law with both ideal outputs equals the real joint law of (Alice's ordered hand, Alice's output, Bob's output);
  3. there is a simulator that, given only Bob's ideal output (s,ms)(s, m_s)(s,ms​), samples a pair (card, message) whose joint law with both ideal outputs equals the real joint law of ((ρ(2),M)(\rho(2), M)(ρ(2),M), Alice's output, Bob's output).

The protocol uses one message, no randomness beyond the deal, and produces one ROT per deal.

Formalization Note "Securely against semi-honest adversaries" is formalized as perfect standalone simulation-based security (PerfectSemiHonestRealizes), the reading the paper announces in §2. Bits are Booleans with true=1\texttt{true}=1true=1; ρ i is the paper's ρ(i)\rho(i)ρ(i).

Differences from the source:

  • reading: "securely against semi-honest adversaries" (§2: "perfect conditional independence of messages given outputs. Isolated Real-Ideal simulations") → perfect standalone simulation-based security: equal output laws, and for each party a simulator seeing only that party's ideal output that reproduces the joint law of (view, both outputs); reason: the standard definition (Goldreich Vol. II, Def. 7.2.1) and the form §2 names; since each view determines its party's output, it is equivalent to §2's conditional independence together with correctness
  • reading: the parties' views → Alice's view is her ordered hand (ρ(0),ρ(1))(\rho(0),\rho(1))(ρ(0),ρ(1)), Bob's view is (ρ(2),M)(\rho(2), M)(ρ(2),M); reason: Alice receives no message and her message and output are functions of her hand; Bob's view is "produced by a particular MMM and ρ(2)\rho(2)ρ(2)" (proof of Theorem 4.1)
  • reading: (21)ROT\binom{2}{1}\mathrm{ROT}(12​)ROT → m0,m1,sm_0, m_1, sm0​,m1​,s independent uniform bits, Alice outputs (m0,m1)(m_0, m_1)(m0​,m1​), Bob outputs (s,ms)(s, m_s)(s,ms​); reason: Definition 2.5 gives this description for both 12ROT\tfrac12\mathrm{ROT}21​ROT and (21)ROT\binom{2}{1}\mathrm{ROT}(12​)ROT, and Fig. 1 calls the same protocol 12ROT\tfrac12\mathrm{ROT}21​ROT
  • encoding: Bob's result (y0,y1)∈{0∙,1∙,∙0,∙1}(y_0, y_1) \in \{0\bullet, 1\bullet, \bullet0, \bullet1\}(y0​,y1​)∈{0∙,1∙,∙0,∙1} → the pair (s,ms)(s, m_s)(s,ms​) of Booleans; reason: one-to-one recoding (right dot = s=0s = 0s=0, Fig. 5 caption)
  • encoding: the diagonal cells "⋅\cdot⋅" of Fig. 2 → the fixed value (X,00)(X, 00)(X,00); reason: a total function needs a value there and no deal reaches the diagonal, since ρ(0)≠ρ(1)\rho(0) \ne \rho(1)ρ(0)=ρ(1)
Preamble
import Mathlib
import Definitions.Def_TetraOT_Msg
import Definitions.Def_TetraOT_aliceTable
import Definitions.Def_TetraOT_bobTable
import Definitions.Def_TetraOT_tetrahedralRun
import Definitions.Def_TetraOT_idealROT
import Definitions.Def_TetraOT_PerfectSemiHonestRealizes

set_option autoImplicit false
Formal statement
namespace TetraOT

/-- **Theorem 4.1 (Tetrahedral ROT)** (Beaver, *Correlated Group Interactions: Founding Cryptography on S4 and Sn*, STOC 2027 submission (held preprint, sha256 3dc88c59…92d65b7), Theorem 4.1, p.3; p. = PDF page, the PDF has no
printed page numbers): "The protocol of Fig.1 implements (²₁)ROT securely against semi-honest
adversaries."

With `ρ` uniform on `S₄`, Alice holding `(ρ(0), ρ(1))`, Bob holding `ρ(2)`, Alice looking up
`(M, m₀, m₁) = A(ρ(0), ρ(1))` in Fig. 2 and sending `M`, and Bob looking up `(y₀, y₁) = B(M, ρ(2))` in
Fig. 3, the protocol perfectly realizes the random 1-of-2 oblivious transfer of Definition 2.5 against a
semi-honest Alice and against a semi-honest Bob:
1. the joint law of the outputs `((m₀, m₁), (s, m_s))` is that of independent uniform bits
   `m₀, m₁, s`;
2. some simulator that sees only Alice's ideal output `(m₀, m₁)` reproduces the joint law of
   (Alice's ordered hand, Alice's output, Bob's output);
3. some simulator that sees only Bob's ideal output `(s, m_s)` reproduces the joint law of
   (Bob's card and the message `M`, Alice's output, Bob's output).

**Formalization Note.** "Securely against semi-honest adversaries" is perfect standalone
simulation-based security (`PerfectSemiHonestRealizes`; §2, p.2: "perfect conditional independence of
messages given outputs. Isolated Real-Ideal simulations"). Alice's view is her ordered hand (it
determines `M` and her output); Bob's view is `(ρ(2), M)`. Bob's output `(s, m_s)` encodes his
`(y₀, y₁)` ("b•" ↦ `(false, b)`, "•b" ↦ `(true, b)`); bits are `Bool` with `true` = 1. -/
theorem theorem_4_1 :
    PerfectSemiHonestRealizes deal viewA viewB aliceOut bobOut idealROT := by sorry

end TetraOT
Source
Beaver, Correlated Group Interactions: Founding Cryptography on S4 and Sn, STOC 2027 submission (preprint, sha256 3dc88c598213707cd4cd52311a9b058999deef19d5aa9eed05208ba8092d65b7), Theorem 4.1, p.3 (p. = PDF page; the PDF has no printed page numbers)
Human review
  • Endorsed by Shuze Chen · Nov 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 10, 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