6 ms·
Lifting Discrete Logarithm Based Cryptography to Post-Quantum Cryptography
- efitz 4y agoThis looks really promising. I wish the abstract used some English words :-D
- Aardwolf 4y agoIndeed! 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?
- texaslonghorn5 4y ago> 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?
- jmount 4y agoYeah, 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.
- tromp 4y agoThere 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.
- opheliate 4y agoIt’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.
- cryptonector 4y agoIt could be a translation error. The author clearly does not speak English as a first language.