Transcript pps

Foundations of Cryptography
Lecture 8
Lecturer: Moni Naor
Recap of lecture 6 (three weeks ago)
• The one-time signature scheme from one-way
function (`Lamport’)
• The idea of regeneration
• Signature schemes
• Notions of security
What Is 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
•
• Output: s
``Anyone” who is given pk and (m,s) can verify it
– Signature Verification Algorithm
• Input: (pk, m, s)
• Output: `accept’ or `reject’
– 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?
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 constitute a failure of the system
•
What is a legitimate forgery?
Existential unforgeability in signature
schemes
A signature scheme is
• existentially unforgeable
under an
• adaptive 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 (m,s) so that
– m {m1, m2, … mq}
But
– (m,s) is a valid signature.
has probability of success at most ε
existentially 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
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 one g  G for all nodes of the tree?
Question: how to assign messages to nodes in the tree?
What exactly are we after? Answered!
Specific proposal
Key generation:
• generate the root
– Three keys for a one-time signature scheme
– A function g  G from a family of UOWHF
Signing algorithm:
• Traverse the tree in a BFS manner
– Generate a new triple (three keys for one-time signatures)
– Sign the message using the middle part of node
– Pt 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
Signing verification:
• Verify the one-times signature given.
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
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 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 then 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
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
Alice
Eve
Bob
The encryption problem
• Relevant both in the shared key and in the secret
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 should remain the same
– Probability of guessing m
• Min entropy of m
•
– Probability of guess whether m is m0 or m1
– Probability of computing some function f of m
Ideally: the message sent is a 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
•
Achievable: one-time pad.
– then |m|
–
–
–
–
Let rR {0,1}n
Think of r and m as elements in a group
To encrypt m send r+m
To decrypt z send m=z-r
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
Pseudo-random generators
Definition: a function g:{0,1}* → {0,1}* is said to be a (cryptographic) pseudorandom generator 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 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
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
Sources
• Goldreich’s Foundations of Cryptography,
volume 1