Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
521
questions
4
votes
1
answer
120
views
Trying to implement the algorithm in Wikipedia regarding key exchange
I am trying to understand the reconciliation technique mentioned in Wikipedia page for Ring-LWE key exchange.
Basically, if we intentionally choose x, y (or the coefficients of calculated shared key ...
- 312
5
votes
1
answer
207
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 ...
- 312
3
votes
1
answer
95
views
Why is a bit biased when generated from random $v \in Z_q$ for odd q?
I am not understanding the following from "Lattice Cryptography for the Internet" by C. Peikert (pages 10, 11):
When $q$ is odd, while it is possible to use the above methods to
agree on a bit ...
- 312
6
votes
1
answer
410
views
Trying to implement ring-LWE KE to understand the concept
Today, after reading so much about ring-LWE key exchange, I decided to implement it in java to see if it works. Not a real world implementation, just to see if math works out. My assumption was that ...
- 312
7
votes
1
answer
480
views
Irreducible polynomial in Ring-LWE
In Ring-LWE polynomials are chosen from the ring $R_q=\mathbb{Z}_q[x]/(x^n+1)$, where $n$ is a power of two.
As far as I understand, to create a ring the polynomial $x^n+1$ has to be irreducible (see ...
- 1,255
31
votes
1
answer
2k
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 ...
- 589
2
votes
1
answer
336
views
Why standard deviation of BLISS is so high?
In lattice based digital signature scheme BLISS why the standard deviation is so high (215) compared to the encryption schemes?
- 1,255
1
vote
1
answer
85
views
Dimension of secret key vector tensor with itself?
In the algorithm FHE.KeyGen on page 18 of BGV, the dimension of the secret key $\textbf{s}_j$ is $n_j+1$. Why would the dimension of the long secret key $\textbf{s}_j' \leftarrow \textbf{s}_j \otimes \...
- 85
10
votes
2
answers
2k
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 \...
- 879
2
votes
1
answer
130
views
Choosing between different Gaussian Sampling algorithms?
Is the gaussian sampling described in the original paper (https://eprint.iacr.org/2013/383.pdf) faster (samples/sec) than the Knuth Yao sampling.
As far as I know KY sampler is the fastest discrete ...
- 1,255
5
votes
1
answer
241
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$. ...
- 85
5
votes
0
answers
3k
views
How babai nearest plane algorithm solves approximate CVP
Babai's nearest plane algorithm solves approximate-CVP (Closest Vector Problem) where the approximation factor is $2(\frac{2}{\sqrt{3}})^n$.
Let $b_1,...,b_n$ be a basis and $t$ be the target. This ...
- 879
2
votes
1
answer
535
views
Bit decomposing a polynomial in BGV cryptosystem
I'm having trouble with the BitDecomp subroutine on page 9 of the BGV cryptosystem. I'm focusing on the RLWE instantiation so $R_q = \mathbb{Z}[x]/(x^d+1,q)$. I can't see how BitDecomp works for a ...
- 85
2
votes
1
answer
1k
views
GSW Homomorphic Encryption
In GSW homomorphic encryption scheme proposed here. The integers are over $Z_q$ where $q$ is a modulus parameter of the scheme. It is not clearly mentioned in paper if the ordinary representation of $...
- 315
2
votes
1
answer
401
views
Why the basis is reduced in nearest plane algorithm in solving CVP
In Babai nearest plane algorithm(solve approximate version of CVP), given the basis as input first step is to find the reduced basis(using LLL reduction algorithm). Why the reduced basis is used for ...
- 879
0
votes
2
answers
315
views
The length of the shortest vector in Lattice
In Micciancio and Regev's paper "Lattice-based Cryptography",the length of the shortest vector is at least $\min\{q, 2^{2\cdot\sqrt{(n\cdot \log{q}\cdot\log{\delta}})}\}$ . I want to ask why the paper ...
- 51
2
votes
2
answers
230
views
How would low-precision Gaussian sampling impact the security of BLISS?
For digital signature, I implemented BLISS in my cryptographic suite, and wrote the Gaussian sampler based on Lattice Signatures and Bimodal Gaussians. But unlike the reference implementation and ...
- 8,648
0
votes
1
answer
51
views
Decomposing an ideal in intersections
Let $R$ be an ring, and let $(a),(b)$ be the ideals generated by $a,b\in R$ respectively. Let $c=a\cdot b$ and $(c)$ the ideal generated by $c$.
I am supposing that, given $c$, it is computationally ...
- 524
5
votes
2
answers
352
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 ...
user27950
3
votes
0
answers
235
views
In NTRU, if $N$ is not prime, prove that one can recover the private key by solving a lattice problem in dimension lower than $2N$
In the NTRU cryptosystem, it is suggested to take $N$ prime.
I want to understand why.
In Jeffrey Hoffstein, Jill Pipher and H. Silverman An Introduction to Mathematical Cryptography, they suggest (...
- 325
2
votes
1
answer
61
views
ZK proof that two short solutions are equal
Let $A_1$ and $A_2$ two $m \times n$ matrices defining SIS problems.
Does there exist a zero knowledge proof that two short solutions are the same, i.e.
$$y_1 = A_1 x $$
$$y_2= A_2 x $$
$$ \Vert x \...
user27950
3
votes
0
answers
84
views
Construct new SIS solutions from given ones
Assume we have a lattice SIS problem
$A x = 0$, with $\Vert x \Vert < \beta$ and we are given $k$ solutions $x_1, \dots, x_k$ by, say an oracle.
Is it then hard or easy to construct from there a ...
user27950
8
votes
2
answers
225
views
Cardinality of the group of units in a cyclotomic ring?
In the NTRU key generation, one samples a polynomial from $K = (\mathbb Z/q\mathbb Z)[X]/(X^n+1)$ and tests if it is invertible. What are the chances of this to happen? In other words:
Let $q$ be a ...
- 524
3
votes
1
answer
609
views
Find an example of a lattice such that LLL algorithm can't find the shortest vector of the lattice, satisfying
I want to find an example of a basis of a lattice of dimension $n$ such that LLL algorithm can't find the shortest vector of the lattice, and such that the shortest vector of this lattice, say $b=...
- 325
19
votes
1
answer
964
views
Quantum complexity of LWE
As per my understanding, LWE is quantum secure because there is no known quantum algorithm to solve LWE in polynomial time. Due to the reductions given by Regev et al., if there is any algorithm that ...
- 1,255
3
votes
1
answer
281
views
proof of correctness Ring-LWE cryptosystem
I've been studying Ring-LWE based crytposystems such as the one in this paper, but I can't seem to find/come up with a proof of correctness for this particular scheme.
The encryption goes as follows:
...
- 31
6
votes
1
answer
1k
views
What is the most efficient attack on NTRU?
So, I got how finding the private key is equivalent to resolving the SVP. I also understood that the LLL algorithm can only be used in small dimensions. Now, I wonder what is the most efficient attack ...
- 61
4
votes
0
answers
235
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 ...
- 243
9
votes
1
answer
148
views
Collisions in the cyclotomic knapsack function
I've been working my way through the paper “Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices” by Peikert and Rosen, and I've come across something that doesn't seem ...
- 193
1
vote
1
answer
103
views
Use $e$ in GGH as shared secret?
I was wondering if we could construct a symmetric encryption scheme by assuming that the secret key itself in GGH is public and the shared "key" is the error vector $e$.
To encrypt we would take the ...
- 215
11
votes
1
answer
3k
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 ...
- 111
7
votes
1
answer
790
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 ...
- 73
2
votes
1
answer
301
views
Practical lattice based signatures and key exchange with strong security reduction
I am looking for practical lattice-based signatures and key exchange with strong security reductions.
Specifically:
Provable security under the relevant standard assumptions.
Fast in software while ...
- 4,763
8
votes
3
answers
2k
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 ...
- 312
4
votes
1
answer
278
views
Would LWE problem be still secure if error were like this $e=2e_1$?
In the Learning with error problem, if the error term $e$ from equation $b=<a,s>/q+e$ were of this kind $e=2e_1$, where $e_1$ is chosen according to the probability distribution for the LWE ...
- 681
1
vote
2
answers
536
views
Gaussian function in lattices
Probability density function of gaussian distribution is
$$ 1/{\sqrt{2 \pi} \sigma} \times {e^{{(x-c)^2/ 2{\sigma}^2 }}} $$
in lattices we assume $$ \sigma =s/\sqrt{2 \pi} $$so the gaussian ...
- 879
1
vote
1
answer
225
views
Use of orthogonal vectors in lattice-based cryptography
In lattice-based cryptography, given the basis of the lattice we compute the orthogonal vectors using Gram-Schmidt Orthogonalization process. What is the use of orthogonal vectors in lattices?
- 879
2
votes
1
answer
604
views
finding the basis of a kernel in a lattice
Given a parity check matrix $A$ we define the $q$-ary lattice
$$\Lambda(A) = \{x \in \mathbb Z^m\;:\;Ax\equiv0\pmod q\}$$
How to find the basis of the lattice and how to find its hermite normal form?
- 879
9
votes
1
answer
1k
views
Gaussian distribution in lattices
In many lattice based cryptosystems, Gaussian distribution is used. Can you explain why only Gaussian distribution is preferred?
- 879
3
votes
1
answer
766
views
Faster discrete Gaussian sampling
Our goal is find a faster discrete Gaussian sampling to solve $"SVP"$ problem in lattice:
A lattice is discrete subgroup of $R^n$ such that define as below:
let $\{b_1,\cdots ,b_n\}$ be a basis in $...
- 141
2
votes
2
answers
443
views
Is secure lattice based cryptography in future?
Lattice cryptography is a post quantum cryptography that work on two NP-hard problem in below:
Find shortest nonzero vector from origin and
Find minimum distance of a arbitrary point out of lattice ...
- 141
3
votes
1
answer
1k
views
Lattice based attack on RSA
Let $n=pq$ be the RSA module and at least one of $p,q$ is a weak prime.It is proved that the number of such $1024$bit $n$ is at least $2^{759}$. With lattices we can factor these $n$ in a second (I ...
- 2,323
11
votes
0
answers
652
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 ...
- 477
7
votes
1
answer
342
views
Lattice attacks against Multilinear Maps [CLT13]
I am currently studying an article on a construction of Multilinear maps. There are some attacks on the scheme presented by the authors and I got stuck at the one in section 5.1.
I will try to ...
- 636
4
votes
2
answers
460
views
How to compare performances of lattice-based and pairing-based IBE schemes
I try to compare the performances (cost of Enc, Dec, ... size of keys, ciphertexts, ...) of IBE schemes using lattices (LWE hardness assumption) or pairing (Diffie-Hellman hardness assumption).
I've ...
- 131
5
votes
2
answers
1k
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 ...
- 643
10
votes
1
answer
1k
views
Use of q-ary lattices in developing cryptosystems
Why q-ary lattices are used to most cryptosystems rather than lattices.
In most of the papers q-ary lattices are used. Is there any advantage?
and
Given $$B=(v_1,v_2,v_3,.....v_n)$$ is the basis, ...
- 879
4
votes
1
answer
212
views
apprSVP in lattices
The approximate Shortest Vector Problem (apprSVP) is a problem where, given the basis and the approximation factor $\gamma$ (a function of the dimension $n$), one must find a vector $v$ belonging to ...
- 879
2
votes
2
answers
290
views
What kind of operations are involved in NTRU?
I've read that lattice based algorithms involve matrix-vector products. Is this the case of the NTRU algorithm?
When I've read the details of the NTRU algorithm, I've seen products of polynoms. Where ...
- 2,827
4
votes
0
answers
253
views
Worst case to average case in Ring LWE
I am currently trying to understand this Ring LWE article and I have a question. I don't understand how to apply Lemma 5.11 in order to get the worst case to average case reduction in Lemma 5.12, as ...
- 41