An apparatus and a method for generating a secure cipher key over an insecure channel. In one embodiment, a set of polynomials is generated and shared between a first party and a second party over the insecure channel. The first party generates a first random exponent for its private cipher key. The second party generates a second random exponent for its private cipher key. The first party operates on the set of polynomials with the first random exponent and sends the results to the second party. The second party operates on the set of polynomials with the second random exponent and sends the results to the first party. A shared cipher key is computed based on the exchanged operation results.