Paper Info
Title
Towards Practical Non-Interactive Public-Key Cryptosystems Using Non-Maximal Imaginary Quadratic Orders
Abstract
We present a new non-interactive public-key distribution system based on the class group of a non-maximal imaginary quadratic order Cl( Δp). The main advantage of our system over earlier proposals based on (Z}/nZ)* [25,27] is that embedding id information into group elements in a cyclic subgroup of the class group is easy (straight-forward embedding into prime ideals suffices) and secure, since the entire class group is cyclic with very high probability. Computational results demonstrate that a key generation center (KGC) with modest computational resources can set up a key distribution system using reasonably secure public system parameters.  In order to compute discrete logarithms in the class group, the KGC needs to know the prime factorization of Δp=Δ1 p2. We present an algorithm for computing discrete logarithms in Cl(Δp) by reducing the problem to computing discrete logarithms in Cl(Δ1) and either F*p or F*p2. Our algorithm is a specific case of the more general algorithm used in the setting of ray class groups [5]. We prove—for arbitrary non-maximal orders—that this reduction to discrete logarithms in the maximal order and a small number of finite fields has polynomial complexity if the factorization of the conductor is known.
Year
DOI
Venue
2003
10.1023/A:1025746127771
Des. Codes Cryptography
Keywords
Field
DocType
discrete logarithm,non-maximal imaginary quadratic order,identity based cryptography,non-interactive cryptography
Prime (order theory),Discrete mathematics,Combinatorics,Finite field,Embedding,Pohlig–Hellman algorithm,Baby-step giant-step,Factorization,Prime factor,Mathematics,Discrete logarithm
Journal
Volume
Issue
ISSN
30
3
1573-7586
Citations 
PageRank 
References 
7
0.54
19
Authors
3
Name
Order
Citations
PageRank
Detlef Hühnlein113041.35
Michael J. Jacobson Jr.232650.65
Damian Weber39816.23