Generalized Homomorphic MACs with Efficient Verification
Foundations of Cryptography
ElGamal Encryption, Oblivious Transfer,
Garbled Circuit
Recap
Public-Key Revolution:
Diffie-Hellman; Merkle; Rivest-Shamir-Adleman; Rabin
Man-in-the-middle Attack:
private-key: one access unlimited access of private + authenticated channel
public-key: authenticated channel private + authenticated channel
Public-Key Encryption:
resolve the issues of key distribution and key storage
significantly slower than private-key
Security:
IND-EAVIND-m-EAVIND-CPAIND-m-CPA
IND-CCAIND-m-CCA
OTP
One-Time Pad:
:
: for , output
: output
Perfect Secrecy: OTP is perfectly secret
for any
Abelian Group: A set together with a binary operation on
closure, associative, identity, inverse, commutative
Example:
is a cyclic group for any prime
Generalizing OTP
The Scheme: , a cyclic group of order (-bit prime)
:
: for , output
: output
Perfect Secrecy: generalized OTP is perfectly secret
for all
Diffie-Hellman Key Exchange:
Alice: ; send to Bob
Bob: ; send to Alice; output
Alice: output
Security: based on DDH assumption- Adversary cannot distinguish and
ElGamal Encryption
Background:
Taher ElGamal: “A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms”, IEEE TIT, 1985
Taher Elgamal (1955- ), PhD student of Hellman at Stanford
basic idea: use as secret key in the generalized OTP
The Scheme:
: ;
:
: output
Correctness:
A Toy Example:
Implementation Issues
Small group? The discrete logarithm is not hard if is too small
And then DDH problem is also easy
Given extract from and then check
How large is used in practice? For example, for
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624225795083
Generate the parameters “once-and-for-all”//NIST
can be an order- subgroup of a group
can be an order- Elliptic curve group
How to encode as an element of
an efficiently computable and reversible map suffices
Security
Theorem: ElGamal encryption is IND-CPA under the DDH assumption.
Let be an adversary in the IND-CPA experiment s.t.
,
for some non-negligible function
Construct a DDH solver
Input:
uses as the public key, picks
Given computes and sends to
Output 1output by is equal to
Security
The difference is non-negligible, DDH problem is solved by
if
if
output
Oblivious Transfer (OT)
1-out-of-2 Oblivious Transfer ()
Alice has two secrets: and
Bob wants to learn for some
Bob’s Security: Alice cannot learn
Alice’s Security: Bob cannot learn
Background:
The notion of OT was introduced by Rabin; (but) Rabin’s OT is not of this form
“How to exchange secrets by oblivious transfer”, 1981
The 1-out-of-2 OT was formalized by Even, Goldreich, and Lempel
“A Randomized Protocol for Signing Contracts”, 1985
OT from Public-Key Encryption
The Scheme:
building block:
Alice’s input:
Bob’s input:
Bob: is randomly chosen; send to Alice
Alice: ; send to Bob
Bob: output
Security:
Alice cannot learn because are both “good” public keys
Bob cannot learn be cause he does not know
A dishonest may send of to Alice
A lot of research has been spent on OT against active Alice or Bob
Millionaires’ Problem
The Problem:
Alice and Bob are two millionaires;
Alice has millions and Bob has millions;
Alice doesn’t know and Bob doesn’t know
They want to decide who is more wealthy: or
They want to keep and hidden from each other
Background:
The problem was introduced by Andrew Chi-Chih Yao (1946-)
“Protocols for secure computations”, 1982
New field in cryptography: secure multi-party computation
numerous research in this field; still hot today
Turing Award 2000
Multi-Party Computation (MPC)
The Problem:
There are players: ……,
There is a function , known to all palyers
Each player has a private input ()
They want to learn
They want to keep the inputs private from each other
Millionaires’ Problem as An Example:
The millionaires’ problem is a secure 2-PC problem
Alice has private input Bob has private input
The function is
Yao’s Garbled Circuit
Represent the function as a Boolean circuit:
Suppose that are 2-bit long, i.e.,
Let and
Construct a Garbled Version of the Circuit:
Tool: private-key encryption
Evaluate the Garbled Circuit:
Tools: OT and private-key encryption
Simple Case:
Truth Table of :
The Circuit:
Alice: choose Keys (Labels)
Alice: Encrypted Truth Table
choose the keys from uniformly and at random
Simple Case:
Alice: permute the Encrypted Truth Table
Alice: send PETT+ to Bob
Bob: learn with
Bob: decrypt PETT with
Alice: decide the output
Alice: notify
= gives
Bob: send the decryption result to Alice
Requirements on the private-key
encryption scheme:
is
IND-CPA secure
Simple Case:
The Truth Table:
The Circuit:
Alice: choose Keys (Labels)
Alice: Encrypted Truth Table
Simple Case:
Alice: permute the Encrypted Truth Table
Alice: send PETT+ to Bob
Bob: learn with
Bob: decrypt PETT with
Alice: Decide the output
Alice: notify
= gives
Bob: send the result to Alice
Simple Case:
The Truth Table:
The Circuit:
Alice: choose Keys (Labels)
Alice: Encrypted Truth Table
Simple Case:
Alice: permute the Encrypted Truth Table
Alice: send PETT+ to Bob
Bob: learn with
Bob: decrypt PETT with
Alice: decide output
Alice: notify
= gives
Bob: send the result to Alice
2-PC of the
The output line of each gate is encrypted by its left input line and then by its right input line.
2-PC of the
2-PC of the
2-PC of the
2-PC of the
2-PC of the
2-PC of the
2-PC of the
2-PC of the
2-PC of the
2-PC of the
2-PC of the