Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

Questions tagged [lattice-crypto]

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

Filter by
Sorted by
Tagged with
3 votes
0 answers
85 views
+50

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 ...
Joe's user avatar
  • 81
1 vote
0 answers
66 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 ...
Gappu's user avatar
  • 31
8 votes
2 answers
593 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 ...
swineone's user avatar
  • 870
2 votes
0 answers
95 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\...
Sam Jaques's user avatar
  • 1,192
0 votes
0 answers
49 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 ...
Cred Mao's user avatar
0 votes
0 answers
192 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.
guangyu liao's user avatar
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 ...
Hilder Vitor Lima Pereira's user avatar
1 vote
1 answer
111 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 ...
PAMG's user avatar
  • 161
2 votes
2 answers
101 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}_{\...
the thinker's user avatar
2 votes
1 answer
51 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 ...
the thinker's user avatar
0 votes
2 answers
41 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 \...
user avatar
2 votes
1 answer
81 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, ...
nnolte's user avatar
  • 121
0 votes
1 answer
45 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 ...
the thinker's user avatar
3 votes
1 answer
132 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 ...
VIKAS SRIVASTAVA's user avatar
0 votes
1 answer
48 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 ...
Solaris's user avatar
2 votes
1 answer
44 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 ...
Sharon's user avatar
  • 23
1 vote
1 answer
101 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. ...
TreeBook1's user avatar
  • 117
3 votes
1 answer
77 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 ...
Jong Hyeok Lee's user avatar
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 ...
kodlu's user avatar
  • 22.6k
0 votes
1 answer
47 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 ...
R_Jalaei's user avatar
  • 141
2 votes
1 answer
46 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 ...
opag's user avatar
  • 63
3 votes
2 answers
101 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 ?
constantine's user avatar
1 vote
1 answer
160 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 ...
Random Bits's user avatar
2 votes
1 answer
77 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,...
user1035648's user avatar
2 votes
1 answer
148 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 V. Right now I'm using the ...
Valéry Giscard d'Estaing's user avatar
3 votes
2 answers
141 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 ...
lstk44's user avatar
  • 73
2 votes
2 answers
186 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 ...
ABCD's user avatar
  • 23
1 vote
1 answer
72 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 ...
Herbrant's user avatar
1 vote
1 answer
113 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, ...
user1035648's user avatar
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 ...
Alexander Ushakov's user avatar
2 votes
0 answers
50 views

What's the lattice dimension of the uSVP for attacking CRYSTALS-Dilithium-128?

I am trying to understand the process of transitioning from a NIST standard to the attacks based on of the Unique Shortest Vector Problem (Unique-SVP). Specifically, I am working with Crystals ...
asdf's user avatar
  • 324
2 votes
1 answer
188 views

Do we know that LWE is harder than Ring LWE?

The plain, normal-form, decisional LWE problem over $\mathbb{Z}/q\mathbb{Z}$ is: given a uniformly random $n\times n$ matrix $A$ and vector $b\in \mathbb{Z}/q\mathbb{Z}^n$, decide if $b=As+e$ for ...
Sam Jaques's user avatar
  • 1,192
1 vote
2 answers
134 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-...
user1035648's user avatar
2 votes
1 answer
95 views

Arithmetic in Cyclotomic Number Rings with Shoup's Number Theory Library (NTL)

I wish to do arithmetic on elements in an integer subring of a cyclotomic number field, i.e, in $\mathcal{O}_K = \mathbb{Z}(\zeta) \cong \mathbb{Z}[X] / <\phi_m(x)>$ where $\zeta$ is a root of ...
Rohit Khera's user avatar
1 vote
0 answers
94 views

Understanding Gentry's initial FHE construction based on ideal lattices

I am trying to understand the encryption procedure in Craig Gentry's initial construction for FHE described in Fully Homomorphic Encryption Using Ideal Lattices. Unfortunately after repeated attempts ...
Parham's user avatar
  • 111
6 votes
1 answer
303 views

NTRU Cryptosystem: Why "rotated" coefficients of key f work the same as f

In the NTRU cryptosystem, we can use a randomly generated polynomial f that is inversible under modulo p and q to encrypt and decrypt our plaintext. While studying this system, I attempted to ...
Ymi's user avatar
  • 175
1 vote
0 answers
59 views

Where do we put known bits of nonce when performing lattice attack on ECDSA?

I have read so many papers and posts about lattice attacks on ECDSA but none of them used an example of different MSB values for k but instead they all used fixed MSB. So here i am trying to ...
diviserbyzero's user avatar
0 votes
0 answers
52 views

Is BGV encryption using different secret keys indistinguishable?

Assume that the same message is encrypted using two different keys within the BGV encryption scheme. Can we assume that the resulting ciphertext are indistinguishable? I.e., given $c_1 = \text{Enc}(...
js wang's user avatar
  • 327
0 votes
0 answers
17 views

[error reducing techinique in lattice based commitment]

I am aware there are many techniques to reduce the error of lattice-based homomorphic encryption. But is there any technique to deal with lattice-based homomorphic commitment, e.g., More Efficient ...
js wang's user avatar
  • 327
1 vote
1 answer
132 views

Is there an efficient way to check if a lattice has a point with all non-zero components?

Given a basis $\{v_1,\dots,v_k\}$ for a $q$-ary lattice $L$ in ${\mathbb Z}_q^n$, is there an efficient (deterministic/randomized) way to find a point in $L$ with all non-zero components, or decide ...
LatticePoint's user avatar
1 vote
1 answer
146 views

True Lovàsz condition and definition of a LLL-reduced basis

I am studying the Shortest Vector Problem and I have some troubles understanding the actual Lovàsz condition used in the LLL algorithm. On the one hand, the original LLL article, the Springer book &...
Hurb27110582's user avatar
3 votes
1 answer
120 views

Differences between the theory and implementation of a lattice attack against ECDSA

I know the theory of lattice attacks against ECDSA from Minerva. So, as far as I can understand, the lattice that they build is $$ L_M = \begin{bmatrix} 2^ln & 0 & 0 & \cdots & 0 & ...
Hurb27110582's user avatar
0 votes
0 answers
37 views

Non-lattice NIST candidates affected by SVP problems

I would like to know if there are non-lattice based NIST submissions that are affected by a polynomial time algorithm to Shortest Vector Problem. Are there known reduction from (e.g.) code based ...
asdf's user avatar
  • 324
1 vote
1 answer
75 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 ...
js wang's user avatar
  • 327
1 vote
0 answers
36 views

Is there a many-to-one reduction from GapSVP to GapCVP?

I was wondering if by now any poly-time Karp reduction between GapSVP and GapCVP (exact or approximate) exist. I know of the Cook reduction between these problems, but I couldn't find anything about ...
kerf's user avatar
  • 33
0 votes
0 answers
56 views

[About choosing params in BGV like ciphertexts]

I am new to lattice-based cryptography, so sorry that this question might seems stupid May I ask that how can I choose the BGV parameter of ciphertext with plain text in mod 128, and error in ...
js wang's user avatar
  • 327
1 vote
0 answers
91 views

Estimating BKZ block size in Kyber

In Section 5.2.1 of the Kyber documentation, it states that the BKZ block size of 413 was chosen using the tool from this paper, i.e., this tool. How was the block size derived from this? Currently, ...
Sam Jaques's user avatar
  • 1,192
0 votes
0 answers
48 views

Approximate-GCD problem in polynomials

I am trying to understand the two main hard problems that have been explored in the context of homomorphic encryption: Learning with Errors Problem (LWE) and the Approximate-GCD (AGCD) problem. I have ...
Anisha's user avatar
  • 11
1 vote
1 answer
75 views

How to set the variance of LWE when using the lwe estimator

based crypto And I would like to use the lwe estimator to calculate bound for ring LWE Found in this issue It seems to me I can set up parameters like params = LWE.Parameters(n=2^14, q=2^438, Xs = ...
js wang's user avatar
  • 327
1 vote
2 answers
137 views

About multiply by constant of LWE

I am new to lattice-based cryptography May I ask that for a lattice-based encryption $$enc(m) = A^{T}R+m \bmod q$$ If I set the $q$ to be able to decrypt to $m$ (and suppose the bound of $q$ is tight ...
js wang's user avatar
  • 327

1
2 3 4 5
12