All Questions
Tagged with lattice-crypto ring-lwe
34 questions with no upvoted or accepted answers
11
votes
0
answers
98
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 ...
- 111
5
votes
1
answer
128
views
Ring LWE distribution definitions
This may be a stupid question but I've been stuck on parsing these definitions for a while.
I am reading the paper "On Ideal Lattices and Learning with Errors Over Rings" by Lyubashevsky, ...
- 113
5
votes
0
answers
492
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, ...
- 678
4
votes
0
answers
439
views
Comparison of NTRU-based schemes and LWE-based schemes
What advantages and disadvantages can be distinguished in NTRU-based and LWE-based schemes relative to each other? In what cases which scheme gives advantage?
UPD: I'm interesting in two things: 1)...
- 143
4
votes
0
answers
242
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 ...
- 243
3
votes
0
answers
84
views
Why RLWE is typically implemented using unsigned integers?
Every RLWE implementation I know uses unsigned integers even when it needs to represent signed values. Why?
3
votes
0
answers
199
views
Attacks on Ring-LWE exploiting structure of ideal lattice?
Currently every LWE-based cryptographic schemes analyze their security using lattice estimators and lattice estimators analyze the security of standard LWE even though the actual scheme is based on ...
- 373
3
votes
0
answers
152
views
Equivalence between search-LWE and decision-LWE
Are there any constraints when it comes to proving that search-LWE and decision-LWE are equivalent? Should we assume that the module $q$ is prime when switching from one version to another?
Please ...
- 505
2
votes
0
answers
48
views
Why could the error term be sampled coefficient wise?
In SEAL homomorphic encryption library, it implements the BFV and CKKS. We know the error $e\in R_q$ which is a Guassian distribution. When sampling an error term $e = \sum_{i=0}^{n-1} e_ix^i$, it ...
- 519
2
votes
0
answers
125
views
How does the rejection sampling lemma work in the proof of HVZK?
In this protocol,
Q1: how does the commitment work? What if the prover sends $\textbf{t}$ directly, and then sends $s_m,s_r,s_{\textbf{e}}$?
Q2: How does the rejection sampling lemma work?
refer to ...
- 519
2
votes
0
answers
157
views
Why should the smudge noise be used?
Consider a threshold FHE scheme based on RLWE like this:
Refer to this paper
$\textbf{Initialization:}$
Every party generates his own secret key $s_i$, then uses the common polynomial $a$ to generate ...
- 519
2
votes
0
answers
241
views
What are the prerequisites for understanding Lattice based Cryptography, LWE or RLWE based on SVP?
I'm new to Quantum Resistant Cryptography, so, I thought of diving into Lattice based crypto, LWE and ring LWE. I realise that the hard problem involving them is the "shortest vector problem"...
- 1,080
2
votes
0
answers
578
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 ...
- 424
2
votes
0
answers
186
views
Can binomial distribution be used to sample noise for Ring-LWE-based homomorphic encryption?
Homomorphic encryption schemes based on Ring-LWE need to sample the noise terms from a discrete probability distribution $\chi$ over the integers with support $[-B,B]$. For example, the Fan-...
- 438
1
vote
0
answers
38
views
Understanding FHE bootstrapping: value of $q$ fed to lattice estimator
I am implementing OpenFHE. In the implementation I'm generating the modulus chain as shown in the example here. I am trying to run Lattice estimator for the same parameters in this example.
I wanted ...
- 19
1
vote
0
answers
54
views
[About parameters effect LWE and SIS to be computation or perfect secure]
Hello I am new to lattice cryptography
I am reading the paper More Efficient Commitments from
Structured Lattice Assumptions
They define bound B in page 3
Then In figure 1 in page 9
Can ...
- 371
1
vote
0
answers
49
views
Tensor and power bases for SIS?
What is there to say about using a power basis or a tensor basis or some combination of them for the RSIS problem in lattice cryptography?
Restricting to dimension 3 for illustration, usually the ...
- 357
1
vote
0
answers
129
views
Why there is so high computational cost of multiplication in Microsoft Seal?
I was doing some Microsoft Seal testing on my macbook pro (i7) and got following results
Coefficient mod $q = 100$ bits and Polynomial degree $n= 8192$
Ciphertext-Plaintext multiplication takes 0.211 ...
- 251
1
vote
0
answers
208
views
The relationship between root hermite factor and bit-security?
The root hermite factor corresponding to an bit-security level, such as 1.0045 corresponding to 128-bit security. What is the root hermite factor corresponding to 100-bit, 160-bit, 180-bit security?
...
- 51
1
vote
0
answers
516
views
Is the error distribution in Learning with Errors (LWE), the discrete Gaussian distribution?
In $\mathbb{Z}$, the discrete Gaussian distribution is defined as $D_{Z,s}(x) = \frac{\rho_s(x)}{\rho_s(\mathbb{Z})}, x\in \mathbb{Z}$.
In LWE, $(\overrightarrow{a}, b = \langle \overrightarrow{a}, \...
- 519
1
vote
0
answers
46
views
Forging a new secret key in RLWE
In a RLWE setting where you are given a secret key $s$ and an associated public key $pk = (p_0,p_1) = (-(p_1s+e),p_1)$, is it possible/easy to forge a new secret key $s'$ such that $p_0+p_1s'$ has a ...
- 11
1
vote
0
answers
150
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}_{...
- 11
1
vote
0
answers
111
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 ...
- 33
1
vote
0
answers
88
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\...
- 516
1
vote
0
answers
184
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 $...
- 133
0
votes
0
answers
28
views
Issue building RLWE based program
I've successfully built a LWE based program now moving onto building a RLWE based python program using: https://blog.openmined.org/build-an-homomorphic-encryption-scheme-from-scratch-with-python/ as a ...
0
votes
0
answers
26
views
Urgent help with R-LWE Parameters Choice
I am trying to understand CKKS bootstrap algorithm and wanted to understand how is p (plaintext modulo) and q (ciphertext modulo) related in determining the size of the modulus chain. Suppose my ring ...
- 19
0
votes
0
answers
24
views
Is there any bound on the size of ring dimension for Torus FHE?
I see that all implementations of TFHE in opensource supports 2^10 to 2^12 size of ring dimensions. Is there any specific reason (crypto) behind choosing the value or can we choose higher dimensions (...
- 19
0
votes
0
answers
94
views
[About choosing params in BGV like ciphertexts]
I am new to lattice-based cryptography, so sorry that this question might seems stupid
May I ask that how can I choose the BGV parameter of ciphertext with plain text in mod 128, and error in ...
- 371
0
votes
0
answers
70
views
Is my proof about uniqueness of ring-LWE secret correct?
Suppose that $n$ is a power of two, $q=3\pmod 8$, prime and $R=\mathbb{Z}[X]/(X^n+1)$. Denote $\Vert\cdot\Vert$ as the infinity norm in $R_q=R/qR$ on the coefficients of elements in $R_q$. The ...
- 135
0
votes
0
answers
99
views
Why is the proof on the commitment correct?
In the paper "Efficient Zero-Knowledge Proofs for Commitments from Learning with Errors over Rings", they gave a commitment from Ring-LWE: to commit to a polynomial $m$ in $Rq(Zq[x]/(x^n+1))$...
- 519
0
votes
0
answers
62
views
GSW and homomorphic addition on integers
Is it possible to use the GSW scheme (Gentry, Sahai, Waters) also on integer values and not just single bits? If not, are there any schemes that support integer arithmetic with the same nice property ...
- 1
0
votes
0
answers
79
views
Discrete Gaussian Sampling in Authenticated key exchange from ideal lattices
I am implementing the key exchange scheme proposed by zhang et al. on Sage. In the implementation of the scheme, they have used the two distributions $\chi_{\alpha}, \chi_{\beta}$.
How to choose $\...
- 207
-1
votes
1
answer
156
views
Urgent help with LWE Estimator
I am trying to estimate LWE parameters. I know of the GitHub library for LWE estimator but it has no instructions for installation and also provides no guidance for running simple examples. I have ...
- 19