Paper 2023/708

Kyber terminates

Manuel Barbosa, University of Porto, INESC TEC
Peter Schwabe, Max Planck Institute for Security and Privacy, Radboud University
Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Contact author(s)
mbb @ fc up pt
peter @ cryptojedi org
History
2023-05-22: approved
2023-05-17: received
See all versions
Short URL
https://ia.cr/2023/708
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2023/708,
      author = {Manuel Barbosa and Peter Schwabe},
      title = {Kyber terminates},
      howpublished = {Cryptology ePrint Archive, Paper 2023/708},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/708}},
      url = {https://eprint.iacr.org/2023/708}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.