1
$\begingroup$

SIDH is quantum secure, why is it quantum secure? Exactly which part of the algorithm is proven to be NP-hard? Computing the isogeny function?

$\endgroup$
3
  • 2
    $\begingroup$ Secure against quantom computer does not imply NP hard. $\endgroup$
    – Meir Maor
    Aug 23, 2018 at 10:05
  • $\begingroup$ @MeirMaor Understood, I meant that SIDH is quantum secure because it’s been proven to be NP-hard, but nowhere can I find that paper. $\endgroup$
    – edlothia
    Aug 23, 2018 at 10:42
  • 2
    $\begingroup$ I don't know of any part of SIDH which has been shown to be NP-hard $\endgroup$
    – poncho
    Aug 23, 2018 at 16:36

1 Answer 1

5
$\begingroup$

SIDH is believed to be quantum secure because the fastest known quantum attacks against it (which is based on claw finding algorithm) require exponential time with complexity $\mathcal{O}(p^{1/6})$.

$\endgroup$
2
  • 1
    $\begingroup$ Is SIDH in itself proven quantum hard (regardless of any attacks planned against it?) $\endgroup$
    – edlothia
    Aug 23, 2018 at 10:52
  • 6
    $\begingroup$ @edlothia No, it is not proven quantum-hard, only believed to be so because no quantum attacks are known, just like factoring et al. are believed to be classical-hard because no classical attacks are known. $\endgroup$
    – fkraiem
    Aug 23, 2018 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.