Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

We study various number theoretic problems that arise from cryptographic

protocols. Our results are used to prove the security of new and

existing protocols. The thesis is divided into five parts. We begin

by studying algebraic algorithms which are a weak model of

computation suitable for modeling number theoretic algorithms.

We prove a hardness criteria for algebraic algorithms and present

several number theoretic consequences of this result.

Next we study black box fields and show how they can be used to

break algebraically homomorphic encryption schemes. These algorithms

show that over the group of points of an elliptic curve the hardness

of computing discrete-log implies the security of the Diffie-Hellman

protocol. We go on to study the security of portions of the

Diffie-Hellman secret. We show that $sqrt{log p}$ bits of the

Diffie-Hellman secret are as hard to compute as the whole secret.

Furthermore, in some cases the individual most significant bit is sufficient.

These results lead us to suggest a new variant of the Diffie-Hellman

protocol for which the most significant bit of the secret is hard to compute.

The fourth part generalizes the Goldreich-Levin theorem to arbitrary

finite groups and describes some applications to learning.

Finally in the last chapter we study a coding theory problem which arises

from the problem of fingerprinting digital data.