Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [lattice-crypto]

Lattice-cryptography is the study and use of lattice problems applied to cryptography.

2
votes
1answer
63 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 ...
1
vote
0answers
27 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 ...
2
votes
0answers
33 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-...
2
votes
1answer
43 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}$ ...
3
votes
0answers
48 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, ...
1
vote
0answers
35 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\...
0
votes
1answer
48 views

How does the 'Flatten' function reduce the coefficients of a vector/matrix?

Seen here, at the bottom of page 5, Flatten() is defined as: Flatten(a)=BitDecomp(BitDecomp$^1$(a)) For an n-dimensional vector a$=(a_{1,0},...,a_{1,l-1},...,a_{k,0},...,a_{k,l-1})$. Where $a_{i,j}$ ...
1
vote
1answer
40 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 \...
4
votes
0answers
50 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 $(-\...
0
votes
1answer
76 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 ...
0
votes
1answer
39 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}...
7
votes
0answers
83 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" - ...
2
votes
1answer
60 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 ...
1
vote
1answer
51 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 ...
3
votes
1answer
57 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 ...
2
votes
0answers
84 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)...
10
votes
2answers
867 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 ...
0
votes
1answer
75 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 ...
5
votes
0answers
79 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 ...
0
votes
1answer
50 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 ...
3
votes
0answers
49 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 ...
6
votes
1answer
93 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 ...
3
votes
1answer
48 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 ...
2
votes
0answers
44 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 ...
1
vote
1answer
71 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 ...
3
votes
2answers
129 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 ...
4
votes
1answer
121 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 ...
2
votes
0answers
76 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 ...
4
votes
1answer
68 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 ...
3
votes
1answer
101 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 ...
0
votes
1answer
89 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 ...
7
votes
1answer
282 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 ...
5
votes
0answers
70 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 ...
1
vote
1answer
57 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 ...
2
votes
1answer
78 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 ...
1
vote
1answer
50 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 ...
1
vote
0answers
25 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 ...
3
votes
1answer
86 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} \...
3
votes
1answer
148 views

LLL - Lattice Reduced Basis Algorithm question?

I have two related questions: Version 1: Let $B=\{b_1,b_2,\dots,b_n\}$ be an orthogonal basis for $R^n$. What is the associated reduced basis obtained by applying LLL algorithm to $B$? I know how ...
3
votes
1answer
104 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 ...
9
votes
1answer
739 views

Lattice-based cryptography

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?
2
votes
0answers
48 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 $\...
2
votes
1answer
106 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 ...
2
votes
2answers
102 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 ...
1
vote
1answer
65 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 \...
1
vote
0answers
66 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 $...
0
votes
0answers
62 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 $\...
4
votes
1answer
112 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?
4
votes
1answer
226 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 ...
2
votes
0answers
31 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 $\...