A generalization of the Diffie-Hellman problem and related cryptosystems allowing fast decryption
Sachar Paulus, Tsuyoshi Takagi · 1998
We present a generalization of the Diffie-Hellman problem. It is based on the problem of determining coset representatives of group "extensions". This generic one-way function allows the development of ElGamal-like encryption protocols where the decryption process is much faster than in existing protocols, while providing the same security. As examples, we present and analyze protocols using ZZ=nZZ, using elliptic curves and using class groups of imaginary quadratic orders. In that latter case, we present a protocol directly based in the coset problem. Key words: Diffie-Hellman key-distribution, ElGamal cryptosystem, discrete logarithm problem, elliptic curve, quadratic field, coset problem, fast decryption, factoring 1 Introduction Consider the following problem: Problem 1 (Diffie-Hellman) Let G be a finite abelian group, a; g 2 G with a = g d and r 2 IN. Given a; g; g r compute a r . If one can solve the discrete logarithm problem, namely given g and a compute d, then one can ...