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?

  • 2
    $\begingroup$ Secure against quantom computer does not imply NP hard. $\endgroup$ – Meir Maor Aug 23 '18 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 '18 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 '18 at 16:36

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})$.

  • 1
    $\begingroup$ Is SIDH in itself proven quantum hard (regardless of any attacks planned against it?) $\endgroup$ – edlothia Aug 23 '18 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 '18 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.