Full text  Click to download. 
Citation  PhD Thesis, Stanford University, 2004.

Author  Jeremy Horwitz

We discuss three main topics: the use of Cayley graphs to present
an essentially optimal algorithm for the discrete logarithm
problem, the extension of identitybased encryption (IBE) to
hierarchical IBE, and the application of higherorder residues to
various cryptologic applications.
First, we focus on the discretelogarithm problem, showing an
algorithm that works in optimal time (up to logarithmic factors)
and uses only a small amount of space. Our algorithm is a
modification of the classic Pollard rho algorithm, introducing
explicit randomization of the parameters for the updating steps of
the algorithm. In proving that the algorithm works as claimed, we
see several intermediate and related results of independent
interest.
Next, we present the concept of hierarchical identitybased
encryption (HIBE) schemes. An IBE scheme is one in which any
string can be used as a public key (e.g., the recipient's email
address); private keys are distributed by one central
authority. An HIBE scheme is the hierarchical analogue of an IBE;
among its many advantages those that come from splitting the
keydistribution burden as well as those that come from
escrowrelated applications. We present an example of an HIBE
scheme, give security definitions, and mention some of the
applications of HIBE schemes.
Finally, we describe some cryptologic applications of the
rthpowerresidue symbol (a higherorder analogue of the Jacobi
symbol). We present an encryption scheme in which recipients only
need an rth root of unity to decrypt. By simply changing the value
of r and distributing roots to a new group, controlling who
receives such roots,the set of decrypters can be changed without
generating a new modulus (N = pq).
We present other applications of the system as well as another
application of the rthpowerresidue symbol: how to speed up the
elliptic curve method for factoring numbers of the form N =
pq^r.