# Tagged Questions

The tag has no usage guidance.

2k views

### What are the benefits of lattice based cryptography?

Previously we visited the benefits of elliptic curves for cryptography. Lattice based cryptography is starting to become quite popular in academia. The primary benefit of lattice based crypto is the ...
76 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 ...
253 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 ...
117 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 ...
66 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 ...
270 views

### Given a 'good' basis for a lattice, how can we solve the CVP?

I'm doing a little bit of reading about lattices. I read that if we can find a 'short' basis for our given lattice, we can solve CVP and SVP very efficiently. However, the paper didn't describe an ...
165 views

270 views

### What is a “lattice” in cryptography?

There are some questions here concerning lattice-based cryptography and this kind of cryptography seems to be especially useful if quantum computers are assumed to exist. When reading such questions ...
141 views

### Ring-LWE elliptic gaussian distribution

I am currently trying to understand this Ring-LWE article: http://www.cims.nyu.edu/~regev/papers/ideal-lwe.pdf and I have a question. Firstly, it is mentioned in the paper that we can view the ...
215 views

### Lattice based attack on RSA

Let $n=pq$ be the RSA module and at least one of $p,q$ is a weak prime.It is proved that the number of such $1024$bit $n$ is at least $2^{759}$. With lattices we can factor these $n$ in a second (I ...
39 views

106 views

### Is secure lattice based cryptography in future?

Lattice cryptography is a post quantum cryptography that work on two NP-hard problem in below: Find shortest nonzero vector from origin and Find minimum distance of a arbitrary point out of lattice ...
95 views

### What kind of operations are involved in NTRU?

I've read that lattice based algorithms involve matrix-vector products. Is this the case of the NTRU algorithm? When I've read the details of the NTRU algorithm, I've seen products of polynoms. Where ...
265 views

### Illustrate NTRU using lattices

I studied some papers related to NTRU. All these papers describe NTRU as a lattice based cryptosystem but I could not find any paper which illustrates NTRU algorithm from lattice point of view. It ...
39 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 ...
187 views

### Understanding Lattice based cryptosystem [closed]

I have heard that there is one paradigm of Public key cryptosystem, called Lattice based crytography. Further, its security claims are such that it will not be affected even if the quantum computers ...
246 views

### How can a lattice attack be applied to ECDSA signatures?

The aim is to check if it is possible to break the ECDSA cryptosystem under the following criteria. Suppose that each ECDSA signature is generated by using the GLV method for point multiplication (...
101 views

### Arithmetic modulo 1

In the context of lattice-based cryptography, in particular the Learning With Errors (LWE) problem, I see some definitions given in terms of equations modulo 1 (see for example, Appendix A of this ...
44 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?
23 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 ...
54 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 ...
23 views

### Proof that two signatures are done with the same short bases

My question is regarding lattice based signatures. Each lattice can have multiple short (secret) bases. Is it possible to proof in zero knowledge that two signatures on a fixed lattice have been ...
67 views

### Gaussian distribution in lattices

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