Lifting Discrete Logarithm Based Cryptography to Post-Quantum Cryptography

eprint.iacr.org

59 points·Laaas··7 comments

> 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.

There is indeed no excuse for saying "there is no" when they mean "there is no known"

It's almost as bad as saying that NP stands for Non Polynomial time.

It could be a translation error. The author clearly does not speak English as a first language.

It’s probably worth remembering this is a pre-print of the paper. This is the kind of thing that would be corrected when actually published.

This looks really promising. I wish the abstract used some English words :-D

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?

Reply on news.ycombinator.com