Studies in Computational Number Theory with Applications to Cryptography (thesis)

Abstract:

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.