Using Ring Learning with Errors Problem to Construct Linkable Ring Signature Scheme

Abstract

In order to solve the problem of large key size and low efficiency in the linkable ring signature scheme on lattice, this paper reconstructs the linkable ring signature scheme from lattice based on the ring learning with errors (RLWE) problem, according to the technical route of “homomorphic commitment→∑-protocol→Fiat-Shamir transformation”. This paper first constructs a homomorphic commitment scheme over a polynomial ring based on the RLWE problem, and then designs a ∑-protocol based on the commitment scheme, and transforms the ∑-protocol into a linkable ring signature scheme using the Fiat-Shamir transformation methods. Finally, this paper proposes a simple digital currency model based on the linkable ring signature scheme. Security analysis shows since the proposed scheme is constructed based on the problem of RLWE, its security can reduce to the lattice-based difficult problem and resist the quantum computer attack. Efficiency analysis shows compared with the previous linkable ring signature schemes on lattice, since the ring elements in the scheme are taken from small polynomials, the proposed scheme has shorter key size and higher computational efficiency, and the description of the scheme is simpler.

Keywords

• commitment scheme
• zero-knowledge proof
• ring learning with errors (rlwe)
• linkable ring signature