# Questions tagged [lattice-crypto]

Lattice-cryptography is the study and use of lattice problems applied to cryptography.

521 questions
Filter by
Sorted by
Tagged with
120 views

### Trying to implement the algorithm in Wikipedia regarding key exchange

I am trying to understand the reconciliation technique mentioned in Wikipedia page for Ring-LWE key exchange. Basically, if we intentionally choose x, y (or the coefficients of calculated shared key ...
207 views

### Why is does the protocol of Ding et al. produce biased bits and does it relate to passive security?

I am not understanding the following from "Lattice Cryptography for the Internet" by C. Peikert (pages 9): We remark that a work of Ding et al. DXL14 proposes a different reconciliation method ...
95 views

### Why is a bit biased when generated from random $v \in Z_q$ for odd q?

I am not understanding the following from "Lattice Cryptography for the Internet" by C. Peikert (pages 10, 11): When $q$ is odd, while it is possible to use the above methods to agree on a bit ...
410 views

### Trying to implement ring-LWE KE to understand the concept

Today, after reading so much about ring-LWE key exchange, I decided to implement it in java to see if it works. Not a real world implementation, just to see if math works out. My assumption was that ...
480 views

### Irreducible polynomial in Ring-LWE

In Ring-LWE polynomials are chosen from the ring $R_q=\mathbb{Z}_q[x]/(x^n+1)$, where $n$ is a power of two. As far as I understand, to create a ring the polynomial $x^n+1$ has to be irreducible (see ...
2k views

### Uniform vs discrete Gaussian sampling in Ring learning with errors

The Wikipedia article on RLWE mentions two methods of sampling "small" polynomials namely uniform sampling and discrete Gaussian sampling. Uniform sampling is clearly the simplest, involving simply ...
336 views

### Why standard deviation of BLISS is so high?

In lattice based digital signature scheme BLISS why the standard deviation is so high (215) compared to the encryption schemes?
1 vote
85 views

964 views

### Quantum complexity of LWE

As per my understanding, LWE is quantum secure because there is no known quantum algorithm to solve LWE in polynomial time. Due to the reductions given by Regev et al., if there is any algorithm that ...
281 views

### proof of correctness Ring-LWE cryptosystem

I've been studying Ring-LWE based crytposystems such as the one in this paper, but I can't seem to find/come up with a proof of correctness for this particular scheme. The encryption goes as follows: ...
1k views

### What is the most efficient attack on NTRU?

So, I got how finding the private key is equivalent to resolving the SVP. I also understood that the LLL algorithm can only be used in small dimensions. Now, I wonder what is the most efficient attack ...
235 views

### Is the ring learning with errors problem still hard if the errors are drawn from some subspace?

Let $R=\mathbb{Z}_p[x]/x^n+1$ be the ring used in normal RLWE, which is linear space over $\mathbb{Z}_p$ with dimension of $n$, let $S$ be a linear subspace of $R$ which described by linear ...
148 views

### Collisions in the cyclotomic knapsack function

I've been working my way through the paper “Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices” by Peikert and Rosen, and I've come across something that doesn't seem ...
1 vote
103 views

### Use $e$ in GGH as shared secret?

I was wondering if we could construct a symmetric encryption scheme by assuming that the secret key itself in GGH is public and the shared "key" is the error vector $e$. To encrypt we would take the ...
3k views

### Is the "New Hope" Lattice Key Exchange vulnerable to a lattice analog of the Bernstein BADA55 Attack?

In the paper, "Post Quantum Key Exhange - A New Hope," the authors present a lattice-based key exchange based on the work of Chris Peikert. In this "New Hope" key exchange the authors try to gain ...
790 views

### Find collision in Ajtai's hash function using short vector

Background What is Ajtai's hash function? Given a matrix $A \hookleftarrow U(\mathbb{Z}_q^{n \times m})$ and a column vector $\vec{m} \in \mathbb{Z}_d^m$, the hash of the message $\vec{m}$ is given ...
301 views

### Practical lattice based signatures and key exchange with strong security reduction

I am looking for practical lattice-based signatures and key exchange with strong security reductions. Specifically: Provable security under the relevant standard assumptions. Fast in software while ...
2k views

### What is a purpose of reducing lattice basis?

This may be too broad question but it is not. I have been studying lattices for few months now, more specifically I studied: Lattice problems ($SVP$, $CVP$ and etc.) Lattice cryptography in post ...
278 views

### Would LWE problem be still secure if error were like this $e=2e_1$?

In the Learning with error problem, if the error term $e$ from equation $b=<a,s>/q+e$ were of this kind $e=2e_1$, where $e_1$ is chosen according to the probability distribution for the LWE ...
1 vote
536 views

### Gaussian function in lattices

Probability density function of gaussian distribution is $$1/{\sqrt{2 \pi} \sigma} \times {e^{{(x-c)^2/ 2{\sigma}^2 }}}$$ in lattices we assume $$\sigma =s/\sqrt{2 \pi}$$so the gaussian ...
1 vote
225 views

### Use of orthogonal vectors in lattice-based cryptography

In lattice-based cryptography, given the basis of the lattice we compute the orthogonal vectors using Gram-Schmidt Orthogonalization process. What is the use of orthogonal vectors in lattices?
604 views

### finding the basis of a kernel in a lattice

Given a parity check matrix $A$ we define the $q$-ary lattice $$\Lambda(A) = \{x \in \mathbb Z^m\;:\;Ax\equiv0\pmod q\}$$ How to find the basis of the lattice and how to find its hermite normal form?
1k views

### Gaussian distribution in lattices

In many lattice based cryptosystems, Gaussian distribution is used. Can you explain why only Gaussian distribution is preferred?
766 views