Skip to main content

Questions tagged [lattice-crypto]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
751 views

What is the meaning for a vector mod a matrix in a lattice?

I'm reading about the lattice recently.In the paper, it gives a method of a vector mod a matrix: $\vec{c} \bmod B \quad \mathrm{as} \quad \vec{c} - \lfloor \vec{c} \times B^{-1} \rceil = \...
4 votes
1 answer
141 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 ...
1 vote
1 answer
39 views

Question of section 1.3 Intuition for Aborting in "Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures"

When I'm reading this paper "Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures" by Lyubashevsky. I have trouble understanding section 1.3 Intuition for Aborting....
3 votes
1 answer
87 views

Definition of Dual Lattice: $\vec{v}\in span_{\mathbb{R}}(\mathcal{L}(\mathbf{B}))$

Consider the definition of the dual lattice for a lattice $\mathcal{L}(\mathbf{B}_{m\times n})\in\mathbb{R}^{m}$ where $\mathbf{B}\in\mathbb{R}^{m\times n}$ and $n\leq m$ [sp2 Seminar, Luxembourg 2019,...
0 votes
1 answer
105 views

Difference between Decryption-failure and Plaintext-checking oracles

I am reading this paper, which in the introduction, tells about two main types of key recovery SCAs : Reaction_type SCAs, which uses a decryption failure oracle Message-recovery-type SCAs, which uses ...
1 vote
0 answers
38 views

How to choose the distribution of error and secret vectors in LWE-based KEMs

The general construction of a LWE-based PKE looks like the following: KeyGen : Secret vector, sk :$ s \leftarrow \chi_s^m$ Public Key, pk: ($A \leftarrow \mathbb{Z}_q^{m \times m}, t = As + e)$ where $...
2 votes
1 answer
195 views

Algorithm to solve SVP (shortest vector problem) using LLL reduction

I'm trying to write a C++ program to solve the shortest vector problem. The program is given a basis of a vector space $V$ and needs to find the shortest non-zero vector in the lattice generated by ...
2 votes
1 answer
267 views

Avoid CKKS Bootstraping

CKKS is a levelled scheme, because the rescale $\lfloor\frac{x}{\Delta}\rceil$ operation requires truncating a modulus to be efficiently evaluated, and rescale is (usually) needed after every ...
3 votes
1 answer
235 views

ISIS problem in the case of $m=n$

The Inhomogeneous Short Integer Solution (ISIS) problem is as follows: given an integer $q$, a matrix $A\in \mathbb{Z}^{n\times m}_q$, a vector $b\in \mathbb{Z}^{n}_q$, and a real $\beta$, find an ...
5 votes
1 answer
148 views

Shortest Vector Problem as Dihedral Hidden Subgroup Problem

I’m a mathematician trying to get into cryptography. I have a somewhat silly question, but I can’t seem to find a proper answer anywhere. I am interested in whether or not there is a way to directly ...
1 vote
0 answers
18 views

How to determine approximate factor (i.e. modulus-to-(bound of)noise ratio) of LWE in advaned primitives is sub-exponential or polynomial?

In advanced primitives like circuit (policy) ABE [BGG+'Eurocrypt2014] or IPFE [ACGU'Asiacrypt2020, appedix A] based on lattices, parameters setting is quite puzzling and vague (for me). (Parameter ...
0 votes
1 answer
96 views

Canonical inclusion map in subfield attack on overstretched NTRU

I'm trying to understand subfield attacks on overstretched NTRU. In the paper https://eprint.iacr.org/2016/127.pdf authors used "canonical inclusion map" to lift vector to full lattice. What does ...
1 vote
1 answer
51 views

Literature on Batching in FHE

From what I understand, the folklore way to batch Ring-LWE style cipher texts is to use the Chinese remainder theorem. I am wondering if there are any different approaches/optimizations to this style ...
2 votes
0 answers
102 views

Can this problem reduce to the SIS problem or LWE problem?

The description of the graceless problem is as below. Given a full rank square matrix $A=(R\cdot S+E)\in\mathbb{Z}_q^{n\times n}$,where: $q>2^\lambda$ is a prime; $R\leftarrow\mathbb{Z}_q^{n\times ...
0 votes
1 answer
55 views

Questions about SIS hard problem

The definition of $\mathrm{SIS}_{q,n,m,\beta}$ problem is as below. Let $A\in\mathbb{Z}_q^{n\times m}$ be an $n\times m$ matrix with entries in $\mathbb{Z}_q$ that consists of $m$ uniformly random ...
0 votes
1 answer
30 views

Gadget Matrix Ring Setting

What would be the analogue of the gadget matrix in the ring setting? Would it be the same matrix? Do the trapdoor algorithms work exactly the same way? Thanks
0 votes
2 answers
51 views

Instantiation of norm bound in SIS

Recall Short Integer Solution: $\textbf{SIS}_{n, q, \beta, m}$: Given $\textbf{A} \in \mathbb{Z}^{n\times m}_q$, $\vec{b} \in \mathbb{Z}^{n}$, find $\vec{z} \in \mathbb{Z}^{m}$ of norm $||z|| \le \...
5 votes
1 answer
100 views

Ring LWE distribution definitions

This may be a stupid question but I've been stuck on parsing these definitions for a while. I am reading the paper "On Ideal Lattices and Learning with Errors Over Rings" by Lyubashevsky, ...
1 vote
0 answers
89 views

Math of Hint usage in Dilithium

For Dilithium, I understand that $$\text{HighBits}(\mathbf{Ay}) = \text{HighBits}(\mathbf{Ay} - c\mathbf{s_2}) = \text{HighBits}(A_z - c\mathbf{t})$$ The first term of the equation is performed on the ...
9 votes
2 answers
617 views

Is NTRU broken?

Today a new paper appeared on ePrint, "Improved Provable Reduction of NTRU and Hypercubic Lattices". It claims that: this is the first provable result showing that breaking NTRU lattices ...
2 votes
1 answer
86 views

The necessity for lattice reduction in LWE

I am trying to understand how exactly lattice reduction and LWE are linked. The attacks on LWE I have seen all use lattice reduction in some way or another, dual attacks, uSVP type and so on. Naively, ...
2 votes
0 answers
100 views

Direct quantum reduction from GapSVP to SIS

Looking through Chen's recent paper, if we forget about complex Gaussians and just build uniform superpositions over hypercubes, we could create the state $$\sum_{v\in L}\vert v\rangle \sum_{y\in\...
62 votes
4 answers
11k views

Polynomial-time Quantum Algorithms for Lattice Problems

A new paper, by Yilei Chen, whose title is Quantum Algorithms for Lattice Problems (https://eprint.iacr.org/2024/555) appeared on eprint and it claims to solve hard lattice problems, such as the ...
3 votes
4 answers
931 views

Why Module-LWE and not Ring-LWE?

I am trying to understand the NIST-submissions for post-quantum cryptography a bit better, and I noticed that the submissions from the CRYSTALS-family in particular is based on Module-LWE. I ...
0 votes
0 answers
59 views

Reaching the bound of Boneh and Durfee Attack

According to the paper, theoretically,we can get $\delta=0.292 \lt 1-\frac{1}{\sqrt{2}}$,but how to set the lattice and implement it in sagemath? I generated some data by ...
0 votes
0 answers
194 views

Is the cryptography scheme over lattice still secure? [duplicate]

In https://eprint.iacr.org/2024/555, the author proposed a quantum algorithm to solve LWE problem. How serious is its impact on the existing scheme over lattice.
1 vote
1 answer
65 views

LWE Decryption: Generating errors for (c1, c2) that match binary message m

In the encryption process, the ciphertexts c1 and c2 are added to errors e1 and ...
1 vote
1 answer
113 views

Degree of inverse of f in NTRU?

In NTRU, we know that $f$ is a ternary polynomial in the ring $$R=\frac{\mathbb{Z}_q[x]}{x^n-1}.$$ Here $f$ has $d+1$ coefficients 1 and $d$ coefficients $-1$ and rest are zero. For computing the ...
2 votes
2 answers
102 views

Probabilistic proof of multiplying two elements from non-prime finite field

I was reading this paper, and there, they use the ring $\mathbb{Z}_{\large p}[\alpha]/(\alpha^{\large n}+1)$ for all their operations. And that looks like a construction of finite field $\mathbb{F}_{\...
1 vote
1 answer
79 views

Why the refresh (modulus and key switching) is required in BGV after addition?

I am reading the BGV paper. On page 18, after addition, the protocol will also refresh (modulus and key switching), may I ask why is this required? It seems to me that I can still use the same secret ...
2 votes
1 answer
52 views

How does linearity work with SWIFFT?

I read that SWIFFT is a linear hash function, but I don't understand what this means. The obvious interpretation is that if you have inputs $X1, X2$ each of which is an array of 16 64-dimensional ...
3 votes
1 answer
143 views

High Hamming Weight Attack on Kyber

I was reading LAC (https://eprint.iacr.org/2018/1009.pdf). They mention about high-hamming weight attacks on the Centered Binomial Distribution (CBD). To counter this, they propose CBD with fixed ...
1 vote
1 answer
69 views

Sigma parameter from Trapdoors for Lattices

In the document Trapdoors for Lattices, section 5.4 Gaussian Sampling, they introduce the parameter $\sqrt{\Sigma_{\bf G}}$, which is related to the lattice $\Lambda^\perp(\bf G)$. They use it as a ...
0 votes
1 answer
49 views

Finding security constraints for different input domains of Ajtai functions

I know that the normal construction for Ajtai hash functions is as follows: Pick $n, m, q \in \mathbb{Z}^+$ such that $n \log q < m < \frac{q}{2n^4}$ and $q = O(n^c)$ for some $c>0$, and some ...
2 votes
1 answer
54 views

Initial approximation in CKKS Bootstrapping

In this CKKS bootstrapping paper https://eprint.iacr.org/2018/153 the authors use a Taylor expansion to approximate the complex exponential function within a small range. More precisely, for the input ...
0 votes
1 answer
49 views

The proof of Claim 5.2 in the "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography"

When I'm reading this paper "On lattices, learning with errors, random linear codes, and cryptography" by O. Regev. I have trouble understanding the proof of claim 5.2. "Hence, it is ...
2 votes
1 answer
46 views

How to measure the denseness of Mod-LWR samples in some space?

I tried to understand how dense the Mod-LWR samples are in some space. I tried to see from a view similar to LWE, i.e. using GV-bound(maybe LPN is better example because GV-bound is for codes). But I ...
1 vote
1 answer
103 views

Ring-LWE lattice cryptography and FFT Trick for $X^n+1$

in reference here the FFT trick for $X^n+1$ is discussed with reference to the Number Theoretic transformation. On page 5, the Chinese Remainder Theorem is used to define the mapping. So far so good. ...
3 votes
1 answer
92 views

How to reconstruct low order bits of $t$ of CRYSTALS-Dilithium from a small number of signatures?

In FIPS 204 (https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.ipd.pdf): "The vector $\textbf{t}$ is compressed in the actual public key by dropping the $d$ least significant bits from each ...
15 votes
1 answer
1k views

Impact of Ryan and Heninger's CRYPTO 2023 paper on post quantum cryptosystems

From Schneier's blog, which seems to have been written in response to a somewhat recent Quanta magazine article: The winner of the Best Paper Award at CRYPTO this year (2023) was a significant ...
0 votes
1 answer
50 views

What does it mean the "Distinguisher" in LWE decision version?

As we know in block ciphers, the distinguisher means that despite thousands ciphertexts (and plaintexts), allows an attacker to distinguish the encrypted data from random data. This attack is ...
3 votes
2 answers
105 views

A Smudging Lemma in Lattice

I saw a paper LLW21 in EUROCRYPT 2021 that used this lemma, but there was no proof or references. How should this lemma be proved ?
1 vote
1 answer
126 views

Decision LWE vs Search LWE: Which one is harder?

Sometimes if we have an attacker who's able to solve decision-LWE problem then we can use them (as a sub-routine) to solve (search) LWE problem, i.e., $\mathsf{sLWE} \leq \mathsf{dLWE}$. Conversely, ...
3 votes
2 answers
151 views

Connection between (noisy) CVP and LWE

What's actually the difference between a (noisy) CVP and LWE? It seems to me that both are the same. With the definition of LWE: $$A * s + e = b$$ solving for secret vector s is the same than solving ...
1 vote
1 answer
205 views

Centred Binomial Distribution and its effects on security in Kyber

I want to concretely understand how exactly choice of error distribution effect the security of KEM in the context of Lattice Based Cryptography. For example, I would like to know the concrete ...
1 vote
2 answers
154 views

Definition of Dual Lattice

1- Can someone explain why we have the definition of dual of a lattice like $\Lambda^*=\{\vec{v}\in span(\textbf{B}): \langle \vec{v},\vec{x} \rangle \in \mathbb{Z}, \forall \vec{x} \in \Lambda\} $. 2-...
2 votes
2 answers
193 views

CRYSTALS-Kyber Compress and Decompress function role

I was reading CRYSTALS-Kyber design. They have used compress_q(x,d) to scale an element of $\mathbb{Z}_q$ to $[ 0,1,...,2^d-1 ]$. The definitions of ...
1 vote
1 answer
81 views

Do you know any library for implementing lattice-based schemes? [closed]

Good afternoon! I'm trying to write a code for a lattice based scheme (based on the SIS problem). I'm looking for a library that may help me in this task without taking care of the implementation of ...
0 votes
0 answers
125 views

Approximate SIVP worst-case hardness: proper mathematical formulation used for cryptographic purposes

Is the following a correct formulation for the assumed worst-case hardness of $SIVP_\gamma$? For every PPT algorithm $A$ for every $n\in\mathbb{N}$ there exists a basis $B_{n,A}=\{v_1,\dots,v_n\} \in ...
1 vote
1 answer
130 views

Matrix multiplication circuit

I am trying to understand which operations are computable by an $\texttt{NC}^1$ circuit. However, I am struggling to understand whether there is such a circuit for multiplying a matrix with a vector ...

1
2 3 4 5
12