Studies in Computational Number Theory with Applications to Cryptography (thesis)
Report ID: TR-523-96Author: Boneh, Dan
Date: 1996-07-00
Pages: 136
Download Formats: |Postscript|
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.