Algebraic generalization of Diffie–Hellman key exchange

Abstract

The Diffie–Hellman key exchange scheme is one of the earliest and most widely used public-key primitives. Its underlying algebraic structure is a cyclic group and its security is based on the discrete logarithm problem (DLP). The DLP can be solved in polynomial time for any cyclic group in the quantum computation model. Therefore, new key exchange schemes have been sought to prepare for the time when quantum computing becomes a reality. Algebraically, these schemes need to provide some sort of commutativity to enable Alice and Bob to derive a common key on a public channel while keeping it computationally difficult for the adversary to deduce the derived key. We suggest an algebraically generalized Diffie–Hellman scheme (AGDH) that, in general, enables the application of any algebra as the platform for key exchange. We formulate the underlying computational problems in the framework of average-case complexity and show that the scheme is secure if the problem of computing images under an unknown homomorphism is infeasible. We also show that a symmetric encryption scheme possessing homomorphic properties over some algebraic operation can be turned into a public-key primitive with the AGDH, provided that the operation is complex enough. In addition, we present a brief survey on the algebraic properties of existing key exchange schemes and identify the source of commutativity and the family of underlying algebraic structures for each scheme.

Keywords

• cryptography
• key exchange
• homomorphic image problem
• universal algebra
• 94a60
• 08a70
• 08a62