Hot answers tagged

4

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 polynomially large in the security parameter, and super-polynomially large. Smaller modulus is better for both efficiency and security. I think only recently we ...


4

Out of curiosity, what is the current state of the art on the sampling over $D_{\mathbb{Z},\alpha q}$ This is a fairly involved question to answer. There are a number of competing ways to sample it, which you can roughly divide into: Techniques that work for any probability distribution Techniques that are specific to the discrete Gaussian Table 1 of [...


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

Given $(A, Ax + e)$ and $(A, x^tA+e')$, you can do (at least) one potentially interesting thing to solve LWE. Namely, compute the sample $$(A+ A^t, Ax + e + (x^tA+e')^t) = (A+A^t, (A + A^t)x + e + {e'}^t)$$ so you can reduce LWE to a case of LWE where the random matrix $A + A^t$ is symmetric. It isn't really clear to me that this helps you cryptanalytically -...


3

First I would like to define more precisely the "same $x$" attack. First interpretation Alice and Bob know their $x$ are the same. It doesn't make sense, because in this scenario, they already share secret information (they can already compute common public key $g^x$ without any communication). Second interpretation Now, let suppose, the adversary ...


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


3

To answer your first short question: this is a (very) special case of Theorem 3.1 of Peikert’10. Specifically, use the “$x_2$ is chosen from a continuous Gaussian” variant, let $\Lambda_1+c_1$ be the integer lattice $\mathbb{Z}$, and let $\Sigma, \Sigma_1, \Sigma_2$ be suitable positive reals. Regarding why true discrete Gaussians are useful: it is often ...


3

If $p$ and $q$ are powers of two, as in Saber, then multiplying and diving by $p$ and $q$ amounts to simple bit shift operations. In Saber, $p = 2^{10}$ and $q = 2^{13}$. Thus, $p/q = 1/2^3$ and $x/8$ can be computed by a right-shift of 3 bits. Using the $bits$ notation, $\frac{p}{q}x = bits(x, \log(p/q), \log p)$. But we can do better, and also compute the ...


3

As a quick aside, while Hermite refers to the same person, "Hermitian" means something different for matrices than "Hermite Normal Form". HNF is essentially "Row Echelon Form/Gaussian Elimination where you can't divide". HNF Optimization: First, we can discuss "Reducing the columns of $E$ modulo the HNF", which does ...


2

Here is the optimization in more detail. Start with $[\bar{A} \mid I_n \mid G']$ where $\bar{A} \in \mathbb{Z}_q^{n \times n}$ and $G = [I_n \mid G']$ (where $I_n$ is the $n$-by-$n$ identity matrix). Note that the concrete gadget matrices $G$ constructed in the paper already contain an identity submatrix (up to reordering of columns). But in general, $G$ ...


2

The distributions are the same. That is, rounding and modding (by any integer $q$) essentially commute: $\lfloor \rho_a \rceil \bmod q = \lfloor \rho_a \bmod q \rceil$, where on the right we are rounding $\mathbb{R}/q\mathbb{Z}$ to the closest element of $\mathbb{Z}/q\mathbb{Z}$ (so the result remains modulo $q$). This follows simply from the fact that $\...


2

This has nothing to do with LWE vs RLWE, and instead has to do with using: Parameters based on cryptanalysis of $SIVP_\gamma$ and worst-case to average-case reductions Parameters based on cryptanalysis of LWE The first is somewhat non-trivial (and requires more than just setting $\sigma > 2\sqrt{n}$) due to the known tightness gaps of the worst-case to ...


2

It is not true that RLWE guarantees that $h_i$ is computationally indistinguishable from uniform for any fixed $p_1$: just consider the case of $p_1 = 0$. At the opposite end, if $p_1$ is invertible is $R_q$ (which is the generic case), then each $h_i$ is exactly uniformly distributed in $R_q$, and they are all independent, so the joint distribution is just ...


2

It's still just evaluation of a circuit, which in general, increases the noise. Yes and no. Homomorphic operations do (generically) increase the noise, but the idea behind bootstrapping is to evaluate a circuit which itself decrypts the ciphertext. Decrypting the ciphertext (if the noise is below some threshold) zeros out the noise. This means there are two ...


2

First, it should be clear that one can always increase the noise in an LWE instance without hurting security, so (for fixed modulus) larger modulus-to-noise ratio implies "not worse" security. Of course, this does not explain why the security should vary with respect to $\sigma/q$, instead of some more complicated expression. There are two reasons ...


2

There are important constraint in the parameters for Ajtai's function, that makes it highly surjective (each image has many preimages). We do not know how to get an encryption scheme from that. On the contrary, Regev's one is typically used in an injective regime. And we do know how to build and encryption scheme from it. Regarding Hardness, solving SIS over ...


2

The statement you are trying to make is information-theoretic (existence of something), not computational (easiness of finding something), so the fact that you invoke the RLWE hardness assumption is concerning. One thing you do have right is to indeed consider the difference of two solutions $[\mathbf A; \mathbf I] \cdot (s-s', e-e') = 0$. In fact, the set ...


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

Yes, for general reasons. Namely, $a$ being invertible is: Publicly verifiable, and occurs with non-negligible probability $p$ (over uniform choice of $a$), see this for details. Whenever you have a condition like this, you can have any hypothetical adversary first check if the condition holds, and if it doesn't then "guess" the answer randomly. ...


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


1

The answer is "yes", and the modifications are relatively straightforward for experts to make (which is why you may not see it often). There are roughly three classes of modifications, I'll try to briefly mention all of them. Throughout, I will be referring to the standard "Regev-type" encryption scheme $$\mathsf{Enc}_s(m) = (A, As + e + (...


1

no Babai's nearest plan algorithm doesn't necessary need a full rank lattice look at this paper here.


1

You should consider $\log q$. Considering that all the other parameters are fixed, the smaller $q$ is, the higher is the security. Even the table in your question is showing this (the table probably supposes that $\sigma$ is a small fixed value). The hardness of the LWE and RLWE problems increases as the ratio $q / || \text{noise}||$ decreases, i.e., larger ...


1

Section 4 of [P16] is perhaps the key section to read. I quote it below: We stress that all these insecure instantiations—excepting [EHL14], for which the following conclusions still apply—are for the “non-dual” version of Ring-LWE with spherical Gaussian errors relative to $R$ (in the canonical embedding). By contrast, the definition of Ring-LWE from [...


1

The Why question has a deep answer since it is deep research! The How question is a lot easier. To check that how an encryption scheme is homomorphic look at the general homomorphism; Let $f:A\to B$ be a map that preserve the structures. $$f(x \cdot y) = F(x)\cdot f(y)$$ then we say $f$ is homomorphism ( in a very simple terms). This is a bit different in ...


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