Stack Exchange Network

Stack Exchange network consists of 174 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

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

1
vote
1answer
31 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
18 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
39 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} \...
2
votes
1answer
95 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
83 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 ...
7
votes
1answer
455 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
29 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
76 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 ...
0
votes
0answers
31 views

Multi-party Key Exchange protocol from lattice

There are many two-party or three-party key exchange protocols from lattice. But, it seems that there is no famous multi-party key exchange protocol. Does anyone know the relevant knowledge? Or ...
2
votes
2answers
67 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
44 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 \...
0
votes
0answers
46 views

About practical implementation of Ring-SIS/LWE Based Signature and IBE

In paper: Practical Implementation of Ring-SIS/LWE Based Signature and IBE, authors provided the source code for IBE. In the Extract algorithm, they said: $a \cdot x = u \bmod p$ but I can not ...
1
vote
0answers
28 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
40 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
79 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?
2
votes
1answer
99 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
26 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 $\...
2
votes
0answers
18 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 ...
4
votes
1answer
86 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|| ...
2
votes
1answer
29 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 ...
2
votes
1answer
174 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 ...
1
vote
1answer
57 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
1answer
65 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 ...
3
votes
1answer
109 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 ...
1
vote
1answer
47 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 ...
0
votes
0answers
45 views

Lattice Reduction Method to solve multivariate equation

I have seen very small work in multivariate RSA polynomial modular equation solutions using Coppersmith's based lattice reduction algorithm (LLL). Is there any mechanism to solve the following type ...
1
vote
1answer
53 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 ...
0
votes
0answers
69 views

Lattice cryptography, key size of public and private key?

An answer to this question what are the NTRU keysize and application in industry? mentions that lattice cryptography has public keys and private keys of the same size. That seems like a property that ...
1
vote
0answers
29 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 ...
4
votes
0answers
31 views

Relation between k-th shortest vector of a lattice and (n-k+1)-th shortest of its dual

Let $\Lambda$ be an $n$-dimensional lattice and $\Lambda^*$ be its dual lattice. For any $k \in \{1, 2, ..., n\}$, let $\lambda_k(\Lambda)$ be the $k$-th successive minima of $\Lambda$ (analogously ...
3
votes
0answers
48 views

How does error distribution affect security in lattices?

It's easy to see that the crucial part of any lattice scheme is the added error. And different schemes seem to use different error distributions, some use Gaussian some use centered Binomial. Though, ...
-1
votes
2answers
88 views

A good book on lattices [closed]

I have recently started studying lattices. The book that I am following is "Complexity of lattice problem by Shafi Goldwasser and Daniele micciancio" but it is too much inclined towards computational ...
1
vote
0answers
55 views

Hardness of $SIS$ and its reduction to an NP-complete problem

Short Integer Solution ($ SIS_\gamma^{(q,n,m,\beta)}$): Given a matrix $A\in Z_{q}^{n×m}$, find $x \in Z^m $, such that $Ax=0\mod q$ and $||x|| \le \beta$ Is $SIS\in NP$ ? If $SIS \in NP$, then it ...
3
votes
1answer
143 views

Minkowski's theorem in lattice-based cryptography

I am studying basic lattice-based cryptography. In the course given by O. Regev, on page number 7, there is Claim 1 and Corollary 2 (Minkowski's First Theorem), both of which are difficult for me to ...
4
votes
1answer
120 views

Lattice-based cryptography prone to side channel attacks?

Are Lattice-based cryptography still prone to side channel attacks? What are some mitigration strategies, if any.
-1
votes
2answers
336 views

Lattice-based cryptosystems for blockchain/ledger?

Are there lattice-based cryptosystems based i.e., SIS (Short Integer Solutions) and LWE (Learning with Errors) blockchain solutions for a post quantum world? Has the Unique Shortest Vector Problem (...
0
votes
0answers
26 views

XORing bitstrings to get small hamming weight using lattice SVP algo

I have a list of bit vectors of same length, and I want to find the combination of them which bitwise-XOR sum have the smallest (non-zero) hamming weight (or just a "rather small" hamming weight). ...
2
votes
0answers
54 views

Lattices with hidden short vectors and an algorithm for a special case of the SVP

For the purpose of testing algorithms for lattice basis reduction or finding short vectors, it would be useful to have examples of lattices where short vectors are hidden, that is, a nontrivial ...
8
votes
0answers
221 views

Potential Flaws With Lattice Based Cryptography?

From researching post-quantum cryptographic schemes it seems hash-based and lattice-based algorithms are the most promising (MQ-based seem to be covered by patents and have more potential unknowns ...
4
votes
1answer
181 views

What is the difference between Module-LWE and Ring-LWE?

Recently, the CRYSTALS lattice-based cryptographic suite has been published, which is based on "module lattices". What is Module-LWE? How is it different from Ring-LWE?
0
votes
0answers
61 views

Is there a connection between lattice based cryptography and random walk on a lattice?

What is the connection between lattice based cryptograph and random walk?
3
votes
1answer
70 views

Why don't we use an Extendable Output Function to efficiently store the public key of Regev's LWE-based encryption scheme over standard lattices?

In LWE-based schemes the public key is generated by choosing a random matrix (or polynomial) $A$, and outputting the pair $(A, b = A\cdot s + e)$, where $s$ and $e$ are vectors/polynomials with ...
3
votes
1answer
126 views

Parameters for ring-LWE

I see on eprint that there are many papers suggesting ways to compute parameters for LWE. How can those be used to compute parameters for ring-LWE (assuming that known algorithms solving LWE are the ...
0
votes
1answer
185 views

One doubt on an NP hard problem

It seems that Shortest Vector Problem in a lattice is NP hard. Then how Ajtai-Kumar-Sivakumar (AKS) algorithm solves it? I mean, what is the witness?
1
vote
0answers
42 views

What is the minimal angle between two LLL reduced vectors?

What is the minimal angle between two LLL reduced vectors? It seems it should be 60 degree as $|\mu_{i,j}| \leq \frac{1}{2}$. If we make the upper bound of $\mu_{i,j}$ by 1/3, can we get better ...
0
votes
0answers
38 views

Average-case hardness of computational diffie-hellman problem

One of the main advantages of lattice-based cryptography is security is based on worst-case hardness i.e., construction based on lattice problem implies if we break the construction, then any instance ...
6
votes
0answers
48 views

Decision R-LWE parameters for spherical error with worst-case hardness

In Peikert et al.'s most recent work (STOC 2017) a direct reduction of worst-case lattice problems to decision R-LWE is achieved for $\alpha q \ge 2 \cdot \omega(1)$ (Theorem 6.2), where $\alpha q$ is ...
-2
votes
1answer
210 views

Advantages of Lattice-based cryptography over elliptic curve cryptography

The two main advantages of lattice-based cryptography are resistance against quantum attacks Cryptosystems constructed using lattice are worst-case hardness. Are there are other advantages of ...
3
votes
0answers
155 views

ring-LWE: Minkowski Embedding , the Co-Different Ideal, etc

While (trying) to go over the reductions from approx. SVP on ideal lattices to search ring-LWE, [1] and [2], for $K = \mathbb{Q}(\zeta)$ where $\zeta$ is an abstract root of a cyclotomic polynomial, ...
1
vote
0answers
146 views

Short integer solution lattice problem with q=2

For large values of $q$, we know that there are worst-case lattice problems which reduce to the average-case short integer solution (SIS) problem. Does this means that for $q=2$, the SIS problem is ...