# Exactly what part of SIDH is proven to be NP-hard?

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?

• Secure against quantom computer does not imply NP hard. – Meir Maor Aug 23 '18 at 10:05
• @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. – edlothia Aug 23 '18 at 10:42
• I don't know of any part of SIDH which has been shown to be NP-hard – poncho Aug 23 '18 at 16:36

## 1 Answer

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

• Is SIDH in itself proven quantum hard (regardless of any attacks planned against it?) – edlothia Aug 23 '18 at 10:52
• @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. – fkraiem Aug 23 '18 at 12:11