4
$\begingroup$

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.

$\endgroup$

closed as too broad by otus, e-sushi Jul 9 '16 at 9:38

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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 '16 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 '16 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$ – Lolums Jul 9 '16 at 13:18
  • $\begingroup$ I read the same article. Too bad they closed this for whatever reason. $\endgroup$ – user9070 Jul 9 '16 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 '16 at 21:05