Questions tagged [lattice-crypto]

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

Filter by
Sorted by
Tagged with
28
votes
2answers
769 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 ...
7
votes
1answer
364 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\...
4
votes
2answers
303 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 ...
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
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_{...
6
votes
1answer
179 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 ...
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 ...
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
660 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 ...
6
votes
1answer
360 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 ...
1
vote
1answer
441 views

What is the intuition of canonical-embedding in homomorphic encryption based on RingLWE?

In the cryptosystem based on Ring-LWE, the noise amount is measured by canonical-embedding norm. What is the intuition behind canonical-embedding?
7
votes
3answers
928 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
197 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 ...
12
votes
0answers
625 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 ...
7
votes
1answer
702 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
481 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 ...
4
votes
1answer
164 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 ...
4
votes
2answers
652 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 ...
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 ...
4
votes
2answers
215 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 ...
4
votes
1answer
217 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|| ...
3
votes
1answer
375 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 $\...
2
votes
1answer
247 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 ...
2
votes
0answers
54 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 $\...