Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
495
questions
4
votes
1
answer
169
views
Famous ideal lattices
I am wondering if there exist some special rings $R$ that gives us, under the canonical embedding, some special lattices, like the root lattices, Barnes-Wall lattices, Leech lattices, ...
In more ...
- 415
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 ...
- 1,235
4
votes
1
answer
238
views
Are all homomorphic encryption schemes based on latticed-based schemes?
PALISADE offers a pool of Homomorphic Encryption schemes and it is stated that "PALISADE is a general lattice cryptography library ...". My question is rather simple: are all homomorphic ...
- 685
3
votes
1
answer
347
views
Lattice reduction question regarding the capability of LLL and BKZ
I've been reading How to estimate the hardness of SIS instances? and following some of its sources, and I want to confirm a few things.
LLL algorithm runs in polynomial time, but isn't capable of ...
- 8,291
6
votes
2
answers
941
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?
- 123
1
vote
1
answer
55
views
Guessing the Secret in RLWE Search-to-Decision
In On Ideal Lattices and Learning with Errors over Rings, the authors prove a search-to-decision reduction by guessing the RLWE secret $s$, and using the guess to transform a sample from $\mathfrak{q}...
- 381
0
votes
1
answer
54
views
Voronoi regions of lattices with dimensions $\leq 16$
Is there any idea about calculating the exact Voronoi regions of lattices with dimensions $\leq 16$?
Thank you!
- 415
4
votes
1
answer
97
views
Proving LWE inversion in Micciancio-Peikert-2012 lattice trapdoors
I'm looking through the lattice trapdoor construction in https://eprint.iacr.org/2011/501.
To summarize, assume we have a matrix $G$ where, on input $b$, we can efficiently find $(s,e)$ such that $s^...
- 1,005
3
votes
2
answers
518
views
Distribution of the Difference of Uniformly Random Elements
In the search to decision reduction of 'On Ideal Lattices and Learning with Errors over Rings', the authors implicitly use the fact that the difference of distinct, uniformly random elements of a (...
- 381
1
vote
0
answers
181
views
What are the prerequisites for understanding Lattice based Cryptography, LWE or RLWE based on SVP?
I'm new to Quantum Resistant Cryptography, so, I thought of diving into Lattice based crypto, LWE and ring LWE. I realise that the hard problem involving them is the "shortest vector problem"...
- 978
3
votes
1
answer
94
views
Dual of a complex lattice
We know that for a real full-ranked lattice $\Lambda$, with real square matrix $\mathbf{B}$, the dual lattice $\Lambda^{\vee}$ has matrix $(\mathbf{B}^{-1})^T$.
Now If we have a complex lattice with $...
- 415
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....
- 2,543
1
vote
2
answers
352
views
Verify that a point is inside a lattice
I am wondering if there's a polynomial time algorithm that, given a lattice $\Lambda$ with basis $\mathbf{B}$ and a point $x$ in space, it tells you whether $x$ is in $\Lambda$ or not!
- 415
3
votes
1
answer
102
views
iO from Matrix Branching Programs
Recently I'm learning about constructing iO from Matrix Branching Programs via Multi-linear Maps (to be exact, [GGH+13] and [GGH15]). However, I have a small question that I couldn't figure out.
It ...
- 77
1
vote
1
answer
107
views
Solving modular matrix equations via Gaussian elimination or System of linear equations (SIS assumption?)
Suppose $S \in \mathbb{Z}_q^{m \times m}$, and the norm of $S$ is less than an upper-bound $\beta$.
Additionally, $A_1, \cdots, A_k, C_1, \cdots, C_k \in \mathbb{Z}_q^{m \times n}$.
Here, $k \geq m>...
- 103
3
votes
0
answers
57
views
It is possible to prove this in zero knowledge?
Let $\mathcal{R}_q = \mathbb{Z}_q/\langle x^n + 1 \rangle$, with $n$ a power of $2$. Suppose that we sample $\mathbf{r} \leftarrow \mathcal{R}_q^m$ uniformly at random with the property that $0 < ||...
- 712
4
votes
0
answers
78
views
LWR parameter estimation
I am trying to estimate parameters for LWR $(n,q,p)$ instance using the LWE estimator. My $q,p$ are $283,256$-bit prime numbers and I am trying to find required $n$ for 128 bit security.
For this, I ...
- 139
1
vote
0
answers
59
views
Proof for, Vectors sampled from $D_{(L,r)}$ have Euclidean norm at most $r\sqrt{n}$ with a high probability
For any $n$-dimensional lattice $L$ and $r > 0$, a point sampled from $D_{L,r}$ has Euclidean norm at most $r\sqrt{n}$ except with probability at most $2^{-2n}$ (where $r$ refers to the standard ...
- 11
2
votes
2
answers
97
views
LWE versus neural nets
It seems like that the construction of the LWE problem: $As + e = b$ resembles how neural nets work: $Ax + b = y$.
In LWE, we are given the problem instance $A$, and the product with errors $b$ and ...
- 77
1
vote
0
answers
93
views
Which are the most Promising Post-quantum Public Crypto Primitives in the Face of a Quantum Apocalypse?
I'm fairly new to the fundamentals of post-quantum cryptography. So, please forgive me for such a direct question. Searching Google opened up a whole lot of amazing ideas that are thought to be ...
- 978
2
votes
0
answers
41
views
Probability that length of shortest nonzero vector is less than a number
Let $\Lambda\subset \mathbb{Z}^n$ be an $n-$ dimensional lattice with determinant $d$. We know that the probability that a uniformly random integer vector $x$ is a point in $\Lambda$ is given by $\...
0
votes
1
answer
119
views
Why do we add error in the definition of LWE?
One of the various equivalent definitions of the LWE problem is the following:
Let $n,q$ be integers ($q$ usually is a prime number), $\chi$ a discrete probability distribution over $\mathbb{Z}$ (...
- 712
3
votes
0
answers
103
views
Why ideal lattices?
An ideal lattice is a lattice $\mathcal{L}(A)$ generated by a block matrix
$A = \left[ A^{(1)} \mid \dots \mid A^{(m/n)} \right]$ whose blocks $A^{(i)}$ are constructed from a vector $a^{(i)}$ and a ...
- 712
2
votes
0
answers
69
views
How to construct a set in which the elements in $\mathbb{Z}[x]/(x^n+1)$ and their differences are invertible and with coefficients in $\{-1,0,1\}$?
I know that in IACR - Better Zero-Knowledge Proofs for Lattice Encryption
and Their Application to Group Signatures it constructs such a challenge set: {$ x^i $}. But the inverse of the difference of ...
- 777
1
vote
0
answers
44
views
Key-Privacy in Postquantum Public-key Encryption
is there any post-quantum public-key encryption that achieves "key-privacy" (IK-CPA, IK-CCA) as described in this paper?
I saw one code-based public-key encryption construction, but I wonder if ...
- 403
0
votes
0
answers
73
views
Hash chain based secret revealing using homorphic princples?
I have recently been looking into Homomorphic encryption and I am looking for a specific hash-based encryption/decryption scheme.
I don't need a full implementation but I am not sure if what I want ...
- 135
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 ...
- 315
1
vote
0
answers
43
views
Forging a new secret key in RLWE
In a RLWE setting where you are given a secret key $s$ and an associated public key $pk = (p_0,p_1) = (-(p_1s+e),p_1)$, is it possible/easy to forge a new secret key $s'$ such that $p_0+p_1s'$ has a ...
- 11
1
vote
0
answers
28
views
Ring (or Ideal) version of Boyen's signature
Boyen's signature is a well-known post quantum digital signature scheme. It's a lattice based scheme that uses a trapdoor of the lattice $\Lambda^{\perp}(A)$ and it's security is based in the SIVP ...
- 113
1
vote
1
answer
57
views
Reduction of decison SIS
In Lyu12, Lemma 3.6 is as follows.
Lemma 3.6 For any non-negative integer $\alpha$ such that $gcd(2\alpha+1, q)=1$, there is a polynomial time reduction from the $SIS_{q, n, m, d}$ decsion ...
- 321
0
votes
1
answer
71
views
Canonical inclusion map in subfield attack on overstretched NTRU
I'm trying to understand subfield attacks on overstretched NTRU. In the paper https://eprint.iacr.org/2016/127.pdf authors used "canonical inclusion map" to lift vector to full lattice. What does ...
- 123
1
vote
1
answer
125
views
Hard random lattices
The content I ask in this question is in the following picture in [GPV08][1]. I do not understand the proof of the first claim in $\bf Lemma$ 5.2. In the proof, which reprensents the uniform ...
- 321
2
votes
1
answer
132
views
Random lattices
The content I ask in this question is in the following picture in GPV08. I do not understand the sentence
computing the syndrome $\bf{Ae} \mod q$ for some $\bf{e} \in \mathbb{Z}^{m}$ is equivalent ...
- 321
1
vote
1
answer
323
views
Average case problem and worst case problem in lattice
In Regev's lecture there is "In contrast, virtually all other cryptographic constructions are based on some average-case assumptions.
For example, in cryptographic constructions based on factoring, ...
- 321
3
votes
1
answer
140
views
Hardware Gaussian random numbers for lattice-based cryptography
I have been recently reading about lattice-based cryptography.
I read that a key aspect of such protocols rely on added Gaussian noise on lattices, and which therefore require highly efficient and ...
- 33
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}...
- 1,005
2
votes
1
answer
108
views
average-case SIS and average-case BDD
In lattice based cryptography, we say the average-case SIS (short integer solution) problem because it is such kind problem
" $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{...
- 321
2
votes
1
answer
213
views
SVP=SIVP in ring lattice (ideal lattice)
SVP (shortest vector problem) is equivalent to SIVP (shortest independent vectors problem) in ring lattice (ideal lattice). How to prove this? Could someone explain it to me? Thanks!
- 321
1
vote
1
answer
893
views
Coppersmith's method for small public exponent
Can Coppersmith's method be used to break RSA when we only have access to public key and one ciphertext?
For e.g. suppose we have N and ciphertext c both are 1024-bit numbers and the public exponent e ...
- 113
3
votes
0
answers
104
views
parameter choosing for SIS based scheme in lattice based cryptography
In SIS based scheme, there is a matrix $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}$, and $n$ is the security parameter. I want to ask that why $n=1$ is also okay for the scheme (in "A ...
- 321
0
votes
0
answers
203
views
domain of Ajtai hash function
I know that when the domain is $\{0, 1\}^{m}$ in function $h(x)=Ax$ for $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}$, this function is called Ajtai hash function. So when the domain is ...
- 321
4
votes
1
answer
89
views
Is Type I lattice trapdoor hard to find even given oracle access to compute inverse of trapdoor function?
Consider the Type I lattice trapdoor in [GPV08]: https://eprint.iacr.org/2007/432.pdf
Suppose a PPT adversary is given the LWE trapdoor function in the picture:
$g_{A^\top} (s,e) = A^\top s + e = b (...
- 43
0
votes
1
answer
82
views
How to have a bound (upper or lower) of Gaussion distribution over lattice based crypto>
In lattice-based crypto, we always need to sample 'noise' from Gaussian distribution, but how to measure the bound the noise? For example, if the Gaussian distribution is D_{u,\sigma}, where u is the ...
- 343
0
votes
1
answer
115
views
security parameter in lattice cryptography
In paper Lattice Signatures Without Trapdoors(Lyubashevsky2012), $n$ is the security parameter, why the authors set $n$ as 512 but not 80/100/112 to get 80-bit security/100-bit/112-bit security?
- 321
0
votes
1
answer
370
views
Learning with rounding (LWR)
This may be a naive question:
LWR assumption states that for ${A} \stackrel{$}{\leftarrow} \mathbb{Z}^{m \times n}_q, s \stackrel{$}{\leftarrow} \mathbb{Z}^n_q$, given $(A, \lfloor A\cdot s \rfloor_p$...
- 139
3
votes
0
answers
210
views
Block size of BKZ algorithm and related security of CRYSTALS-Kyber
Security of lattice-based schemes in the NIST Posto-Quantum Project often relies on the complexity of dual attack. Complexity of this attack depends on the running time of lattice basis reduction ...
- 167
1
vote
2
answers
162
views
set of integers modulo an integer q in lattice
Some literature about lattices set $\mathbb{Z}_{q}$ in $[-\frac{q}{2}, \frac{q}{2})\cap \mathbb{Z}$ but not $[0,q-1]$ such as "lattice signatures without trapdoors" and "lattice based blind ...
- 321
3
votes
1
answer
1k
views
How to find the inverse of a polynomial in NTRU-PKCS
I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key ...
1
vote
1
answer
142
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, ...
user4936
1
vote
1
answer
86
views
How decode works in CCA1 scheme based on MP12 construction?
In Section 6.3 from MP12 we have that $encode(m) = Sm$, for $S$ any basis of $\Lambda(G^t)$. Then I have:
$S = \begin{pmatrix}
1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256\...
