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

Abstract. We present Rhyme, a Fiat-Shamir lattice-based digital signature scheme featuring a novel 3C (Compact-Concise-Capacious) sampling technique. Traditional lattice-based signatures based on the Fiat-Shamir transform, such as Dilithium, rely on rejection sampling to produce signatures that do not leak the secret key. Rhyme introduces a new sampling approach that achieves more compact signatures by reducing the number of rejection sampling iterations and optimizing the distribution of the signature components. We provide a detailed security reduction and parameter selection for multiple security levels. Compared to Dilithium, Rhyme achieves comparable or smaller signature sizes with similar signing and verification speeds, highlighting the effectiveness of the 3C sampling approach for lattice-based signature design.