Questions tagged [gaussian-noise]
The gaussian-noise tag has no usage guidance.
18 questions
1
vote
1
answer
42
views
Conditional distribution of an integer error vector, taken from an appropriate discrete Gaussian, given its syndrome [GPV'STOC2008]
I'm reading lemma 5.2 of [GPV'STOC2008, page 18] about conditional distribution of an integer error vector $\mathbf{e}\in\mathbb{Z}^{m}$, taken from an appropriate discrete Gaussian $\mathbf{e}\sim D_{...
- 586
1
vote
1
answer
64
views
Gaussian width in lattice setting
In the lattice setting (like LWE, RLWE) , the Gaussian function is often defined as
$$
\rho_{\Sigma}(x) = e^{-\pi x^T\Sigma^{-1}x}
$$
The discrete Gaussian distribution $\mathcal{D}_{\Lambda, \Sigma}$ ...
- 11
5
votes
1
answer
128
views
Noise flooding in Lattices
I noticed that in the paper [HLL24], the authors used the noise flooding technique to choose parameters and complete the proof.
But I am confused that why set $\sigma \ge 2^{\kappa+6}y$ to guarantee ...
- 51
0
votes
1
answer
194
views
Discrete Gaussian distribution on a lattice vs. the periodic Gaussian function on a lattice
Gaussian distribution on lattices generally seems esoteric (at least for me, for now). My question is:
Does Gaussian distribution on a lattice mean to add a Gaussian noise on a single point of a ...
- 586
1
vote
1
answer
100
views
proof of uniform hypersphere sampling
In this paper,
they shortly introduced how to uniformly sample points from the n-sphere.
The points of n-sphere consist with normal variables.
My question is ..
If I samlpe coefficients of ring using ...
- 33
1
vote
1
answer
64
views
Gaussian distribution propoprties
Good day,
I've a question regarding Gaussian distribution properties over lattices :
Let $\mathcal{L}$ := $ \mathcal{L}(\,b_{1}$,..., $b_{m})$ be a lattice over $\mathbb{R}^{n}$, and $W$ = span($b_{1}$...
- 11
1
vote
0
answers
38
views
Introducing differential privacy in two different ways
I would like to investigate if it is possible to introduce Differential Privacy (DP) to a model via both adding Laplacian noise to the training data and then training with DP-SGD updates. Is it a ...
- 11
1
vote
1
answer
229
views
Why predicting an error in Crystal Kyber is considered to be hard?
Hi I have started studying on crystal kyber recently. Gained some knowledge regarding its algorithm and how it works. My doubt is why it is tough for attacker to extract secret vector from pk itself ...
- 21
2
votes
1
answer
381
views
The sum of independent discrete Gaussians is a discrete Gaussian
I am currently learning about lattice-based cryptography and, reading from A Decade of Lattice Cryptography by Peikert, specifically section 2.3, it emerges that
[...] if the parameter s is greater or ...
- 23
2
votes
1
answer
600
views
How to choose the large noise when using noise flooding technique in FHE?
In LWE based multi party FHE schemes, the parties should choose a much larger noise when perform joint decryption. In this paper, the author just said that using noise flooding technique to avoid the ...
- 519
1
vote
1
answer
105
views
Errors for $\mathsf{LWE}$
Why do we take Gaussian-like errors in $\mathsf{LWE}$?
Why for example we don't take uniform errors?
- 505
1
vote
1
answer
191
views
A smaller modulus-to-noise ratio means more security in LWE
Let $\text{Adv}^{\text{DLWE}}_{n,m,q,\sigma}$ be the advantage of an attacker to distinguish LWE samples from uniform ones, where $m$ is the number of samples, $q$ the modulus and $\sigma$ the ...
- 505
2
votes
1
answer
166
views
How is it legal to use a rounded Gaussian for LWE?
As far as I understood, in Regev's initial paper, the error distribution was first constructed as follows:
Then rounded in the following way:
Using this distribution, the reduction in the theorem ...
- 505
1
vote
0
answers
516
views
Is the error distribution in Learning with Errors (LWE), the discrete Gaussian distribution?
In $\mathbb{Z}$, the discrete Gaussian distribution is defined as $D_{Z,s}(x) = \frac{\rho_s(x)}{\rho_s(\mathbb{Z})}, x\in \mathbb{Z}$.
In LWE, $(\overrightarrow{a}, b = \langle \overrightarrow{a}, \...
- 519
1
vote
1
answer
141
views
Is the discretization of the Guassian distribution on torus still a discrete Gaussian distribution?
Let $\rho_s(x) = e^{-\pi x^2/s^2}$ be the Gaussian measures, then the discrete Gaussian distribution on $\mathbb{Z}$ could be defined as $D_{\mathbb{Z},s}(x) = \rho_s(x)/\sum_{n\in \mathbb{Z}}\rho_s(n)...
- 519
3
votes
1
answer
557
views
How small can the error be in LWE?
For modulus $Q$ and stddev $\sigma$, [GHS12] suggests that, to achieve 128-bit security, just choose the dimension $N$:
$$
N\geq(Q/\sigma)\cdot 33.1
$$
This seems to suggest flexibility to choose ...
- 564
6
votes
1
answer
760
views
Differential privacy guarantees of Gaussian noise, when each coordinate has different sensitivity
Suppose you have a function $f$ that takes a dataset $D$ as input and returns an output in $\mathbb{R}^d$.
If this function has $L^2$-sensitivity $\Delta$, then the analytical Gaussian mechanism (...
- 1,028
2
votes
1
answer
151
views
Standard deviation of gaussian noise in FHEW scheme
I've got two questions regarding the paper FHEW: Bootstrapping Homomorphic Encryption
in less than a second.
First, the final error of a ciphertext after the refresh procedure is stated as following ...
- 438