Transcript pptx - Stefan Dziembowski

Modern Cryptography
www.dziembowski.net/Studenti/BISS09
Lecture 11
Two-Party Computation Protocols
Stefan Dziembowski
University of Rome
La Sapienza
BiSS 2009
Bertinoro International
Spring School
2-6 March 2009
Plan
1.
2.
3.
4.
Motivation
Definitions
Information-theoretic impossibility
Constructions
1. oblivious transfer
2. computing general circuits
5. Applications
A love problem
A :=
0 if Alice doesn’t love Bob
1
if Alice loves Bob
B :=
They want to learn the value of
f(A,B) := A and B
0 if Bob doesn’t love Alice
1
if Bob loves Alice
Solution?
A
B
computes
A and B
locally
computes
A and B
locally
Problem
If A = 0 and B = 1 then Bob knows that Alice loves him while he doesn’t!
If B = 1 and A = 0 then Alice knows that Bob loves him while she doesn’t!
Solution?
A
A and B
B
trusted
party
computes
A and B
A and B
Alice and Bob learn only the value of f(A,B) = A and B.
Of course: if A = B = 1 then f(A,B) = 1 and there is no secret to protect.
But, e.g., if A = 0 and B = 1 then f(A,B) = 0 then Alice will not know the
value of B.
Question: Is it possible to compute f without a trusted party?
Another example:
“the millionaire’s problem”
A := how much money Agnelli has
f(A,B) :=
B := how much money Berlusconi has
“Agnelli”
“equal”
if A > B
if A = B
“Berlusconi” if A < B
How to solve this problem?
Can they compute f in a secure way?
(secure = “only the output is revealed”)
Of course, they do not trust any “third party”.
Answer
It turns out that:
in both cases, there exists a cryptographic protocol that
allows A and B to compute f in a secure way.
Moreover:
In general, every poly-time computable function f can be
computed securely by two-parties.
Of course, this has to be defined...
(assuming some problems are computationally hard)
Plan
1.
2.
3.
4.
Motivation
Definitions
Information-theoretic impossibility
Constructions
1. oblivious transfer
2. computing general circuits
5. Applications
What do we mean by a “secure function
evaluation”?
In general, the definition is complicated, and we will not present it here.
Main idea: suppose we have a function f: {0,1}* × {0,1}* → {0,1}*
A
B
protocol
π
f(A,B)
f(A,B)
Each of the parties may try to:
• learn something about the input of the other party, or
• disturb the output of the protocol.
What do we mean by a “secure
function evaluation”?
“real” scenario
A
“ideal” scenario
B
A
B
A
protocol
π
f(A,B)
f(A,B)
f(A,B)
f(A,B)
A malicious participant (Alice or Bob) should not be able to
• learn more information, or
• do more damage to the output
in the “real” scenario, than it can in the “ideal” one.
B
f(A,B)
f(A,B)
What do we mean by this?
For example:
Alice can always declare that she loves Bob, while in fact
she doesn’t.
A millionaire can always claim to be poorer or reacher
than he is...
But:
Berlusconi cannot force the output of the protocol to be
“equal” if he doesn’t know the value of A.
Let’s generalize it a bit:
A
B
f1(A,B)
f2(A,B)
1. the outputs of Alice and Bob can be different
2. the function that they compute may be randomized
An adversary
It is convenient to thing about an adversary that
corrupts one of the players.
(clearly if the adversary corrupts both players,
there is no sense to talk about any security)
Two goals that the adversary may want
to achieve
1. learn about the input of the other party
“more than he would learn in the ideal
scenario”,
2. change the output of the protocol.
Two types of adversarial behavior
In general, we consider two types of adversarial
behavior:
• passive, also called: honest-but-curious:
a corrupted party follows the protocol,
• active, also called Byzantine
a corrupted party doesn’t need to follow the
protocol
Two types of security
• a protocol is passively secure if it is secure
against one of the parties behaving
maliciously in a passive way.
• a protocol is actively secure if it is secure
against one of the parties behaving
maliciously in an active way.
Problem with active security
In general, it is impossible to achieve a complete
fairness.
That is: one of the parties may (after receiving her
own output)
prevent the other party from receiving her output
(by halting the protocol)
(remember the coin-flipping protocol?)
Fact
Let π be a passively secure protocol computing
some function f.
Then, we can construct a protocol π’ that is
actively secure, and computes the same
function f.
How?
Using Zero-Knowledge!
(we skip the details)
Power of the adversary
The malicious parties may be
• computationally bounded (poly-time)
• computationally unbounded.
In this case we say that security is
information-theoretic
We usually allow the adversary to “break the
security” with some negligible probability.
Plan
1.
2.
3.
4.
Motivation
Definitions
Information-theoretic impossibility
Constructions
1. oblivious transfer
2. computing general circuits
5. Applications
Most of the natural functions cannot be
computed by an information-theoretically
secure protocol
Example
Consider a function
f(A,B) = A and B.
There exists an infinitely-powerful adversary that
breaks any protocol computing it.
The adversary may even be passive.
A transcript
A
RA
B
RB
transcript
T
A and B
A and B
Definition
for B – symmetric
Transcript T is consistent with input A=A0
if there exist random inputs RA (for Alice) and (B,RB) (for Bob)
such that
T is a transcript of the execution of the protocol with inputs
• (A0,RA) – for Alice
• (B,RB) – for Bob.
1. Suppose A = 0 and B = 0
A=0
A
B
B=0
T
has to be consistent with A=1
Otherwise a
malicious Bob
knows that A = 0
2. Suppose A = 0 and B = 1
A=0
A
B
B=1
T
cannot be consistent with A=1
Because the output of the protocol
has to be different in these two cases:
• A=0 and B=1 and
• A=1 and B=1
So, if A = 0 then a malicious Alice has a way to learn
what the input of Bob!
A
B
T
Alice checks if T is consistent with
A=1
If yes then she knows that B=0
otherwise B=1
Moral
If we want to construct a protocol for computing
AND, we need to rely on computational
assumptions.
Plan
1.
2.
3.
4.
Motivation
Definitions
Information-theoretic impossibility
Constructions
1. oblivious transfer
2. computing general circuits
5. Applications
A question
Does there exist a protocol π that is “complete
for secure two-party computations”?
In other words:
We are looking for π such that:
if we have a protocol for π then we can
construct a provably secure protocol for any
function?
Answer
Yes!
A protocol like this is exists.
It is called Oblivious Transfer (OT). There are two
versions if it:
• Rabin’s Oblivious Transfer
M. O. Rabin. How to exchange secrets by oblivious transfer, 1981.
• One-out-of-Two Oblivious Transfer
S. Even, O. Goldreich, and A. Lempel, A Randomized Protocol for
Signing Contracts, 1985.
Rabin’s Oblivious Transfer
input
bit A
receiver
sender
The sender should have no
information which was the case
outputs B such that
B :=
A with probability 0.5
?
with probability 0.5
If B = ? then the receiver has no
information on A
One-out-of-two Oblivious Transfer
input
bits
(A0,A1)
input
bit B
receiver
sender
The sender should have no
information which was the case
outputs C such that
C :=
A0 if B = 0
A1
if B = 1
We will also write
C := OT((A0,A1),B)
then the receiver has no
information on the other Ai
Fact
Rabin’s Oblivious Transfer
and
One-out-of-Two Oblivious Transfer
are “equivalent”.
Claude Crépeau. Equivalence between two flavours of oblivious transfer, 1988
1-out-of-2 OT
Rabin OT
Rabin
input
bit A
sender
receiver
choose random (A0,A1) such that A0 xor A1 = A
input
bits
(A0,A1)
choose random bit R
choose a random bit B
1-out-of-2
sender
receiver
input
bit B
AB
AR
If R ≠ B then output A = AB xor AR
otherwise he has no information on
A1-B so he has no information on A
It remains to show the opposite
direction
1-out-of-2 OT
Rabin OT
input
bits
(A0,A1)
input
bit B
α1 α2 α3 α4 α5 α6 α7
random string
of bits
k times
Rabin OT
α1
the receiver
knows only the
indices in βB
 0 :  α i
if B=0 send (X0,X1) := (I,Ic)
if B=1 send (X0,X1) := (Ic,I)
?
?
α 4 α5
?
Let I be the set of indices of the
bits that he “knows”.
Let Ic be the complement of I.
iX 0
1 :  αi
iX1
send
(Z0,Z1) := (β0 xor A0, β1 xor A1)
α7
He outputs βB xor ZB
Security?
1. The learn B the sender would need to
distinguish I from Ic
2. To learn both A0 and A1 the receiver would
need to know both β0 and β1
This is possible only if he knows all αi’s
This happens with probability 0.5k.
An implementation of Rabin’s OT
input
bit A
sender
a random RSA public key pk := (N,e)
C := Epk(A)
y :=
x2
mod N
receiver
chooses a random
x from ZN*
If x = ± z mod N output ?
random z such that z2 = y mod N
Remember the proof that computing square root is
equivalent to factoring?
We used exactly the reasoning:
1. with probability 0.5 we have x ≠ ± y mod N
2. if x ≠ ± y mod N then gcd(x-z, N) is a non-trivial factor
of N
otherwise gcd(x-z, N) is a
non-trivial factor of N
hence the receiver can
decrypt A from C.
Output A
Is it secure?
Against passive cheating?
YES!
Against active cheating?
Not so clear...
The sender acts as an oracle for computing square roots
modulo N.
Does it can help him?
We don’t know.
Solution
Add an intermediary step in which the sender proves in
zero-knowledge that he knows x.
How does it look now?
input
bit A
sender
receiver
a random RSA public key pk := (N,e)
C := Epk(A)
y := x2 mod N
chooses a random
x from ZN*
receiver proves in ZK
that he knows x
If x = ± y mod N output ?
random z such that z2 = y mod N
otherwise gcd(x-z, N) is a
non-trivial factor of N
hence the receiver can
decrypt A from C.
Output A
How to solve the love problem of Alice
and Bob using OT?
A
B
Sets (A0,A1) := (0,A)
1-out-of-2
OT
output A and B
A and B
the output of Bob is equal to 1
iff A = B = 1,
so it is equal to A and B
Bob just outputs it
works, because: A and B = OT((0,A),B)
Plan
1.
2.
3.
4.
Motivation
Definitions
Information-theoretic impossibility
Constructions
1. oblivious transfer
2. computing general circuits
5. Applications
How to compute any function?
We will now show how Alice and Bob can
securely compute any function f.
More precisely: they can compute any function
that can be computed by a poly-time Boolean
circuit.
Boolean circuits
size: number of gates
c1
c2
and
depth
c4
c5
and
and
neg
conjunciton
gates
neg
and
and
output gates
and
and
neg
a0
c3
and
and
and
and
a1
neg
a2
input of Alice
a3
b1
b2
b3
input of Bob
b4
negation
gates
input gates
2-out-of-2 secret sharing
“shares of S”
secret S
SA
SB
1. Both parties together can reconstruct S.
2. a share Si alone gives no information about S.
How to construct such a secret sharing
scheme?
Suppose S Є Z2
secret S
SA – random element of G
SB := SA xor S
Essentially, we use the one-time pad encryption.
Idea
At the beginning, every party will share her
secrets between herself and the other party.
Then the circuit will be evaluated gate-by-gate.
Maintaining the invariant, that
the value of each gate is shared between the
parties.
The evaluation
c1
c2
and
c4
c5
and
neg
and
and
and
neg
neg
and
and
a0
c3
at the end they
can learn the
output by
reconstructing
c1,c2,c3,c4,c5,..
and
and
and
and
a1
neg
a2
input of Alice
a3
b1
b2
b3
input of Bob
b4
At the beginning:
Alice does the following for every bit of her input:
ai
sends a random si
stores
ai xor si
Bob does a symmetric thing...
How to handle negation?
Just let Alice negate her bit...
the original circuit
not x
not x = (not xA) xor xB
neg
x
not xA
xB
neg
x = xA xor xB
xA
xB
How to handle multiplication?
?
zy
zA
and
x
zB
and
y
xA
xB
yA
yB
(xA xor xB) (yA xor yB) = xA yA xor xA yA xor xB yA xor xB yA
sharing of
x
xA
xAyA
xAyB
yA
yB
sharing of
y
xB
xByA
xByB
knows this
zA := xAyA
how can Bob compute
xByA and xAyB?
Alice cannot just send it
to Bob
knows this
xy = zA xor zB
zB := xByA xor xAyB xor xByB
Idea: let Alice and Bob compute this
Idea
Randomize!
Alice will chose some random bits R0 and R1
xA
xB
yA
xAyA xor R0 xor R1
xByA xor R0
yB
xAyB xor R1
xByB
zA := xAyA
xor R0 xor R1
xy = zA xor zB
zB := xByA
xor (xAyB xor R1)
xor (xByA xor R0)
xA
How to do it?
R0
yB
R, A
we want to construct the
following protocol:
Solution
A·B xor R = OT((R, R xor A), B)
Why does it work?
if B = 0 then A·0 xor R = R = OT((R, R xor A), 0)
if B = 1 then A·1 xor R = A xor R = OT((R, R xor A), 1)
B
A·B xor R
Putting things together
xA
yA
xB
OT((R0, R0 xor xA), yB)
yB
xA yB xor R0
OT((R1, R1 xor yA), xB)
xB yA xor R1
zA := xAyA
xor R0 xor
R1
zB := xByA
xor (xAyB xor R0)
xor (xByA xor R1)
Overview of the construction
1. Alice and Bob “share” with each other their
inputs.
2. They evaluate the circuit gate-by-gate.
3. They construct the output.
Plan
1.
2.
3.
4.
Motivation
Definitions
Information-theoretic impossibility
Constructions
1. oblivious transfer
2. computing general circuits
5. Applications
Applications?
In practice this protocol is extremely inefficient.
But it shows that some things in principle can be
done.
Research problem
Construct protocols (for concrete problems) that
are efficient.
Example
Michael J. Freedman, Kobbi Nissim, Benny Pinkas: Efficient Private
Matching and Set Intersection. EUROCRYPT 2004
Set intersection:
Alice and Bob want to see which friends they have in common
(without revealing to each other their lists of firends)
input:
set A
input:
set B
output:
intersection of
A and B
A natural question?
What if the number of parties is greater than 2?
We will deal with this on the next lecture.
Is the oblivious transfer in Minicrypt?
As far as we know:
no!
cryptomania
???
trap-door permutations
exist
public-key encryption
exists
minicrypt
oblivious transfer
exist
???
???
???
key exchange
protocols exist
one way functions
exist
©2009 by Stefan Dziembowski. Permission to make digital or hard copies of part or all of
this material is currently granted without fee provided that copies are made only for
personal or classroom use, are not distributed for profit or commercial advantage, and
that new copies bear this notice and the full citation.