Zemlyanika — Module-LWE based KEM with the power-of-two modulus, explicit rejection and revisited decapsulation failures

Alexey S. Zelenetsky; Peter G. Klyucharev

Paper 2025/746

Zemlyanika — Module-LWE based KEM with the power-of-two modulus, explicit rejection and revisited decapsulation failures

Alexey S. Zelenetsky

, QApp, Russian Federation, Bauman Moscow State Technical University

Peter G. Klyucharev, Bauman Moscow State Technical University

Abstract

This work introduces Zemlyanika, a post-quantum IND-CCA secure key encapsulation mechanism based on the Module-LWE problem. The high-level design of Zemlyanika follows a well-known approach where a passively secure public-key encryption scheme is transformed into an actively secure key encapsulation mechanism using the Fujisaki-Okamoto transform. Our scheme features three main elements: a power-of-two modulus, explicit rejection, and revised requirements for decapsulation error probability. The choice of a power-of-two modulus is atypical for Module-LWE based schemes due to the unavailability of Number Theoretic Transform (NTT). However, we argue that this option offers advantages that are often underestimated. We employ explicit rejection because it is more efficient than implicit rejection. Recent works show that both types of rejection are equally secure, so we do not reduce the security by this choice. Finally, we present compelling arguments that the probability of decapsulation failure may be higher than commonly accepted. This allows us to increase performance and security against attacks on the Module-LWE.

Note: This is a a preprint submitted to Journal of Computer Virology and Hacking Techniques

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: key encapsulation mechanism M-LWE explicit rejection decapsulation failure
Contact author(s): azelenetskiy @ qapp tech
pk iu8 @ yandex ru
History: 2025-04-27: approved; 2025-04-26: received; See all versions
Short URL: https://ia.cr/2025/746
License: CC BY

BibTeX

@misc{cryptoeprint:2025/746,
      author = {Alexey S. Zelenetsky and Peter G. Klyucharev},
      title = {Zemlyanika — Module-{LWE} based {KEM} with the power-of-two modulus, explicit rejection and revisited decapsulation failures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/746},
      year = {2025},
      url = {https://eprint.iacr.org/2025/746}
}