Theorem 4.1 (Tetrahedral ROT) — perfect semi-honest random oblivious transfer from one deal
ProvedTetraOT.theorem_4_1Shuffle a deck of four distinct cards by a uniformly random permutation . Alice receives the ordered hand , Bob receives , and is not seen. Alice reads from her table (Fig. 2) and sends ; Bob reads from his table (Fig. 3), that is, a selection bit and a bit .
Theorem 4.1 (Tetrahedral ROT). This protocol implements random 1-of-2 oblivious transfer perfectly securely against semi-honest adversaries. That is, with the law of for independent uniform bits :
- the joint law of the real outputs equals ;
- there is a simulator that, given only Alice's ideal output , 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);
- there is a simulator that, given only Bob's ideal output , samples a pair (card, message) whose joint law with both ideal outputs equals the real joint law of (, 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 ; ρ i is the paper's .
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 , Bob's view is ; reason: Alice receives no message and her message and output are functions of her hand; Bob's view is "produced by a particular and " (proof of Theorem 4.1)
- reading: → independent uniform bits, Alice outputs , Bob outputs ; reason: Definition 2.5 gives this description for both and , and Fig. 1 calls the same protocol
- encoding: Bob's result → the pair of Booleans; reason: one-to-one recoding (right dot = , Fig. 5 caption)
- encoding: the diagonal cells "" of Fig. 2 → the fixed value ; reason: a total function needs a value there and no deal reaches the diagonal, since
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
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.