4 ms·

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 wond

• floatboth 5y ago
  IIUC, NTRU is only "quantum proof" because there is no (publicly known) quantum algorithm for breaking it, while there is Shor's for everything discrete logarithm based (both RSA and elliptic curve anything).
  • bawolff 5y ago
    Until we prove P!=NP that (i.e. its only secure because we dont know how to solve it) is pretty much true of all crypto algorithms, even classically.
    • gpm 5y ago
      This is true, but we don't know even more for quantum computers, because we have spent a lot less time studying quantum algorithms, so not yet having found an algorithm is much weaker evidence that the algorithm doesn't exist.
• 0xdeadb00f 5y ago
  I can understand Curve25519, Diffie-Hellman, but lattice-based crypto goes way over my head.
• eximius 5y ago
  I have a really old (college) implementation of plain old NTRU in Python, if you'd like a little insight into what NTRU is and how it works at a superficial level (kind of like how RSA is never textbook RSA). There are also some slides explaining the math, but you have to be comfortable with some college level group theory (even reading my own slides is hard because I haven't used it since then). 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%93Lov%C3%A1sz_lattice_basis_reduction_algorithm 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. :) https://github.com/logannc/pyNTRUEncrypt https://github.com/logannc/pyNTRUEncrypt
• SideQuark 5y ago
  QC can only solve two problems more efficiently than classical (and this is proven very thoroughly): unstructured search and discrete log problem (well, more accurately, certain hidden subgroup problems). DLP covers factoring, hence RSA. Elliptic curve crypto is directly a discrete log problem, as the crypto is based on the underlying group defined over rational curve points. NTRU is based on neither problem; it's based on a lattice problem in a certain class of rings. Lattice problems cannot be reduced to either class of problems for which quantum provides speedups. 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 https://arxiv.org/abs/quant-ph/0411037
  • nullc 5y ago
    > Lattice problems cannot be reduced to either class of problems for which quantum provides speedups. 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.
    • SideQuark 5y ago
      Unstructured search has sqrt n speedup once all items are loaded, which generally takes O(n) classical time anyways, so Grover doesn't generally present a sqrt speedup for crypto (or any database search where the database is not already loaded as a quantum state). 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.
      • nullc 5y ago
        The 'database' can be a function implemented as a quantum circuit, e.g. a function that takes a candidate private key (and noise inputs) and computes a public key from it and compares it to the target's key. Grover gets handed this function as an oracle and asked to find the input that makes it return 1, which it can do with sqrt(|key|) operations. 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