1
$\begingroup$

I've been reading up on the Ring Learning with Errors problem and the proposed attacks, in relation to homomorphic encryption. Some of the literature has been quite difficult to understand - what I want to know is if it is possible to solve this problem? And if so, what is a general outline of a possible attack? I'm quite new to this so any basic explanations would be very helpful!

Edit (thanks to user fgrieu): What are known methods to solve small instances of RLWE problems, as used or proposed in cryptography with larger parametrization?

$\endgroup$
  • 1
    $\begingroup$ The question is similar to: (how) is it possible to solve the factorization problem?. That is insufficiently specific: we can factor the integer 15, but not a properly chosen 4096-bit composite, at least today. Similarly, we can solve some RLWE problems. Those we can solve are by definition not of practical interest for use in cryptography. The question could and should be reworded to be more specific. $\endgroup$ – fgrieu Sep 3 '19 at 15:20
  • $\begingroup$ Even the most basic example of one of the problems which has been broken or the technique behind it would be helpful in understanding some of the method! Or maybe an explanation of what makes some of the problems easier to solve, and some harder? Do we need to use the method of factorization to solve it? $\endgroup$ – dashybrown Sep 3 '19 at 16:07
  • $\begingroup$ Suggestion to maybe avoid that the question gets closed: what are known methods to solve small instances of RLWE problems, as used or proposed in cryptography with larger parametrization? $\endgroup$ – fgrieu Sep 3 '19 at 16:13
  • $\begingroup$ I wrote a paper and presentation that survey the attacks and the nature of the “weak” instantiations of Ring LWE. See web.eecs.umich.edu/~cpeikert/pubs/slides-instantiate-rlwe.pdf and web.eecs.umich.edu/~cpeikert/pubs/instantiate-rlwe.pdf $\endgroup$ – Chris Peikert Sep 4 '19 at 23:20
  • 1
    $\begingroup$ @ChrisPeikert Could I persuade you to create a minimal summary and post that as an answer? There are multiple close votes on this question as "too broad", but such a summary would very likely count as an answer. $\endgroup$ – Maarten Bodewes Sep 9 '19 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.