I read that Google want to integrate this into HTTPS because it is safe against quantum computers.

However, the Wikipedia article might as well be written in Latin because it makes very little sense to me.

How does Ring Learning with Errors work and why is the algorithm safe from quantum computers?

Edit: there's a question like this about how public key encryption works, so I figured that this would be good too but it seems that it's too complicated to explain in simple terms.

  • $\begingroup$ It is considered safe from quantum computers because it was proven to be as hard as lattice problem (gapCVP if I'm not mistaken). The proof consist of a quantum reduction, meaning that as if a quantum computer could break LWE it is able to solve gapCVP. I suggest you take a look at Oded Regev's video on youtube where he explains how LWE works and how the reduction is done. $\endgroup$
    – Yuon
    Jul 9, 2016 at 9:24
  • $\begingroup$ Do you know the mathematical meaning of rings? ​ Do you know modular arithmetic? ​ Do you know what Z/qZ means? ​ Do you know what polynomial rings are? ​ Do you know about polynomial long division? ​ ​ ​ ​ $\endgroup$
    – user991
    Jul 9, 2016 at 10:14
  • $\begingroup$ @RickyDemer no, nah, nope, negative, uhh that's just regular long division? Looks like I have some reading to do. Thanks! $\endgroup$
    – Lucien
    Jul 9, 2016 at 13:18
  • $\begingroup$ I read the same article. Too bad they closed this for whatever reason. $\endgroup$
    – user9070
    Jul 9, 2016 at 14:29
  • $\begingroup$ @Lolums : ​ It might be better to read about modular arithmetic before rings, since modular arithmetic is a significant motivator for the definition of rings. ​ ​ ​ ​ $\endgroup$
    – user991
    Jul 9, 2016 at 21:05


Browse other questions tagged or ask your own question.