14

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 replace Gaussians by other distributions without too much trouble. Theory First, let me elaborate on a few reasons why Gaussians are better in theory: When ...


10

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" theorem of a reviewed and established paper by Peikert. Putting to the side the question of whether the paper is correct or not, there are RLWE instances ...


9

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 Regev’s original idea for public-key encryption from plain LWE but specialized to a power-of-2 cyclotomic ring structure, enabling smaller ciphertext and key ...


6

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 cyclotomics for “packing” and SIMD operations on plaintexts. However, it is simplest to properly define and use RLWE over two-power cyclotomics, in large part ...


6

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 LWE, we have reductions showing that breaking the average-case hardness of LWE requires breaking the worst-case hardness of some lattice problems - which would ...


6

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 way to discuss homomorphic encryption as well without essentially writing some (informal) lecture notes, so won't in this answer. The LWE Problem: The central ...


5

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{align*} \mathbb{Z}[\zeta_{2^k}]&\cong \mathbb{Z}^{2^{k-1}}\\ \mathbb{Z}[\zeta_p] &\cong A_{p-1}^*\\ \mathbb{Z}[\zeta_{p^k}]&\cong \bigoplus_{i = 1}^{p^...


5

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 choice of $a$ that there exists $s_1 \neq s_2$ such that $\|a s_1 - a s_2\| = \sqrt{n}$. Indeed, $a$ is invertible in $R_q$ with probability about $1 - n/q$. Take $...


5

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 irreducible $f(x)$; this ring is (isomorphic to) an order of the number field $K=\mathbb{Q}(x)/f(x)$, but may not be the full ring of integers. Another important ...


5

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; what Bob gets is merely one properly distributed RLWE sample. However, if Bob may choose $a$ in a malicious or “sneaky” way, then there can be attacks. For ...


5

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. Let $n > d > 1$ be powers of two such that $q$ is a prime and $q \equiv 1 + 2d \mod 4d$, then $X^n + 1$ splits into $d$ irreducible polynomials of the ...


4

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 lattice problems, to have some geometry) we want to analyze them in vector spaces. So, representing those ring elements as vectors is what we call embedding. There ...


4

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$ instead of $A$ for the actually exchange. Gen($\cdot$) is a prior-agreed pseudorandom function that extracts and extends the seed.


4

δ_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


4

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 elliptic curves use scalar multiplication, not exponentiation. This notation is used for multiplicative groups. This commitment now turns into a discrete logarithm ...


4

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 operations increase the noise somewhat, but it starts out so small that the result still doesn’t have much noise. It doesn’t really matter that the ciphertext being ...


4

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 example. In this case, $\omega$ is simply the complex number $e^{-2\pi i / (2n)}$, which is independent of $q$. However, you are performing the multiplication $a \...


3

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 (all the computations are done modulo some number, let's say $q$), the mod $t$ operation won't yield the message $m$, but $m$ + $t*e$ mod $q$. Now when you're ...


3

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 + \frac{p}{2} \cdot m)$$ with different terms $\vec a \in \mathbb{Z}_p^n$ and $e \in \mathbb{Z}$. Notice that the probability that two ciphertexts have the same ...


3

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 $-125$ rather than $132$ . And $-125 \mod 2 = 1$. Thus, $sk_a \neq sk_b$ and the output of oracle $\mathcal B$ is $0$.


3

(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 has advantage very close to 1 over the random samples $(a_i, a_i s + e_i + r_i)$, i.e., the oracle outputs the correct answer for almost all choices of $s, a_i,...


3

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 example) have. Specifically, the Mukherjee-Wichs paper you linked defines security to say (roughly) that, given the evaluated ciphertext, its underlying ...


3

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 in the output ciphertext will be bigger than the one in the input ciphertexts. Now when adding ciphertexts, the new noise is just the sum of previous noises, ...


3

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 distribution is normal, as above. Then, it is not difficult to prove that after about $O(n)$ equations, the only assignment to $s$ that "approximately ...


2

Instead of plain matrix, a matrix similar this (but bigger): +a -h -g -f -e -d -c -b +b +a -h -g -f -e -d -c +c +b +a -h -g -f -e -d +d +c +b +a -h -g -f -e +e +d +c +b +a -h -g -f +f +e +d +c +b +a -h -g +g +f +e +d +c +b +a -h +h +g +f +e +d +c +b +a which one can deduce it's equivalant in addition and multiplication to a polynomial reduced by $X^8+1$. ...


2

The security proofs on the papers about (R)LWE use several samples (usually denoted by $m$) because then the results (and the security guarantees) are stronger. And, anyway, they usually give upper bounds to $m$ (as being at most polynomially big in $n$), but not lower bounds. For both, the decisional and the search version of the problem, giving less ...


2

Sage itself has an internal negacyclic convolution, which is what is necessary here. To avoid type errors, we convert the polynomials to lists of coefficients, and work with those instead: from sage.rings.polynomial.convolution import _negaconvolution_fft n = 10 # degree 1024 Rq = GF(40961) R.<X> = PolynomialRing(Rq) S.<x> = R.quotient_ring(X^(...


2

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 (wikipedia). One very useful property is that the $m^{th}$ cyclotomic polynomial has roots that are all the $m^{th}$ primitive roots of unity. For any $n \geq 1$, the ...


2

You should visit the Homomorphic Encryption Standardization web page. There you can find Homomorphic Encryption Standardization. Also, there is a workshop The Second Homomorphic Encryption Standardization Workshop there you can find this document Homomorphic Encryption Standard see section 2.0.3 I hope, all this will help in your research.


2

Correction to kelalaka's answer: Bob chooses a polynomial $a\in R_q$ and sends it to Alice, Alice compute $as+e$, where $e\leftarrow \chi$ is a secure distribution in RLWE, then in this situation, whether Bob will learn the secret $s$? If Bob is limited to a single interaction, then no, Bob cannot recover $s$ (with the RLWE assumption, of course). ...


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