16 votes

Uniform vs discrete Gaussian sampling in Ring learning with errors

The TL;DR: From a theoretic point of view, Gaussians are the better choice, both for the easiness of the security proof and its optimality in terms of tightness; In practice, most of the time you can ...
user avatar
  • 1,092
11 votes

NewHope and NIST's Post-quantum standardization

From Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process 3.12 NewHope NewHope is a KEM based on the presumed hardness of the RLWE problem. At its core is ...
user avatar
  • 43.5k
10 votes
Accepted

Is Ring-LWE now (2021) broken?

Update: 20210403 TL;DR If correct, the paper would affect the security of a wide range of RLWE systems, including all of the most commonly used variants. However, the paper violates a "no go&...
user avatar
  • 11.7k
7 votes

Ring-LWE in other fields

We don’t always use power-of-two cyclotomics for RLWE. Many cryptosystems use other cyclotomics, or subfields thereof, or even other fields altogether. For example, many FHE schemes use non-two-power ...
user avatar
7 votes

How is R-LWE related to lattice cryptography and homomorphic encryption?

While I still think it would be good for you to ask more specific questions, the following might be useful in clearing up your understanding of the underlying hard problems on lattices. I do not see a ...
user avatar
  • 8,677
6 votes
Accepted

MLWE (and RLWE) to LWE reductions proof

There is no known reduction from LWE to MLWE (or to RLWE). That is, it could be that both MLWE and RLWE are broken, yet LWE is secure. However, this seems highly unlikely. To support the security of ...
user avatar
5 votes
Accepted

Minimum distance between polynomials in ring-LWE

I'm assuming $n$ is a power of $2$ and that $q$ is an odd prime larger than $n$. I'm discarding the trivial case $s_1 = s_2$. If you consider everything $\mod q$, then it is most likely over the ...
user avatar
  • 1,119
5 votes

Famous ideal lattices

Yes, there are. The following table is taken from this paper of Ducas and van Woerden, although the results are not derived there (in the below, $p$ is an odd prime, and $n, m$ are coprime). \begin{...
user avatar
  • 8,677
5 votes

What is the difference between Poly-LWE and Ring-LWE?

One main difference is that in Ring-LWE, the ring $R$ is the full ring of integers $\mathcal{O}_K$ of a number field $K$, whereas in Poly-LWE it is of the form $R=\mathbb{Z}[x]/f(x)$ for some ...
user avatar
5 votes

Is it secure to compute the exponentiation and the LWE operation?

For the second question, it depends on whether we can trust Bob to generate $a$ uniformly at random and without any “hidden structure.” If we can trust him, then this is secure assuming RLWE is hard; ...
user avatar
5 votes
Accepted

Is FFT for power-of-two cyclotomic rings possible if q is not 1 modulo 2n?

Yes, in a way. When $q \neq 1 \mod 2n$ the ring $R_q$ is not fullt splitting (into polynomials of degree one). However, it might be splitting into several smaller polynomials of degree larger than one....
user avatar
4 votes
Accepted

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?

I believe it is also used in other lattice based schemes that use standard LWE. For example, the Frodo paper. They used a $seed_A$ and a Gen($\cdot$) function to compute $A$. Then Alice sends $seed_A$ ...
user avatar
4 votes
Accepted

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

The ciphertexts contains a certain amount of noise for security reasons. The downside is that if this noise is too big, the decryption will fail. When using homomorphic operations, the noise contained ...
user avatar
4 votes

$\ell_2$-norm vs canonical embedding norm on ring-lwe

I think you are mixing up some concepts... There are two things here: the embedding and the norm. Those schemes are defined over polynomial rings, but for several reasons (e.g. to relate them with ...
user avatar
4 votes

what does output parameters of lwe estimator stands for?

δ_0: the root Hermite factor required β: the BKZ block size d: the dimension of the lattice being reduced m: the number of LWE samples used
user avatar
4 votes

Is it secure to compute the exponentiation and the LWE operation?

Whether the interaction will reveal Alice's secret key? I'm reading this like, Bob chose the base point $G$ and sends it to Alice then Alice sends back to Bob $[s]G$. The reason is simple, the ...
user avatar
  • 43.5k
4 votes
Accepted

Why does bootstrapping (R)LWE homomorphic encryption produce small noise?

The output of bootstrapping has relatively small noise because it starts from an encryption (of the secret key) that has very small noise, and performs some homomorphic operations on it. These ...
user avatar
4 votes

Is FFT for power-of-two cyclotomic rings possible if q is not 1 modulo 2n?

Another alternative that can be viable in some scenarios is to use the usual FFT over $\mathbb{C}$ instead of the Number Theoretic Transform (NTT) over $\mathbb{Z}_q$. This is what FHEW does, for ...
user avatar
4 votes

Why RLWE is hard or even has a solution?

There are two key points that you are mentioning (one mentioned by Poncho in the comments --- I repeat here for exposition purposes). The RLWE errors $e_i(x)$ are small, and the secret $s(x)$ is ...
user avatar
  • 8,677
4 votes
Accepted

LWE and pseudorandom functions

You can. There is a certain caveat that should be mentioned here --- the LWE problems hardness is controlled (in part) by the size of the modulus $q$. Two important parameter regimes are $q$ being ...
user avatar
  • 8,677
4 votes
Accepted

RLWE Explanation

The cyclotomic polynomials are used in the proofs that worst-case lattice problems reduce to the RLWE. If you try to instantiate RLWE with other polynomials, then you don't have such formal guarantees ...
user avatar
3 votes
Accepted

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

The decomposition helps with the noise growth of your scheme. You see, the decryption only works if you "error" (here the terms you denote by $e$) is small enough. If $t*e$ grows beyong the modulus (...
user avatar
3 votes

Replay attacks and LWE

By looking the encryption procedure, you will see that we use a different sum of the vectors $\vec a_i$'s at each encryption. Thus, every ciphertext has the form $$(\vec a, ~\vec a\cdot \vec s + e + \...
user avatar
3 votes
Accepted

Complete Attack on RLWE Key Exchange with reused keys, without signal leakage

There is a condition that is not considered, that is, the value after modulo 257 should be in $\mathbb Z_q$. When $q = 257, \mathbb Z_q = \{ -128, ... , 128 \}$, so, $(4+128)\mod 257$ should be $-...
user avatar
  • 177
3 votes
Accepted

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

(The full version of the paper is at https://eprint.iacr.org/2012/230, and my answer below refers to it.) The answer to your question is that a different part of the reduction ensures that the oracle ...
user avatar
3 votes
Accepted

Threshold decryption in multi-key homomorphic encryption

Everything you write looks correct. However, you may be expecting the distributed decryption protocol to have a security property that it does not (and was not intended to, and really cannot in your ...
user avatar
3 votes

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

Why use $f(x) = x^{2^n} + 1$? This is a very special polynomial called a "cyclotomic" polynomial. Cyclotomic polynomials are very interesting, and I recommend reading up on them separately (...
user avatar
  • 166
3 votes
Accepted

Proof that (ring-)LWE secret is unique

Regev's LWE Survey contains a sketch of the proof. Algorithms. One naive way to solve LWE is through a maximum likelihood algorithm. Assume for simplicity that $q$ is polynomial and that the error ...
user avatar
  • 8,677
3 votes
Accepted

Security level of FHE constructions for non-standard parameters

The standard way is by using the LWE estimator (if it is simple or not it is debatable). It estimates the cost of known attacks against LWE instances given parameters $n$, $\alpha$, and $q$, where $\...
user avatar
3 votes

Functional and security model for SEAL

decryptions of Microsoft SEAL ciphertexts should be treated as private information only available to the secret key owner, as sharing decryptions of ciphertexts may in some cases lead to leaking the ...
user avatar
  • 8,677

Only top scored, non community-wiki answers of a minimum length are eligible