EUVIMEDEUVIMED entdecken
Crossref

Kyber terminates

Manuel Barbosa, Peter Schwabe

Polynesian Journal of Mathematics · 2024

DOI: 10.69763/polyjmath.1.6 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Polynesian Journal of Mathematics, 2024. Verfasst von Manuel Barbosa und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitieren

Abstract (Originalsprache)

The key generation of the lattice-based key-encapsulation mechanism CRYSTALS-Kyber (or short, just Kyber) involves a rejection-sampling routine to produce coefficients modulo q = 3329 that look uniformly random. The input to this rejection sampling is output of the SHAKE-128 extendable output function (XOF). If this XOF is modelled 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 for Kyber exists. Computing a tight upper bound, however, is (likely to be) infeasible. We remark that the result has no real practical value, except that it may be useful for computer-assisted reasoning about Kyber using tools that require a simple proof of termination.

Zitieren

APA

Barbosa, M., & Schwabe, P. (2024). Kyber terminates. Polynesian Journal of Mathematics. https://doi.org/10.69763/polyjmath.1.6

Vancouver

Barbosa M, Schwabe P. Kyber terminates. Polynesian Journal of Mathematics. 2024. doi:10.69763/polyjmath.1.6

BibTeX
@article{Barbosa2024,
  author = {Barbosa, Manuel and Schwabe, Peter},
  title = {Kyber terminates},
  journal = {Polynesian Journal of Mathematics},
  year = {2024},
  doi = {10.69763/polyjmath.1.6}
}
Kostenlos starten →