search

defeo / hhs-keyex

Research paper on improving the Hard Homogeneous Spaces key exchange protocol (by Couveignes and Rostovtsev-Stolbunov)
0 stars 0 forks source link

Hardness #15

Closed abelian closed 6 years ago

abelian commented 6 years ago

In the intro we say "But for other homogeneous spaces, inverting \varphi_x may have no relationship with any DLP, and may potentially be harder to solve, even for a quantum computer". But Couveignes notes that we can always use BSGS under certain conditions on G and X, which I think are met in the isogeny paradigm, and which I'm going to wildly generalize and say are probably met whenever X is a cryptographically useful HHS, too. So the classical difficulty is at most O(\sqrt{#X}) time and space, which isn't harder than the DLP. Classic isogeny-finding algorithms are just doing the Pollard version of this, I suppose. My point is that

  1. Maybe HHS inversion is indeed "harder to solve" than the DLP on a quantum computer, but
  2. It can't be harder to solve in an absolute sense.

I can't think of a way of expressing this in the intro without everything spiralling out of control, but we should make sure we've fixed this statement before submitting.

defeo commented 6 years ago

Something alog the lines of "may potentially not be victim to the same families of attacks" (Shor, I'm looking at you)?

abelian commented 6 years ago

Done.