Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
495
questions
2
votes
1
answer
187
views
The error distribution in LWE
$\textbf{Continuous LWE}$ : $(\overrightarrow{a}, b)\in \mathbb{Z}_q^n\times \mathbb{T}$, where $\mathbb{T}=\mathbb{R}/\mathbb{Z}$, $b = \langle \overrightarrow{a},\overrightarrow{s}\rangle/q + e\mod ...
- 499
2
votes
0
answers
122
views
Howgrave-Graham lattice attack on NTRU
I am lookin for a good example to illustrate this attack on NTRU using low parameters but I failed to do that, The attack consist to use LLL reduction on A basis of NTRU Lattice, let us use the column ...
- 396
1
vote
1
answer
63
views
Euclidean norms do not need full rank lattices
There is a sentence in Micciancio's Lattice lectures that says when we bound the minimum distance of a lattice using the convex body theorem for norms other than the Euclidean norm we need to assume ...
- 259
4
votes
1
answer
88
views
Is NTRU still hard if $G$ is set to 1?
I'm looking at the description of NTRUEncrypt given on page 21 of http://archive.dimacs.rutgers.edu/Workshops/Post-Quantum/Slides/Silverman.pdf and using its notation. So in NTRU there are always two ...
- 143
4
votes
0
answers
278
views
Which parts of CRYSTALS-Kyber and CRYSTALS-Dilithium are compatible?
The papers CRYSTALS-Kyber and CRYSTALS-Dilithium both have been written by quite different authors. It seems that at least the key generation is very different from each other. CRYSTALS mainly seems ...
- 90.2k
1
vote
1
answer
179
views
Why does orthogonal basises makes it easier to solve SVP in lattices?
I've been looking through https://courses.maths.ox.ac.uk/node/view_material/12662 and it mentions that:
Some bases make SVP easier:
A “good” basis has shorter vector norms
A “good” basis has nearly ...
- 13
2
votes
0
answers
69
views
The Primal and Dual attack security estimates in Kyber round 3 specification
In Kyber round 3 specification, the table 4 gave the security estimates of Primal and Dual attack with respect to Kyber 512, 768 and 1024 (see the figure below). However, using the python script given ...
- 171
5
votes
0
answers
157
views
How did Kyber's authors compute the error probability $\delta$?
I'm studying the specification of Kyber that was submitted to NIST PQC Round 3. However, I cannot figure out how they compute the error probability $\delta$ for Kyber 512, 768 and 1024. I have read ...
- 171
1
vote
1
answer
210
views
Security of the Goldreich–Goldwasser– Halevi (GGH) Scheme
There is a statement in the article of "Public-Key Cryptosystems from Lattice Reduction Problems" that presents GGH encryption scheme:
"The cryptanalytic problem underlying our scheme ...
- 500
3
votes
0
answers
160
views
Is there a source(book, thesis, paper) that explains Lattice basis reduction algorithms (LLL, HKZ) and provides an in depth analysis of the same?
I want to give a slight background about me: I've Bachelors in Computer Engineering and I've been interested in Cryptography since my college days and have been following the field ever since. I'm ...
- 151
2
votes
1
answer
64
views
Choosing rings for PLWE
In [ELOS15], the authors give an attack on RLWE, and claim that "the hardness of Ring-LWE is...
dependent on special properties of the number field" chosen; whereas, responding to prior ...
- 381
0
votes
0
answers
58
views
Gram-Schmidt upper triangular basis
I'm trying to understand the Gram-Schmidt Orthogonalization process. Below, there is an explanation that a lattice basis can be described by an upper triangular vector.
It is often convenient to ...
- 33
1
vote
0
answers
329
views
Is the error distribution in Learning with Errors (LWE), the discrete Gaussian distribution?
In $\mathbb{Z}$, the discrete Gaussian distribution is defined as $D_{Z,s}(x) = \frac{\rho_s(x)}{\rho_s(\mathbb{Z})}, x\in \mathbb{Z}$.
In LWE, $(\overrightarrow{a}, b = \langle \overrightarrow{a}, \...
- 499
1
vote
1
answer
148
views
Error Correcting Codes Post Quantum Finalists
I have been looking into error-correcting codes in lattice, I am specifically hoping to find some information on hardware implementations for the NIST PQ PKE/KEM finalists (Saber, CRYSTALS-Kyber, NTRU)...
- 51
3
votes
0
answers
133
views
Coppersmith attack on NTRU and non-commutativity
In this paper, Coppersmith and Shamir used lattice reduction to attack NTRU. At the very end of the paper, they note that developing non-commutative variants of NTRU would be wise, in light of their ...
- 381
4
votes
3
answers
1k
views
Why do Problems for Post-Quantum algorithms have to be NP-Hard?
The mathematical problems used for Post-Quantum Cryptography problems I came across, are NP-complete, e.g.
Solving quadratic equations over finite fields
short lattice vectors and close lattice ...
- 277
1
vote
1
answer
96
views
Is the discretization of the Guassian distribution on torus still a discrete Gaussian distribution?
Let $\rho_s(x) = e^{-\pi x^2/s^2}$ be the Gaussian measures, then the discrete Gaussian distribution on $\mathbb{Z}$ could be defined as $D_{\mathbb{Z},s}(x) = \rho_s(x)/\sum_{n\in \mathbb{Z}}\rho_s(n)...
- 499
2
votes
1
answer
84
views
Error Check in Lattice PQC
I am by no means an expert in the PQC field and am just trying to self teach myself about it. I was hoping to look into error correcting in lattice. I want learn about error or fault detection as it ...
- 51
2
votes
1
answer
270
views
How is R-LWE related to lattice cryptography and homomorphic encryption?
Can someone tie everything together for me? I'm interested in H.E and I have some background in AES, DES, RSA and the like. While reading around I stumbled on Shai Halevi's course on lattice ...
1
vote
0
answers
92
views
References on lattice-based cryptography [duplicate]
I need earlier references (books, articles, etc) on lattice-based cryptography, and any advice will be helpful to me. I am reading Stinson & Paterson's Cryptography: theory and practice. Thanks in ...
- 396
1
vote
1
answer
300
views
SVP algorithms and complexity
I took image from Simons Institute's presentation. Complexity classes of Approximate SVP problem according to approximation factors are given in the table. My question is, What is the meaning of blue ...
- 500
2
votes
1
answer
301
views
Worst-Case hardness of lattice problems
I just started work on lattice-based cryptography and I could not understand the concept of worst-case to average-case reduction.
We generally say,
Average Case Hardness: Random instance of a problem ...
- 500
0
votes
0
answers
84
views
Software package to create a basis of the q-ary lattice $\Lambda_q(A)$
Consider a matrix $A \in \mathbb{Z}_q^{m \times n}$ and its respective lattice
$$\Lambda_q(A) = \{x \in \mathbb{Z}^m : \exists z \in \mathbb{Z}_q^n, x = Az \mod q\}$$
The basis for such a lattice is ...
- 347
2
votes
1
answer
97
views
A function $H(x)$ is given. If there is an algorithm $B(H(x))$ that get part of $x$, is $H(x)$ a one-way function?
I came up with this question while I was reading this paper: Pilaram, Hossein, and Taraneh Eghlidos. "An efficient lattice based multi-stage secret sharing scheme." IEEE Transactions on ...
- 31
0
votes
1
answer
47
views
Trapdoor committement using ring lattices involving three parties
Assume there are three parties say A, B, C.
A commits to a message $m$ say $c(m)$ and sends tuple $(m,c(m))$ to B.
B has to prove to C that he possesses commitment $c(m)$. There is no interaction ...
3
votes
1
answer
831
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 ...
- 33
2
votes
0
answers
45
views
Why could the error term be sampled coefficient wise?
In SEAL homomorphic encryption library, it implements the BFV and CKKS. We know the error $e\in R_q$ which is a Guassian distribution. When sampling an error term $e = \sum_{i=0}^{n-1} e_ix^i$, it ...
- 499
0
votes
0
answers
64
views
Lattice based cryptography: How do negative coefficients in $Z_q[x]/(X^n+1)$ work? [duplicate]
I saw that in lattice-based cryptography schemes, for example Dilithium, coefficients in $Z_q$ are allowed to be negative. For example, in Dilithium the secret key is $s_1 \in R_q^{k \times l}$, where ...
- 347
2
votes
0
answers
93
views
How does the rejection sampling lemma work in the proof of HVZK?
In this protocol,
Q1: how does the commitment work? What if the prover sends $\textbf{t}$ directly, and then sends $s_m,s_r,s_{\textbf{e}}$?
Q2: How does the rejection sampling lemma work?
refer to ...
- 499
7
votes
2
answers
680
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 ...
- 1,096
4
votes
1
answer
290
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.
...
- 237
2
votes
0
answers
113
views
Why should the smudge noise be used?
Consider a threshold FHE scheme based on RLWE like this:
Refer to this paper
$\textbf{Initialization:}$
Every party generates his own secret key $s_i$, then uses the common polynomial $a$ to generate ...
- 499
4
votes
1
answer
222
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 ...
- 1,096
2
votes
1
answer
135
views
Computational LWE-Trapdoor without tag
In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller, Micciancio and Peikert mention that it is possible to save an additive $n$ term in the dimension $\bar{m}$ in paragraph $\...
- 23
0
votes
0
answers
79
views
Why is the proof on the commitment correct?
In the paper "Efficient Zero-Knowledge Proofs for Commitments from Learning with Errors over Rings", they gave a commitment from Ring-LWE: to commit to a polynomial $m$ in $Rq(Zq[x]/(x^n+1))$...
- 499
0
votes
0
answers
54
views
GSW and homomorphic addition on integers
Is it possible to use the GSW scheme (Gentry, Sahai, Waters) also on integer values and not just single bits? If not, are there any schemes that support integer arithmetic with the same nice property ...
- 1
0
votes
0
answers
64
views
GSW13 scheme and integer arithmetic
I'm new to lattice-based cryptography and have trouble understanding if the GSW13 (Gentry, Sahai, Waters) scheme works only on single bits. But is it also possible to encrypt integers with this scheme ...
- 1
1
vote
1
answer
94
views
Algebraic Variants of NTRU
There are a large number of algebraic NTRU variants: for example, in some (such as ETRU), the underlying ring has been changed to the ring of integers of a certain number field; there is GR-NTRU, ...
- 381
2
votes
1
answer
202
views
Significance of parameter q in NTRU lattice attack
In NTRU (N,p,q,d), N is usually chosen to be prime and q be a power of 2. Why is it that if I increase the parameter q, the probability of finding a key or spurious key that can decrypt the message is ...
- 237
1
vote
0
answers
66
views
Attacks on LWE when q is a power of 2
I am working on an LWE instance where q is a power of 2 and I'm wondering if there is any literature about attacks in this context, especially if there are any attacks which work significantly better. ...
- 63
0
votes
0
answers
114
views
Short Integer Solution Problem with ||z||<=B
Why following constraints on $||z||$ are required
$||z||<=B, B<q$
1
vote
3
answers
828
views
I need a pathway for studying Lattice-Based Cryptography
I realize that I need a study pathway for post-quantum cryptography.
I started to study post-quantum crypto by reading NIST PQC 3rd-round submissions of the lattice-based schemes (let's start with the ...
- 113
3
votes
1
answer
503
views
The equivalence of SIS and ISIS(Inhomogeneous SIS)
I would like to know whether these two problems are equivalent or not, namely:
$SIS_\alpha$: Given $A \in \mathbb{Z}_q^{n\times m}$ find $ e \in \mathbb{Z}_q^{m}$ such that $ Ae = 0$ and and $\|e\| \...
- 33
1
vote
0
answers
39
views
How to prove to recipient that we are using public parameters correctly in lattice IBE
Many lattice IBE scheme follow the scheme outlined in ABB10.
In ABB10, the ciphertext is
$c_0 = u^\top s + x$, where $u$ is a public parameter. (No consider message here.)
I want to ask:
Is it ...
- 103
1
vote
0
answers
79
views
Solving RLWE modulo a prime ideal
Suppose you have the following set up for RLWE: $K$ is a cyclotomic field of degree $n$ over $\mathbb{Q}$, and $p\in\mathbb{Z}$ is a prime integer that splits as follows in $R = \mathcal{O}_K$: $p\...
- 381
3
votes
0
answers
151
views
How to use Rényi divergence for noise flooding
Let $\chi_\sigma$ be a discrete (or continuous) Gaussian distribution with standard deviation $\sigma$.
Then, it is known that for $y \in \mathbb{Z}$, a statistical distance between $\chi$ and $\chi + ...
- 149
3
votes
0
answers
88
views
Gram-Schmidt coefficients in LLL algorithm
To my understanding the LLL lattice reduction algorithm starts with a set of integer vectors $\{b_1, \dots, b_2\}$, which span a lattice, and tries to generate a new basis of shorter vectors of the ...
- 31
1
vote
0
answers
60
views
Artificial abort in Adaptively-secure Lattice IBE in [ABB10]
I have read the paper [ABB10] several times but I still cannot understand thoroughly the "artificial abort" in the security proof of the adaptively-secure IBE in the paper. So my questions ...
- 33
0
votes
1
answer
175
views
CKKS security estimation for Palisade
My question is rather practical and specific. I am trying to setup an efficient CKKS scheme in Palisade. To this end, the automatic choice for secure parameters has to be turned off and I rely on the ...
- 33
2
votes
1
answer
186
views
Rounding function used in Saber Key Exchange
In Saber: Module-LWR based key exchange, the authors use a rounding function called $\textit{bits}$, defined (in page 3) as follows:
$bits(x, i, j)$, with $j \leq i$, gives $j$ consecutive bits of a ...
- 381