| 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 identity-based encryption (IBE) to
hierarchical IBE, and the application of higher-order residues to
various cryptologic applications.
First, we focus on the discrete-logarithm 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 identity-based
encryption (HIBE) schemes. An IBE scheme is one in which any
string can be used as a public key (e.g., the recipient's e-mail
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
key-distribution burden as well as those that come from
escrow-related 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
rth-power-residue symbol (a higher-order 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 rth-power-residue symbol: how to speed up the
elliptic curve method for factoring numbers of the form N =
pq^r.