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
1 vote
1 answer
49 views

Effect of multiplying message by $q/2$ LWE

I have recently started learning about the LWE problem, and I am wondering about how multiplying the message bit $\mu \in \mathbb{Z}_2$, affects the encoding of this message. The LWE-based ...
MathematicallyUnsound's user avatar
1 vote
0 answers
38 views

CRYSTALS-Kyber Central Binomial Distribution reference inplementation in c

In lines 8 to 10, why it does not get input bytes as it is (i.e., line 8)? It first does some changes (line 9 and 10). Do authors do this changes as we cannot work with binary form of a variable ...
user1035648's user avatar
2 votes
2 answers
32 views

Security of Ring-LWE and Module-LWE encryption scheme

Regev-05 encryption under plain LWE consists in using a public key $\mathsf{pk} = (\mathbf{A}, \mathbf{b} = \mathbf{A}^\top\mathbf{s}+\mathbf{e})$, where $\mathbf{A}\in \mathbb{Z}_q^{n\times m}$ is ...
vxek's user avatar
  • 509
2 votes
1 answer
56 views

Modulus in Lattice-Based Cryptography?

The common modulus methods are standard modulus (the result is confined to the range $[0, q-1]$) and centered modulus (the result is confined to the range $[- \lfloor q/2 \rfloor, \lceil q/2 \rceil)$)....
user109993's user avatar
2 votes
1 answer
33 views

Understanding Canonical-embedding vs Coefficient-embedding in Ideal Lattices: Relation to NTT?

I'm trying to understand the relationship between different representations of ideal lattices, particularly the canonical embedding and coefficient embedding. While studying these concepts, I noticed ...
a15600712's user avatar
4 votes
0 answers
75 views

What is a Lattice trapdoor?

In "A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors" , Brent Waters uses lattice trapdoors to build hidden bit generators. Can someone explain to me what a ...
Francesco Maria  Favuzza's user avatar
0 votes
2 answers
55 views

Can the message space for Ajtai Hash be extened?

I have a question regarding the Ajtai hash function. Typically, the message space for this function is the binary space $\{0, 1\}^m$. However, I am considering extending the message space to $\{-1,0, ...
user109993's user avatar
1 vote
1 answer
69 views

Is there an efficient algorithm to compute the inverse of a small-norm element in a special polynomial ring?

The paper "Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs" presents a corollary stating that in a polynomial ring $...
user109993's user avatar
0 votes
1 answer
37 views

Is $A \in \mathbb{Z}_q^{m \times m}$ is a one-way function?

In lattice-based Cryptography, Ajtai [1996] demonstrated the family of one-way functions. For a uniformly chosen matrix $A \in \mathbb{Z}_q^{n \times m}$ and $x \in \{0,1\}^m$, $A \cdot x \mod q$ is a ...
preethi's user avatar
  • 919
0 votes
0 answers
24 views

Proof of random-self-reucibility of LWE (worst- to average-case) in Regev paper, Lemma 4.1

I'm reading proof of [Regev'arXive2401.03703, lemma 4.1, page 30]. I can't figure out how Oded Regev estimates acceptance probability of the average-case distinguisher by Chernoff bound Thorem (...
user1035648's user avatar
6 votes
1 answer
125 views

Do the specific powers of two $2^{23}$ and $2^{13}$ in the modulus $q = 2^{23} - 2^{13} + 1 = 8380417$ have any special purpose in its design?

I recently started exploring Post-Quantum Cryptography, particularly Lattice-based Cryptography, and came across the modulus $q = 2^{23} - 2^{13} + 1 = 8380417$, which is used in schemes like ...
a15600712's user avatar
1 vote
0 answers
74 views

Why are matrix-secrets used on lattice based signatures?

I was wondering why in the Fiat-Shamir with aborts paradigm on lattices such Lyuba12, matrices S and E are used to generate the public key ($AS + E = B$ or $AS = B$). And not just vectors like on ...
t3st12's user avatar
  • 11
2 votes
1 answer
51 views

How does lattice reduction produce $s$ and $e$ from public parameters of an LWE instance?

It has been shown that by embedding $A$ and $t$ from an LWE instance $A$, $t=As+e$ inside a lattice, we can find a vector from the reduced lattice that contains $s$ and $e$. For example, in the ...
Xavier's user avatar
  • 91
2 votes
1 answer
52 views

How does the size of the parameter $n$ in $Kyber$ affect the success of lattice reduction of LWE instances?

I'm learning about using lattice reduction to find the secret $s$ of an LWE instance. When testing it on code, I have noticed that when $n$ is 32 or lower, I am able to retrieve $s$ successfully, but ...
Xavier's user avatar
  • 91
0 votes
1 answer
59 views

Why consider/formulate Shortest Vector Problem as a Promise Problem and not as a Decision Problem?

We know (search) approximate Shortest Vector Problem ($\mathsf{SVP}_{\gamma}$): Given an arbitrary basis $\mathbf{B}$ of some lattice $\mathcal{L}=\mathcal{L}(\mathbf{B})$, find a shortest non-zero ...
user1035648's user avatar
2 votes
2 answers
139 views

Is the variant of LWE-based encryption scheme secure?

Suppose that there exists a SIS instance generator $Gen_{SIS}(n,m-1,q)\to(A\in\mathbb{Z}^{n\times m}_q,s\in\{0,1\}^{m-1})$, where $(s,1)$ is the short integer solution for the SIS instance $A$, s.t. $...
X.H. Yue's user avatar
  • 456
2 votes
2 answers
184 views

How is it that a matrix of polynomials can be represented as a circulant matrix for purposes like lattice reduction?

When using lattice reduction on polynomial matrices, I have seen examples where a matrix can be represented as a circulant matrix before lattice reduction. Is there an explanation on why this works? ...
Xavier's user avatar
  • 91
2 votes
2 answers
103 views

Understanding LWE's Correctness Proof

In this paper, on page 33, we are presented with Claim 5.2 which is supposed to show that for the selected parameters in LWE, namely: $\alpha(n)=o(1/(\sqrt{n}\log ...
Alon .G.'s user avatar
3 votes
0 answers
84 views

Why RLWE is typically implemented using unsigned integers?

Every RLWE implementation I know uses unsigned integers even when it needs to represent signed values. Why?
Guerlando OCs's user avatar
3 votes
1 answer
101 views

Choosing $x^n+1$ as an irreducible polynomial in $\mathbb{Z}[x]$ instead of $x^n-1$ for ring $\mathbb{Z}[x]/\langle f(x)\rangle$ of Ring-LWE

In the note of ["Ring-SIS and Ideal Lattices by Noah Stephens-Davidowitz (for Vinod Vaikuntanathan’s class", footnote 3], it has written: 3 The ring $\mathbb{Z}[x]/(x^n + 1)$, ideal ...
user1035648's user avatar
2 votes
1 answer
61 views

I have the best basis possible for a lattice. How well can I solve CVP?

Let's suppose I've given a lattice $L$. I'm allowed to spend as much pre-computation as I want to produce a poly-sized advice string, and I use it to find the best basis possible for the lattice. Then ...
Sam Jaques's user avatar
  • 1,614
2 votes
1 answer
44 views

Why are only primal and dual attacks dealt with among the various attacks on LWE?

As we see in https://estimate-all-the-lwe-ntru-schemes.github.io/docs/, only dual and primal attacks are the most important attacks against LWE and NTRU schemes. On the other hand, many attacks such ...
R_Jalaei's user avatar
  • 161
2 votes
0 answers
35 views

When can radix-3 NTT faster than radix-2 NTT?

I am a beginner in Lattice based cryptography and now I am encountering some cryptography algorithms using NTT. And I am trying to change the NTT in algorithms and I am going to make an appoche to use ...
user122891's user avatar
1 vote
0 answers
43 views

How to batch-prove the knowledge of Module-SIS secrets

If the prover wishes to prove knowledge of Module-SIS secrets $\mathbf{s}_i$ satisfies $\mathbf{A}_i \cdot \mathbf{s}_i = \mathbf{u}_i\ \text{mos}\ q, i \in \{1,2,\cdots,N\}$ where $R_q$ is a ...
user109993's user avatar
3 votes
0 answers
57 views

If $\Vert cs\Vert$ is short in a lattice signature, how large can $s$ be?

I would like a result of the following form: "Let $s\in \mathcal{R}_q^n$ where $\mathcal{R}_q = \mathbb{Z}_q[x]/(x^d+1)$. If $\Vert s\Vert > q$, then (with all but negligible probability) for ...
Sam Jaques's user avatar
  • 1,614
1 vote
0 answers
22 views

SIVP to SIS: Why we must use uniformly random input for an hypothetical oracle in reduction?

I'm reading a handout about worst-case to average-case reduction by Peikert and Banerjee: https://github.com/cpeikert/LatticesInCryptography/blob/main/lec11.pdf In the reduction from SIVP to SIS, we ...
Haotian Yin's user avatar
0 votes
1 answer
38 views

Is it possible to prove with high certainty part of a preimage must exist to produce an LtHash output?

Given a H calculated using the LtHash algorithm, is it possible to prove a section of the preimage must have been part of the specific original preimage? i.e. given H = lt(A | X | B) give proof that X ...
Eddie Hazel's user avatar
1 vote
1 answer
42 views

Conditional distribution of an integer error vector, taken from an appropriate discrete Gaussian, given its syndrome [GPV'STOC2008]

I'm reading lemma 5.2 of [GPV'STOC2008, page 18] about conditional distribution of an integer error vector $\mathbf{e}\in\mathbb{Z}^{m}$, taken from an appropriate discrete Gaussian $\mathbf{e}\sim D_{...
user1035648's user avatar
3 votes
0 answers
184 views

Estimate security parameter $n$ for Ajtai commitment

Let $x$ be a binary string of length $m \approx 2^{20}$, $A_{n \times m}$ be a random matrix with entries independently and uniformly drawn from $\mathbb{Z}^*_{q}$, and $q$ be a $128$-bit prime number....
Jason's user avatar
  • 57
0 votes
0 answers
27 views

A few questions about smooth paramter in lattice signature

I was recently studing lattice signature and reading the GPV08 paper. For my comprehension, given a continuous guassian distribution, the smooth parameter decides a bound that, by placing the same ...
shiiu akiyama's user avatar
0 votes
0 answers
34 views

How to get a sample from $D_{q\mathbb{Z}+c,r}$?

In the paper Compact Lattice Gadget and Its Applications to Hash-and-Sign Signatures, the preimage sampling boils down to only n times sampling of $D_{q\mathbb{Z}+c,r}$. How can we obtain a sample ...
guangyu liao's user avatar
10 votes
1 answer
234 views

Relationship between LWE, SIS, and ISIS

Suppose I have a short-secret LWE instance $As+e=b\mod q$. If I treat this as a single matrix, it becomes an ISIS problem: $$ \begin{pmatrix} I &A\end{pmatrix}\begin{pmatrix} e \\ s\end{pmatrix}=b\...
Sam Jaques's user avatar
  • 1,614
1 vote
2 answers
74 views

A problem about fundamental region of a lattice

This lemma is from Peikert and Carter's handout of lecture 2. $\mathbf{\tilde{B}}$ is the Gram-Schmidt orthogonalized matrix of $\mathbf{B}$. I want to prove this lemma. My idea is to prove it by ...
Haotian Yin's user avatar
1 vote
1 answer
64 views

Gaussian width in lattice setting

In the lattice setting (like LWE, RLWE) , the Gaussian function is often defined as $$ \rho_{\Sigma}(x) = e^{-\pi x^T\Sigma^{-1}x} $$ The discrete Gaussian distribution $\mathcal{D}_{\Lambda, \Sigma}$ ...
Robert's user avatar
  • 11
2 votes
1 answer
106 views

Smaller module ranks of MLWE imply more algebraic structure?

In CRYSTALS-Kyber, they mentioned that the module rank $k$ should not be too small, they argued "having a smaller $k$ implies more algebraic structure, making the scheme potentially susceptible ...
Sharon's user avatar
  • 75
2 votes
2 answers
403 views

Why is the public key included in the private key in Kyber KEM?

We know that CRYSTALS-KYBER's KEM (key encapsulation mechanism) key generation algorithm is: Output: Public key pk $\in B^{12\cdot k\cdot n/8+32}$, Secret key sk $\in B^{24\cdot k\cdot n/8+96}$ $z \...
user120654's user avatar
2 votes
1 answer
59 views

In GPV08 lattice signature, why the fact that the bijective from quotient group to the set of syndromes holds?

I was recently reading the lattice-based signature scheme GPV08 (full paper), and the following statement confuses me alot (which is in the section 5.1, page 17&18): Throughout the paper, we use ...
shiiu akiyama's user avatar
0 votes
0 answers
62 views

Is there split-radix (mixed-radix) number theoretic transform?

Can I use multiple radices (for example, radix-2 and radix-4) for one NTT? If so, what would the twiddle factors be?
user22714606's user avatar
1 vote
0 answers
37 views

How to compute the vector $\mathbf{v}$ in verifiable encryption scheme?

In the subsection 6.3 of Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General, if the module p of encryption scheme is co-prime to the module q of commitment scheme,...
guangyu liao's user avatar
3 votes
1 answer
307 views

Questions about LWE in NIST standards

LWE instances have the form $\vec{a}_i,b_i = \langle\vec{a}_i,\vec{s}\rangle+e_i\bmod q$ for some integer $q$ and for $i=1,\dots,m$. My questions are about the NIST proposed standards. In the ...
Turbo's user avatar
  • 1,025
1 vote
1 answer
106 views

A question about smoothing lemma and proof

I'm a beginner on lattice-based cryptography and currently reading a handout of Prof. Vinod Vaikuntanathan. The first question In section 2.4 Smoothing Lemma and Proof, I cannot figure out why the ...
Haotian Yin's user avatar
3 votes
1 answer
162 views

Compare Saber and Kyber, about their techniques of message bit layout in encryption

I'd like to discuss message bit layout in the Saber and Kyber's IND-CPA encryptions.(Details of these two schemes follows behind these question paragraphs). From my understanding, both Saber and Kyber ...
Sharon's user avatar
  • 75
2 votes
1 answer
78 views

Centered Binomial Distribution vs Fixed Weight Ternary Sampler

Fixed weight ternary polynomial vector sampler randomly selects a polynomial from ${R_q[x]}/{(x^n+1)}$ with coefficients $-1,1,0$. Notable KEMs that uses fixed weight ternary samplers include NTRU, ...
Swaminathan V's user avatar
5 votes
1 answer
127 views

Noise flooding in Lattices

I noticed that in the paper [HLL24], the authors used the noise flooding technique to choose parameters and complete the proof. But I am confused that why set $\sigma \ge 2^{\kappa+6}y$ to guarantee ...
ANRIII's user avatar
  • 51
5 votes
1 answer
428 views

In lattice, does converting a "bad" basis to a "good" basis constitute a hard problem?

In lattice, a "good" basis are the set of "almost" orthogonal set of vectors which have small norms and a "bad" basis are those basis which are in certain sense hardest ...
shiiu akiyama's user avatar
1 vote
0 answers
48 views

Doubts regarding the ternary vector sampler in SMAUG-T KEM

SMAUG-T is an efficient post-quantum key encapsulation mechanism (KEM). It is the winner of Korean PQC Competition. SMAUG-T uses a Hamming Weight Sampler $HWT_h$ to sample secret polynomial vectors $s,...
Swaminathan V's user avatar
1 vote
0 answers
39 views

What is the difference between PLWE (Polynomial Learning with Errors) and RLWE (Ring Learning with Errors)? [closed]

Recently, I have been studying lattice-related concepts, and I want to understand the differences between PLWE and RLWE, such as how their security compares, as well as their structure and value ...
Lexie's user avatar
  • 11
0 votes
0 answers
28 views

Issue building RLWE based program

I've successfully built a LWE based program now moving onto building a RLWE based python program using: https://blog.openmined.org/build-an-homomorphic-encryption-scheme-from-scratch-with-python/ as a ...
ringlearningwemmet's user avatar
0 votes
0 answers
21 views

Tutorial of lattice estimator to compute a specific function with BGV

I recently try to go into lattice estimator https://github.com/malb/lattice-estimator I did find the document of it, but unfortunately, can not follow. May I ask how to run the lattice estimator to ...
js wang's user avatar
  • 371
2 votes
1 answer
103 views

About the notion of "full rank" in lattices

I'm a newer to the lattice theory, so there is a basic notion about "full rank" confusing me. In some papers focusing on the lattice theory, they always use the full rank lattice (the number ...
X.H. Yue's user avatar
  • 456

1
2 3 4 5
13