Quantum-safe DualRing with shorter signature and public key

Abstract

With the standardization of post-quantum signature schemes such as Dilithium and Falcon, lattice-based ring signatures have become a promising tool for anonymous authentication and privacy-preserving encryption in big data environments. Specifically, the DualRing-LB scheme (CRYPTO’ 21), despite its short signatures and elegant structure, suffers from the large public key size, which dominates its communication cost and hinders scalability. There are two methods to reduce the public key size: the first is a compression technique, and the second is the bimodal distribution. The former discards the lower bits of the public key while the latter utilizes a smaller modulus. However, the unforgeability proof of DualRing-LB is incompatible with these methods because they lead to a rapid increase in the norm bound of the module short integer solution (or MSIS) problem, thereby significantly reducing security. In this paper, we follow the original security method of DualRing-LB and apply the trapdoor sampling technique to derive a tighter upper bound of MSIS problem, yielding a fixed security level independent of the ring size. The new proof result enables the use of both the compression technique and the bimodal distribution to enhance the communication efficiency of lattice-based DualRing schemes. Based on this result, we propose three practical lattice-based instantiations that reduce the public key size by 56%, 67%, 50%, compared to DualRing-LB, respectively, and achieve overall size reductions of at least 52%, 56%, 38%, respectively, across different ring sizes. Our results can contribute to lightweight, privacy-preserving cryptographic mechanisms for secure data sharing and authentication in large-scale distributed systems.