Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
562
questions
0
votes
1
answer
41
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
42
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
86
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
70
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
44
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 ...
2
votes
1
answer
37
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 ...
3
votes
2
answers
91
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
82
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 ...
2
votes
1
answer
68
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,...
2
votes
1
answer
85
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 ...
3
votes
2
answers
119
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 ...
2
votes
2
answers
165
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
64
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 ...
1
vote
1
answer
97
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, ...
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 ...
2
votes
0
answers
47
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 ...
2
votes
1
answer
175
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 ...
1
vote
2
answers
113
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
1
answer
89
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 ...
1
vote
0
answers
87
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 ...
6
votes
1
answer
295
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 ...
1
vote
0
answers
47
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 ...
0
votes
0
answers
51
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}(...
0
votes
0
answers
16
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 ...
1
vote
1
answer
131
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 ...
1
vote
1
answer
139
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 &...
3
votes
1
answer
107
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 & ...
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 ...
1
vote
1
answer
58
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 ...
1
vote
0
answers
33
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 ...
0
votes
0
answers
50
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 ...
1
vote
0
answers
82
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, ...
0
votes
0
answers
42
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 ...
1
vote
1
answer
58
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 = ...
1
vote
2
answers
125
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 ...
2
votes
1
answer
87
views
in NTRU, can g be recovered given f and h?
The NTRU key generation involves polynomials and their arithmetic in polynomial rings, which is a bit different from arithmetic in modular integers.
In the NTRU cryptosystem, the public key $h$ is ...
0
votes
0
answers
41
views
question for lemma 4 of the BGV paper
I would like to ask a question that arose when reading the proof of lemma 4 on page 10 of this BGV paper:
The assumption is:
And the inequality:
So it seems that
$$ \sum_{j=1}^{n} \parallel c'[j]-(p/...
1
vote
0
answers
85
views
Can lattice attack work MSB or LSB are unkown but 16 bytes of private key are known?
I have been reading about lattice attack on ECDSA when partial bits of nonce are known for amount of signatures, So i went through some source code trying to understand how it works.
First of all, ...
8
votes
2
answers
2k
views
Is lattice encryption susceptible to Grover's algorithm?
So Grover's algorithm, also known as the quantum search algorithm, can find an entry, with a high probability, in an unstructured database.
Well can't we consider the basis of a lattice problem an ...
0
votes
0
answers
38
views
What are the implications for the proof when we substitute matrix multiplication with a bitwise XOR operation in Definition 5.1 (LWE degree-k PRF)?
In the paper located at https://eprint.iacr.org/2011/401.pdf, suppose we replace matrix multiplication with bitwise XOR operations in Definition 5.1 to create an LWE degree-k PRF. I'm seeking ...
1
vote
1
answer
100
views
Finding two inputs [i, j] of a custom Hash function where their Hashes are [H(i), H(j)] = [H(i), H(i)^2] [closed]
I came upon the following hash function (pseudo-code):
...
2
votes
1
answer
114
views
Computing the intersection of two lattices
Given two lattices $L_1$ and $L_2$ represented by bases $B_1$ and $B_2$, is there an efficient algorithm to compute $L_1\cap L_2$?
I can show, I think, that if $\gcd(\det(B_1),\det(B_2))=1$, then $...
0
votes
1
answer
96
views
Discrete Gaussian distribution on a lattice vs. the periodic Gaussian function on a lattice
Gaussian distribution on lattices generally seems esoteric (at least for me, for now). My question is:
Does Gaussian distribution on a lattice mean to add a Gaussian noise on a single point of a ...
0
votes
0
answers
69
views
Sagemath help: Introduction to Lattices
Hi im doing a problem from the Chapter Lightweight Introduction to Lattices in "Learning and Experiencing Cryptography with CrypTool and SageMath"
I'm curious if my implementation is wrong ...
1
vote
2
answers
56
views
[Questions about a proof in the prelim of paper "Lattice-Based Zero-Knowledge Proofs and Applications"]
May I ask that in section 2.7 challenge space in the paper Lattice-Based Zero-Knowledge Proofs and Applications:
Shorter, Simpler, and More General
What is rot(c), why does rot(c) $\in Z^{d*d}$, and ...
2
votes
1
answer
87
views
$\epsilon$ parameter choice in lattice-based schemes
I am trying to implement Pei10 and BB13, but I am confused about what concrete parameters to use.
In Pei10, Algorithm 1 takes a rounding parameter $r = \omega(\sqrt{\log n})$ as parameter, but it does ...
1
vote
0
answers
40
views
[About parameters effect LWE and SIS to be computation or perfect secure]
Hello I am new to lattice cryptography
I am reading the paper More Efficient Commitments from
Structured Lattice Assumptions
They define bound B in page 3
Then In figure 1 in page 9
Can ...
2
votes
1
answer
102
views
Question about the description from ring SIS to SIS in the survey paper: A Decade of Lattice Cryptography
I am currently reading "A Decade of Lattice Cryptography"
At page 30, section 4.3.2, it descrip left multiplication by any fixed ring element a
It mention something about curcilant matrix ...
3
votes
1
answer
209
views
Kyber-CCA-KEM - Deterministic implicit rejection
In Kyber-CCA-KEM, there's a step in the Fujisaki-Okamoto transformation, where decryption failure results in a random shared secret returned from the decapsulation call.
I have a C language project ...