International Association
for Cryptologic Research

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.