Secure Computation and Yao's Protocol

• Explores secure computation and Yao's protocol.
• Focuses on concepts, definitions, and semi-honest secure computation for boolean circuits.

Secure Computation

• This involves mutually distrusting parties, each holding private inputs.
• Parties aim to learn the outcome of an agreed-upon computation without revealing their private inputs.
• Examples include elections and auctions.
• Security guarantees include privacy, input independence, and output consistency.
• These guarantees must hold even if some parties cheat or collude.

Examples of Secure Computation

• Sugar beet farmers and purchasers submit bids to determine a market-clearing price (MCP).
• In 2009, secure computation was used to compute the MCP and associated bids.
• Google and its customers use secure computation to compute ad conversions.
• Wage equity studies, such as the Boston Women's Workforce Council Report 2017, utilize secure multi-party computation for data submission to ensure individual compensation data remains private.

Defining Security

• Security risks need to be addressed, for example, adversaries learning more than f(x, y), preventing an honest party from learning, causing inconsistent outputs, or influencing input choices based on an honest party's input.
• In the ideal world, a corrupt party can choose any input (independent of others), learn only f(x, y), and ensure the honest party also learns f(x, y).
• The real-ideal paradigm aims for real protocol interactions to be as secure as ideal-world interactions, ensuring that for every "attack" on a real protocol, there's an equivalent effect achievable in the ideal world.
• A generic attack results in the adversary learning something about the honest party or influencing the honest party’s output.

Defining Security

• For every real-world adversary, there should exist an ideal adversary such that the joint distribution of honest and adversarial outputs is indistinguishable.
• Without loss of generality (WLOG), a simulator exists that mimics real-world interactions in the ideal world.
• The role of the simulator is to send protocol messages that appear authentic and extract an f-input by examining the adversary's protocol messages.
• The simulator also "explains" the impact on the honest party's output using the ideal world concept.

Semi-Honest Security

• This is security against passive adversaries who follow the protocol but may try to learn information.
• In this scenario, there's no need to extract information; the simulator only needs to simulate the transcript given the ideal input and output.

Garbled Truth Table

• Alice writes a truth table for function f, then chooses a random cryptographic key for each possible input.
• Alice encrypts each output with the corresponding keys.
• Alice randomly permutes the ciphertexts and sends the result to Bob.
• Bob somehow obtains correct keys, then decrypts to learn f(x,y) through trial decryption.
• Bob’s view in the protocol needs to be simulated given Bob's ideal input/output.
• Simulation is indistinguishable as long as encryption satisfies this requirement: EA,B(C) ≈ EA',B'(C'), if at least one A,B is random and unknown to distinguisher.
• The cost scales with the size of the truth table.
• Instead of encrypting outputs, encrypt keys to yet more garbled tables using oblivious transfer.

Garbled Circuit Framework

• Pick random labels W0, W1 on each wire.
• Encrypt the truth table of each gate.
• Garbled circuit includes all encrypted gates, and garbled encoding involves one label per wire.
• In garbled evaluation, only one ciphertext per gate is decryptable, meaning the result of decryption equals value on outgoing wire.
• Only (blindly) evaluating the circuit with input is possible.
• It's hard to guess the "complementary" label if you only know one label.
• Hiding logical value on wire is possible with a single label, but revealing output wire labels leaks only circuit output.
• Security means garbled evaluations remain secure.

Syntax and Security

• Garble encodes function f into garbled circuit F, encoding info e, and encodes input x into garbled input X in encode.
• Eval evaluates the inputs and encodes into garbled output Y, finally decoded to the function f(x).
• Privacy means (F, X, d) reveals nothing beyond f and f(x).
• Obliviousness means (F, X) reveals nothing beyond f.
• Authenticity is guaranteed if, given (F, X), it's hard to find Y that doesn't decode to f(x)
• Gate-hiding means (F, X, d) reveals nothing beyond the topology of f and f(x).

Oblivious Transfer

• Oblivious Transer shows how Bob gets the garbled output
• Alice knows both A0 and A1, and must transfer the correct one
• Evaluator inputs require oblivious transfer.
• Need public-key encryption that supports blind key generation.
• Sample a public key without knowledge of secret key
• ElGamal satisfies this requirement (sample group element without knowing discrete log).

Yao's Protocol Overview

• Alice sends the garbled circuit and output wire labels.
• Bob inputs his wire labels garbled by OT (xn), and receives f(x, y).
• Bob learns only f(x, y) given garbled inputs and outputs.

Summary

• Secure Computation facilitates computation on private inputs, revealing only the output.
• Security is achieved by simulating attacks in an ideal world interaction.
• Yao's protocol uses garbled lookup tables for each gate, plus oblivious transfer for each input wire

Moving Forward

• Ways to reduce the large size of Garbled circuits.
• The standard Yao protocols are insecure against malicious attacks and how to protect against them
• More efficient ways of Oblivious Transfer, for example how to "amplify" OT instances using cheap crypto
• Faster secure Special-purpose protocols, instead of standard Yao's, and using secure set intersection.