Rhyme: A Fiat-Shamir Lattice-based Signature with 3C Sampling

Zhongxiang Zheng; Anyu Wang; Chunhuan Zhao; Guangwu Xu; Zhengtao Jiang; Sibo Feng; Zhichen Yan; Shuang Sun; Xiaoyun Wang

Paper 2025/1350

Rhyme: A Fiat-Shamir Lattice-based Signature with 3C Sampling

Zhongxiang Zheng, School of Computer and Cyber Sciences, Communication University of China, Beijing, China

Anyu Wang, Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China

Chunhuan Zhao, Huawei Technologies, Beijing, China

Guangwu Xu, School of Cyber Science and Technology, Shandong University, QingDao, China

Zhengtao Jiang, School of Computer and Cyber Sciences, Communication University of China, Beijing, China

Sibo Feng, School of Computer and Cyber Sciences, Communication University of China, Beijing, China

Zhichen Yan, School of Computer and Cyber Sciences, Communication University of China, Beijing, China

Shuang Sun, Blockchain Laboratory, ChinaBond Finance and Information Technology Co., LTD, Beijing, China

Xiaoyun Wang, Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China

Abstract

In this paper, we propose a new postquantum lattice-based digital signature named Rhyme. The scheme is based on the Fiat-Shamir structure and does not rely on flooding, rejection sampling, or Gaussian convolution as previous methods. Instead, its security is based on a variant of LWE combined with a new sampling method (3C sampling). We prove its security in ROM/QROM and provide concrete parameters as well as reference implementation to show that our scheme enjoys high efficiency and very compact signature size compared with former results.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Lattice LWE Fiat-Shamir Digital Signature
Contact author(s): zhengzx @ cuc edu cn
xiaoyunwang @ tsinghua edu cn
History: 2025-07-25: approved; 2025-07-24: received; See all versions
Short URL: https://ia.cr/2025/1350
License: CC BY-NC-SA

BibTeX

@misc{cryptoeprint:2025/1350,
      author = {Zhongxiang Zheng and Anyu Wang and Chunhuan Zhao and Guangwu Xu and Zhengtao Jiang and Sibo Feng and Zhichen Yan and Shuang Sun and Xiaoyun Wang},
      title = {Rhyme: A Fiat-Shamir Lattice-based Signature with {3C} Sampling},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1350},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1350}
}