Paper 2023/739

SMAUG: Pushing Lattice-based Key Encapsulation Mechanisms to the Limits

Jung Hee Cheon, Seoul National University, CryptoLab Inc.
Hyeongmin Choe, Seoul National University
Dongyeon Hong, CryptoLab Inc.
MinJune Yi, Seoul National University
Abstract

Recently, NIST has announced Kyber, a lattice-based key encapsulation mechanism (KEM), as a post-quantum standard. However, it is not the most efficient scheme among the NIST's KEM finalists. Saber enjoys more compact sizes and faster performance, and Mera et al. (TCHES '21) further pushed its efficiency, proposing a shorter KEM, Sable. As KEM are frequently used on the Internet, such as in TLS protocols, it is essential to achieve high efficiency while maintaining sufficient security. In this paper, we further push the efficiency limit of lattice-based KEMs by proposing SMAUG, a new post-quantum KEM scheme whose IND-CCA2 security is based on the combination of MLWE and MLWR problems. We adopt several recent developments in lattice-based cryptography, targeting the \textit{smallest} and the \textit{fastest} KEM while maintaining high enough security against various attacks, with a full-fledged use of sparse secrets. Our design choices allow SMAUG to balance the decryption failure probability and ciphertext sizes without utilizing error correction codes, whose side-channel resistance remains open. With a constant-time C reference implementation, SMAUG achieves ciphertext sizes up to 12% and 9% smaller than Kyber and Saber, with much faster running time, up to 103% and 58%, respectively. Compared to Sable, SMAUG has the same ciphertext sizes but a larger public key, which gives a trade-off between the public key size versus performance; SMAUG has 39%-55% faster encapsulation and decapsulation speed in the parameter sets having comparable security.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Selected Areas in Cryptography 2023
Keywords
Key Encapsulation MechanismPublic Key EncryptionPQCMLWEMLWR
Contact author(s)
jhcheon @ snu ac kr
sixtail528 @ snu ac kr
jjoker041 @ gmail com
yiminjune @ snu ac kr
History
2023-09-13: revised
2023-05-23: received
See all versions
Short URL
https://ia.cr/2023/739
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/739,
      author = {Jung Hee Cheon and Hyeongmin Choe and Dongyeon Hong and MinJune Yi},
      title = {SMAUG: Pushing Lattice-based Key Encapsulation Mechanisms to the Limits},
      howpublished = {Cryptology ePrint Archive, Paper 2023/739},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/739}},
      url = {https://eprint.iacr.org/2023/739}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.