As of May 31, 2023, we have updated our Code of Conduct.

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,880
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
  • 777
19 votes
1 answer
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 ...
mikeazo's user avatar
  • 38.3k
19 votes
1 answer
942 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,235
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
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,616
14 votes
4 answers
5k 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
  • 341
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
1k 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,545
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
1 answer
2k 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
650 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
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
  • 941
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
635 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
  • 10.8k
10 votes
3 answers
821 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,543
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
  • 879
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
  • 879
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
547 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
  • 990
9 votes
1 answer
517 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
146 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
390 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
  • 879
9 votes
0 answers
487 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,005
9 votes
0 answers
171 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
1 answer
598 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,235
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
220 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
1 answer
264 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
214 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
1k 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
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
  • 337
7 votes
1 answer
474 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,235
7 votes
2 answers
681 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
7 votes
1 answer
764 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
2k 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
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
  • 302
7 votes
1 answer
258 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
623 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
7 votes
1 answer
253 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
332 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
  • 626
7 votes
0 answers
362 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
6 votes
1 answer
804 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
  • 990
6 votes
1 answer
644 views

Hardness of Short Interger Solution in Lattices

Short Integer Solution ($SIS_{n,m,q,\beta}$) is defined as: Given a matrix $A \in \mathbb{Z}_{q}^{n \times m}$, find a non-zero vector $x \in \mathbb{Z}^{m}$ such that $A \cdot x = 0\mod q$ and $||x|| ...
preethi's user avatar
  • 879

1
2 3 4 5
10