6

I haven't read your full question, but the answer to: Is there an equivalent analytical result where we can add Gaussian noise proportional to each coordinate sensitivity? and (implicitly) Can the noise scale better than $O(d)$ for $d$-dimensional output? Then the answer is yes. The following should be able to be easily adapated for essentially any ...


2

Apologies for seeing this question just now. For your first question, well, there seems to be a typo: I should have written $\|s\|^2 \leq n/2$, and then we have $\sqrt{(\|s\|^2 +1) /12 } = \sqrt{251/12} \approx 4.57$. Now, we take 2 ciphertext with LWE error of std-deviation $\beta$, and sum them. Assuming independence the std-dev of the sum of the errors ...


1

I can't find an explicit expression for this advantage. There isn't one. This is because it is consistent with the state of the art of complexity theory that $\mathsf{P} = \mathsf{NP}$, and therefore $\mathsf{Adv}_{n,m,q,\sigma}^{\mathsf{DLWE}}$ is some polynomial in the sizes of the relevant parameters. It is also consistent with current cryptographic ...


1

I think this is just an artifact of Regev representing values in $\mathbb{T} \cong \mathbb{Z} / q\mathbb{Z} = \{0, 1/q, \dots, (q-1)/q\}$, rather than in $\{0,1,\dots,q\}$ directly. There are still a few things to mention though: First, modern consensus is that for the hardness of $\mathsf{LWE}$ [1], the particular error distribution you use does not matter ...


1

There are two ways to discretize: rounding and conditioning. The first discretization you use to define $D_{\mathbb Z,s}$ from $\rho_s$ is using conditionning. The second one defining $\bar \Psi_s$ from $\Psi_s$ is using rounding (the density at integer $x$ of the former distribution is given the total density of the interval $[x-\frac 1 2, x+ \frac 12]$ of ...


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