Hot answers tagged

2

I think the following reduction is intended: Let $D$ be a distinguisher for $f, g$. Build a distinguisher $D'$ for LWE that: Takes as input an LWE instance $(A, b')$ Create the oracle $h_{A, b'}(b,x) = Ax + bb' + e\bmod q$ Simulates $D$ with oracle access to $h$, and returns what $D$ does. It seems relatively straightforward that this adversary should work,...


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

Note that you don't strictly need the dual ideal for RLWE's security, you just take an efficiency hit if you don't use it. See page 4 of Algebraically Structured LWE, revisited for some commentary on this. It does show up in the "Bounded Distance Decoding on the dual -> Discrete Gaussian Sampling on the primal -> BDD on the dual -> $\dots$"...


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


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