Questions tagged [kyber]
Kyber is a Key Encapsulation Mechanism (KEM) based on the Module Learning with Errors (MLWE) problem. It is an example of lattice-based cryptography and is part of the Crystals family together with the signature scheme Dilithium. It was selected for standardisation as part of the NIST post-quantum cryptography process in 2022. The standard is in progress.
45
questions
1
vote
2
answers
67
views
What scheme is the best for combining two shared secrets?
I'm developing a program that uses a hybrid Key Encapsulation Mechanism (KEM) scheme, employing Kyber and X25519, with each producing a 32-byte shared secret. What would be the best scheme to combine ...
- 47
2
votes
1
answer
147
views
NTT - Transformation of Polynomials in Kyber
In Kyber with $q=3329$, we end up with a field that das 256th roots of unity, when we apply the chinese remainder theorem (CRT) for such a field, it may look like, according to a post here:
$$\mathbb{...
- 35
1
vote
1
answer
103
views
Is it safe to derive Ed25519 and Kyber private keys from the same seed?
I am designing a Hybrid Key exchange library using x25519 and Kyber, and the scheme I have in mind is as follows:
Alice sending a file/message to Bob:
...
- 47
1
vote
1
answer
92
views
Parse Algorithm in Kyber Specification
In the Kyber specification there is an algorithm "Parse", which receives a byte stream as input and from this the NTT representation $\hat{a} = \hat{a}_0+\hat{a}_1X + ... + \hat{a}_{n-1}X^{n-...
- 35
3
votes
1
answer
94
views
Implementation of centered binomial distribution in Kyber Key Encapsulation Mechanism?
In the implementation of centered binomial distribution of crystals-kyber, the authors load 24-bits of buffer to a 32 bit integer and then they and the answer with 0x00249249. The complete operations ...
0
votes
1
answer
75
views
Primal attack On Kyber algorithm specifications
In the Kyber Algorithm specifications document, chapter 5.1.2 primal attack, it says that:
Given the matrix LWE instance $(A,b=As+e)$, one builds the lattice $\Lambda = \{x\in \mathbb{Z}^{m+kn+1}:(A\...
- 3
1
vote
0
answers
73
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, ...
- 1,095
0
votes
0
answers
70
views
Kyber and Dilithium usage limits?
What are the theoretical usage limits of Kyber and Dilithium? Are there any sources to back this up? Maximum number of encryptions/signatures allowed per key, etc.?
- 73
1
vote
0
answers
72
views
Two-party randomness for KEM
As indicated in an earlier Q / A, KEM's do not necessarily directly encrypt a pre-generated random value. However, it is clear that some KEM's do actually do this, with RSA-KEM being an obvious ...
- 91.8k
3
votes
1
answer
174
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 ...
- 9,001
1
vote
1
answer
48
views
Composition of ciphertexts in post quantum schemes Kyber and Frodo
I took a look at the Kyber and Frodo procedures and found that the ciphertext consists of two components. In Kyber these are the lines 5-7 in algorithm 2 $c := (\mathbf{u},v)$ and in Frodo line 8 of ...
- 95
0
votes
1
answer
80
views
Hybrid Approaches: ECIES-Kyber768 [closed]
I am considering using a hybrid approach by combining ECIES (Elliptic Curve Integrated Encryption Scheme) with Kyber KEX (Kyber Key Exchange) for secure communication. Instead of using the traditional ...
0
votes
0
answers
57
views
Bound for quantum adversary in CRYSTALS-Kyber
In Kyber the following estimation is given for a quantum adversary:
Theorem 4. For any quantum adversary $A$ that makes at most $q_{RO}$ many queries to quantum random oracles $H$ and $G$, and at
...
- 393
3
votes
1
answer
196
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 ...
- 678
2
votes
1
answer
112
views
Authenticated Key Exchange of Kyber.AKE
I have some questions about the setting of the one-way authenticated key exchange of Kyber.AKE as defined in section 5 of the paper.
How does $P_2$ authenticate itself to $P_1$? It is not obvious to ...
- 393
2
votes
1
answer
46
views
Two way key transport?
For a KEM mechanism like RSA, Kyber, etc. is there it usually worth doing key trapping/key encapsulation both directions in a key exchange? By this I mean: Alice wraps a symmetric key and sends it to ...
- 73
3
votes
1
answer
129
views
Questions on difference distribution in Kyber
I have two elementary questions related to the special distribution $|x'-x \text{ mod}^{\pm} \, q| \leq B_q := \left\lceil \frac{q}{2^{d+1}} \right\rfloor$ in Kyber. The first question is about the ...
- 393
1
vote
1
answer
271
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 ...
- 351
0
votes
0
answers
44
views
Question is regarding Kyber implementation in RTL (enocode 12 algorithm)
Hi everyone I am trying to implement the Basic skeleton of the PQC Kyber Algorithm. Until now I have obtained t=As+e and s after performing point-wise multiplication (Frequency to Time domain). Now I ...
- 21
3
votes
0
answers
106
views
CRYSTALS-Kyber - Decryption and Decoding
I have a question about the decryption in Kyber [1]. I will first give important statements of the paper and then ask my actual question with an example.
In the paper it is stated:
... decrypt to a ...
- 393
1
vote
1
answer
35
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$ ...
- 367
3
votes
0
answers
81
views
Proof on the bound of Compression and Decompression in CRYSTALS-Kyber
I am dealing with the bounding of compression and decompression functions in CRYSTALS-Kyber, see the lemma in this post or the original reference KYBER, section 2.2 topic "Compression and ...
- 393
1
vote
1
answer
94
views
Matrix parsing in kyber
In the Kyber specification the parse function (algorithm 1 on page 6) takes as input a non-terminating byte stream. Although unlikely, an unlimited number of bytes ...
- 21.9k
1
vote
1
answer
207
views
Related to ntt implementation in crystal kyber
Recently I started implementing basic skeleton of crystal kyber. Right now I got stuck at NTT, where I am not able to understand how values has to be fed (twiddle factor, actual data which has to be ...
- 21
3
votes
0
answers
52
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
1
vote
1
answer
118
views
How is Crystal Kyber CPA-secure algorithms converted into a CCA-secure algorithm
In Crystal Kyber specification, page no10, there are 3 algorithms namely KYBER.CCAKEM for making the CPA-secure Kyber into CCA-secure one.
Q1: How is the shared key K being generated in KYBER.CCAKEM....
- 33
1
vote
1
answer
63
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.
- 33
1
vote
1
answer
131
views
Why predicting an error in Crystal Kyber is considered to be hard?
Hi I have started studying on crystal kyber recently. Gained some knowledge regarding its algorithm and how it works. My doubt is why it is tough for attacker to extract secret vector from pk itself ...
- 21
0
votes
1
answer
233
views
How is MLWE used for key generation in Kyber?
I've been reading about Crystal kyber, and i read that the in the key generation process, the public key pk is computed using secret key s in such a way that the ...
- 33
3
votes
1
answer
408
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 ...
15
votes
4
answers
6k
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?
- 351
3
votes
2
answers
507
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....
- 65
3
votes
1
answer
187
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 ...
- 393
2
votes
1
answer
213
views
Question on the proof of correctness in CRYSTALS-Kyber
I am currently trying to follow the proof of correctness in the CRYSTALS-Kyber paper. The following is an excerpt of the proof:
On the one hand, I am interested in how exactly one justifies/argues ...
- 393
2
votes
2
answers
381
views
Compression and Decompression in CRYSTALS-Kyber
I am currently studying the Kyber Paper. I have a question about section 2.2 Compression and Decompression, but first I would like to quote the statement:
Compression and Decompression. We now define ...
- 393
12
votes
1
answer
3k
views
Why did NIST select Kyber and Dilithium?
NIST selected Kyber for key agreement and Dilithium for digital signature applications some days ago. But IDF's MATZOV group, in their paper, broke Kyber and Dilithium and brought the security levels ...
- 121
1
vote
1
answer
194
views
Kyber PKE correctness proof, how is triangle inequality used
Im reading the CRYSTALS kyber paper and am stuck on the PKE correctness proof on page 5. I can't see how the triangle inequality would help to get to the result $|| \lceil q / 2 \rfloor \cdot (m - m') ...
- 11
4
votes
0
answers
331
views
Which parts of CRYSTALS-Kyber and CRYSTALS-Dilithium are compatible?
The papers CRYSTALS-Kyber and CRYSTALS-Dilithium both have been written by quite different authors. It seems that at least the key generation is very different from each other. CRYSTALS mainly seems ...
- 91.8k
2
votes
0
answers
110
views
The Primal and Dual attack security estimates in Kyber round 3 specification
In Kyber round 3 specification, the table 4 gave the security estimates of Primal and Dual attack with respect to Kyber 512, 768 and 1024 (see the figure below). However, using the python script given ...
- 171
5
votes
0
answers
188
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 ...
- 171
8
votes
0
answers
247
views
How are the constants found in the AVX2 implementation of CRYSTALS-KYBER round 2 generated?
The post-quantum lattice-based cryptosystem CRYSTALS-KYBER which has made it to the second round of NIST PQC includes two implementations: 1) a baseline reference implementation in C and 2) an ...
- 315
3
votes
0
answers
236
views
Block size of BKZ algorithm and related security of CRYSTALS-Kyber
Security of lattice-based schemes in the NIST Posto-Quantum Project often relies on the complexity of dual attack. Complexity of this attack depends on the running time of lattice basis reduction ...
- 167
0
votes
1
answer
77
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$ ?
- 418
1
vote
1
answer
170
views
Explanation of the tables found in Kyber round1 code?
The precomp.c file in Kyber NIST round 1 submission has three tables, could you please let me know how to generate these three tables? If I want to understand how ...
- 11
2
votes
1
answer
105
views
Why do the game-hops in Kyber and related papers contain 2 steps at a time?
In the Kyber paper in section 3 about the Kyber IND-CPA Encryption there is a proof by sequence of games containing three games. I understand that in the first game hop the M-LWE advantage is used to ...
- 346