Cryptography Reference
In-Depth Information
Guideline:
Start by showing that the ensemble DES
1
F
n
is not pseudorandom (a single
query suffices here). Use two related queries in order to distinguish DES
2
F
n
from a random
permutation.
Exercise 37 (Suggested by Luca Trevisan):
Assuming the existence of pseu-
dorandom function ensembles, prove that there exists a pseudorandom permutation
ensemble that is not strongly pseudorandom.
Guideline:
First construct a pseudorandom permutation ensemble with seed length
smaller than or equal to the logarithm of domain size. Next modify it so that the seed
is mapped to a fixed point (e.g., the all-zero string) and so that the modified ensemble
remains one of permutations.
Exercise 38:
In similarity to Exercise 36, prove that the ensemble DES
3
F
n
is notstrongly
pseudorandom.
Guideline:
This requires more thought and probably more than a couple of queries. You
should definitely use queries to both oracles.
