Questions tagged [ring-lwe]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
10
votes
0answers
70 views

Decision R-LWE parameters for spherical error with worst-case hardness

In Peikert et al.'s most recent work (STOC 2017) a direct reduction of worst-case lattice problems to decision R-LWE is achieved for $\alpha q \ge 2 \cdot \omega(1)$ (Theorem 6.2), where $\alpha q$ is ...
4
votes
1answer
149 views

Minimum distance between polynomials in ring-LWE

Let $R_q=\mathbb{Z}_q[x]/\langle f(x)\rangle$ where $f(x)=x^n+1$, as in the ring-LWE problem. Let $a(x)$ be chosen uniformly at random from $R_q$. Question: Is there any theorem that lower bounds ...
3
votes
1answer
88 views

Why don't we use an Extendable Output Function to efficiently store the public key of Regev's LWE-based encryption scheme over standard lattices?

In LWE-based schemes the public key is generated by choosing a random matrix (or polynomial) $A$, and outputting the pair $(A, b = A\cdot s + e)$, where $s$ and $e$ are vectors/polynomials with ...
3
votes
1answer
127 views

What is the purpose of decomposing ciphertext into digits during relinearization in Brakerski Vaikuntanathan homomorphic encryption?

In Brakerski and Vaikuntanathan's homomorphic encryption scheme, the relinearization function turns a 3-element cipher back to a 2-element cipher by using a set of public homomorphism keys (https://...
3
votes
1answer
51 views

what does output parameters of lwe estimator stands for?

I want to use lwe estimator to find classical and quantum security of my proposed key exchange protocol. On this website, I want to understand the output of sage code on lwe estimator given bellow. ...
3
votes
1answer
136 views

Adapting LWE Trapdoors for Ring-LWE

In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE. Theorem 5.1: There is an ...
3
votes
0answers
241 views

ring-LWE: Minkowski Embedding , the Co-Different Ideal, etc

While (trying) to go over the reductions from approx. SVP on ideal lattices to search ring-LWE, [1] and [2], for $K = \mathbb{Q}(\zeta)$ where $\zeta$ is an abstract root of a cyclotomic polynomial, ...
3
votes
0answers
192 views

Is the ring learning with errors problem still hard if the errors are drawn from some subspace?

Let $R=\mathbb{Z}_p[x]/x^n+1$ be the ring used in normal RLWE, which is linear space over $\mathbb{Z}_p$ with dimension of $n$, let $S$ be a linear subspace of $R$ which described by linear ...
2
votes
1answer
41 views

RLWE decision to search: probability that oracle work on all automorphic images

After watching this talk https://www.youtube.com/watch?v=Eg_pyyeT_Qc&feature=plcp, I tried to formalize the presented search-to-decision reduction for Ring LWE, but got stuck at one point. I ...
2
votes
1answer
41 views

Reference for the Security Analysis of Ring-LWE

Can someone please share a link of any research paper or web-page analyzing the security of Ring-LWE? Essentially, how should I choose my parameters to get security equivalent to 128-bit or 256-bit?
2
votes
1answer
49 views

Calculation of failure probability in basic Ring-LWE-DH key agreement

This is the basic unauthenticated Ring-LWE-based Diffie-Hellman key exchange, based on Peikert's Ring-LWE KEM: (from BCNS15) Alice and Bob have shared public polynomial $a$ randomly drawn from $R_q = ...
2
votes
0answers
42 views

What is optimal error distribution in Ring-LWE?

I am new to Ring-LWE. I had assumed that error distribution in Ring-LWE (or, in any lattice-based cryptography) is always Gaussian. However, while reading a few research papers (e.g. page 5, Section "...
2
votes
0answers
49 views

What is the intuition of attacks on ring lwe?

I know that there are several attacks on ring lwe. But I am not sure why they work. Does anyone have intuition of such attacks? What is the common idea used? Reducing the Search space (modulus space)?...
1
vote
1answer
45 views

Choices of $q$ and $f$ for RLWE-based constructions

I understand that RLWE was introduced to avoid the quadratic overhead in the matrices that appear in plain LWE. However, I have a series of questions about this setting. First, Ring-LWE-based ...
1
vote
1answer
68 views

Fully Homomorphic Encryption - state of the art

What are the latest advances in fully homomorphic encryption? First of all, I am interested in cryptosystems based on LWE / RLWE and NTRU problems.
1
vote
1answer
150 views

Is it secure using LWE-based cryptosystem under RLWE-based parameters?

I'm computer guy having trouble with cryptography. I recently read the BGV Homomorphic encryption paper which was constructed under both LWE and RLWE assumptions. I was implementing Threshold ...
1
vote
1answer
67 views

Practical Key exchange for Internet

In section 3.2 (page 10) of Vikram Singh's paper A practical Key Exchange for the internet using Lattice Cryptography, he gives the number of elements in each set for odd $q$. However, the results do ...
1
vote
0answers
37 views

How many ring-LWE samples are required for the (Search) Ring Learning With Errors problem to have a unique solution?

Consider the LWE distribution $\{(\pmb{a}_{i},\left<\pmb{a}_{i} , \pmb{s}\right> + e_{i})\}$ where secret $\pmb{s} \in \mathbb{Z}_{q}^{n}$, randomness is $\pmb{a}_{i} \xleftarrow{\$} \mathbb{Z}_{...
1
vote
0answers
69 views

How to solve a simple case of a RLWE problem

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 ...
1
vote
0answers
89 views

Canonical embedding vs. plaintext slots in Ring-LWE

I'm working on the canonical embedding mentioned in [LPR10] and [LPR13]. What confuses me is that the difference and the relationship between the canonical embedding and the concept of ''plaintext ...
1
vote
0answers
26 views

Computational benefits of using exponent as a power of 2 in Ring-LWE

In most of the RLWE based cryptosystems, the parameter $n$, which defines the cyclotomic polynomial $\Phi_{n}(X)$, is chosen to be a power of $2$. Apart from other benefits such as ease of writing ...
1
vote
0answers
57 views

How does the polynomial module impact the security of ring/lattices-based SIS problem?

Consider the following SIS problem: for a function $f_A(s)$=$As$, where $A$ is a fixed, randomly-chosen matrix in $(R_q)^{r \times n}$=$\left(\mathbb{Z}_q[X]/(X^N+1)\right)^{r \times n}$ and $q$ a ...
1
vote
0answers
47 views

Probability of an RLWE sample

Let $R_q=\mathbb{Z}_q[x]/(x^n+1)$ as usual in the RLWE assumption. Suppoes that I choose a sample of the RLWE distribution, that is, I compute $(a,y=as+e)$ where $a$ is uniform in $R_q$ and $s,e\...
1
vote
0answers
46 views

Security of ring-lwe sample? can we do it simpler?

Assuming a secret key $s\in \mathbb{Z}_2[X]/\langle X^n+1\rangle$, a plaintext $m\in \mathbb{Z}_2[X]/\langle X^n+1\rangle$, $e,e'$ are sampled from B-bounded Discrete Gaussian Distribution over $\...
1
vote
0answers
88 views

Effitiently sampling the error (noise) distribution in ring-LWE

In LPR12, page 4 is described a ring-LWE encryption in which we are working in a ring $R = \mathbb{Z}[x]/(x^n + 1)$ for a $n$ a power of 2. The public key is of the form $(a, b= a\cdot s + e)$ where $...
0
votes
1answer
146 views

Why is Ring-LWE based homomorphic encryption secure with one sample?

Suppose $R=\mathbb{Z}[X]/f(X)$ is a polynomial ring. Decisional Ring-LWE is hard if one cannot distinguish the following samples: $(a_i, b_i) \in R^2$ for $i\in [0,k-1]$ (completely random) $(a_i, ...
0
votes
1answer
91 views

FFT multiplication for RLWE key exchange [closed]

I am try to multiply two polynomial quotient ring of type $R=Z[x]/\phi(x) $ in sage using Fast Fourier Transform.: a=Rq.random_element() R. = PolynomialRing(GF(40961)) # Gaussian field of ...
0
votes
1answer
82 views

Why is low-degree polynomial preferred on Ring-LWE based somewhat homomorphic encryption?

I'm wondering why Ring-LWE based homomorphic encryption (somewhat homomorphic encryption, not fully) requires low-degree polynomial in order to avoid decryption error. For example, a plaintext $m$ is ...
0
votes
1answer
117 views

Refreshing Procedure in FHEW: membership test

I am facing an issue regarding the paper FHEW: Bootstrapping Homomorphic Encryption in less than a second. It concerns the MSBextract algorithm during the refresh procedure. Especially, they ...
0
votes
0answers
23 views

Secure Computation with TTP using Ring-LWE Homomorphic Encryption

I was working with secure outsourced computation for multi-party computation in which security is assured by ring-LWE based asymmetric homomorphic encryption in the semi-honest model. Is it feasible ...
0
votes
0answers
47 views

Implementation of Post-quantum Authenticated Key Exchange from Ideal Lattices

I am implementing the Authenticated Key Exchange from Ideal Lattices on sage maths. On page number 3 the full key exchange scheme is presented. In this key exchange scheme, they are using the Hash ...