You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
The text was updated successfully, but these errors were encountered:
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?
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.
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.
The text was updated successfully, but these errors were encountered: