A printable PDF is available.

**Objectives:** There are two objectives with this assignment:
To start you thinking about models of security and to give you some
practice using LaTeX in writing mathematical material. Therefore,
solutions should be prepared
using LaTeX!

- Write up the coin-flipping protocol from Bellare/Rogaway Section
1.2.3 in your own words, using a step-by-step presentation (use an
`enumerate`

environment in LaTeX). Next, make a table of some values of*p*,*q*, and*N*that could be used by Alice to commit to a 0 and to a 1 (at least two examples for each value). Obviously, to be able to write this out you'll want to use values that are much smaller than the 500-bit primes mentioned in the notes, but this is simply to illustrate the process, not to give values that would provide any security. Your table should look something like this:Bit Committed *p**q**N*0 ... ... ... 0 ... ... ... 1 ... ... ... 1 ... ... ... - The most fundamental notion of computational complexity used in
discussing the security of cryptographic protocols is
the notion of polynomial-time algorithms. Specifically, we would like
for our protocols to be such that no polynomial-time algorithm can
break them. A key assumption for many public-key algorithms is that
there is no polynomial-time algorithm for factoring -- in other
words, an algorithm that can take the product of two
large prime numbers (
*N=pq*) as input and produce the factors*p*and*q*.Consider the basic algorithm of trying all integers from

*2,...,N-1*as possible divisors and testing them all using a trial division. This obviously is a correct factoring algorithm, but what is the complexity of the algorithm? Carefully justify your analysis, and clearly justify your answer to the basic question: Is this a polynomial time algorithm? - (
*Graduate Students Only*) Answer this question with as much detail and justification as you can: a pseudorandom number generator (a "PRNG" -- described in Section 1.2.1) should be one-way in the sense that if you are given*b*bits of output you cannot (in polynomial time) compute the seed used by the PRNG. What does this mean as far the size of the seed? Can it be a constant number of bits (unrelated to*b*)? Could it be*Theta(logb)*bits? What is the right restriction on the size?