Secure Two-Party Computation and Basic Secret-Sharing Concepts

Slide Note

In today's lecture of "Foundations of Cryptography," the focus is on secure two-party and multi-party computation, emphasizing semi-honest security where Alice and Bob must compute without revealing more than necessary. Concepts such as real-world vs. ideal-world scenarios, the existence of PPT simulators, and leveraging Oblivious Transfer (OT) for secure two-party computation are explored. Additionally, the basics of secret-sharing schemes between Alice and Bob are discussed to enable collaboration while preserving individual privacy.

pjiv Follow

Uploaded on Sep 20, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

MIT 6.875 Foundations of Cryptography Lecture 22

TODAY: Secure Two-Party and Multi-Party Computation

Secure Two-Party Computation Input: ? Input: ? Alice Bob Alice and Bob want to compute ? ?,? . Semi-honest Security: Alice should not learn anything more than ? and ? ?,? . Bob should not learn anything more than ? and ? ?,? .

Secure Two-Party Computation Input: ? Input: ? REAL WORLD: Alice Bob IDEAL WORLD:

Secure Two-Party Computation Input: ? Input: ? Alice Bob There exists a PPT simulator ???? such that for any ? and ?: ????(?,?(?,?)) ?????(?,?)

Secure Two-Party Computation Input: ? Input: ? Alice Bob There exists a PPT simulator ???? such that for any ? and ?: ????(?,?(?,?)) ?????(?,?)

Secure 2PC from OT Theorem [Goldreich-Micali-Wigderson 87]: OT can solve any two-party computation problem.

Tool: Oblivious Transfer (OT) ?0 ?1 Choice bit: ? Receiver Sender Sender holds two bits ?0 and ?1. Receiver holds a choice bit ?. Receiver should learn ??, sender should learn nothing.

How to Compute Arbitrary Functions For us, programs = functions = Boolean circuits with XOR (+ ??? 2) and AND ( ??? 2) gates. ??(? + ? ) X ? + ? ?? + X ? ? ? ? Want: If you can compute XOR and AND in the appropriate sense, you can compute everything.

Basic Secret-Sharing A secret (bit) ? is shared between Alice and Bob if Alice holds a bit ? and Bob holds a bit ? s.t. ? ? = ? ? and ? are (typically) individually random, so neither Alice nor Bob knows any information about ?. Together, however, they can recover ?.

Recap: OT Secret-Shared-AND Alice gets random ?, Bob gets random ? s.t. ? ? =ab. ? {0,1} ? {0,1} Output: ? Output: ? Run an OT protocol ?0= ? ?1= ? ? Choice bit ? Alice outputs ?. Bob gets ??? + ??? ? = (?? ??)? + ??= ?? ? ?

How to Compute Arbitrary Functions Secret-sharing Invariant: For each wire of the circuit, Alice and Bob each have a bit whose XOR is the value at the wire. XOR gate: Locally XOR the shares AND gate?? X ? ? + X ? 0 ? 0 0 ? 0 ? Base Case: Input wires

Recap: XOR gate ? ? Alice has ? and Bob has ? s.t. + ? ? = ? ? ? Alice has ? and Bob has ? s.t. ? ? = ? Alice computes ? ? and Bob computes ? ? . So, we have: (? ? ) ? ? = ? ? ? ? = x x

AND gate ?? Alice has ? and Bob has ? s.t. X ? ? = ? ? ? Alice has ? and Bob has ? s.t. ? ? = ? Desired output (to maintain invariant): Alice wants ? and Bob wants ? s.t. ? ? = ??

AND gate ?? ?? = (? ?)(? ? ) X = ?? ?? ?? ?? ?? ?? ?? ? ? ?? ? ? ? ? ss-AND ss-AND ?? ?? ?? ?? ? = ?? ?? ?? ? = ?? ?? ??

How to Compute Arbitrary Functions Secret-sharing Invariant: For each wire of the circuit, Alice and Bob each have a bit whose XOR is the value at the wire. Finally, Alice and Bob exchange the shares at the output wire, and XOR the shares together to obtain the output. ? ? ? = ??(? ? ) ? X + X ? ? ? ?

Security: Intuition Imagine that the parties have access to an ss-AND angel. ? ? =ab

Security: Intuition Imagine that the parties have access to an ss-AND angel. Simulator for Alice s view: XOR gate: simulate given Alice s input shares X ? ? + X ? 0 ? 0 0 ? ? 0 Input wires: can be simulated given Alice s input

Security: Intuition Simulator for Alice s view: AND gate: simulate given Alice s input shares & outputs from the ss-AND angel. Alice s share = ? 0 + ????? ?,? + ?????(0,0) ?????? X ? ? ?????? + X ? 0 ? 0 0 ? ? 0 ?????? and ?????? are random, independent of ?

Security: Intuition Simulator for Alice s view: Output wire: need to know both Alice and Bob s output shares. Bob s outputshare = Alice s output share function output X ? ? Simulator knows the function output, and can compute Bob s output share given Alice s output share. + X ? 0 ? 0 0 ? ? 0

We showed: Secure 2PC from OT Theorem [Goldreich-Micali-Wigderson 87]: OT can solve any two-party computation problem.

In fact, GMW does more: Theorem [Goldreich-Micali-Wigderson 87]: OT can solve any multi-party computation problem.

MPC Outline Secret-sharing Invariant: For each wire of the circuit, the n parties have a bit each, whose XOR is the value at the wire. Base case: input wires. ? XOR gate: given input shares ?1, ,?? s.t. ?=1 and ?1, ,?? s.t. ?=1 output of the XOR gate: ?1+ ?1, ,??+ ?? ??= ? ? ??= ?, compute the shares of the AND gate: given input shares as above, compute the shares of the output of the XOR gate: ? ?1, ,?? s.t ?=1 ??= ?? Exercise!

Optimization 1: Preprocessing OTs Random OT tuple (or AND tuple, or Beaver tuple after D. Beaver): Alice has (?,??) and Bob has (?,??) which are random s.t. ?? ??= ??. Theorem: Given O(1) many random OT tuples, we can do OT with information-theoretic security, exchanging O(1) bits.

Optimization 2: OT Extension Theorem [Beaver 96, Ishai-Kushilevitz-Nissim-Pinkas 03]: Given O(?) many random OT tuples, we can generate ? OT tuples exchanging O(?) bits --- as opposed to the trivial O(??) bits --- and using only symmetric-key crypto.

Complexity of the 2-party solution Number of OT protocol invocations = 2 #??? gates Can be made into O(#inputs ?): Yao s garbled circuits Number of rounds = AND-depth of the circuit Can be made into O(1) rounds: Yao s garbled circuits Communication in bits = ?(#??? ? + #???????) Can be made into O(? #inputs) using FHE: but FHE is computationally more expensive concretely.