Can someone please tell me why is the Ring-LWE more efficient?
By introducing polynomials in place of matrices, what kind of optimizations do we introduce that make Ring-LWE more efficient?


The previous (galvatron's) answer gave two good reasons why Ring-LWE is more efficient. They explain why the running time of LWE schemes is worse than of Ring-LWE ones. (The n^2 vs n equations is more of an efficiency issue because in both cases, this part of the key is expanded from a 256-bit seed using an XOF. So it just takes a lot longer to expand an LWE key than a Ring-LWE one).

In addition to the speed advantage, there is also the size advantage schemes based on Ring-LWE enjoy. In PKE, the message space corresponds to the size of the ring -- therefore ring-LWE over an n-dimensional ring allows one to encrypt a larger message at no extra cost.

In Fiat-Shamir digital signatures (ones that are constructed from Sigma protocols), the ring dimension determines the size of challenge space. The larger the challenge space, the less soundness error the scheme has and the fewer times the underlying identification scheme has to be repeated, and the shorter the signature is.

There are ways to go around having a small message/challenge space when using regular LWE, but those always require increasing the size of the public key by a factor related to the security parameter.

  • $\begingroup$ Are we restricted to $\{ 0, 1 \}$ for our message space in case of LWE? Also, I'm not sure if a crypto system based on Torus has been made yet, but what kind of advantages does it have over Ring structures? $\endgroup$ – AdveRSAry May 22 '17 at 22:14
  • 1
    $\begingroup$ By increasing the modulus, you can make your message-space larger for LWE. For a message space of {0,1}^k, you need to increase your modulus by roughly a factor of 2^k. You can look at the LWE key exchange Frodo where they use a bunch of tricks to find a nice balance between the public key size and the message space. In the end, it ends up being about a factor of 10 larger than Ring-LWE (for 256-bit messages). ... I do not know what a cryptosystem based on Torus is. $\endgroup$ – Vadim L. May 22 '17 at 22:41
  • $\begingroup$ I meant to ask that does LWE only support homomorphic bit operations as atomic operation? I know that we can extend them to arithmetic circuits, but is there an atomic homomorphic operation on integer level? Like, I read in a paper based on Ring LWE by Brakerski and Vaikuntanathan in which we could directly obtain homomorphic multiplications and additions on integers. But, in all the LWE based schemes I've seen, we only encrypt bits, and encrypt multiple times to get an encryption of an integer. So, can we achieve integer encryption in LWE? $\endgroup$ – AdveRSAry May 22 '17 at 22:54
  • 1
    $\begingroup$ You can encrypt integers modulo p using LWE. All operations are implicitly modulo q. pk: A, t=As+e. sk: s enc(m): ( u=p(rA+e'), v=p(rt+e'')+m ). dec(u,v) = (v-us mod p) = p(rAs+re+e'') + m - p(rAs+e's) mod p = pre +pe''+m -pe's mod p = m. Everythyng holds as long as the error term pre +pe''- pe's is small-enough. This is why you cannot take p to be too large with respect to q. $\endgroup$ – Vadim L. May 23 '17 at 7:20
  • $\begingroup$ Seems I'm currently too ignorant in the field. Thanks! :) $\endgroup$ – AdveRSAry May 23 '17 at 10:21
  1. If you're using LWE for cryptography, then you'll need a system of $n$ linear equations with errors (mod some $q$). So for those $n$ equations, your key size will have $O(n^2)$ coefficients. In Ring-LWE, you only need $n$ coefficients (see Oded Regev's survey, page 5).
  2. Because you're dealing with polynomials now, you can use the Fast Fourier Transform or (even better for finite fields) the number theoretic transform to multiply them.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.