Indeed! The main thing that interests me is how does it compare to other post-quantum crypto schemes, e.g. does it also require a very large key size like some others do?
> rising to the non-associative power indices ... in the last two decades has
been analyzed and does not have a quantum polynomial algorithm that solves it. The problem is called
Exponential Congruences Problem.
The author uses similar wording a couple times and it is a little ambiguous? Does "does not have" mean a superpolynomial quantum lower bound has been discovered for this algorithm (or is there a reduction to some other important conjectured complexity theorem)? Or is it just that a polynomial algorithm has not been discovered yet?
Yeah, knowing there is no poly-time quantum algo would be as big as showing P!=NP. If it is "no known" algo, it is well known not to use the stronger wording. Outside of oracle results an "at least this hard result" is a big deal.
7 comments
[ 0.73 ms ] story [ 28.0 ms ] threadThe author uses similar wording a couple times and it is a little ambiguous? Does "does not have" mean a superpolynomial quantum lower bound has been discovered for this algorithm (or is there a reduction to some other important conjectured complexity theorem)? Or is it just that a polynomial algorithm has not been discovered yet?
It's almost as bad as saying that NP stands for Non Polynomial time.