# Questions tagged [lattice-crypto]

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

583 questions
Filter by
Sorted by
Tagged with
751 views

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 ...
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 ...
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 ...
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
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 ...
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
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 ...
102 views

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
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 ...
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 ...
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, ...
100 views

1 vote
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
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-...
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