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


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.


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

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


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

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


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

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


1

I guess the latest real production grade homomorphic library is Microsoft SEAL, which implements the BFV and the CKKS encryption schemes. I'm not a big MS fan. There are other options to explore: HELib implements the BGV scheme with GHS optimizations. NuFHE implements a GPU reference of fully homomorphic encryption on torus Also checkout the open group ...


1

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


1

One concrete solution is to explicitly compute the distribution of each coefficients. In this particular ring, and if the distribution of the coefficients of e and s are symmetric, this ca just be computed as an 2n-fold convolution of the distribution of products of coefficients. An example (with some complication due to rounding) is available here: https://...


1

There are to my knowledge two articles that develop further on generalized member test (or even function) extraction, I hope this may help you out: https://link.springer.com/chapter/10.1007/978-3-319-22174-8_7 and https://eprint.iacr.org/2017/996.pdf A small difference there is that the ring dimension is a prime rather than a power of 2, and this ...


1

Am I right? Possibly, but it's not guaranteed, even if we assume that LWE is secure. RLWE is a special instance of LWE; however that doesn't mean that RLWE is secure if LWE is. The LWE assumption holds if we have a random instance; that is, one chosen from a specific probability distribution. The RLWE problem has a different probability distribution; one ...


1

$4 < 17/4 = 4.25$, so $4 \in [0, 17/4) = [0, 4.25)$. Hence $I_0 = \{0,1,2,3,4\}$, not $\{0,1,2,3\}$.


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