Re: Quantum Computer vs. crypto

From: Unruh (unruh-spam_at_physics.ubc.ca)
Date: 06/27/05 

Date: 27 Jun 2005 20:53:59 GMT

Mike Amling <nospam@nospam.com> writes:

>Kristian Gjøsteen wrote:
>> Mike Amling <nospam@nospam.com> wrote:
>>
>>> All the DH I've seen has used a single, fixed, generator and its
>>>powers. If there's another way of using DH, I don't know what it is.
>>
>>
>> DH is for a finite cyclic group. The non-abelian groups I've seen in
>> crypto are infinite, and use commuting elements.
>>
>> I can never remember exactly how things go, but it looks something
>> like the following:
>>
>> c is a fixed element in the group. Alice and Bob can choose random
>> elements x and y such that xy = yx.
>>
>> Alice Bob
>>
>> x random y random
>>
>> --- xcx^{-1} -->
>>
>> <-- ycy^{-1} ---
>>
>> secret = secret =
>> x(ycy^{-1})x^{-1} y(xcx^{-1})y^{-1}
>>
>> They have the same secret because x and y commute, so
>>
>> (xy)c(yx)^{-1} = (yx)c(xy)^{-1} .
>>
>> The idea is that given c, xcx^{-1} and ycy^{-1}, finding xyc(xy)^{-1}
>> should be hard. I don't think anyone has come up with a group where
>> this problem seems to be hard.

There is no reason why c should commute with xy, in fact if it did, both
would just give c, and the secret would be rather public.

Quantcast