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
36 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
57 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
69 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
  • 393
1 vote
1 answer
48 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
267 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
0 answers
38 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
1 vote
0 answers
30 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
87 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
50 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
42 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
109 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
  • 341
1 vote
1 answer
28 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
  • 265
1 vote
0 answers
54 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
138 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
  • 313
4 votes
1 answer
216 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
51 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
234 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
  • 313
2 votes
0 answers
42 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
  • 21
0 votes
0 answers
28 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 vote
1 answer
49 views

LWE Decryption: Generating errors for (c1, c2) that match binary message m

In the encryption process, the ciphertexts c1 and c2 are added to errors e1 and ...
user108142's user avatar
2 votes
0 answers
38 views

Learning with rounding: uniformity

Naively, when one applies rounding to a uniform random value one anticipates that the change is uniformly distributed. In lattice-based cryptography, is there a formal notion or proof of equivalence ...
Daniel S's user avatar
  • 20.2k
0 votes
1 answer
61 views

Unable to retrieve the binary string using LWE and Lattice-based decryption

I am new to this encryption scheme, so I may not be exactly sure of its implementation. I have a list of (u, v) ciphertext pairs to decrypt, each of them are 1-bit. ...
user108142's user avatar
1 vote
2 answers
94 views

LWE and Lattice-based cryptography: How to recover binary message $M$ from $(u, v)$ values?

I am given a set of $(u, v)$ values, matrix $A$, primary key vector, private key vector, error vector and prime $q$. I wanted to recover the binary value of each $(u, v)$ pairs using LWE decryption. ...
user108142's user avatar
3 votes
1 answer
71 views

Equivalence of lattice definitions

I have come across two supposedly identical definitions of lattices in the lattice crypto literature. There are mainly these two definitions of lattices, the first considers lattices as discrete ...
P_Gate's user avatar
  • 393
1 vote
1 answer
51 views

How & where is concepts of Good basis and bad basis used in Crystal kyber?

I've read the documentation of Crystal Kyber, but nowhere it is mentioned about good basis and bad basis. Please explain how and where is the good basis and bad basis is used in crystal kyber.
Sujan SM's user avatar
1 vote
2 answers
156 views

Are lattice-based cryptography and error-correcting codes mathematically unsound?

From Ronald de Wolf's The potential impact of quantum computers on society: The first is so-called post-quantum cryptography. This is classical cryptography, based on computational problems that are ...
HarryFoster1812's user avatar
0 votes
0 answers
40 views

What is this parameter? in Lyubashevsky's ID-scheme

I am studying Lybashevsky's ID-scheme from the article Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures(https://www.iacr.org/archive/asiacrypt2009/59120596/59120596.pdf) ...
Rory's user avatar
  • 313
1 vote
0 answers
37 views

Public seed expansion for uniform reference strings

Many cryptographic protocols are parameterized by a uniformly random reference string (e.g. the commitment key for Pedersen commitments). Our goal is to publicly generate the random values of this ...
Joseph Johnston's user avatar
1 vote
2 answers
94 views

How "unorthogonal" can a LLL-reduced basis be?

I have been recently studying LLL-reduction. I get from the size condition and Lovasz condition that the basis are guaranteed to be somewhat orthogonal. But I couldn't figure out how orthogonal the ...
haoyu's user avatar
  • 21
3 votes
1 answer
92 views

The successive minima of a lattice

I am new to lattice theory. I hope(will be grateful) that one could explain to me this claim 7 in REGEV course(this claim appears in this file page 6 : https://cims.nyu.edu/~regev/teaching/...
vinod's user avatar
  • 31
3 votes
1 answer
37 views

Why do we need "selective security" for ABE?

The general question is: Why are ABE schemes usually/sometimes proven in the selective-set of attributes model of security? Or even co-selective (both attributes and policy function)? Is it just ...
user1035648's user avatar
1 vote
1 answer
63 views

Hardness of a modified version of NTRU

Let the modified NTRU be $h=f/g$ such that $f$ is not necessarily a short polynomial, is the NTRU problem still hard in this case?
Don Freecs's user avatar
4 votes
1 answer
91 views

NTRUEncrypt proof that there are plenty of keys

In NTRU algorithm one is supposed generate a vector which is invertible as a polynomial in both $(\mathbb{Z}/p\mathbb{Z})[x]/(x^n-1)$ and $(\mathbb{Z}/q\mathbb{Z})[x]/(x^n-1)$. But is there a ...
Ali Haktan German's user avatar
0 votes
1 answer
101 views

How to show additive subgroup of $R^n$ is not discrete? [closed]

Suppose we have the additive subgroup of reals generated by $\sqrt{3}$ and $\sqrt{5}$. How would you show you that this subgroup does not form a lattice?
Ali Haktan German's user avatar
3 votes
1 answer
149 views

Hardness of LWE

I was reading "TFHE Deep Dive" from Ilaria Chillotti, and I am a bit confused over the sample given in 31:08 In the above toy sample, isn't it possible to directly eliminate noise by ...
xade93's user avatar
  • 51
5 votes
1 answer
108 views

Which lattice-based encryption scheme/signatures is fundamental?

If I would like to focus on only one signature scheme, and only one encryption based on lattices in a pedagogical context (to introduce the concept of lattice-based crypto to people familiar with ...
Ievgeni's user avatar
  • 2,542
2 votes
1 answer
100 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 ...
xade93's user avatar
  • 51
3 votes
1 answer
221 views

CRYSTALS-KYBER versus FrodoKEM, what makes each of them different than the other?

NIST's main recommendation for encryption/decryption mechanism is CRYSTALS-KYBER. Whereas, the BSI (German equivalent) chooses FrodoKEM. As far as my knowledge goes both these mechanisms use LWE ...
Chirag Parmar's user avatar
14 votes
4 answers
5k views

Kyber and Dilithium explained to primary school students?

Kyber and Dilithium are post-quantum cryptographic designs, but the resources are hard to understand. Is it possible to explain those ciphers to children?
Flan1335's user avatar
  • 341
3 votes
1 answer
128 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 ...
Don Freecs's user avatar
2 votes
2 answers
129 views

Base of $(n+1)$ elements in a lattice

Does there exist a lattice in $\mathbb{R}^n$, with an independent generative family $(b_1, \dots, b_{n+1})$ of $(n+1)$ vectors (without any loss of generality I suppose $(b_1, \dots, b_{n})$ is a $\...
Ievgeni's user avatar
  • 2,542
2 votes
0 answers
46 views

High density SIS and Low density SIS

I am searching for the exact definition of High density SIS and Low density SIS, but there is something unclear about it. SIS problem is to find $x\in \mathbb{Z}^m$ such that for random $A\in\mathbb{Z}...
Lee Seungwoo's user avatar
3 votes
1 answer
262 views

NTRUEncrypt fails on sedonion algebra

This question is a direct follow-up (hopefully - the last) of my previous one; please see it for full information. I would like to further generalise NTRU cryptosystem on higher-order algebras. ...
max's user avatar
  • 189
2 votes
1 answer
112 views

NTRUEncrypt fails on quaternion algebra

This is a follow-up of my previous two questions (1 and 2), might be relevant to check them out first for a full context. I am trying to re-create results from this paper. The basic algorithm is ...
max's user avatar
  • 189
4 votes
1 answer
89 views

"Shifting" a dual-Regev keypair away from a trapdoored instance

This question pertains to identity-based key encapsulation mechanisms (IB-KEMs). To recap the functionality: $\mathsf{KeyGen}(1^\lambda) \to (\mathsf{msk}, \mathsf{mpk})$ Generates the master keypair ...
rozbb's user avatar
  • 189
3 votes
1 answer
149 views

Why is the best way to solve LWE (and Cryptographic related Systems) with SVP (approx)?

Community, I'm new into lattice based cryptography, and I'm interested about the security of cryptography schemata like Kyber and why the focus of solving this problem lead into solving approx. SVP. ...
Max Weber's user avatar
1 vote
1 answer
90 views

Choice of Polynomial Quotient Ring

In (lattice-based) cryptography, the quotient ring $\mathbb{Z}[X]/(X^n+1)$ where $n = 2^e$ is a power of 2 is used in various cryptographic schemes (e.g., CRYSTALS-Kyber). It is my understanding that ...
muukong's user avatar
  • 13
1 vote
0 answers
59 views

Good libraries for lattice-crypto [closed]

I'm searching good libraries to manipulate lattice tools to do cryptography. I'm mainly interested by C/C++. But I'm also interested if it is in python.
Ievgeni's user avatar
  • 2,542
3 votes
2 answers
365 views

Break Lattice-Based Cryptography with Variational Quantum Algorithm (only 25 k. Qbits for Kyber1024)?

I am currently writing a seminar paper on Kyber and other lattice-based methods. I was so excited about the lattice-based methods that I also currently searched quantum algorithms to solve the methods....
Max Weber's user avatar
3 votes
1 answer
151 views

Question about Theorem 2 in CRYSTALS-Kyber Paper

I have some questions about the Kyber paper, especially about Theorem 2 on page 6, which I would like to ask here. First of all I quote the following theorem from the paper and ask my questions ...
P_Gate's user avatar
  • 393

1
2 3 4 5
10