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
3 answers
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 ...
mephisto's user avatar
  • 2,888
31 votes
1 answer
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 ...
Morty's user avatar
  • 589
24 votes
3 answers
5k views

What does the work "An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor" mean?

In An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor, the author claims they give a polynomial-time quantum algorithm for solving the Bounded Distance ...
user77340's user avatar
  • 787
19 votes
1 answer
5k 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 ...
mikeazo's user avatar
  • 38.5k
19 votes
1 answer
995 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 ...
Rick's user avatar
  • 1,265
17 votes
2 answers
2k 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 ...
robertkin's user avatar
  • 428
15 votes
4 answers
6k views

Kyber and Dilithium explained to primary school students?

Kyber and Dilithium are post-quantum cryptographic designs, but the resources are hard to understand. Is it possible to explain those ciphers to children?
Flan1335's user avatar
  • 351
15 votes
0 answers
1k 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 ...
pg1989's user avatar
  • 4,626
14 votes
1 answer
2k views

Is lattice-based cryptography practical?

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?
Steven Sagona's user avatar
13 votes
3 answers
1k 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?
Little Nan's user avatar
12 votes
5 answers
2k 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 ...
mallea's user avatar
  • 1,595
12 votes
1 answer
2k views

Current Consensus on Security of Lattice Based Cryptography?

In an edit to an answer by user forest, it was mentioned that there has been a new attack developed for lattice-based cryptography. I thought lattice-based cryptography is a fairly well established ...
Steven Sagona's user avatar
12 votes
2 answers
4k 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 ...
Habib's user avatar
  • 951
12 votes
1 answer
3k views

Why did NIST select Kyber and Dilithium?

NIST selected Kyber for key agreement and Dilithium for digital signature applications some days ago. But IDF's MATZOV group, in their paper, broke Kyber and Dilithium and brought the security levels ...
Daniel's user avatar
  • 121
12 votes
0 answers
677 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 ...
CoryG's user avatar
  • 549
11 votes
3 answers
951 views

Error-correcting Code VS Lattice-based Crypto

I'm not an expert in PQ-crypto, but as I understand error-correcting code and lattice-based crypto, the cryptographic assumptions are very similar. The key difference for me is the nature of the noise....
Ievgeni's user avatar
  • 2,565
11 votes
1 answer
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 ...
Andrea Russo's user avatar
11 votes
0 answers
97 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 ...
Daniela's user avatar
  • 111
11 votes
0 answers
661 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 ...
JongHyun Kim's user avatar
10 votes
2 answers
1k 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 ...
Mark's user avatar
  • 11.7k
10 votes
2 answers
2k 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 \...
preethi's user avatar
  • 889
10 votes
1 answer
1k 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, ...
preethi's user avatar
  • 889
10 votes
1 answer
1k 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 ...
Kirill Tsar.'s user avatar
9 votes
2 answers
569 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 ...
Hamidreza's user avatar
  • 999
9 votes
1 answer
572 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{...
Demi's user avatar
  • 4,763
9 votes
1 answer
1k 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 ...
user avatar
9 votes
1 answer
150 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 ...
Mar Johnson's user avatar
9 votes
1 answer
395 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) ...
MountainLogic's user avatar
9 votes
1 answer
1k views

Gaussian distribution in lattices

In many lattice based cryptosystems, Gaussian distribution is used. Can you explain why only Gaussian distribution is preferred?
preethi's user avatar
  • 889
9 votes
0 answers
578 views

Can LWE be NP-hard?

Regev's reduction shows that LWE is quantumly at least as hard as CVP with an approximation factor of $n/\alpha$ for $0<\alpha<1$. But I just watched this talk which said that if $\sqrt{n/\log n}...
Sam Jaques's user avatar
  • 1,105
9 votes
0 answers
173 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" - ...
Zachary's user avatar
  • 177
8 votes
2 answers
2k views

Is lattice encryption susceptible to Grover's algorithm?

So Grover's algorithm, also known as the quantum search algorithm, can find an entry, with a high probability, in an unstructured database. Well can't we consider the basis of a lattice problem an ...
Steve Mucci's user avatar
8 votes
1 answer
1k 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 ...
Daniel B's user avatar
  • 347
8 votes
1 answer
644 views

NewHope and NIST's Post-quantum standardization

Where can I find NIST's reasoning to eliminate NewHope from the 3rd round of the post-quantum competition? I see all the lattice KEMs finalists are based on modules. Is being a ring-based KEM ...
Rick's user avatar
  • 1,265
8 votes
2 answers
822 views

LWE: Round a continuous Gaussian to a true Discrete Gaussian

Short version: how is it possible to round a continuous Gaussian into a true discrete Gaussian (usually denoted $\mathcal{D}_{\mathbb{Z},\alpha q}$)? The goal is to obtain a reduction from continuous ...
Léo Colisson's user avatar
8 votes
1 answer
1k 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 ...
user avatar
8 votes
2 answers
229 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 ...
Tal-Botvinnik's user avatar
8 votes
3 answers
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 ...
Node.JS's user avatar
  • 312
8 votes
1 answer
767 views

What's the purpose of the smoothing parameter in lattice-based cryptography?

I see nearly all the lattice-based crypto papers talk about the smoothing parameter $\eta$. And I believe even some parameters are chosen with respect to that. However, I do not quite understand what'...
user avatar
8 votes
1 answer
280 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 ...
floor cat's user avatar
  • 214
8 votes
0 answers
247 views

How are the constants found in the AVX2 implementation of CRYSTALS-KYBER round 2 generated?

The post-quantum lattice-based cryptosystem CRYSTALS-KYBER which has made it to the second round of NIST PQC includes two implementations: 1) a baseline reference implementation in C and 2) an ...
caesar's user avatar
  • 315
7 votes
1 answer
2k views

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

In my long-distance cryptography course, an assignment covers lattice-based cryptography. It is hard, and I am lost. There is no one to help me. Thus far, I have understood that: Lattices are a ...
user2012620's user avatar
7 votes
1 answer
906 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\...
Hamidreza's user avatar
  • 999
7 votes
1 answer
497 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 ...
Rick's user avatar
  • 1,265
7 votes
1 answer
806 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 ...
user33284's user avatar
7 votes
1 answer
3k 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?
Naruto999's user avatar
  • 436
7 votes
1 answer
295 views

Is LPN not as important as LWE and SVP?

I've been learning about lattice cryptography and have noticed that most resources such as this survey by Chris Peikart, the Winter School on Lattice Cryptography etc don't include material on LPN, ...
fraiser's user avatar
  • 438
7 votes
1 answer
275 views

IND-CCA2 post-quantum key exchange

QUIC requires that servers reuse keys so that session resumption works. That breaks many post-quantum key exchange systems. I am looking for a post-quantum key exchange algorithm with the following ...
Demi's user avatar
  • 4,763
7 votes
1 answer
343 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 ...
Dragos's user avatar
  • 646
7 votes
0 answers
385 views

Does there exist trapdoor permutation from lattices?

It seems that the lattice functions are either surjective (SIS) or injective (LWE), due to the error that is basically intended to destroy the structure and provide security. I was wondering whether ...
user avatar

1
2 3 4 5
11