Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Our goal is find a faster discrete Gaussian sampling to solve $"SVP"$ problem in lattice:

A lattice is discrete subgroup of $R^n$ such that define as below:

let $\{b_1,\cdots ,b_n\}$ be a basis in $R^n$. Then $L:=\{a_1b_1+\cdots+a_nb_n | a_i \in Z\}$ is a lattice.

Shortest vector problem in $L$ is:

$SVP(L)$ = shortest non-zero $y\in L$.

This is a $NP-hard$ problem to solve. The best algorithm to improve approximation of this problem mentioned by "Discrete Gaussian Sampling". In this method, the TIME and SPACE computed $2^{n+ o(n)}$. What is the faster discrete Gaussian sampling?

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.