Transcript pps - The Faculty of Mathematics and Computer Science

On necessary and sufficient cryptographic
assumptions: the case of memory checking
Lecture 2 : Authentication and Communication
Complexity
Lecturer: Moni Naor
Weizmann Institute of Science
Web site of lectures: www.wisdom.weizmann.ac.il/~naor/COURSE/ens.html
Recap of Lecture 1
• Key idea of cryptography: use computational
intractability for your advantage
• One-way functions are necessary and sufficient to
solve the two guard identification problem
– Notion of Reduction between cryptographic primitives
• Equivalence of the existence of one-way functions:
– Amplification of weak one-way functions
– Distributionally one-way functions
Existence of one-way functions is equivalent:
The existence of one-way functions is equivalent to
• Pseudo-random generators [HILL]
• Pseudo-random functions and permutations
– Block ciphers
• Bit commitment
– Implies zero-knowledge
• Signature Schemes
• (Non trivial) shared-key encryption
Goal of these talk: add two other items to the list:
•Sub-linear authentication
•Memory Checking
Authentication
• Verifying that a string has not been modified
– A central problem in cryptography
– Many variants
• Relevant both in communication and in storage
The authentication problem
one-time version
• Alice would want to send a message m  {0,1}n
to Bob
• They want to prevent Eve from interfering
– Bob should be sure that the message m’ he receives is
equal to the message m Alice sent
m
Alice
Eve
Bob
Specification of the Problem
Alice and Bob communicate through a channel
Bob has an external register R  N (no message) ⋃ {0,1}n
Eve completely controls the channel
Requirements:
• Completeness: If Alice wants to send m  {0,1}n and Eve does
not interfere – Bob has value m in R
• Soundness: If Alice wants to send m and Eve does interfere
– R is either N or m (but not m’ ≠m )
– If Alice does not want to send a message R is N
Since this is a generalization of the identification problem – must use shared
secrets and probability or complexity
Probabilistic version:
• for any behavior from Eve, for any message m  {0,1}n, the
probability that Bob is in state m’ ≠ m or N is at most ε
Authentication using hash functions
• Suppose that
–
–
–
–
H= {h| h: {0,1}n → {0,1}k } is a family of functions
Alice and Bob share a random function h  H
To authenticate message m  {0,1}n Alice sends (m,h(m))
When receiving (m’,z) Bob computes h(m’) and compares to z
• If equal, moves register R to m’
• If not equal, register R stays in N
• What properties do we require from H
– hard to guess h(m’) - at most ε
• But clearly not sufficient: one-time pad.
– hard to guess h(m’) even after seeing h(m) - at most ε
• Should be true for any m’
– Short representation for h - must have small log|H|
– Easy to compute h(m) given h and m
Universal hash functions
• Given that for hH we have h: {0,1}n → {0,1}k we know that
ε≥2-k
• A family where this is an equality is called universal2
Definition: a family of functions H= {h| h: {0,1}n → {0,1}k } is
called Strongly Universal2 or pair-wise independent if:
– for all m1, m2 {0,1}n and y1, y2 {0,1}k we have
Prob[h(m1) = y1 and h(m2) = y2 ] = 2-2k
Where the probability is over a randomly chosen h H
In particular Prob[h(m2) = y2 | h(m1) = y1 ] = 2-k
when a strongly universal2 family is used in the protocol, Eve’s
probability of cheating is at most 2-k
Constructing universal hash functions
The linear polynomial construction:
• fix a finite field F of size at least the message space 2n
– Could be either GF[2n] or GF[P] for some prime P ≥ 2n
• The family H of functions h: F→ F is defined as
H= {ha,b(m) = a∙m + b | a, b  F}
Claim: the family above is strongly universal2
Proof: for every m1, m2 , y1, y2 F there are unique a, b  F
such that
a∙m1+b = y1
a∙m2+b = y2
Size: each hH represented by 2n bits
Lower bound on size of strongly universal
hash functions
Theorem: let H= {h| h: {0,1}n → {0,1} } be a
family of pair-wise independent functions. Then
|H| is Ω(2n)
More precisely, to obtain a d-wise independence
family |H| should be Ω(2n└d/2┘)
Theorem: see
N. Alon and J. Spencer, The Probabilistic Method
Chapter 15 on derandomization, proposition 2.3
An almost perfect solution
By allowing ε to be slightly larger than 2-k we can get
much smaller families
Definition: a family of functions
H= {h| h: {0,1}n → {0,1}k } is called δ-Universal2
if
for all m1, m2 {0,1}n where m1 ≠ m2 we have
Prob[h(m1) = h(m2) ] ≤ δ
An almost perfect solution
Idea: combine
• a family of δ-Universal2 functions H1= {h| {0,1}n → {0,1}k }
with
• a Strongly Universal2 family H2= {h| {0,1}k → {0,1}k }
Consider the family H where each h  H is {0,1}n → {0,1}k is defined by h1  H1
and h2  H2
As before Alice sends m, h(m)
h(x) = h2(h1(x)).
Claim : probability of cheating is at most δ + 2-k
Proof: when Eve sends m’, y’ we must have m ≠ m‘ but either
– y’ =h(m), which means that Eve succeeds with probability at most δ + 2-k
• Collision in h1 Or in h2
Or
– y’ ≠ h(m) which means that Eve succeeds with probability at most 2-k
• Collision in h2
Size: each hH represented by log |H1 |+ log |H2|
Constructing almost universal hash functions
The polynomial evaluation construction {0,1}n → {0,1}k :
• fix a finite field F of size at least the target space 2k
– Could be either GF[2k] or GF[P] for some prime P ≥ 2k
• Let n = ℓ ∙ k
• Treat each (non-zero) message m{0,1}n as a degree (ℓ-1)polynomial over F. Denote by Pm
m
• The family H of functions h: Fℓ → F is defined by all elements in F:
H= {hx (m)= Pm (x)| x  F}
Claim: the family above is δ-Universal2 for δ= (ℓ-1)/2k
Proof: the maximum number of points where two different degree (ℓ-1)
polynomials agree is ℓ-1
Size: each hH represented by k bits
Parameters for authentication
• To authenticate an n bits message with probability
of error ε
Need:
• Secret key length: (log n + log 1 / ε )
log n Lower bound does not hold for
interactive protocols
• Added tag length (log 1 / ε)
Authentication for Storage
• Large file residing on a remote server
• Verifier stores a small secret `representative’ of file
– Fingerprint
– When retrieving the file should identify corruption
• The size of the fingerprint
– A well understood problem
Sub-linear Authentication
What about sub-linear authentication:
– Do you have to read the whole file to figure out whether
it has been corrupted?
– Encode the information you store (Authenticators).
– How large a fingerprint do you need?
How much of the encoding do you need to read?
Authenticators
How to authenticate a large and unreliable memory with a
small and secret memory
secret
encoding sx
x
{0,1}n
E
V
public encoding
public encoding
px
py
•
Encoding Algorithm E:
•
Decoding Algorithm D:
•
Consistency Verifier V:
•
An adversary sees (only) the public encoding and can change it
accept
reject
D
x
y
– Receives a vector x 2 {0,1}n, encodes it into:
• a public encoding px
• a small secret encoding sx. Space complexity: s(n)
– Receives a public encoding p and decodes it into a vector x 2 {0,1}n
– Receives public px’ and secret sx encodings, verifies whether decoder output = encoder input
– Makes few queries to public encoding: query complexity: t(n)
Power of the Adversary
• We have seen the access the
Adversary has to the system
• Distinguish between computationally
– all powerful
and
– Bounded
Adversaries
Dr. Evil
Pretty Good Authenticator
• Idea: encode X using a good error correcting code C
– Actually erasures are more relevant
– As long as a certain fraction of the symbols of C(X) is available, can decode X
– Good example: Reed Solomon code
• Add to each symbol a tag Fk(a,i), a function of
• secret information k 2 {0,1}s,
• symbol a 2 
• location i
• Verifiers picks random location i reads symbol ’a’ and tag t
– Check whether t=Fk(a,i) and rejects if not
• Decoding process removes all inappropriate tags and uses the
decoding procedure of C
How good is the authenticator
Suppose it is impossible to forge tags
• If adversary changes  fraction of symbols
– Probability of being caught per test is 
• If the code C can recover X from 1- of the symbols
– then the probability of false `accept’ is 
– Can make it smaller by repetition
• How to make the tags unforgeable?
– Easy: Need the range of Fk(a,i) to be large enough to make
guessing unlikely
– Need that for random k 2 {0,1}s any adversary
• given many tags {(aj,ij) Fk(aj,ij)}j
• Hard to guess Fk(a,i) for any (a,i) not in the list
Computational Indistinguishability
Definition: two sequences of distributions {Dn} and {D’n} on
{0,1}n are computationally indistinguishable if
for every polynomial p(n) and sufficiently large n, for every probabilistic
polynomial time adversary A that receives input y  {0,1}n and
tries to decide whether y was generated by Dn or D’n
|Prob[A=‘0’ | Dn ] - Prob[A=‘0’ | D’n ] | < 1/p(n)
Without restriction on probabilistic polynomial tests: equivalent to
variation distance being negligible
∑β  {0,1}n |Prob[ Dn = β] - Prob[ D’n = β]| < 1/p(n)
Pseudo-random Functions
Let {s(n), m(n), ℓ(n)} be a sequence of parameters:
F:
{0,1}s
{0,1}m

 {0,1}
Domain
Range
ℓ
key
Denote Y= Fk (X)
A family of functions Φn ={Fk | k0,1}s } is
pseudo-random if it is
• Efficiently computable - random access
and...
Pseudo-random
Any polynomial time tester A that can choose
adaptively
– X1 and get Y1= FS (X1)
– X2 and get Y2 = FS (X2 )
…
– Xq and get Yq= FS (Xq)
• Then A has to decide whether
Not important for us
– Fk R Φn or
– Fk R Rm  ℓ = { F | F :{0,1}m  {0,1}ℓ }
Pseudo-random
For a function F chosen at random from
(1) Φn = {Fk | k0,1s 
ℓ
m

ℓ
m
(2) R
= { F | F :{0,1}  {0,1} }
For all polynomial time machines A that choose q
locations and try to distinguish (1) from (2) for all
polynomial 1/p(n)
 ProbA ‘1’  FR Fk 
- ProbA ‘1’  FR R n  m   
1/p(n)
Equivalent/Non-Equivalent Definitions
• Instead of next bit test: for XX1,X2 ,, Xq
chosen by A, decide whether given Y is
– Y= FS (X) or
– YR0,1m
• Adaptive vs. Non-adaptive
• Unpredictability vs. pseudo-randomness
Really what we need
Existence of Pseudo-Random functions
and Authenticators
• If one-way functions exist so pseudo-random
generators
• If pseudo-random generators exist, so do pseudorandom functions
Probability of error
Authenticators
• Conclusion: If one-way functions exist,
– so do sublinear authenticators with
• Secret memory: sufficient to store a key
• Query complexity log n or log n log 1/
So are we done
Two problems:
• Need
– computational bounded adversary
and
– one-way functions
• Efficiency: the evaluation of a pseudo-random
function might be a burden to add to every memory
fetch operation
Communication Complexity
x2X
Alice
Bob
Let f:X x Y Z
Input is split between two participants
Want to compute outcome: z=f(x,y)
while exchanging as few bits as possible
y2Y
A protocol is defined by the communication
tree
Alice: 0
Bob: 1
Alice: 0
Bob: 1
z0
z1 z2
z3 z4
zz55
z6
z7 ...
A Protocol
A protocol P over domain X x Y with range Z is a binary tree
where
– Each internal node v is labeled with either
• av:X {0,1} or
• bv:Y {0,1}
– Each leaf is labeled with an element z 2 Z
• The value of protocol P on input (x,y) is the label of the leaf
reached by starting from the root and walking down the tree.
• At each internal node labeled av walk
– left if av(x)=0
– right if av(x)=1
• At each internal node labeled bv walk
– left if bv(y)=0
– right if bv(y)=1
– The cost of protocol P on input (x,y) is the length of the path taken
on input (x,y)
– The cost of protocol P is the maximum path length
Motivation for studying communication
complexity
•
•
•
•
•
Originally for studying VLSI questions
Connection with Turing Machines
Data structures and the cell probe model
Boolean circuit depth
…
New application: lower bound for the authentication
problem
Communication Complexity of a function
• For a function f:X x Y Z the (deterministic)
communication complexity of f (D(f)) is the
minimum cost of protocol P over all protocols that
compute f
Observation: For any function f:X x Y Z
D(f) ≤ log |X| + log |Z|
Example:
let x,y µ {1,…,n} and let f(x,y)=max{x [ y}
Then D(f) · 2 log n
Median
let x,y µ {1,…,n} and let MED(x,y) be the median
of the multiset x [ y
If the size is even then element ranked |x[ y|/2
Claim: D(MED) is O(log2 n)
protocol idea: do a binary search on the value, each party
reporting how many are above the current guess
Exercise: D(MED) is O(log n)
protocol idea: each party proposes a candidate
See which one is larger - no need to repeat bits
Combinatorial Rectangles
• A combinatorial rectangle in X x Y is a subset R µ X x Y such that
R= A x B for some A µ X and B µ Y
Proposition: R µ X x Y is a combinatorial rectangle iff (x1,y1) 2 R and
(x2,y2) 2 R implies that (x1,y2) 2 R
For Protocol P and node v let Rv be the set of inputs (x,y) reaching v
Claim: For any protocol P and node v the set Rv is a combinatorial
rectangle
Claim: For any given the transcript of an exchange between Alice an Bob
possible (but not x and y) possible to determine z=f(x,y)
Fooling Sets
• For f:X x Y Z a subset R µ X x Y is f-monochromatic if f is
fixed on R
• Observation: any protocol P induces a partition of X x Y into fmonochromatic rectangles. The number of rectangles is the number of
leaves in P
• A set Sµ X x Y is a fooling set for f if there exists a z 2 Z where
– For every (x,y) 2 S, f(x,y)=z
– For every distinct (x1,y1), (x2,y2) 2 S either
• f(x1,y2)≠z or
• f(x2,y1)≠z
y1
x1
x2
z
z
Property: no two elements of a fooling set S can be in the same
monochromatic rectangle
Lemma: if f has a fooling set of size t, then D(f) ≥ log2 t
y2
Applications
Equality: Alice and Bob each hold x,y 2 {0,1}n
– want to decide whether x=y or not.
• Fooling set for Equality
S={(w,w)|w 2 {0,1}n }
Conclusion: D(Equality) ¸ n
Disjointness: let x,y µ {1,…,n} and let
– DISJ(x,y)=1 if |x  y|¸ 1 and
– DISJ(x,y)=0 otherwise
• Fooling set for Disjointness
S={(A,comp(A))|A µ {1,…,n} }
Conclusion: D(DISJ) ¸ n
Probabilistic Protocols
Random
coins
x
y
ALICE
BOB
Probabilistic Communication Complexity
•
Alice an Bob have each, in addition to their inputs, access to random strings of
arbitrary length rA and rB (respectively)
A probabilistic protocol P over domain X x Y with range Z is a binary tree where
– Each internal node v is labeled with either av(x, rA ) or bv(y, rB )
– Each leaf is labeled with an element z 2 Z
Take all probabilities over the choice of rA and rB
• P computes f with zero error if for all (x,y)
Pr[P(x,y)=f(x,y)]=1
• P computes f with  error if for all (x,y)
Pr[P(x,y)=f(x,y)]¸ 1-
For Boolean f, P computes f with one-sided  error if for all (x,y) s.t. f(x,y)=0
Pr[P(x,y)=0]=1
and for all (x,y) s.t. f(x,y)=1
•
Pr[P(x,y)=1]¸ 1-
Measuring Probabilistic Communication Complexity
For input (x,y) can consider as the cost of protocol P on input (x,y) either
• worst-case depth
• average depth over rA and rB
Cost of a protocol: maximum cost over all inputs (x,y)
The appropriate measure of probabilistic communication complexity:
• R0(f): minimum (over all protocols) of the average cost of a randomized protocol
that computes f with zero error.
• R(f): minimum (over all protocols) of the worst-case cost of a randomized
protocol that computes f with  error.
– Makes sense: if 0< <½ . R(f) = R1/3(f):
• R1(f): minimum (over all protocols) of the worst-case cost of a randomized
protocol that computes f with one-sided  error .
– Makes sense: if 0< <1. R1(f) = R½1(f):
Equality
•
Idea: pick a family of hash functions
H={h|h:{0,1}n  {1…m}}
such that for all x≠y, for random h 2RH
Pr[(h(x)=h(y)]· 
Protocol:
Alice: pick random h 2RH and send <h, h(x)>
Bob: compare h(x) to h(y) and announce the result
This is a one-sided  error protocol with cost log|H|+ log m
Constructing H:
Fact: over any two polynomials of degree d agree on at most d points
Fix prime q such that n2 · q · 2n2
map x to a polynomial Wx of degree d=n/log q over GF[q]
H={hz|z 2 GF[q]} and hz(x)=Wx(z)
 = d/q= n/q log q · 1/n log n
Public coins model
• What if Alice and Bob have access to a joint source of bits.
Possible view: distribution over deterministic protocols
Let Rpub(f): be the minimum cost of a public coins protocol computing
f correctly with probability at least 1- for any input (x,y)
Example: Rpub(Equality) = (-log )
Theorem: for any Boolean f:
R+(f) is Rpub(f)+O(log n + log 1/)
Proof: choose t = 8n/2 assignments to the public string…
Simulating large sample spaces
Collection that should
resemble probability of
success on ALL inputs
Bad 
Good 1-
• Want to find among all possible public
random strings a small collection of strings
on which the protocol behave similarly on
all inputs
• Choose m random strings
• For input (x,y) event Ax,y is more than
(+) of the m strings fail the protocol
2t
-2
Pr[Ax,y] · e
< 2-2n
Pr[[x,y A x,y] ·  x,y Pr[A x,y] <22n 2-2n=1
Number of rounds
• So far have not been concerned with the number of
rounds
• It is known that there functions with a large gap in
the communication complexity between protocols
with few and many rounds
• What is the smallest number of rounds?
What happens if we flatten the tree?
x
ALICE
mA
CAROL
y
BOB
mB
f(x,y)
The simultaneous messages model:
• Alice receives x and Bob who receives inputs y
• They simultaneously send a message to a referee Carol
who initially get no input
• Carol should compute f(x,y)
Several possible models:
• Deterministic: all lower bounds for deterministic protocols
for f(x,y) are applicable here
• Shared (Public) random coins:
– Equality has a good protocol
• Consider public string as hash functions h,
• Alice sends h(x) Bob sends h(y) and Charlie compares the outcome
• The complexity can be as little as O(1) is after constant probability of error
Provided the random bits are chosen independently than the inputs
Simultaneous Messages Protocols
x
{0,1}n
ALICE
mA
CAROL
y
{0,1}n
BOB
• Suggested by Yao 1979
mB
f(x,y)
Simultaneous Messages Protocols
• For the equality function:
• There exists a protocol where
– |mA| x |mB| = O(n)
– Let C be a good error correcting code
– Alice and bob arrange C(x) and C(y)
in an |mA| x |mB| rectangle
• Alice sends a random row
• Bob send a random columns
• Carol compares the intersection
Simultaneous Messages Protocols
• Lower bounds for the equality function:
– |mA| + |mB| = (√n) [Newman Szegedy 1996]
– |mA| x |mB| = (n) [Babai Kimmel 1997]
• Idea: for each x 2 {0,1}n find a `typical’ multiset of messages
Tx = {w1, w2,…,wt} where
t 2 O(|mB|)
Each wi is a message in the original protocol, |mA| bits
Over
random i,
and
randomness
of Carol
Property: for each message mB the behavior on Tx approximates the real
behavior
Average behavior of Carol on w1, w2,…,wt is close to its average response
during protocol
Over randomness of
Alice and Carol
Simultaneous Messages Protocols
How to find for each x 2 {0,1}n such a `typical’ Tx of size t
• Claim: a random choice of wi’s is good
Proof by Chernoff
– Need to `take care’ of every mB
(2|mB| possibilities )
• Claim: for x  x’ we have Tx  Tx’
– Otherwise behaves the same when y = x for x and x’
• Let Sx be the mB’s for which protocol mostly says ’1’
• Let Wx be the mB’s for which protocol mostly says ’0’
• Then for y=x the distribution should be mostly on Sx
• Conclusion: t ¢ |mA| ¸ n and we get
|mA| x |mB| = (n)
[Babai Kimmel 1997]
General issue
• What do combinatorial lower bounds men when
complexity issues are involved?
• What happens to the pigeon-hole principal when
one-way functions (one-way hashing) are involved?
• Does the simultaneous message lower bound hold
when one-way functions exist
– Issue is complicated by the model
– Can define Consecutive Message Protocol model with
iff results
And now for something completely
different
Faculty members in Cryptography and Complexity
‫אורי פייגה‬
• Prof. Uri Feige
• Prof. Oded Goldreich
‫עודד גולדרייך‬
• Prof. Shafi Goldwasser
‫שפי גולדווסר‬
‫מוני נאור‬
• Prof. Moni Naor
• Dr. Omer Reingold
‫עומר ריינגולד‬
• Prof. Ran Raz
• Prof. Adi Shamir
One of the most active groups in the world!
‫רן רז‬
‫עדי שמיר‬