I have been reading up on Kyber PKE and in the specification, it says that $n$ is set to encapsulate a key with a certain number of bits. Is there a relationship between $n$ and $k$ where a certain value $n$ can only pair with a certain value of $k$, or is there no restriction on the set of $n$ and $k$?
Edit: Sorry, I meant $n$ and $q$.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Assuming that in your question $n$ is the degree of the underlying ring (which is 256 in all ML-KEM parameterisations) and $k$ is the dimension of the square matrix (2, 3, or 4 depending on parameter set in ML-KEM), then yes, these are essentially independent, subject to the product $nk$ being sufficiently large to be secure and sufficiently small to control noise.
In ML-KEM, $n$ is fixed at 256 and we always extract one key bit per coefficient mid $q$ so that 256 bit keys are always extracted.
Once this is established, the constraints on $k$ are that it should not be so small that the underlying lattice problem is easy, nor so large that a failure probability grows too large.
The choices of $k$ in ML-KEM are chosen to meet the targeted security levels. Smaller $k$ would be insecure, but moderately larger $k$ would be feasible though inefficient.
As a rule of thumb $nk$ should be at least several hundred bits to meet good security standards (though there will be other criteria as well).
