Applications of Cayley Graphs, Bilinearity, and Higher-Order Residues to Cryptology

Full textClick to download.
CitationPhD Thesis, Stanford University, 2004.
AuthorJeremy 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.

Back to publications
Back to previous page