Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
544
questions
3
votes
1
answer
153
views
A problem about Gaussian distribution in paper GPV08
These are contents from the paper Trapdoors for Hard Lattices
and New Cryptographic Constructions(GPV08). I do not know the reason about the last sentence. Why these two distributions $D_{\Lambda, s, ...
- 341
1
vote
1
answer
142
views
Is it possible that a signing algorithm produces no output?
I am reading Vadim Lyubashevsky's paper on Lattice Signatures without Trapdoors and I came across a somehow counter-intuitive part where he defined an algorithm $\mathcal{A}$:
$y\leftarrow D_\sigma^m$...
2
votes
0
answers
99
views
Multibit LWE Encryption
What's the simplest way to encrypt multiple bits with LWE public key cryptosystem? Some paper say use a different secret key for each bit of the message. Does that mean the length of the message ...
- 83
1
vote
1
answer
262
views
Trying to Understand Ring Learning With Error Encryption
I'm trying to understand the following RLWE encryption scheme from this Chris Peikert's paper
Say i choose $q = 97$, $n=8$ and the polynomial
$a = 96 x^8+30 x^7+76 x^6+12 x^5+57 x^4+77 x^3+70 x^2+49 ...
- 83
6
votes
1
answer
544
views
Decision to Search LWE when modulus $q=p^e$
I am reading Applebaum et al..
In Lemma 1. (page 7), Applebaum et al. proved the decision to search reduction when the modulus $q=p^e$ for prime $p$.
In the proof, they define the hybrid ...
- 145
5
votes
0
answers
83
views
Relation between LPN and GAPSVP?
I have a question regarding the relationship between the (search) LPN problem and the GapSVP problem.
I have read a related problem that explains the main theorem in Reg05: the GapSVP problem can be ...
- 145
1
vote
1
answer
158
views
Compute statistical distance between two distributions over tuples
Let $X$ denote one distribution. Let $f,g, \text{ and } h$ denote three functions. If we have the results: $g(X)$ is within a negligible statistical distance of $h(X)$. Is it possible to prove
$$(f(...
- 145
3
votes
1
answer
107
views
Randomness of Decision Learning With Error Problem
I read the statement of the Decision Learning with error problem is:
distinguish between $(\vec a, \langle \vec a, \vec s \rangle + e)$ from uniformly random samples.
Can anyone explain what does ...
- 83
0
votes
1
answer
144
views
understanding LWE public key algorithm
I'm trying to understand this LWE public key system
say I use matrix A = [[44, 73, 20, 54],[92, 19, 78, 22],[31, 34, 94, 29],[82, 32, 70, 68]]
q = 97
bit = 1
and secret key s: [56, 90, 0, 46]
and ...
- 83
5
votes
1
answer
242
views
Are there any masking methods for integer multiplication masking?
I'm interested in lattice type cryptosystem such as Mod-LWR.
But I found that integer multiplication¹ is not safe for side-channel attacks.
I tried to make masking method by own method but it failed ...
- 51
2
votes
1
answer
62
views
Security of somewhat homomorphic encryption via LSB encoding?
I'm reading this paper
https://eprint.iacr.org/2011/344.pdf
It says that
"The secret-key encryption scheme whose security is based on the LWE assumption is rather straightforward.
To encrypt a bit, $...
- 247
1
vote
1
answer
243
views
Is there a LWE based public-key encryption scheme which is CCA1-secure?
Is there a lattice based PKE which is IND-CCA1 secure? Actually I am only familiar with LWE and SIS. So I want to know that what the IND-CCA1-secure LWE based PKE scheme looks like?
- 1,582
0
votes
1
answer
115
views
Trapdoors for Lattices: CCA-secure encryption
In Trapdoors for Lattices:Simpler, Tighter, Faster, Smaller, Micciancio and Peikert proposed a CCA-secure encryption.
However, I am confused about the step in decryption algorithm (p.36 Lemma 6.2.).
...
- 113
7
votes
1
answer
293
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, ...
- 438
8
votes
1
answer
766
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'...
user4936
1
vote
0
answers
141
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}_{...
- 11
3
votes
2
answers
215
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 ...
- 3,922
2
votes
0
answers
71
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{...
- 61
1
vote
0
answers
51
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 ...
- 589
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 ...
- 589
0
votes
1
answer
179
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 ...
1
vote
1
answer
171
views
Explanation of the tables found in Kyber round1 code?
The precomp.c file in Kyber NIST round 1 submission has three tables, could you please let me know how to generate these three tables? If I want to understand how ...
- 11
6
votes
1
answer
290
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$. ...
- 357
3
votes
0
answers
73
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?
- 87
4
votes
1
answer
211
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 ...
- 61
2
votes
0
answers
480
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 ...
- 414
3
votes
0
answers
195
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.
...
- 247
1
vote
1
answer
649
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 ...
- 1,384
3
votes
0
answers
120
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 ...
- 31
4
votes
1
answer
457
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 ...
- 889
2
votes
1
answer
97
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 = ...
- 436
5
votes
1
answer
2k
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
0
answers
118
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$ ...
4
votes
2
answers
423
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?
- 355
1
vote
1
answer
343
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 ...
- 355
2
votes
1
answer
110
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) ...
- 355
3
votes
1
answer
293
views
What makes lattice-based cryptography quantum-resistant?
As opposed to RSA or elliptic curve cryptography?
- 355
3
votes
1
answer
168
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 ...
- 41
1
vote
0
answers
430
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 ...
- 111
2
votes
1
answer
151
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 ...
- 247
1
vote
0
answers
98
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 ...
- 33
2
votes
0
answers
149
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-...
- 436
2
votes
1
answer
181
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}$ ...
- 33
5
votes
1
answer
218
views
What is the difference between discrete-then-gaussian and gaussian-then-discrete?
In lattice cryptography, we always face the probem of discrete gaussian sampling. To the beginners, it is a bit complex. However, gaussian sampling from a continous space is much easier to understand, ...
- 313
1
vote
0
answers
361
views
Dilithium signature scheme - Public key derivation
I was looking at post quantum signature schemes, and I came across Dilithium(https://github.com/pq-crystals/dilithium), and our system currently runs on Ed25519 which based on my question can easily ...
1
vote
0
answers
80
views
Probability of an RLWE sample
Let $R_q=\mathbb{Z}_q[x]/(x^n+1)$ as usual in the RLWE assumption.
Suppoes that I choose a sample of the RLWE distribution, that is, I compute $(a,y=as+e)$ where $a$ is uniform in $R_q$ and $s,e\...
- 486
3
votes
1
answer
120
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-...
- 93
3
votes
1
answer
241
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 \...
- 1,136
5
votes
0
answers
234
views
Why is it safe to generate the secret key and masking vectors using rejection sampling in CRYSTALS-Dilithium?
In CRYSTALS-Dilithium module lattice-based digital signatures, the secret key vectors $s_1, s_2$ with coefficients in $[-\eta, \eta]$ and the signature masking vector $y$ with coefficients in $(-\...
- 436
0
votes
1
answer
306
views
Relations between Number theory/Algebra and Lattice based cryptography
I am an intern (I started yesterday) in a research lab on lattice based cryptography and I have a more mathematical background, in particular algebra.
I would like to know what type of algebraic ...
- 147