1. Write an algorithm, in pseudocode or a language of your choice, to compute a^b (mod n) where a, b, n may be hundreds of bits long (i.e. larger than the built-in integer type).

    Answer should use repeated squaring and some BigInteger library.

  2. If large numbers can be efficiently factored, how does one break RSA cryptography?

    If the modulus m=pq is factored, the size of the RSA group, (p-1)(q-1) is known. Since the public and private keys e, d satisfy ed=1 (mod (p-1)(q-1)), d can now be computed from e.

  3. In a zero-knowledge protocol, the verifier issues a challenge that can be correctly answered with probability 1 by an honest prover, and with probability 1/2 by a dishonest prover. How can the verifier construct a zero-knowledge protocol where she is convinced by a dishonest prover with probability less than 1/1000?

    Run the original protocol ten times, re-randomizing the challenge each time. The probability the dishonest prover answers correctly is 1/2^10 = 1/1024 < 1/1000.

  4. If Alice proves a statement to Bob interactively in zero knowledge, why must Charlie, a bystander observing the interaction, be not convinced of the statement?

    The zero-knowledge property stipulates that verifiers can simulate accepting interaction transcripts without the underlying statement being true. Therefore, seeing an accepting interaction transcript does not prove the statement; all the content of the proof lies in flipping the private coins yourself.

    Informally: Alice and Bob could be colluding to produce an accepting interaction transcript, i.e. if Bob is sharing with Alice his private coins.

  5. What does it mean for a commitment scheme to be computationally binding? How can one attack a commitment scheme that is not computationally binding?

    A probabilistic polynomial-time committer cannot, with non-negligible probability, find two messages with the same commitment. If a commitment scheme is not computationally binding, a dishonest committer can publish a commitment and later decide which of multiple messages it corresponds to, rather than being bound to one message at commit-time.

  6. What is an extractor and why is it important?

    An extractor is a polynomial-time algorithm run with oracle access to a prover. In a ZK proof of knowledge, an extractor formalizes the notion of having knowledge. If a prover can convince the verifier he knows some witness (the knowledge), the extractor, with oracle access to that prover, should be able to output that witness.

  7. How would you explain the Fiat-Shamir heuristic to a friend?

    The Fiat-Shamir heuristic makes a non-interactive version of an interactive ZK proof of knowledge. In the interactive proof, the verifier sends the prover random challenges, which the prover must answer correctly. The Fiat-Shamir heuristic transforms the protocol as follows: wherever the verifier flips coins in the interactive proof, the prover simulates those coin flips with the output of a cryptographic hash function.