Transcription
Jack Doerner[Northeastern U]An Introduction toPractical Multiparty Computation
This TalkMPC Frameworks - General ComputationCircuit Structures - Solving Specific ProblemsThe Memory Problem - A Perpetual BugbearCustom Protocols - Beyond CircuitsBut not:Theory, Protocols, Security Models
MPC History1982Yao’s Garbled Circuits2004Fairplay2016FairplayMP, Obliv-C, ObliVM,FastGC, TASTY, SPDZ, EMP,TinyOT, ShareMind, PCF,Sharemonad, TinyOT, Fresco,Wysteria, Plus, many schemes that havenever been implemented!
MPC FrameworksObliv-CObliVMSPDZSharemind
The n Millionaires Problem
The n Millionaires Problem1. Millionairesadditively sharetheir inputs2. Computationauthorities engagein MPC3. Result is revealed
MPC FrameworksObliv-CObliVMSPDZSharemind
Protocol: Yao’s Garbled Circuits (others possible) Language type: C-compatible DSL Philosophy: Minimalism and expressivenessOnly one additional keyword over C Raw speed: 3M AND gates per second reported Unique feature: Compiled; C-compatible[ZE15]
Language features not seen obliv functions obliv intelligent typecasting
Scalability Example: Secure Stable Matching[DEs16]
Scalability Example: Linear System Solving[GSBRDZE16]
MPC FrameworksObliv-CObliVMSPDZSharemind
ObliVM Protocol: Yao’s Garbled Circuits Language type: Java/C style DSL Philosophy: Common operations are first-classlanguage constructs. Includes everythingand the kitchen sink. Raw speed: 700K AND gates per second reportedor 1.8M with preprocessing[LWNHS15]
ObliVM
ObliVMLanguage features not seen phantom functions shared random types bounded loops hinted loop-coalescing automatic ORAM built-in map reduce C-style structs
MPC FrameworksObliv-CObliVMSPDZSharemind
SPDZ Protocol: n-party Linear Secret Sharing SHE No Language: programmed via python library calls Raw Speed (2PC Online): 358K multiplications/second(2PC Offline): 4800 multiplications/second Unique feature: Covert or Malicious security againstdishonest majority[DPSZ11] [DKLPSS12] [KOS16]
SPDZ
SPDZ
SPDZLanguage features not seen Native GF(2n) types Many bits of syntax
MPC FrameworksObliv-CObliVMSPDZSharemind
A Commercial “Application Server Platform” (free forresearchers). Similar to Java or .NET Originally used a 3-party semi-honest protocol; nowincludes SPDZ, YGC, three-party malicious Programming environments: C/C library calls SecreC, a C-like DSL Rmind, an R-inspired statistical analysis languageUnique feature: vector optimized[sharemind.cyber.ee] [BLW08] [J10] [BKLS14]
Scalability Example: Tax Fraud Detection[BJSV15]
Scalability Example: Population-scale Statistical Studies[sharemind.cyber.ee] [BKKRST16]
MPC FrameworksObliv-CObliVMSPDZSharemindYao’s GCn-party LSS SHEMultipleProtocolYao’s GC(others ke DSLPython Library“ApplicationServer Platform”PhilosophyMinimalism,Be like CDo the sensiblethingNo Is like C,Compiled, fastMany languagefeaturesMalicious orCovert SecurityDiverse Toolset,Vector-optimizedDisadvantagesIs like C,No Floating PointComplicatedSyntaxPrecomputation,Leaky AbstractionCommercial
Circuit Structures
Circuit StructuresSeems simple enough, right?But how do we sort?
“Standard” SortsO(logn)O(n)Heapsort’s data-dependent branches make it inefficientQuicksort is totally unsuitable
Batcher’s Mergesort
Batcher’s MergesortA sorting algorithm withno data-dependent branches
RecursivelySort Lower HalfRecursivelySort Upper HalfMerge EvenRowsMerge OddRowsCompare NeighborElements
Circuit StructuresBatcher MergeO(nlogn)[B68]Batcher Odd-EvenMergesortO(nlog2n)[B68]AKS Sorting NetworkO(nlogn)[AKS83]Waksman PermutationNetworkO(nlogn)[W68]
Circuit StructuresBatcher MergeO(nlogn)[B68]Batcher Odd-EvenMergesortO(nlog2n)[B68]AKS Sorting NetworkO(nlogn)[AKS83]Waksman PermutationNetworkO(nlogn)[W68]
The Memory Problem
Oblivious Stack
Oblivious Stack
Oblivious Stack
Oblivious Stack12
Oblivious Stack12
Oblivious Stack
Oblivious Stack
Oblivious Stack5 blocksevery access10 blocks every2nd access20 blocks every4th access40 blocks every8th accessAmortized cost: 5 blocks per layer per accessLayers: O(logn)
Sublinear-time MemoriesStack, QueueSquare-root ORAMTree ORAM(Circuit, DEs16]
Sublinear-time MemoriesStack, QueueSquare-root ORAMTree ORAM(Circuit, DEs16]
Custom Protocols
MPC haremindsharemind.cyber.ee
Jack Doerner[Northeastern U]jackdoerner.netAn Introduction toPractical Multiparty Computation
An Introduction to Practical Multiparty Computation Jack Doerner [Northeastern U] This Talk MPC Frameworks Circuit Structures The Memory Problem Custom Protocols - General Computation - Solving Specific Problems - A Perpetual Bugbear - Beyond Circuits But not: . A sorting algorithm with no data-dependent branches.
