Questions tagged [lattice-crypto]

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

Filter by
Sorted by
Tagged with
5
votes
0answers
42 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, ...
4
votes
0answers
85 views

Parameters for high density SIS

I am considering the SIS problem of finding $x\in \mathbb{Z}^m$ such that for random $A\in\mathbb{Z}_q^{n\times m}$, $Ax=0$ and $\lVert x\rVert < \beta$ for some $p$-norm and bound $\beta < q$. ...
5
votes
0answers
50 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'...
1
vote
0answers
32 views

How many ring-LWE samples are required for the (Search) Ring Learning With Errors problem to have a unique solution?

Consider the LWE distribution $\{(\pmb{a}_{i},\left<\pmb{a}_{i} , \pmb{s}\right> + e_{i})\}$ where secret $\pmb{s} \in \mathbb{Z}_{q}^{n}$, randomness is $\pmb{a}_{i} \xleftarrow{\$} \mathbb{Z}_{...
27
votes
2answers
746 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 ...
2
votes
0answers
34 views

ZKPoK for RLWE secret and error

I came across How to validate the secret of a Ring Learning with Errors (RLWE) key paper by Ding et al., which seems to provide a ZK proof that the given $p$ is of the form $as + e$ with $s, e$ small ...
3
votes
1answer
173 views

Using the Babai's Naive Rounding algorithm to decode, in the conditions of the SIS problem, is secure?

Given the SIS Problem: Given an integer q, a matrix $A \in \mathbb{Z}_q^ {n \times m}$ uniformly random, a real $\beta$, a syndrome $u \in \mathbb{Z}_q^n$, find a nonzero integer $e \in \mathbb{Z}^m$ ...
0
votes
0answers
26 views

The implementation of Lattice-based HIBE

There are many lattice-based scheme papers adopt the lattice basis delegate technical from Agrawal et al. But I can't find the relevant implementation on the Internet since 2010. In fact, I almost ...
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 ...
3
votes
2answers
192 views

How is the matrix A related to the lattice space L in SIS?

Is the matrix $A= (b_1|,...,|b_m)$ where B=$(b_1,...,b_m)$ is the basis of the lattice space, $L$(B)? Not sure if the answer is trivial however I'm having trouble seeing how SIS is a lattice hard ...
3
votes
0answers
168 views

CVP over $\Bbb Z_{q}$ - is the problem still hard?

I'm reading about the CVP problem, and all the papers I've read so far handle the case where the CVP matrix and vector are over $\Bbb R^{n}$ (or over $\Bbb Z^{n}$), and the distance is a real number. ...
1
vote
0answers
24 views

Choices of $q$ and $f$ for RLWE-based constructions

I understand that RLWE was introduced to avoid the quadratic overhead in the matrices that appear in plain LWE. However, I have a series of questions about this setting. First, Ring-LWE-based ...
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 ...
1
vote
0answers
119 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 ...
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 ...
3
votes
1answer
73 views

LWE secure with one entry without noise

I'd like to know, is Learning With Error (LWE) (with modular noise) "secure" if one entry has no noise? More precisely, I have: a random matrix $A \in \mathbb{Z}_q^{m \times n}$ a random string $s \...
4
votes
1answer
173 views

Lattice-based cryptography prone to side channel attack?

Is lattice-based cryptography still prone to side channel attacks? What are some mitigation strategies, if any?
2
votes
0answers
34 views

Why round off vector sampling from continuous Gaussian distribution not directly sample from discrete Gaussian distribution

For any vector $\mathbf{c}$, real $s > 0$, and lattice $\Lambda$, define the probability distribution $D_{\Lambda, s,\mathbf{c}}$ over $\Lambda$ by $$D_{\Lambda, s,\mathbf{c}}(\mathbf{x})=\frac{...
7
votes
3answers
908 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 ...
2
votes
1answer
69 views

Gentry-Halevi’s Fully-Homomorphic Encryption and hermite factor

In section 7.2, page 18 in Chen-Nguyen paper regarding BKZ 2.0, they point out different Hermite factors related to Gentry-Halevi FHE. More precisely, it is said that the critical Hermite factor for ...
1
vote
0answers
24 views

Again on discrete gaussians over lattices [duplicate]

Define $$\rho_{s,c}(x) = exp(-\pi \cdot \frac{\|x - c\|^2}{s^2})$$ and $$\rho_{s,c}(L) = \sum_{x \in L} \rho_{s,c}(x)$$ Then Discrete Gaussian over $L$ with center $c$ and standard deviation $s$ is ...
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 ...
0
votes
1answer
65 views

Help understanding lattice-based aggregate signature scheme

I came across this paper about aggregate lattice-based signatures, however, I'm not able to fully understand it. Specifically, I'm wondering if someone could help answer the following questions: In ...
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" ...
3
votes
0answers
189 views

Is the ring learning with errors problem still hard if the errors are drawn from some subspace?

Let $R=\mathbb{Z}_p[x]/x^n+1$ be the ring used in normal RLWE, which is linear space over $\mathbb{Z}_p$ with dimension of $n$, let $S$ be a linear subspace of $R$ which described by linear ...
4
votes
1answer
237 views

Why does Learning With Errors require a bunch of samples?

Solving Learning with Errors(LWE) with average case complexity is as hard as solving the SVP with worst case complexity. LWE requires $n$ dimensional lattice and $m$ samples of it, and Decisional-LWE ...
0
votes
0answers
30 views

Trapdoors of Lattices: SampleD and SamplePre

In Trapdoors for Hard Lattices and New Cryptographic Constructions by Gentry et. al, they discuss SamplePre and in Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio et.al, they ...
4
votes
1answer
129 views

Noise of ciphertexts in LWE/RLWE based FHE

Often times $[\langle \textbf{c}, \textbf{s} \rangle]_q$ is referred to as the noise associated to the ciphertext $\textbf{c}$, and that decryption is correct when the norm of the noise is $< q/2$. ...
3
votes
0answers
57 views

Lattice Based Cryptography domain

Some cryptosystems operate on the domain of the form $\mathbb{Z}_q[x]/\langle x^n-1\rangle$ and others operate on $\mathbb{Z}_q[x]/\langle x^n+1\rangle$. What's the security impact of the two forms?
4
votes
1answer
75 views

Why is the vector sampled from Gaussian or Subgaussian distribution in lattice-based cryptography? [duplicate]

I have known that the vector is sampled from Gaussian distribution in lattice-based cryptography because the distribution of the vector $\mod{\mathcal{P}(\mathbf{B})}$ approximates to uniform ...
1
vote
1answer
132 views

What is the purpose of adding secondary error to calculated key in BCNS and NewHope protocols

The answer to this question might be trivial or very short, but I would like to ask it anyway. In both BCNS and NewHope Ring-LWE key-exchange protocol one party adds a secondary error to their ...
1
vote
0answers
76 views

Canonical embedding vs. plaintext slots in Ring-LWE

I'm working on the canonical embedding mentioned in [LPR10] and [LPR13]. What confuses me is that the difference and the relationship between the canonical embedding and the concept of ''plaintext ...
9
votes
0answers
466 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 ...
1
vote
1answer
56 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 ...
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|| \...
2
votes
1answer
42 views

Calculation of failure probability in basic Ring-LWE-DH key agreement

This is the basic unauthenticated Ring-LWE-based Diffie-Hellman key exchange, based on Peikert's Ring-LWE KEM: (from BCNS15) Alice and Bob have shared public polynomial $a$ randomly drawn from $R_q = ...
4
votes
1answer
117 views

Finding the basis of the transpose of a q-ary lattice

Given $q$ and a matrix $A \in \mathbb{Z}_q^{n \times m}$, the $q$-ary lattice is defined as $$\Lambda(A)=\{x \in \mathbb{Z}^m:Ax=0 \bmod q\} $$ An instance of a q-ary lattice and its short basis is ...
2
votes
0answers
56 views

Adaptation of Stern Zero-Knowledge protocol from coding to lattices

I'm currently working on Zero-Knowledge-proofs in lattice context, for which there exist two major frameworks. One of those two is the adaptation of Stern protocol from code-based-crypto. There is in ...
2
votes
0answers
50 views

Estimating the Security of SIS-Based Signature, by verifiying a subset of coordinates?

As I understood, the GPV signature scheme works as follows: KeyGen($1^n$) : Generate a Lattice with public $A \in Z_q^{n.m}$ and a secret trapdoor $t$. Sign $m$: compute $\vec y = H(m) \in Z_q^n$ ...
1
vote
1answer
93 views

What is the most efficient lattice problem solving algorithm?

I've recently become very interested in post-quantum cryptography, specifically lattice-based cryptography. As of this posting there exists no quantum algorithm that can perform better at solving ...
3
votes
2answers
117 views

Is lattice-based cryptography relevant in symmetric cryptography?

I've seen that lattice-based cryptography works well with public key cryptography as well as cryptographic hashing algorithms, but does it apply to symmetric key cryptography?
2
votes
1answer
75 views

Is there an equivalent to an RSA UFO in lattice-based cryptography?

So there's this concept within the realm of RSA cryptography called an RSA UFO. It is an extremely important function in the context of cryptocurrency. When starting up a cryptocurrency the creator(s) ...
3
votes
1answer
121 views

What makes lattice-based cryptography quantum-resistant?

As opposed to RSA or elliptic curve cryptography?
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 ...
1
vote
0answers
131 views

RSA vs. Super Computer vs. Quantum Computer [closed]

I know that RSA is known to be secure in the current landscape of computing, and I know that RSA is known to be broken in the world of quantum computing and cryptography. I have two questions, can ...
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 ...
2
votes
1answer
80 views

Why does the following SIS-based decision language not make sense?

I'm currently reading about important lattices problems and noticed that while CVP, SVP, and LWE have decisional versions, SIS does not. I read in the question Relation between decisional SIS and ...
1
vote
0answers
53 views

How does the polynomial module impact the security of ring/lattices-based SIS problem?

Consider the following SIS problem: for a function $f_A(s)$=$As$, where $A$ is a fixed, randomly-chosen matrix in $(R_q)^{r \times n}$=$\left(\mathbb{Z}_q[X]/(X^N+1)\right)^{r \times n}$ and $q$ a ...
2
votes
0answers
47 views

Can binomial distribution be used to sample noise for Ring-LWE-based homomorphic encryption?

Homomorphic encryption schemes based on Ring-LWE need to sample the noise terms from a discrete probability distribution $\chi$ over the integers with support $[-B,B]$. For example, the Fan-...
2
votes
1answer
65 views

Can I connect the hardness of a linear short integer solution problem to that of SIS problem?

As we know, SIS problem is defined as: for a function $f_A(s)$=$As$, where $A$ is a fixed, randomly-chosen matrix in $\mathbb{Z}_q^{r \times n}$, it is hard to find elements $s \in \mathbb{Z}_q^{n}$ ...