Questions tagged [lattice-crypto]

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

Filter by
Sorted by
Tagged with
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
  • 599
4 votes
2 answers
613 views

What is the difference between the standard representants of $\mathbb Z/q\mathbb Z$?

The symbol $\mathbb Z/q\mathbb Z$ (given that $q$ is prime) represents the prime field $\mathbb Z_q$. Basically, the elements of this field are represented by $\{0, 1, \dots, q-1\}$, let's call this ...
caesar's user avatar
  • 315
10 votes
1 answer
2k 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
8 votes
1 answer
937 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
  • 1,019
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
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
8 votes
1 answer
2k 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
866 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
820 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
6 votes
1 answer
235 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 ...
vivek's user avatar
  • 197
6 votes
1 answer
1k views

How to estimate the hardness of SIS instances?

The Short Integer Solution (SIS) problem is to find, given a matrix $A \in \mathbb{F}_q^{n \times m}$ with uniformly random coefficients, a vector $\mathbf{x} \in \mathbb{Z}^m \backslash \{\mathbf{0}\}...
Alan's user avatar
  • 1,450
3 votes
1 answer
515 views

RLWE Explanation

In RLWE, we often choose the following polynomial ring, where q is a prime, and n is a power of 2, e.g. $2^k$ $$\mathbb Z_q[X]/(X^n + 1)$$ We know that ${X^{2^k}} + 1$ is an irreducible polynomial ...
fuo55631's user avatar
3 votes
1 answer
242 views

Is LWE easy when the matrix $A$ is sparse?

Recall that the LWE problem is the following. LWE problem. Let $q$ be a prime, let $\chi$ be a distribution of small elements over $\mathbb{Z}/q$, and let $n,m$ be two integers (dimensions of vectors ...
Kolja's user avatar
  • 143
2 votes
2 answers
235 views

How would low-precision Gaussian sampling impact the security of BLISS?

For digital signature, I implemented BLISS in my cryptographic suite, and wrote the Gaussian sampler based on Lattice Signatures and Bimodal Gaussians. But unlike the reference implementation and ...
DannyNiu's user avatar
  • 9,080
2 votes
1 answer
214 views

Why does lattice KEX not require sampling with high precision?

I was reading the NewHope paper, and I see that they are using Binomial distribution and not a discrete Gaussian distribution as was used by BCNS. I also remember hearing somewhere that lattice key ...
typos's user avatar
  • 809
2 votes
1 answer
123 views

NTRUEncrypt fails on quaternion algebra

This is a follow-up of my previous two questions (1 and 2), might be relevant to check them out first for a full context. I am trying to re-create results from this paper. The basic algorithm is ...
max's user avatar
  • 219
1 vote
1 answer
747 views

Do q-ary lattices have parallelogram kind of structure?

An $m$-dimensional lattice is defined by a basis $A \in \mathbb{R}^{m \times n}$ is the set of points $\{Az : z \in \mathbb{Z}^n\}$. A picture of these points would be like a nice parallelogram kind ...
satya's user avatar
  • 1,404
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
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
7k 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
  • 361
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,636
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
10 votes
2 answers
3k 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
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
8 votes
0 answers
417 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
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
6 votes
1 answer
753 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
  • 889
6 votes
2 answers
1k views

MLWE (and RLWE) to LWE reductions proof

In crypto papers, cryptanalysis of MLWE/RLWE/etc. is often reduced to LWE. Why can we do this? Is there strict proof of such reductions?
OneUser's user avatar
  • 123
6 votes
2 answers
1k views

How to find the value of a vector modulo a basis in lattice-based cryptography

In Gentry's paper on fully homomorphic encryption using ideal lattices, he finds the values of vectors modulo a certain basis. For instance: $\psi \leftarrow \psi' \mod B$ Taken from page 69 of ...
danxinnoble's user avatar
5 votes
1 answer
208 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 ...
Node.JS's user avatar
  • 312
5 votes
1 answer
274 views

$L^3$ Grover search of NTRU variants

I was reading a text on cryptology by Wayne Patterson and came across the $L^3$ algorithm which reduces integer lattices with respect to their base. I've also read on the NIST CFP A8 that attacks ...
floor cat's user avatar
  • 214
5 votes
2 answers
2k 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{...
LQWE's user avatar
  • 91
4 votes
1 answer
266 views

LWE with identity sub-matrix and reused sampled from [MP12]: why is it secure?

I studied this paper a while ago, but now I'm confused by the paper Trapdoors for Lattices:Simpler, Tighter, Faster, Smaller by Micciancio and Peikert. Page 24 and 25, they present an algorithm that ...
Léo Colisson's user avatar
4 votes
1 answer
490 views

What is the largest parameter broken for NTRU?

The original secure parameters for NTRU shown below are from the original HPS98 paper. This is vastly different from the current secure suggested parameters in the NIST PQC round 3 submission. ...
evernal's user avatar
  • 237
4 votes
1 answer
229 views

Finding the exact solution of an LWE instance with a sparse matrix

I already asked a question about the feasibility of LWE when the matrix A is sparse or small here. Let $q$ be a prime, let $\chi$ be a distribution of $\textit{small}$ elements over $\mathbb{Z}/q$, ...
Kolja's user avatar
  • 143
4 votes
1 answer
228 views

Prove that a small Ring-LWE secret is unique

I just want to know whether my proof is correct, which is about proving that if the Ring-LWE secret is small, then it is unique. Before giving my proof, here is a fact: Fact 1: $\Pr [\Vert r \Vert_\...
Chito Miranda's user avatar
4 votes
2 answers
426 views

How to determine the concrete security of lattice cryptosystems?

I am currently reading about lattice cryptography and am interested in the cryptosystems based on the LWE problem. I understand the reductions from lattice problems to dLWE. Then we base our belief in ...
AntoineD's user avatar
3 votes
1 answer
121 views

How does the 'Flatten' function reduce the coefficients of a vector/matrix?

Seen here, at the bottom of page 5, $\operatorname{Flatten}(\vec{a})$ is defined as: $\operatorname{Flatten}(\vec{a})=\operatorname{BitDecomp}(\operatorname{BitDecomp}^{-1}(\vec{a}))$ For an n-...
Stilton's user avatar
  • 93
3 votes
1 answer
407 views

Gap problem for Learning With Errors

Informally, a "Gap problem" arises when solving the computational (or search) version using an oracle for the decisional version. This definition of Gap Problem was introduced by Okamoto and ...
cygnusv's user avatar
  • 4,952
3 votes
1 answer
777 views

Trapdoors for lattices

I refer to an article https://eprint.iacr.org/2011/501. I focus on (a bit modified) Algorithm 1 which runs as follows (in my understanding): For given $n, m\in \mathbb N$, $q=2^k$ and a distribution $\...
vladkkkkk's user avatar
  • 133
3 votes
1 answer
280 views

NTRUEncrypt fails on sedonion algebra

This question is a direct follow-up (hopefully - the last) of my previous one; please see it for full information. I would like to further generalise NTRU cryptosystem on higher-order algebras. ...
max's user avatar
  • 219
3 votes
1 answer
1k views

Understanding Unique-SVP and Kannan's Embedding

I am trying to understand the Kannan embedding technique. But I am confused about the formation of the B' and the finding of the short vector inside that basis. How does this basis matrix in the ...
Semiramis's user avatar
2 votes
1 answer
566 views

Bit decomposing a polynomial in BGV cryptosystem

I'm having trouble with the BitDecomp subroutine on page 9 of the BGV cryptosystem. I'm focusing on the RLWE instantiation so $R_q = \mathbb{Z}[x]/(x^d+1,q)$. I can't see how BitDecomp works for a ...
sycs's user avatar
  • 85
2 votes
1 answer
222 views

Classification of attacks against lattices

I'm interested about the cryptanalysis side of lattice-based cryptography, and was wondering whether there is a survey paper or something that gives some classification of attacks against lattices, ...
user avatar
2 votes
3 answers
305 views

LWE with a binary matrix A

In LWE, we know that given reasonable public parameter $A\in \mathbb{Z}_q^{n\times \lambda}$, secret $s\in \mathbb{Z}_q^{\lambda}$ and noise $e\in \mathcal{X}^{n}$, random $r\in \mathbb{Z}_q^{n}$, $(A,...
user102777's user avatar
2 votes
0 answers
189 views

SampleLeft function in lattice trapdoors

We have SampleLeft function in lattice trapdoors as Algorithm $\textbf{SampleLeft}(A,M_1,T_A,u,\sigma)$: $\textbf{Input}$: a rank $n$ matrix $A$ in $\mathbb{Z}^{n×m}_q$ and a matrix $M_1$ in $\...
chelsea's user avatar
  • 404
2 votes
0 answers
223 views

Hardness of $SIS$ and its reduction to an NP-complete problem

Short Integer Solution ($ SIS_\gamma^{(q,n,m,\beta)}$): Given a matrix $A\in Z_{q}^{n×m}$, find $x \in Z^m $, such that $Ax=0\mod q$ and $||x|| \le \beta$ Is $SIS\in NP$ ? If $SIS \in NP$, then it ...
preethi's user avatar
  • 889
1 vote
1 answer
108 views

value bound of r⋅e for LWE Decryption correctness

For LWE decryption, Someone told me that If we can bound r⋅e by q/4 then we can retrieve M by checking if this is closer to <...
kevin's user avatar
  • 121
1 vote
1 answer
134 views

NTRUEncrypt fails on complex algebra

I am following the NTRUEncrypt cryptosystem as described on the wikipedia. I have implemented it in Sage Math engine (with small problems along the way, but in the end - succesfully resolved) and the ...
max's user avatar
  • 219
1 vote
1 answer
361 views

How long time per operation to crack Kyber1024 compared to AES256 for quantum computers?

How long time does quantum computers take per operation when search the key of Kyber? Grover's algorithm weakens 256-bit AES to 128-bit security, quantum computers at most take 2^128 operations to ...
Flan1335's user avatar
  • 361