Volume 1, Issue 6
Abstract:
The key-generation function of the lattice-based key-encapsulation mechanism CRYSTALS-Kyber (or short, just Kyber) involves a rejection-sampling routine to produce coefficients modulo that look uniformly random. The input to this rejection sampling is output of the SHAKE-128 extendable output function (XOF). If this XOF is modeled as a random oracle with infinite output length, it is easy to see that Kyber terminates with probability 1; also, in this model, for any upper bound on the running time, the probability of termination is strictly smaller than 1.
In this short note we show that an (unconditional) upper bound for the running time of Kyber exists. Computing a tight upper bound, however, is (likely to be) infeasible. The highly non-tight bound we prove in this paper does not have any implications for the use of Kyber in practice, but it may be useful for computer-assisted reasoning about Kyber using tools that require a simple proof of termination.
Citation:
Manuel Barbosa and Peter Schwabe. Kyber terminates. Polynesian Journal of Mathematics, Volume 1, Issue 6, Pages 1–5. (Dec. 2024) DOI: 10.69763/polyjmath.1.6
Milestones:
Received 16 Oct 2024
Accepted 1 Dec 2024
Published 30 Dec 2024
Communicated by Nicolas Thériault
The above content is released under the terms of the Creative Commons Attribution 4.0 International license.