Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
6 votes
Accepted

Differential privacy guarantees of Gaussian noise, when each coordinate has different sensitivity

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 ...
Mark Schultz-Wu's user avatar
  • 13.3k
2 votes

How to choose the large noise when using noise flooding technique in FHE?

Using statistical distance yields a crude bound of $\sigma$ noise bits for $\sigma = 2^\lambda$, and Micciancio and Walter's 2018 Eurocrypt paper implies that $\sigma = 2^{\lambda/2}$ is sufficient. ...
NickGenise's user avatar
2 votes

Errors for $\mathsf{LWE}$

There are a few main reasons we use Gaussians for errors: It makes tight security proofs easier, or at least most hardness proofs rely on the error distribution being Gaussian. They produce small ...
Stanley's user avatar
  • 211
2 votes
Accepted

proof of uniform hypersphere sampling

Per you comment, if we sample coordinates from a finite ring, the probability distribution function will have to be discreet and so the closest that we can hope for is a discretised normal ...
Daniel S's user avatar
  • 23.9k
2 votes
Accepted

Standard deviation of gaussian noise in FHEW scheme

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/...
LeoDucas's user avatar
  • 1,253
1 vote

Discrete Gaussian distribution on a lattice vs. the periodic Gaussian function on a lattice

The excerpt looks pretty clear to me, so I'm not sure this will help, but let's try with a slightly different perspective. If we formulate things in terms of lattices as opposed to lattice cosets, and ...
Mehdi Tibouchi's user avatar
1 vote

Gaussian distribution propoprties

As Daniel's comment mentions, the answer to your question appears to be "no, for trivial reasons" (plausibly due to some typo in your question). Still, any question of this form has a ...
Mark Schultz-Wu's user avatar
  • 13.3k
1 vote

Why predicting an error in Crystal Kyber is considered to be hard?

The entries in error vectors for Kyber are drawn from a centred binomial distribution based on the difference of two sets of two coin flips. In code this likely means generating two random bits and ...
Daniel S's user avatar
  • 23.9k
1 vote
Accepted

The sum of independent discrete Gaussians is a discrete Gaussian

You mention Unfortunately each reference is very dense and carries a lot of highly non-trivial results. I'm sure that an exhaustive answer is to be found in one or more of the references, but from a ...
Mark Schultz-Wu's user avatar
  • 13.3k
1 vote
Accepted

A smaller modulus-to-noise ratio means more security in LWE

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 ...
Mark Schultz-Wu's user avatar
  • 13.3k
1 vote

How is it legal to use a rounded Gaussian for LWE?

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 ...
Mark Schultz-Wu's user avatar
  • 13.3k
1 vote

Is the discretization of the Guassian distribution on torus still a discrete Gaussian distribution?

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$ ...
LeoDucas's user avatar
  • 1,253
1 vote

How small can the error be in LWE?

Per Mark's suggestion, I looked into the "hidden" tests in lwe-estimator and read a few papers. I summarized my findings as an answer here: Arora-Ge attack, and the improved version using ...
Weikeng Chen's user avatar

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