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.
68
questions
2
votes
0
answers
12
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 ...
- 75
4
votes
1
answer
254
views
Attacks exploiting decryption failures in KYBER
I am going through the portion mentioned under the heading Original KYBER analysis inside Section 5.5 titled Attacks exploiting decryption failures.
$${\sf Pr}[\|v\|> k\sigma \sqrt{m}]< k^m e^{\...
- 151
2
votes
2
answers
304
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 \...
- 21
2
votes
1
answer
121
views
Kyber prime modulus p and base generator g
I am trying to learn more about Crystals Kyber. I am playing around with a Java implementation. I am only focussing on Kyber-512 for now, I have locally changed the source code in order to remove the ...
- 123
3
votes
1
answer
128
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 ...
- 75
2
votes
0
answers
35
views
Difference in the CCA security bound of KYBER KEM in IEEE S&P Version and NIST Submission
I was going through the KYBER CCA security bounds. I noticed one intriguing discrepancy in the CCA bound mentioned in IEEE EuroS&P version (https://eprint.iacr.org/2017/634.pdf) and KYBER NIST ...
- 43
2
votes
1
answer
113
views
Not able to reproduce the security estimates in Kyber through leaky-LWE-estimator
Kyber has provided refined estimate for classical attacks in the Section 5.2 entitled "Beyond core-SVP hardness". Kyber utilized leaky-LWE-estimator https://github.com/lducas/leaky-LWE-...
- 151
1
vote
1
answer
110
views
How to choose the distribution of error and secret vectors in LWE-based KEMs
The general construction of a LWE-based PKE looks like the following:
KeyGen :
Secret vector, sk :$ s \leftarrow \chi_s^m$
Public Key, pk: ($A \leftarrow \mathbb{Z}_q^{m \times m}, t = As + e)$ where $...
- 151
0
votes
0
answers
56
views
X25519Kyber768Draft00 Key Exchange still in use, even after GPO/Registry to disable
I am trying to find out if there is another place to disable the Post-Quantum key exchange options other than what has been published Chrome/MS for browsers. The X25519Kyber768Draft00 Key Exchange ...
- 1
0
votes
1
answer
176
views
Kyber and Classic McEliece as Public Key Encryption algorithms
Can Crystal Kyber and Classic McEliece be used as public key encryption (PKE) algorithms?.
Is there any problem with using these KEM algorithms as PKE for some reason, e.g., doing some holomorphic ...
- 33
2
votes
1
answer
220
views
Why did NIST Post Quantum Standardization have 2 schemes?
NISTs Post Quantum Standardization process selected Kyber as the KEM scheme.
I'm a bit confused over why NIST would standardize for a 'scheme' and not just a 'cipher'. Does Crystals-Dilithium use a ...
- 123
1
vote
0
answers
80
views
Kyber implementation possible overflow in the NTT subroutine?
I took a look at the code from Kyber, which I would like to quote here:
...
- 423
0
votes
0
answers
60
views
SampleNTT in Kyber [duplicate]
I was going through Kyber specification mentioned here - https://csrc.nist.gov/pubs/fips/203/ipd
The SampleNTT is an algo used for matrix A calculation that takes XOF(p,i,j) as input.
If the input is ...
- 81
1
vote
1
answer
198
views
In x25519kyber768 what is the use of the server kyber keys if only the client public kyber key is used for encapsulation in kem?
In x25519kyber768 what is the use of the server kyber keys if only the client public kyber key is used for encapsulation of the kyber shared secret in kem?
3
votes
1
answer
292
views
Confusion in the security level offered by KYBER
I was looking at security level offered by KYBER. I have attached the table for the reference. I am little bit confused regarding the security level offered by KYBER.
By definition,
Level 1 in the ...
- 151
2
votes
0
answers
68
views
Matrix-vector multiplication in Kyber implementation
I took a look at the implementation of Kyber, which can be found in this GitRepo. I made a small discovery in the indcpa.c in the function indcpa_keypair, starting ...
- 117
2
votes
1
answer
402
views
Core-SVP Hardness of Kyber
This question is with reference to the python file model_BKZ.py provided in the GitHub repository https://github.com/pq-crystals/security-estimates/blob/master/...
- 151
4
votes
1
answer
177
views
High Hamming Weight Attack on Kyber
I was reading LAC (https://eprint.iacr.org/2018/1009.pdf). They mention about high-hamming weight attacks on the Centered Binomial Distribution (CBD). To counter this, they propose CBD with fixed ...
- 151
2
votes
1
answer
92
views
Kyber - Compression and Decompression Implementation Example
I have a question about the implementation of the functions
$$Compress_q(x,d) = \left\lfloor (2^d/q)\cdot x\right\rceil mod^{+}2^d$$
and
$$Decompress_q(x,d) = \left\lfloor (q/2^d)\cdot x\right\rceil$$
...
- 117
2
votes
1
answer
141
views
Question on the Implementation of Kyber's NTT in the Reference
As defined in Kyber's specification 1, the NTT consists of two formulas:
$$\hat{f}_{2i} = \sum_{j=0}^{127} f_{2j} \zeta^{(2 \cdot \text{br}_7(i)+1)\cdot j}$$
$$\hat{f}_{2i+1} = \sum_{j=0}^{127} f_{2j+...
- 117
1
vote
0
answers
107
views
The Role of Discrete Fourier Transform (DFT) and Number Theoretic Transform (NTT) in Kyber and Falcon: Seeking Clarification
In exploring post-quantum cryptography algorithms like Kyber and Falcon, I've come across their utilization of Discrete Fourier Transform (DFT) and Number Theoretic Transform (NTT), but I'm seeking ...
- 31
1
vote
1
answer
324
views
Centred Binomial Distribution and its effects on security in Kyber
I want to concretely understand how exactly choice of error distribution effect the security of KEM in the context of Lattice Based Cryptography.
For example, I would like to know the concrete ...
- 11
1
vote
1
answer
89
views
How zetas are computed in CRYSTALS-Kyber?
As shown below it explains how generate zetas table and use it. But curious thing is that how KYBER_ROOT_OF_UNITY constant is generated ? I've tried multiple ways to generated it and cannot explain ...
- 11
2
votes
2
answers
208
views
CRYSTALS-Kyber Compress and Decompress function role
I was reading CRYSTALS-Kyber design. They have used compress_q(x,d) to scale an element of $\mathbb{Z}_q$ to $[ 0,1,...,2^d-1 ]$. The definitions of ...
- 43
1
vote
1
answer
354
views
Recursive NTT for Kyber
since the NTT is a variant of the DFT respectively FFT, it seems possible to implement a recursive algorithm for the NTT of Kyber with a divide-and-conquer concept. This is the reason for my question ...
- 117
1
vote
2
answers
212
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 ...
- 59
2
votes
1
answer
283
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{...
- 117
1
vote
1
answer
266
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:
...
- 59
1
vote
1
answer
202
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-...
- 117
4
votes
1
answer
210
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
120
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
108
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,212
0
votes
0
answers
114
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.?
- 83
1
vote
0
answers
88
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 ...
- 93.9k
3
votes
1
answer
293
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,672
1
vote
1
answer
56
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
141
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 ...
3
votes
1
answer
349
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
225
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 ...
- 423
2
votes
1
answer
60
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 ...
- 83
4
votes
1
answer
154
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 ...
- 423
1
vote
1
answer
504
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 ...
- 371
3
votes
0
answers
280
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 ...
- 423
1
vote
1
answer
42
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$ ...
- 420
3
votes
0
answers
106
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 ...
- 423
2
votes
2
answers
186
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 ...
- 25.4k
1
vote
1
answer
525
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
55
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
232
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
98
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