It's hard for me to comprehend simple asymmetric encryption let alone understand how this solution is quantum proof. Everytime I read something like this I wonder if I'll ever catch up with the times.
As a side effect of quantum only being more efficient for a very limited set of problems, there are many crypto systems for which quantum provides no effective benefits.
This can all be made very precise. For those with some math background, almost two decades ago I wrote a decent technical summary of the DLP style aspect at https://arxiv.org/abs/quant-ph/0411037
Do you mean those are the only two KNOWN problems? Otherwise the claim is very surprising. It is not even known whether QBP=P, I thought, while on the other hand there are some sampling problems in QBP that last I heard were thought to be outside PH (Aaronson and Arkhipov's boson sampling, and whatever the quantum supremacy crowd is currently doing). But, those are probably useless for cryptography.
Essentially any problem can be poised as an unstructured search. But the quantum speedup for generic unstructured search is modest-- a sqrt in the number of operations. This can be compensated just by doubling the number of bits of the effective search space.
But the idea is right, sqrt speedups even if possible would not weaken crypto enough to break it since encoding would still be exponentially faster, and that's all that's needed for crypto: encoding sufficiently faster than decoding without knowing a secret.
Of course, the circuit for reversibly computing a public key ends up ginormous... but it's still vastly smaller than the keyspace. And if we were limiting ourselves to the practical we wouldn't be talking about quantum computers. :P
> QC can only solve two problems more efficiently than classical (and this is proven very thoroughly)
I didn't see a discussion of the proof in your article, although maybe I missed it. I thought your article instead emphasized that all quantum algorithms that have been discovered so far can only be more efficient relative to classical algorithms with problems that can be reduced to hidden subgroup problems.
Is there some other research (that maybe you mentioned) that goes on to prove that no new quantum algorithm could ever do any better on other problems? If not, isn't this a conjecture (perhaps a widely-believed conjecture) of complexity theory? When I last looked at the Complexity Zoo, I thought there were quite a few different complexity classes that had been defined relative to quantum computing, and it was apparently unresolved whether many of them could be reduced to one another.
I don't really know this area at all, beyond having heard of Grover's and Shor's algorithms and read the SMBC on what quantum computing doesn't do. And having seen some candidate PQ cryptographic algorithms, without understanding exactly why any of them were considered credible as candidates. :-)
The short answer is that NTRU uses convolution polynomial lattices. Breaking the cryptosystem requires finding a "short" basis for a lattice described by the private key. There are efficient algorithms for this in R^2, but not for high dimensional convolutional polynomial spaces (LLL Reduction is the best I'm aware of, which is greater than O(d^5) where d is the number of dimensions https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%...).
Do note the impl I did is absolutely terrible and probably subtly buggy but might get the idea across. Also, it splits the message into blocks and encrypts that instead of just wrapping a symmetric encryption algorithm because I was young and naive. :)