Questions tagged [lattice-crypto]
Lattice-cryptography is the study and use of lattice problems applied to cryptography.
495
questions
1
vote
1
answer
51
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 ...
- 10.8k
4
votes
1
answer
61
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'...
- 393
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?
4
votes
4
answers
263
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 ...
- 1,098
1
vote
1
answer
46
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}$...
- 10.8k
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 ...
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 ...
- 450
2
votes
2
answers
128
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 $\...
- 2,543
1
vote
1
answer
107
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 ...
- 20.1k
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, ...
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\...
- 10.8k
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 ...
- 357
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
...
CommunityBot
- 1
1
vote
1
answer
27
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$ ...
- 10.8k
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 ...
CommunityBot
- 1
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 ...
- 193
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.
...
CommunityBot
- 1
1
vote
2
answers
125
views
Why do we need the leftover hash lemma for this hybrid proof (Learning with Errors)?
I've been reading about Learning with Errors here. On p. 7 there's a proof for the security of the PKE scheme, that goes through the leftover hash lemma, in order to prove that: $$ (pk, Enc(0))\equiv (...
- 63
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 ...
- 10.8k
5
votes
1
answer
134
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 ...
- 20.1k
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 ...
- 147
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 ...
- 185
3
votes
1
answer
231
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 ...
- 548
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 ...
- 21
0
votes
0
answers
27
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 ...
- 21
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.
...
- 2,543
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 ...
- 20.1k
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 ...
- 10.8k
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.
- 20.1k
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) ...
- 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 ...
- 357
2
votes
1
answer
99
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 ...
CommunityBot
- 1
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 ...
- 10.8k
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 ...
CommunityBot
- 1
3
votes
1
answer
90
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/...
- 1
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 ...
- 396
7
votes
1
answer
253
views
IND-CCA2 post-quantum key exchange
QUIC requires that servers reuse keys so that session resumption works. That breaks many post-quantum key exchange systems.
I am looking for a post-quantum key exchange algorithm with the following ...
- 415
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?
- 20.1k
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 ...
- 10.8k
3
votes
1
answer
148
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 ...
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?
- 10.8k
1
vote
0
answers
269
views
Dilithium signature scheme - Public key derivation
I was looking at post quantum signature schemes, and I came across Dilithium(https://github.com/pq-crystals/dilithium), and our system currently runs on Ed25519 which based on my question can easily ...
- 14.9k
4
votes
1
answer
513
views
Dilithium signature scheme and timing attacks – Does the running time actually depend on the secret key?
The paper “CRYSTALS – Dilithium: Digital Signatures from Module Lattices” (by Léo Ducas, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé) introduces a digital ...
- 14.9k
5
votes
0
answers
199
views
Why is it safe to generate the secret key and masking vectors using rejection sampling in CRYSTALS-Dilithium?
In CRYSTALS-Dilithium module lattice-based digital signatures, the secret key vectors $s_1, s_2$ with coefficients in $[-\eta, \eta]$ and the signature masking vector $y$ with coefficients in $(-\...
- 14.9k
3
votes
2
answers
363
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....
- 14.9k
1
vote
1
answer
148
views
Error Correcting Codes Post Quantum Finalists
I have been looking into error-correcting codes in lattice, I am specifically hoping to find some information on hardware implementations for the NIST PQ PKE/KEM finalists (Saber, CRYSTALS-Kyber, NTRU)...
- 14.9k
2
votes
0
answers
124
views
Can binomial distribution be used to sample noise for Ring-LWE-based homomorphic encryption?
Homomorphic encryption schemes based on Ring-LWE need to sample the noise terms from a discrete probability distribution $\chi$ over the integers with support $[-B,B]$. For example, the Fan-...
- 14.9k
3
votes
1
answer
148
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.
...
- 14.9k
0
votes
1
answer
62
views
Is the "decapsulate" function from lattice based cryptography homomorphic?
Observing the code example from pqcrypto-kyber, is the decapsulate function $d$ homomorphic?
If $d(ct, sk_i) = ss_i$, is it true that $d(ct, \sum_i sk_i) = \sum_i ss_i$ ?
- 14.9k
5
votes
0
answers
157
views
How did Kyber's authors compute the error probability $\delta$?
I'm studying the specification of Kyber that was submitted to NIST PQC Round 3. However, I cannot figure out how they compute the error probability $\delta$ for Kyber 512, 768 and 1024. I have read ...
- 14.9k