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
2 votes
1 answer
90 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 ...
Tobsec's user avatar
  • 23
0 votes
0 answers
42 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/...
js wang's user avatar
  • 327
2 votes
0 answers
116 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, ...
Alexio puk2sefu's user avatar
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 ...
Steve Mucci's user avatar
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 ...
DP2040's user avatar
  • 73
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): ...
bd55's user avatar
  • 33
2 votes
1 answer
183 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 $...
Sam Jaques's user avatar
  • 1,202
0 votes
1 answer
114 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 ...
user1035648's user avatar
0 votes
0 answers
72 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 ...
mandoo's user avatar
  • 1
1 vote
2 answers
60 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 ...
js wang's user avatar
  • 327
2 votes
1 answer
89 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 ...
Gareth Ma's user avatar
  • 350
1 vote
0 answers
45 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 ...
js wang's user avatar
  • 327
2 votes
1 answer
111 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 ...
js wang's user avatar
  • 327
3 votes
1 answer
234 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 ...
DannyNiu's user avatar
  • 9,409
0 votes
0 answers
31 views

The asymptotic form of Hermite's constant in lattice

The are some linearly upper bounds on Hermite's constant $\gamma_d$, such as $\gamma_d \leq 2d/3$, $\gamma_d \leq d/4+1$. So we can claim that $\gamma_d=O(d)$. There is also a rather tight ...
kangli's user avatar
  • 75
1 vote
0 answers
84 views

Literature on (concrete) hardness of Short Integer Solution (SIS)

I am interested in what the state of the art results on the hardness of the Short Integer Solution (SIS) instances are. The one I am the most familiar with (and the most discussed) is to use lattice ...
Gareth Ma's user avatar
  • 350
1 vote
1 answer
158 views

learning with errors

If I talk about efficiency of system of learning with error, is it it fine for q to be composite in Z_q, the ring of integers. As when q would not be prime, Z_q will not be field anymore, won't it ...
user479610's user avatar
1 vote
1 answer
95 views

Can you instantiate Ring-LWE with coefficients from a prime-power field?

Generally, we instantiate Ring-LWE with the polynomial ring $R = \mathbb{F}_q\ /\ (X^N+1)$ for prime $q$ and some power-of-two $N$. Can we instead do Ring-LWE over the ring $R = \mathbb{F}_q\ /\ (X^N+...
S. M.'s user avatar
  • 11
2 votes
1 answer
196 views

Why use small error vectors in LWE instead of big ones?

In LWE systems, why is it recommended to add only small error vectors to the system of equations and not big error vectors? Can someone come up with an example?
user479610's user avatar
1 vote
0 answers
60 views

Misuse Attacks on Lattice Crypto

I've been reading "Misuse Attacks on Post-Quantum Cryptosystems" (https://eprint.iacr.org/2019/525). In what scenarios are the attacks described in the paper applicable? Is it specifically ...
Lev Knoblock's user avatar
4 votes
2 answers
240 views

LWE and distributions

In LWE, the error term $e$ is "classically" obtained from the discrete normal distribution. Why is it so often found that this distribution is used? Are there other possibilities for ...
Zpeed78's user avatar
  • 95
0 votes
0 answers
48 views

Does randomization make a big difference in the output of the BKZ algorithm?

We all know that block Korkine-Zolotarev (BKZ) algorithm is essentially a deterministic lattice reduction algorithm. However, in the actual implementation, the BKZ algorithm contains some ...
constantine's user avatar
3 votes
1 answer
111 views

Trapdoor Quality for Lattice Crypto

In these two papers the authors mention the "quality" of a trapdoor [GPV] https://eprint.iacr.org/2007/432 [MP] https://eprint.iacr.org/2011/501 But the best detail on this matter I could ...
Cristian Baeza's user avatar
1 vote
1 answer
125 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 ...
Mjf T's user avatar
  • 21
3 votes
4 answers
843 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 ...
user110127's user avatar
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 ...
Cristian Baeza's user avatar
0 votes
1 answer
57 views

Finite index quotient group, lattice crypto

A $m$-dimentional full-rank integer lattice $\Lambda\in\mathbb{Z}^{m}$ can be defined as the set of all integer linear combinations of $m$ linearly independent over $\mathbb{R}$ basis vectors $\textbf{...
user1035648's user avatar
1 vote
1 answer
132 views

Post-quantum secure trapdoor function

I am looking for examples post-quantum secure trapdoor functions. Ideally, the inversion knowing the trapdoor should be "simple" in the sense that it can be computed by a circuit in NC^1.
Mjf T's user avatar
  • 21
3 votes
1 answer
301 views

KYBER.CPAPKE: IND-CCA Security of Lyubashevsky, Peikert, Regev (LPR) Encryption

The NIST Kyber KEM spec. defines an encryption scheme, KYBER.CPAPKE, that's a variant of the so called Lyubashevsky, Peikert, Regev ("LPR") encryption scheme [1]. While LPR encryption is ...
Rohit Khera's user avatar
0 votes
1 answer
44 views

About learning with error rings with only constant coefficient

I am new to RLWE, would like to ask whether what I am thinking make sense Suppose I have a message e.g.: x=5 And I have a lattice based encryption scheme, e.g.: BGV could I encrypt x with BGV by ...
js wang's user avatar
  • 327
1 vote
1 answer
103 views

How does big Galois groups yield better security in NTRU Prime?

I'm still kinda new to Galois theory so I apologize if this question is very obvious to some people. Basically I'm reading this paper by the NTRU Prime team and in section 2.5 it's explaining how ...
faust's user avatar
  • 13
2 votes
1 answer
122 views

LLL on Knapsack-eque problem

Given integers $s_1, \dots , s_n$ and target integer $t$, I'm trying to find small integer coefficients $x_1, \dots , x_n$ such that: $$ t \approx x_1 s_1 + \dots +x_ns_n $$ Taking inspiration from ...
user348382's user avatar
1 vote
1 answer
95 views

On the spectral norm in lattice-based cryptography

In the preliminaries section of a paper$^\color{magenta}{\star}$ on lattice-based cryptography, the matrix norm $\| \cdot \|_{2}$ is used. Why do we define such norm? What's the purpose of defining ...
user1035648's user avatar
4 votes
1 answer
91 views

Proof regarding a property of "$q$-ary" lattices

In this question we are dealing with "$q$-ary" lattices. I will give the definition available to me and I'm interested in proving the lemma. As a reference see the PDF on page 2 from Peikert'...
P_Gate's user avatar
  • 413
1 vote
1 answer
56 views

Gaussian distribution propoprties

Good day, I've a question regarding Gaussian distribution properties over lattices : Let $\mathcal{L}$ := $ \mathcal{L}(\,b_{1}$,..., $b_{m})$ be a lattice over $\mathbb{R}^{n}$, and $W$ = span($b_{1}$...
aussy's user avatar
  • 11
4 votes
4 answers
518 views

Average- and worst-case complexity

The terms "average-case", "worst-case" hardness are quite confusing. What do they mean when they say certain problems (like lattices) have an average-case to worst-case ...
user1035648's user avatar
0 votes
1 answer
82 views

Two problem about noise management of BFV

I have stuck in two problems when understanding the noise management of BFV scheme, and I don't have any idea about the two problem, help me please. Problem 1: In the ...
Xiangyu Zhang's user avatar
5 votes
1 answer
97 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, ...
cryptolearner's user avatar
2 votes
1 answer
96 views

Hiding sum of vectors. Hardness based on CVP

This is the problem Let $\mathcal{L}$ be a lattice and $v_1,v_2,\ldots,v_n\notin\mathcal{L}$. Given the values $a_1,\ldots,a_n$ such that $$a_1=\lfloor v_1\rceil+v_2+\ldots+v_n$$ $$a_2=v_1+\lfloor v_2\...
Cristian Baeza's user avatar
1 vote
1 answer
64 views

What are the most important parameters when it comes to lattice based cryptography security?

When utilizing the closest vector problem for decrypting data, does lattice size matter. For example, is a 1000x1000 grid necessarily more safe than a 100x100 grid? And if so, why would these affect ...
Eugenio Kuri Student's user avatar
1 vote
0 answers
47 views

Tensor and power bases for SIS?

What is there to say about using a power basis or a tensor basis or some combination of them for the RSIS problem in lattice cryptography? Restricting to dimension 3 for illustration, usually the ...
Joseph Johnston's user avatar
1 vote
1 answer
431 views

How long time per operation to crack Kyber1024 compared to AES256 for quantum computers?

How long time does quantum computers take per operation when search the key of Kyber? Grover's algorithm weakens 256-bit AES to 128-bit security, quantum computers at most take 2^128 operations to ...
Flan1335's user avatar
  • 361
1 vote
1 answer
39 views

LWE KEMs and message coding

In many proposed lattice PKE schemes, the plaintext is encoded or modulated in a simple fashion, e.g. using Kyber-ish notation: key gen: $pk=(A, t=As+e)$, $\quad sk=s\quad$ ($A$ random, $s$, $e$ ...
yoyo's user avatar
  • 420
2 votes
0 answers
144 views

Attacks on Ring-LWE exploiting structure of ideal lattice?

Currently every LWE-based cryptographic schemes analyze their security using lattice estimators and lattice estimators analyze the security of standard LWE even though the actual scheme is based on ...
Lee Seungwoo's user avatar
5 votes
1 answer
482 views

Do we need the quantum random oracle model (QROM)?

I am currently studying the proof of the Dilithium signature in the quantum random oracle model (QROM). I am curious to hear if anyone have any thoughts on the importance of having proofs in the QROM ...
Rory's user avatar
  • 335
4 votes
1 answer
320 views

Reducing exact SVP to exact SIVP

In "Efficient reductions among lattice problems" by Micciancio (2007) it is said, that SVP reduces to SIVP in their exact versions. I did not found anything about this fact, is a reduction ...
user108492's user avatar
3 votes
0 answers
54 views

Why was A doubled in size

Why was the dimension of A doubled in kyber? LWE encryption uses a public matrix A of dimension K but kyber uses a double matrix A resulting in $A ^{ k * k * n }$ When deriving the results of the ...
Tarick Welling's user avatar
3 votes
1 answer
849 views

CRYSTALS-Dilithium - How do the supporting algorithms work?

I am studying the Dilithium signature from Ducas et al's CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme. Wanting to understand how the supporting algorithms work together, I am trying ...
Rory's user avatar
  • 335
3 votes
0 answers
122 views

Hardness of LWE with Uniform Secrets and Error Distributions

I have seen various papers discussing the security of the Learning with Errors problem with very small uniform secrets and errors but I have not found any papers on the general LWE problem with ...
Marco's user avatar
  • 31
0 votes
1 answer
97 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 ...
rerouille's user avatar

1
2
3 4 5
12