Transcript ppt

Foundations of Cryptography
Lecture 5: Signatures and pseudo-random generators
Lecturer: Moni Naor
Recap of last week’s lecture
• One-time signatures
• UOWHFs
–
–
–
–
Definition
Compositions
Construction from one-way permutations
Known: construction from one-way functions
General construction (n, k)-UOWHFs
• Use tree composition
• Description length: k log (n/k) (n, n/2)descriptions of hash function
– 2k bits in the example
Recall: Regeneration
•
If we could get a smaller public-key could be able to regenerate smaller and
sign/authenticate an unbounded number of messages
– What if you had three wishes…?
Idea: use G a family of UOWHF to compress the message
• Question: can we use a global g  G for all nodes of the tree?
• Question: how to assign messages to nodes in the tree?
• What exactly are we after?
Components of a Signature Scheme
•
•
Allow Alice to publish a public key pk while keeping hidden a secret key sk
– Key generation Algorithm
• Input: security parameter n, random bits
• Output: pk and sk
Given a message m Alice can produce a signature s
– Signing Algorithm
• Input: pk and sk and message m (plus random bits)
– Possible: also history of previous messages
•
KGA
pk
• Output: s
``Anyone” who is given pk and (m,s) can verify it
– Signature Verification Algorithm
• Input: (pk, m, s)
• Output: `accept’ or `reject’
– Completeness: the output of the Signing Algorithm is assigned `accept’
All algorithms should be polynomial time
Security: ``No one” who is given only pk and not sk can forge a valid (m,s)
How to do define properly?
sk
Rigorous Specification of Security of a
Scheme
Recall: To define security of a system must specify:
1. The power of the adversary
–
–
computational
access to the system
•
•
Who chooses the message to be signed
What order
2. What constitutes a failure of the system
•
What is a legitimate forgery?
Existential unforgeability in signature schemes
A signature scheme is
• existentially unforgeable
under an
• adaptive chosen message attack
if
any polynomial adversary A with
• Access to the system: for q rounds
adaptive message attack
– adaptively choose messages mi and receive a valid signature si
• Tries to break the system: find pair (m, s) so that
– m {m1, m2, … mq}
But
– (m,s) is a valid signature.
has probability of success at most ε
existential forgery
For any q and 1/ε polynomial in the security parameter and for large enough n
Weaker notions of security
• How the messages are chosen during the attack
– E.g. random messages
– Non adaptively (all messages chosen in advance)
• How the challenge message is chosen
– In advance, before the attack
– randomly
Homework: show how to construct from a signature scheme
that is
existentially unforgeable against random message attack
a signature scheme that is
existentiallly unforgeable against adaptively chosen message attacks
Hint: use two schemes of the first type
Specific proposal
Key generation:
• generate the root
– Three sets of keys for a one-time signature scheme
– A function g  G from a family of UOWHF
triple
Signing algorithm:
• Traverse the tree in a BFS manner
– Generate a new triple
– Sign the message using the middle part of node
– Put the generated triple in the next available node in the current level
• If all nodes in current level are assigned, create a new one.
– The signature consists of:
• The one-time signature on the message
• The nodes along the path to the root
• the one-time signatures on the hashed nodes along the path to the root
• Keep secret the private keys of all triples
Verification of signature:
• Verify the one-times signature given.
Size of signature:
Depth of tree ¢ triple size
When is using a single hash function sufficient?
The rule of thump of whether a global hash function g is
sufficient or not is:
• Can the legitimate values hashed be chosen as a function
of g
In this case the only legitimately hashed values are the triples
Chosen independently of g by the signer
Note: if we want to hash the message itself (to obtain a
shorter one-time signature:
need a separate has function for each node
Why is tree regeneration secure
Consider the legitimate tree and a forged message
There is the first place where the two differ
•
This must occur when either:
1. a forged one-time signature is produced
Or
2. a false child is authenticated
•
Can guess the place where this happens and what
happens with probability at least 1/p(n)
–
–
If 1) happens more often: can break the one-time signature
If 2) happens more often: can break the UOWHF
Proof of Security
Want to construct from the forging algorithm A which is a target collision finding for G
algorithm B
x
Algorithm B:
• Generate a random triple and output it as target x
• Obtain the challenge g
• Generate the public key/secret key of the scheme
g
B
A
– Using g as the global hash function
•
•
Run algorithm A that tries to break the signature scheme
Guess the node where the forgery occurs
•
What is the probability of success of B?
x’
– Put the triple x
– If a false child is authenticated there: found a collision with x under g !
The same as the simulated forging algorithm A for G divided by 2q
Claim: the probability the simulated algorithm A witnesses is the same as the real A
x’
Conclusion
Theorem: If families of UOWHF exist, then signature
schemes existentially unforgeable under adaptive chosen
message attacks exist
Corollary: If one-way permutations exist, then signature
schemes existentially unforgeable under adaptive chosen
message attacks exist.
Corollary: If one-time public-key identification is possible
(equivalent to existence of one-way functions), then
signature schemes existentially unforgeable under adaptive
chosen message attacks exist.
Several other paradigms for creating
secure signature schemes
• Trapdoor permutations
– Protection against random attack and forgery of a random challenge
• Other forms of tree like schemes
– Claw-free
– Trapdoor
• Converting interactive identification schemes
– If challenge is random
• Creating a random instance of a problem
– Solvable if you know the trapdoor
– Example: RSA
• Only analysis known: assumes an idealized random function
– Black box that behaves as a random function
– All users including adversary have black-box access to it but cannot see it
inside
– Much debate in crypto literature
Trapdoor One-way Permutations
A collection functions with three probabilistic polynomial time algorithms
• Key generation: on input n, the security parameter, and random bits,
generates two keys
KP (Public) and KS (secret) and domain size D (could be 0,1n)
• Forward computation: each KP defines a permutation f(KP,,¢) on D.
Given KP and x easy to compute f(KP,,x)
Hard to invert: for any PPT A given y=f(KP,,x) for a random KP
(generated as above) and x 2R D, probability that A finds x is
negligible
• Backward computation: given Ks easy to invert f(KP,,¢)
there is an algorithm that given KP (Public) and KS (secret) and y=f(KP, x) finds x
The RSA Permutation
• Public key: N=P∙Q and public exponent e s.t. e is
relatively prime to (N)=(P-1)(Q-1)
Euler's totient
• Secret key: d s.t. d¢e = 1 mod (N)
– Equivalently: factorization of N
• The permutation: RSAN,e(x) = xe mod N
– The domain DN = ZN*
• Inverting the permutation RSAN,e(-1)(y) = yd mod N
The RSA Assumption: for random N (and e) for random y 2 ZN* hard to
invert y
Trapdoors and Signatures
Using trapdoors `naively’:
• A signature scheme secure against random
message attack for forging a random message
• Exercise: do the tree signature with trapdoors
instead of UOWHFs
The Encryption problem:
• Alice would want to send a message m{0,1}n to Bob
– Set-up phase is secret
• They want to prevent Eve from learning anything
about the message m
m
Alice
Eve
Bob
The encryption problem
• Relevant both in the shared key and in the public
key setting
• Want to use many times
• Also add authentication…
• Other disruptions by Eve
What does `learn’ mean?
• If Eve has some knowledge of m, it should remain the same
– Probability of guessing m
• Min entropy of m
– Probability of guessing whether m is m0 or m1
– Probability of computing some function f of m
• Ideally: the ciphertext sent is independent of the message m
– Implies all the above
• Shannon: achievable only if the entropy of the shared secret is at
least as large as the message m entropy
• If no special knowledge about m: then need |m| bits
• Achievable: one-time pad.
–
–
–
–
{0,1}n
Let rR
Think of r and m as elements in a group
To encrypt m send r+m
To decrypt z send m=z-r
m
©
r
c
Pseudo-random generators
• Would like to stretch a short secret (seed) into a
long one
• The resulting long string should be usable in any
case where a long string is needed
– In particular: as a one-time pad
• Important notion: Indistinguishability
Two probability distributions that cannot be distinguished
– Statistical indistinguishability: distances between
probability distributions
– New notion: computational indistinguishability
Statistical Difference
Statistical difference between two distributions X and Y on domain D is:
(X,Y) = ½  2 D |Pr[X=] – Pr[Y=]|
Equivalently
(X,Y) = maxA µ D |Pr[X 2 A] – Pr[Y 2 A]|
Statistical test
Two probability sequences {Xn}nN and {Yn}nN are statistically
indistinguishable if: for all polynomials p(.) and for all sufficiently large n
(X,Y) · 1/p(n)
Computational Indistinguishability
• Make the test A into a polynomial time computable
one
Computational Indistinguishability
Definition: two sequences of distributions {Dn} and {D’n} on
{0,1}n are computationally indistinguishable if
for every polynomial p(n) for every probabilistic polynomial time
adversary A for sufficiently large n
If A receives input y  {0,1}n and tries to decide whether y was
generated by Dn or D’n then
|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)
advantage
Pseudo-random generators
Definition: a function g:{0,1}* → {0,1}* is said to be a (cryptographic)
x
pseudo-random generator if
seed
• It is polynomial time computable
g
• It stretches the input |g(x)|>|x|
– Let ℓ(n) be the length of the output on inputs of length n
ℓ(n)
• If the input (seed) is random, then the output is indistinguishable
from random
For any probabilistic polynomial time adversary A that receives input y of length
ℓ(n) and tries to decide whether y= g(x) or is a random string from {0,1}ℓ(n) for
any polynomial p(n) and sufficiently large n
|Prob[A=`rand’| y=g(x)] - Prob[A=`rand’| yR {0,1}ℓ(n)] | · 1/p(n)
Anyone who considers arithmetical methods of producing random numbers is, of course, in
a state of sin.
J. von Neumann
Pseudo-random generators
Definition: a function g:{0,1}* → {0,1}* is said to be a
(cryptographic) pseudo-random generator if
• It is polynomial time computable
• It stretches the input (seed): g(x)|>|x|
– denote by ℓ(n) the length of the output on inputs of length n
• If the seed is random the output is indistinguishable from random
For any probabilistic polynomial time adversary A that receives input y of length
ℓ(n) and tries to decide whether y= g(x) or is a random string from {0,1}ℓ(n)
for any polynomial p(n) and sufficiently large n
|Prob[A=`rand’| y=g(x)] - Prob[A=`rand’| yR {0,1}ℓ(n)] | · 1/p(n)
Important issues:
• Why is the adversary bounded by polynomial time?
• Why is the indistinguishability not perfect?
Construction of pseudo-random generators
• Idea given a one-way function there is a hard
decision problem hidden there
• If balanced enough: looks random
• Such a problem is a hardcore predicate
• Possibilities:
– Last bit
– First bit
– Inner product
Hardcore Predicate
Definition: for f:{0,1}* → {0,1}* we say that h:{0,1}* → {0,1} is a
hardcore predicate for f if:
• h is polynomial time computable
• For any probabilistic polynomial time adversary A that receives input
y=f(x) and tries to compute h(x) for any polynomial p(n) and
sufficiently large n
|Prob[A(y)=h(x)] - 1/2| < 1/p(n)
where the probability is over the choice x and the random coins of A
• Sources of hardcoreness:
– not enough information about x
• not of interest for generating pseudo-randomness
– enough information about x but hard to compute it
Homework
Assume one-way functions exist
• Show that the last bit/first bit are not necessarily hardcore
predicates
• Generalization: show that for any fixed function h:{0,1}*
→ {0,1} there is a one-way function f:{0,1}* → {0,1}*
such that h is not a hardcore predicate of f
• Show a one-way function f such that given y=f(x) each
input bit of x can be guessed with probability at least 3/4
Single bit expansion
• Let f:{0,1}n → {0,1}n be a one-way permutation
• Let h:{0,1}n → {0,1} be a hardcore predicate for f
Consider g:{0,1}n → {0,1}n+1 where
g(x)=(f(x), h(x))
Claim: g is a pseudo-random generator
Proof: can use a distinguisher for g to guess h(x)
f(x), h(x))
f(x), 1-h(x))
Hardcore Predicate With Public Information
Definition: let f:{0,1}* → {0,1}* be a function. We say that h:{0,1}* x
{0,1}* → {0,1} is a hardcore predicate for f if
• h(x,r) is polynomial time computable
• For any probabilistic polynomial time adversary A that receives input
y=f(x) and public randomness r and tries to compute h(x,r) for any
polynomial p(n) and sufficiently large n
|Prob[A(y,r)=h(x,r)] -1/2| < 1/p(n)
where the probability is over the choice y of r and the random coins of A
Alternative view: can think of the public randomness as modifying the
one-way function f: f’(x,r)=f(x),r.
From single bit expansion to many bit expansion
Input
r
x
Internal
Configuration
f(x)
f(2)(x)
f(3)(x)
f(m)(x)
• Can make r and f(m)(x) public
– But not any other internal state
• Can make m as large as needed
Output
h(x,r)
h(f(x),r)
h(f (2)(x),r)
h(f (m-1)(x),r)
Two important techniques for showing
pseudo-randomness
• Hybrid argument
• Next-bit prediction and pseudo-randomness
Hybrid argument
To prove that two distributions D and D’ are indistinguishable:
• suggest a collection of distributions
D= D0, D1,… Dk =D’
If D and D’ can be distinguished, then there is a pair Di and
Di+1 that can be distinguished.
Advantage ε in distinguishing between D and D’ means advantage
ε/k between some Di and Di+1
Use a distinguisher for the pair Di and Di+1 to derive a
contradiction
Next-bit Test
Definition: a function g:{0,1}* → {0,1}* is said to pass the next bit test
if:
• It is polynomial time computable
• It stretches the input |g(x)|>|x|
– denote by ℓ(n) the length of the output on inputs of length n
• If the input (seed) is random, then the output passes the next-bit test
For any prefix 0≤ i< ℓ(n), for any probabilistic polynomial time adversary A that is a
predictor: receives the first i bits of y= g(x) and tries to guess the next bit, for any
polynomial p(n) and sufficiently large n
|Prob[A(yi,y2,…, yi) = yi+1] – 1/2 | < 1/p(n)
Theorem: a function g:{0,1}* → {0,1}* passes the next bit test if
and only if it is a pseudo-random generator
Sources
• Goldreich’s Foundations of Cryptography,
volumes 1 and 2
• Goldwasser, Micali and Rivest, A Digital Signature
Scheme Secure Against Adaptive ChosenMessage Attacks, SIAM J. on Computing, 1988.
Homework
• Show that the existence of UOWHFs implies the existence of
one-way functions
• Show that there are family of UOWHFs of which are not
collision intractable
• Show that if the (n, βn)-subset sum assumption holds for
β<1, then the corresponding subset function defines a family
of UOWHFs
– You may use the fact that for m=βn for most a1, a2 ,…, an
{0,…2m -1} the distribution of T=∑ i S ai is close to uniform,
when S is random.