Capacity Inversion and MPC over Elastic Noisy Channels
summary
Shows how to get oblivious transfer from “elastic” noisy channels (receiver can reduce erasure/flip rate from alpha to beta) by decomposing repeated-channel outputs into subchannels and exploiting a new phenomenon capacity inversion where the honest party’s maximum subchannel capacity exceeds the adversary’s average. Gives concrete bounds: for erasures need alpha,beta < 1/2 and for an example alpha=1/3, beta=1/6 an encoding length seven construction achieves inversion; protocols extend to many OTs and can be UC-upgraded.
AI-written summary · about
chapters (18)
- 0:00Intro
- 1:1100 Example of Elastic Channel
- 2:48Our Goal
- 3:13Oblivious Transfer (OT)
- 3:53Protocol
- 7:06Receiver Security
- 11:25Sender Security
- 14:52Elastic Erasure Channel
- 18:16Capacity of a Channel
- 18:38Stepping Back
- 20:44OO Binary Symmetric Channel
- 21:12Elastic BSC
- 21:44Bottleneck
- 22:10Main Idea
- 26:37When Does it Work?
- 27:04Feasible Parameters
- 29:1425 Years of Research
- 30:19Future Research
related talks
27mComputation Over the Noisy Broadcast Channel with Malicious Parties
32mNew Techniques for Building Information-Theoretic Asynchronous MPC with Linear Communication
41mMPC-in-the-Head based Zero Knowledge Proofs
23mRecent progress in MPC-in-the-Head protocols
34mPrivacy Preserving Aggregation of Ad Conversions using MPC
29mRampart Communications: Cryptographic Modulation: Zero-Attack-Surface Wireless
32mPeeking into the Future: MPC Resilient to Super-Rushing Adversaries
33mYes, There is an Oblivious RAM Lower Bound!