Questions tagged [lattice-crypto]

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

Filter by
Sorted by
Tagged with
32
votes
3answers
3k views

New quantum attack on lattices (or Shor strikes again)?

Lior Eldar and Peter W. Shor published a paper on arXiv.org in which they present a new quantum algorithm against a variant of BDD. They claim that their new algorithm can efficiently solve the ...
27
votes
2answers
745 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 ...
19
votes
1answer
591 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 ...
15
votes
1answer
4k 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 ...
13
votes
3answers
644 views

Why are only lattice problems used in cryptography?

There are thousands of NP-hard problems out there. Why have only lattice problems been applied to cryptography?
12
votes
0answers
601 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 ...
11
votes
1answer
2k 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 ...
11
votes
0answers
392 views

Potential Flaws With Lattice Based Cryptography?

From researching post-quantum cryptographic schemes it seems hash-based and lattice-based algorithms are the most promising (MQ-based seem to be covered by patents and have more potential unknowns ...
10
votes
2answers
914 views

Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?

A recent eprint paper claims to bound $\lambda_1(\Lambda^\perp(\mathbf{A}))$ for $\mathbf{A}\in\mathbb{Z}^{n\times m}$, a uniformly random matrix, by $O(1)$, specifically by $4$. This has applications ...
10
votes
1answer
858 views

Lattice-based cryptography

How viable is lattice-based cryptography in a "practical" setting? It has been said that lattice-based cryptography would be a "post-quantum" cryptography scheme, but is it feasibly implementable?
10
votes
0answers
67 views

Decision R-LWE parameters for spherical error with worst-case hardness

In Peikert et al.'s most recent work (STOC 2017) a direct reduction of worst-case lattice problems to decision R-LWE is achieved for $\alpha q \ge 2 \cdot \omega(1)$ (Theorem 6.2), where $\alpha q$ is ...
9
votes
2answers
424 views

Peikert's framework for attacks on R-LWE: What “reduction modulo q” means?

I am reading Peikert's paper [Pei16] about secure instantiating of R-LWE problem. In section 3.1, The author gives a new attack framework by using "reduction modulo an ideal divisor $\mathfrak{q}$ of ...
9
votes
1answer
117 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 ...
9
votes
0answers
465 views

Why SIVP Is Worst Case Problem?

I just started to study lattice Cryptography. I'm now studying worst-case to average-case reduction for SIS. In previous question, "worst means any and average means random". And I wonder why the ...
8
votes
2answers
2k views

What does “Worst-case hardness” mean in lattice-based cryptography?

In the wiki page of Lattice-based Cryptography the "Worst-case hardness" is defined as below: Worst-case hardness of lattice problems means that breaking the cryptographic construction (even with ...
8
votes
1answer
330 views

Converting NewHope/LWE key exchange to a Diffe-Hellman-like algorithm

By a “Diffe-Hellman-like” algorithm, I mean one that has the same API as Curve25519, etc (disregarding trivial differences such as the size of parameters): a function $$F: (P_\text{other}, S_\text{...
8
votes
1answer
692 views

Lattice Crypto worst case to average case

I am currently reading the ETSI white paper Quantum Safe Cryptography and Security On page 24 one finds the following statement: Lattice problems also benefit from something called worst-case to ...
8
votes
1answer
1k views

Problem with LLL reduction on truncated LCG schemes

I am struggling to apply Freize et al. paper to break a truncated LCG. A truncated LCG is a pseudo random generator that outputs the $n$ leading bits $y_i$ of $x_i$, where $(x_i)$ is such that $x_{...
8
votes
2answers
151 views

Cardinality of the group of units in a cyclotomic ring?

In the NTRU key generation, one samples a polynomial from $K = (\mathbb Z/q\mathbb Z)[X]/(X^n+1)$ and tests if it is invertible. What are the chances of this to happen? In other words: Let $q$ be a ...
8
votes
1answer
321 views

Is HIMMO For Real?

I've come across something out of Philips Research called HIMMO Key Pre-Distribution Scheme (https://eprint.iacr.org/2016/410.pdf and https://www.ietf.org/proceedings/96/slides/slides-96-cfrg-2.pdf) ...
8
votes
1answer
253 views

Lattice attacks against Multilinear Maps [CLT13]

I am currently studying an article on a construction of Multilinear maps. There are some attacks on the scheme presented by the authors and I got stuck at the one in section 5.1. I will try to ...
8
votes
1answer
202 views

LWE: error and float operations

Background I'm trying to make sense of the error in implementations of LWE and R-LWE. In LWE and R-LWE error is added to vectors in lattices to make it computationally infeasible to recover any ...
7
votes
1answer
342 views

Relation between decisional SIS and leftover hash lemma in lattices

The semantic security of Regev's cryptosystem [Reg05] is based on the LWE assumption and leftover hash lemma. This lemma implies that because $m \approx (n+1)\log q$ is large enough, so for uniform $A\...
7
votes
1answer
1k views

Why is the Lovász condition used in the LLL algorithm?

The LLL algorithm is used to approximate the Shortest Vector Problem, i.e., it outputs a reduced basis. Such a basis will satisfy two conditions: $$ \forall i \gt j. \quad \lvert\mu_{ij}\rvert \le \...
7
votes
1answer
157 views

Are LPN and LWE problems equivalent?

Learning with Error (LWE) problem seems like a generalization of Learning Parity with Noise (LPN) problem, where in the latter one uses bits. But, this also makes LPN seem very related to the problem ...
7
votes
1answer
472 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 ...
7
votes
1answer
334 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 ...
7
votes
3answers
907 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 ...
7
votes
1answer
689 views

Gaussian distribution in lattices

In many lattice based cryptosystems, Gaussian distribution is used. Can you explain why only Gaussian distribution is preferred?
7
votes
1answer
590 views

Why is Approximate GCD a hard problem?

There are many Fully Homomorphic Encryption over the Integers schemes whose security is based on the intractability of the Approximate GCD (AGCD) problem. The paper Algorithms for the Approximate ...
7
votes
0answers
110 views

Differences between “NewHope” and “NewHope-simple”

The well-known paper described a key exchange (KE) scheme named "NewHope" on USENIX 2016. The authors then proposed "NewHope-Simple" - a PKE/KEM scheme. They also submitted "NewHope for NIST" - ...
6
votes
1answer
1k views

Help in understanding exactly how lattices used as one way functions for hashing

I am doing a cryptography course via long distance and we have been given an assignment which is based on lattice-based cryptography. I have spent the majority of the past week sifting through papers ...
6
votes
1answer
343 views

Discrete Gaussian Sampling role in Lattice-Based Crypto?

I'm reading up on how post-quantum cryptography works, and stumbled upon the notion of discrete Gaussian sampling. However, I can't understand where it fits in the greater picture - currently it feels ...
6
votes
1answer
278 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 ...
6
votes
1answer
758 views

Use of q-ary lattices in developing cryptosystems

Why q-ary lattices are used to most cryptosystems rather than lattices. In most of the papers q-ary lattices are used. Is there any advantage? and Given $$B=(v_1,v_2,v_3,.....v_n)$$ is the basis, ...
6
votes
1answer
178 views

Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-QuantumWorld

In this paper (Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-Quantum World), author describe password authenticated key exchange scheme on page 9 and 10 (see Fig. 1 on ...
6
votes
3answers
253 views

Is the HNF basis the worst basis for a lattice?

I am researching lattice problems and some methods for solving them. I read some books that mentioned Babai's algorithm for finding the Closest Vector Problem (CVP) cannot be successful with a "bad" ...
6
votes
1answer
145 views

When does the SIS (Short Integer Solution) Lattice-problem start becoming easy (According to the parameters size)?

SIS (Short Integer Solution) Problem : Given $m$ uniformly random vectors $a \in Z_q^n$, grouped as the columns of a matrix $A \in Z_q^{n.m}$, find a nonzero integer vector $z \in Z^m$ with $||z|| \...
6
votes
0answers
87 views

Most influential/illuminating papers/books/courses on lattice based cryptography?

I'm interested in some sort of "compendium" on lattice based crypto. There are a bunch of maths behind FALCON and other stuff. A lot of articles are devoted to lattice crypto, but not of them are of ...
5
votes
4answers
440 views

R-LWE key exchange why using FFT instead of Karatsuba

In the paper Post-quantum key exchange for the TLS protocol from the ring learning with errors problem one of the authors, Douglas Stebila, uses the FFT algorithm for polynomial multiplication but he ...
5
votes
3answers
274 views

A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem

In this paper (A simple provably secure key exchange by Ding et al.) At page number 8, the author gives correctness of the technique as follows then SK A = SKB with overwhelming probability i.e. if ...
5
votes
1answer
457 views

Why is lattice-based cryptography believed to be hard against quantum computer?

Why is lattice-based cryptography believed to be hard against quantum computer? Learning With Errors(LWE) problem (reduction to SVP) is just one example. Can you provide some intuition of the ...
5
votes
1answer
187 views

What is meant by a “short” vector in cryptography?

I was trying to understand Learning with Errors for Lattice-based Cryptography and I came across this. The learning with errors problem is: Given an $m \times n$ matrix $A$ and a vector $b \equiv ...
5
votes
1answer
274 views

How the condition $s \geq 8$ is determined in Lindner-Peikert cryptosystem?

In Lindner & Peikert paper, the authors propose that to set the cryptosystem's parameters, one should choose $q$ to be large enough to allow for a Gaussian parameter $s \geq 8$. My question is, ...
5
votes
1answer
426 views

How to generate new LWE samples

Assume we are given a small fixed number of LWE samples with secret $s$ and error $e$, where the error distribution is taken so that the LWE problem is hard. My question: How can one further ...
5
votes
2answers
515 views

What is the direct connection between LWE and GapSVP?

Learning with Errors Problem (LWE): Given a polynomial number of random noisy linear equations $b_i$ in the form of pairs $$ (a_i, \quad b_i = \langle s, a_i \rangle + e_i) $$ where $a_i \in \mathbb{...
5
votes
1answer
502 views

What is the difference between Module-LWE and Ring-LWE?

Recently, the CRYSTALS lattice-based cryptographic suite has been published, which is based on "module lattices". What is Module-LWE? How is it different from Ring-LWE?
5
votes
1answer
188 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 ...
5
votes
2answers
249 views

ZK Proof for SIS

Let $A x = 0 \bmod q$ with $\Vert x \Vert < \beta$ as part of a lattice SIS problem. Does there exist an efficient zero knowledge proof of knowledge for such a solution? My idea is to use it for ...
5
votes
1answer
614 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 ...