10

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?

AdveRSAry
  • 624
  • 3
  • 14

2 Answers2

8
  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.
8

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.

Vadim L.
  • 1,146
  • 6
  • 9
  • 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?     – AdveRSAry May 22 '17 at 22:14
  • 1
    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. – Vadim L. May 22 '17 at 22:41
  • 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? – AdveRSAry May 22 '17 at 22:54
  • 1
    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. – Vadim L. May 23 '17 at 07:20
  • Seems I'm currently too ignorant in the field. Thanks! :) – AdveRSAry May 23 '17 at 10:21
  • @VadimL. I believe with "cryptosystem based on a torus" is meant to use a torus $\mathbb{T} = \mathbb{R}/\mathbb{Z}$, which is a set of real numbers modulo 1. And to use something like $\mathbb{T}_N[X] = \mathbb{R}[X]/(X^N + 1) \mod 1$ for LWE. Indeed, is something like that possible? And what would be its security? –  Aug 06 '17 at 12:50
  • One could almost certainly "artificially" modify lattice-based schemes so that they work over the torus, but I am not sure what advantage this would have. If there is an example of a scheme that naturally uses this structure, then we can discuss its security and efficiency. – Vadim L. Aug 07 '17 at 12:42
  • Asking for clarification, the efficiency doesn't really apply to storage, right? in your presentation way back on 2nd BIU https://cyber.biu.ac.il/wp-content/uploads/2017/01/slides-barilan11.pdf#page=17, you hinted that by using dependent (cycled) $a_i$, we can reduce the storage of the public matrix $A$ from $O(n^2)$ to $O(n)$.

    But we actually use independently sampled $a_i$, each being a degree $n$ polynomial, so the overall storage is still $O(n*m)$ with m samples for matrix $A$, correct?

     – Alex Xiong Jul 05 '23 at 03:42