Quantum security of OSIDH

[xbonnetain]

I have not looked at OSIDH in details, but presenting an identical classical and quantum security level is a bit surprising. From what I understood from [DD21], the cost of the classical attack comes from lattice sieving, thus using a quantum sieving algorithm would directly give a better attack.
A few quantum sieving algorithms have been proposed, to the best of my knowledge the smallest claimed exponent is 0.2563 in https://eprint.iacr.org/2022/676 by me, Chailloux, Schrottenloher and Shen.

[defeo]

Hi Xavier. Thanks for the report, I think you're right, there must be a gap between the quantum and the classical cost. TBH, I'm not convinced 0.292 is the right classical exponent either. As we explain on page 18 of https://eprint.iacr.org/2021/1681, the complexity is dominated by the cost of solving SVP in ∞-norm, and the best exponent known for this is 0.62. But in practice we solve for ℓ₂-norm, and that works very well for proposed parameters.

Since this site is about proven attacks, I think is better if we only use proven statements. In your opinion, what's the best quantum exponent for SVP in ∞-norm?

[xbonnetain]

I'm not aware of any quantum work on that matter, ad I don't see any obvious naive algorithm for sieving in ∞-norm that would give a relevant exponent, so 0.62 might be the answer for now.