Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
544
questions
0
votes
1
answer
83
views
LWE: does using only a small subspace of the plaintext space influence the security of the encryption scheme?
Regarding LWE schemes where the encryption is performed this way:
for $m \in \mathbb{Z}_t$, compute $c = LWE_{\mathbf{s}}^{t/q}(m) = \{ \mathbf{a}, \mathbf{a \cdot s} + m\cdot q/t + e\} \in \mathbb{Z}...
- 408
9
votes
0
answers
173
views
Differences between “NewHope” and “NewHope-simple”
The well-known paper described a key exchange (KE) scheme named "NewHope" on USENIX 2016. The authors then proposed "NewHope-Simple" - a PKE/KEM scheme. They also submitted "NewHope for NIST" - ...
- 177
3
votes
1
answer
658
views
trapdoor commitment from lattice-based assumptions?
I'm wondering that is there any equivocal commitment scheme (i.e., trapdoor commitment) can be constructed from lattice-based assumptions? I know there are a lot of commitment schemes from lattices as ...
- 932
1
vote
1
answer
337
views
What is the security model of the FHE system introduced in Fully Homomorphic Encryption Using Ideal Lattices?
How would one construct a security model to play against the adversary, and define the security of the overall scheme? This is in reference to the scheme introduced in "Fully Homomorphic Encryption ...
- 93
4
votes
1
answer
226
views
BGV KeyGen-- Can a maliciously-generated secret-shared key break security (e.g. SPDZ)?
I was (re)reading the paper "Practical Covertly Secure MPC for Dishonest Majority–or: Breaking the SPDZ Limits".
One of the key points in this paper is that they present a covertly secure BGV key ...
- 663
3
votes
0
answers
364
views
Comparison of NTRU-based schemes and LWE-based schemes
What advantages and disadvantages can be distinguished in NTRU-based and LWE-based schemes relative to each other? In what cases which scheme gives advantage?
UPD: I'm interesting in two things: 1)...
- 123
10
votes
2
answers
1k
views
Concrete evidence for the asymptotics of $\lambda_1(\Lambda^\perp(A))$?
A recent eprint paper claims to bound $\lambda_1(\Lambda^\perp(\mathbf{A}))$ for $\mathbf{A}\in\mathbb{Z}^{n\times m}$, a uniformly random matrix, by $O(1)$, specifically by $4$. This has applications ...
- 11.6k
0
votes
1
answer
166
views
Refreshing Procedure in FHEW: membership test
I am facing an issue regarding the paper FHEW: Bootstrapping Homomorphic Encryption in less than a second. It concerns the MSBextract algorithm during the refresh procedure.
Especially, they ...
- 408
7
votes
0
answers
385
views
Does there exist trapdoor permutation from lattices?
It seems that the lattice functions are either surjective (SIS) or injective (LWE), due to the error that is basically intended to destroy the structure and provide security. I was wondering whether ...
user4936
2
votes
1
answer
187
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 ...
- 969
3
votes
0
answers
60
views
Hardness or negligibility of finding small non-trivial addition coefficients for random values to sum to zero
In my cryptographic scheme, I would like to rely on the hardness or negligibility of the following problem or situation, respectively. Note the original motivation: it shall be impossible to find two ...
- 181
8
votes
1
answer
1k
views
Are LPN and LWE problems equivalent?
Learning with Error (LWE) problem seems like a generalization of Learning Parity with Noise (LPN) problem, where in the latter one uses bits. But, this also makes LPN seem very related to the problem ...
user4936
3
votes
1
answer
55
views
Solutions to $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ with $|x_i| < \ell$
Are there any clear conditions on $p,\ell$ and $m$ under which the equation $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ has at most one solution with $|x_i|<\ell$ with high probability over ...
- 3,922
2
votes
0
answers
86
views
Size of reduced bases of orthogonal lattice
I consider the following setting. Let $L$ be a lattice of rank $d$ in $\mathbb{Z}^m$ ($d\leq m$). The orthogonal lattice of $L$, denoted by $L^{\perp}$, is defined as the intersection of the ...
- 41
1
vote
1
answer
350
views
Rejection Sampling reasoning for Lattice Based Signatures
I'm new to lattices.
According to Lattice Signatures and Bimodal Gaussians in the Rejection Sampling section.
In Schnorr, GQ you can simply commit to $y$, use it to hide a secret key $s$.
But this ...
- 395
3
votes
2
answers
364
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 ...
- 93
4
votes
1
answer
205
views
Minimum distance between polynomials in ring-LWE
Let $R_q=\mathbb{Z}_q[x]/\langle f(x)\rangle$ where $f(x)=x^n+1$, as in the ring-LWE problem.
Let $a(x)$ be chosen uniformly at random from $R_q$.
Question: Is there any theorem that lower bounds ...
- 486
3
votes
0
answers
157
views
In Lattice Cryptography, why is it hard to find short vectors if given long vectors?
In lattice cryptography it seems like giving out long vectors for a lattice that can be drawn from much shorter vectors (generating an identical lattice) is somehow useful for public-private key ...
- 73
-4
votes
1
answer
134
views
hello i am a junior coder and programmer . what are the first step towards learning the beauty and function's of data science [closed]
"I really enjoy and would like to learn about cryptography. How and where to start? what programs did you first use, and support teams? I am learning lots of things which I should include in my ...
- 109
5
votes
1
answer
194
views
Hash and sign via trapdoors for lattices
Both the papers GPV'08 and MP'11 present trapdoors for lattices that allow to recover $s\in\mathbb{Z}_q^n$ and the error vector $e\in\mathbb{Z}_q^m$ when given $y=As+e$, for $A\in\mathbb{Z}_q^{m\times ...
- 486
4
votes
1
answer
313
views
Adapting LWE Trapdoors for Ring-LWE
In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio and Peikert, they present the following theorem about the existence of trapdoor for LWE.
Theorem 5.1: There is an ...
- 486
0
votes
1
answer
526
views
Regarding Lattice atttacks on ECDSA with a portion of known bits of the nonce k
I am new in the field of cryptography, and I am having some troubles understanding a concept regarding the lattice dimension needed in the attack on ECDSA using several messages with L known bits of ...
17
votes
2
answers
2k
views
Why is Approximate GCD a hard problem?
There are many Fully Homomorphic Encryption over the Integers schemes whose security is based on the intractability of the Approximate GCD (AGCD) problem.
The paper Algorithms for the Approximate ...
- 428
7
votes
1
answer
275
views
IND-CCA2 post-quantum key exchange
QUIC requires that servers reuse keys so that session resumption works. That breaks many post-quantum key exchange systems.
I am looking for a post-quantum key exchange algorithm with the following ...
- 4,763
1
vote
1
answer
200
views
How does forking lemma work in regard to Digital signatures produced by GPV hash and sign algorithm based on lattices?
I am working on understanding the concepts and approach behind digital signatures that are based on lattices specifically the GPV algorithm.
During the security reduction of this method, the forking ...
- 113
2
votes
1
answer
266
views
Original NTRU : How to calculate the size of private key?
In the original NTRU paper：NTRU: A Ring-Based Public Key Cryptosystem,1996, the author proposes 3 choices of implementation parameters: moderate, high and highest. Let's take moderate security level ...
- 177
1
vote
1
answer
84
views
Counting the number of binary solutions of quadratic system
I have a quadratic system of equations related to a balanced RSA modulus $n=pq$ (i.e. $\log p\approx\log q$), and I want to give an upper bound on the number of solutions. Indeed, let $p_i,q_i$ be ...
- 524
1
vote
0
answers
55
views
Extending the basis
Suppose I have $A \in \mathbb{Z}_q^{n \times m},A_1 \in \mathbb{Z}_q^{n \times m},A_2 \in \mathbb{Z}_q^{n \times m}$. I am following the $\textbf{ExtBasis}$ algorithm of this (Page No. 13). I ...
- 394
3
votes
1
answer
693
views
Encoding of the message in Regev encryption
In public key encryption from LWE, we do the following steps
$\textbf{PKE.KeyGen($1^n$)}$ takes as input the security parameter n, samples $A \leftarrow \mathbb{Z}_p^{n \times m}$ and $\textbf{e} \...
- 394
3
votes
1
answer
178
views
Cryptanalysis on affine like matrix based strange cryptographic scheme [closed]
This is a garage made encryption scheme provided as cryptanalysis practice during 34C3 CTF.
The challenge is done under the following assumptions
All Mersenne twister instances are MT19937 64bit ...
- 139
14
votes
1
answer
2k
views
Is lattice-based cryptography practical?
How viable is lattice-based cryptography in a "practical" setting?
It has been said that lattice-based cryptography would be a "post-quantum" cryptography scheme, but is it feasibly implementable?
- 313
2
votes
0
answers
185
views
SampleLeft function in lattice trapdoors
We have SampleLeft function in lattice trapdoors as
Algorithm $\textbf{SampleLeft}(A,M_1,T_A,u,\sigma)$:
$\textbf{Input}$: a rank $n$ matrix $A$ in $\mathbb{Z}^{n×m}_q$ and a matrix $M_1$ in $\...
- 394
2
votes
1
answer
166
views
A query on Learning with errors(LWE) problem
In generating an LWE sample, we do
$s\xleftarrow{$}\mathbb{Z}_q^{n}, A \xleftarrow{$}\mathbb{Z}_q^{n \times m}~$and $e\xleftarrow{$}\mathbb{{\chi}^{m}}$
Then we compute $b^T$ = $s^TA$ + $e^T$ and ...
- 394
2
votes
2
answers
314
views
Lattice generation from basis?
This might be a very short very obvious answer, because I've yet to come across a question similar to mine in my searches.
Given a lattice L, with a good base B1 and a bad base B2, what stops an ...
- 347
1
vote
1
answer
186
views
Can i use Babai algorithm in q-ary lattice
Let's assume we have the q-ary lattice
$$ \mathcal{L}_q({\bf A})=\{ {\bf z}\in \mathbb{Z}^{n} : \exists {\bf s}\in \mathbb{Z}^{n}_{q} \ , \ {\bf z}={\bf A s}^{T} \mod q \},$$
where ${\bf A}\in \...
- 61
1
vote
0
answers
162
views
Effitiently sampling the error (noise) distribution in ring-LWE
In LPR12, page 4 is described a ring-LWE encryption in which we are working in a ring $R = \mathbb{Z}[x]/(x^n + 1)$ for a $n$ a power of 2. The public key is of the form $(a, b= a\cdot s + e)$ where $...
- 133
0
votes
0
answers
78
views
Discrete Gaussian Sampling in Authenticated key exchange from ideal lattices
I am implementing the key exchange scheme proposed by zhang et al. on Sage. In the implementation of the scheme, they have used the two distributions $\chi_{\alpha}, \chi_{\beta}$.
How to choose $\...
- 187
4
votes
1
answer
427
views
Decision-LWE to Search-LWE
Regev requires $q$ to be prime on lemma 4.2 of his paper for LWE.
Why does he require that and how this effect the proof of lemma 4.2?
- 61
8
votes
1
answer
1k
views
Discrete Gaussian Sampling role in Lattice-Based Crypto?
I'm reading up on how post-quantum cryptography works, and stumbled upon the notion of discrete Gaussian sampling. However, I can't understand where it fits in the greater picture - currently it feels ...
- 347
3
votes
1
answer
189
views
determinant of intersection of two lattices
Say $L_1,L_2$ are contained in $\mathbb Z^r$ with
\begin{gather*}
\operatorname{rank}(L_1) = \operatorname{rank}(L_2) = r, \\
\gcd(\det(L_1), \det(L_2)) = 1.
\end{gather*}
How do I prove $\...
- 29
3
votes
0
answers
93
views
Size of $q$ in reductions from lattice problems to R-SIS
The Short integer solution problem is parameterized by four values:
$n$, the dimension of the vectors that must be added
$m$, the number of samples (dimension of the solution)
$\beta$, upper-bound ...
6
votes
1
answer
718
views
Hardness of Short Interger Solution in Lattices
Short Integer Solution ($SIS_{n,m,q,\beta}$) is defined as:
Given a matrix $A \in \mathbb{Z}_{q}^{n \times m}$, find a non-zero vector $x \in \mathbb{Z}^{m}$ such that $A \cdot x = 0\mod q$ and $||x|| ...
- 889
2
votes
1
answer
58
views
Dividing elements in $R_q$ by $z$ in Grag-Gentry-Halevi (GGH) Graded Encoding Scheme
I'm trying to understand the GGH graded encoding scheme, but something there leaves me very confused and I can not figure out how to explain it:
Let $R := \mathbb{Z}[X]/(X^n+1)$, where $n$ is a power ...
- 23
3
votes
1
answer
1k
views
Breaking Truncated Linear Congruential Generator with known parameters
There is an elaborate discussion on the breaking of TLCG on the link below, where they show how to break the generator with known parameters given the most significant bits.
Problem with LLL reduction ...
- 31
1
vote
1
answer
172
views
Function families from lattices
On this course, Micciancio talks about function families (functions parametrized by some value) that can be used in cryptography.
On page 2, he presents the following function family parametrized by ...
3
votes
1
answer
245
views
Effect of tail cutting and precision of discrete Gaussian sampling on LWE / Ring-LWE security
How does tail cutting and precision of discrete Gaussian sampling implementations affect LWE / Ring-LWE security? Is there a rule of thumb or guideline for choosing the tail cut and the precision for ...
- 436
4
votes
1
answer
303
views
Is there any course video for lattice cryptography? [closed]
Recently, I started doing research about Lattice Based Cryptography. and searched on YouTube a lot of public talks or seminars about it.
But is there any course video (graduated course) related to ...
- 43
2
votes
1
answer
298
views
Is it secure using LWE-based cryptosystem under RLWE-based parameters?
I'm computer guy having trouble with cryptography.
I recently read the BGV Homomorphic encryption paper which was constructed under both LWE and RLWE assumptions.
I was implementing Threshold ...
- 509
1
vote
1
answer
77
views
Practical Key exchange for Internet
In section 3.2 (page 10) of Vikram Singh's paper A practical Key Exchange for the internet using Lattice Cryptography, he gives the number of elements in each set for odd $q$. However, the results do ...
- 187
2
votes
1
answer
105
views
Why do the game-hops in Kyber and related papers contain 2 steps at a time?
In the Kyber paper in section 3 about the Kyber IND-CPA Encryption there is a proof by sequence of games containing three games. I understand that in the first game hop the M-LWE advantage is used to ...
- 346