Lattice-based Linkable Linear Homomorphic Ring Signature Scheme

Under the paradigm of cloud computing and big data, lattice-based linearly homomorphic ring signature schemes aim to simultaneously satisfy the requirements of verifiable data outsourcing computation and identity anonymity while resisting quantum computing threats. However, existing schemes suffer from the problem that ring public keys and signature sizes grow linearly with the number of members, leading to limited efficiency and a lack of effective traceability mechanisms for signer behavior, resulting in regulatory blind spots. Therefore, this paper constructs a lattice-based linkable linearly homomorphic ring signature scheme. By designing a ring public key construction method based on trapdoor derivation and matrix aggregation, the ring public key size is fixed to a constant level, significantly improving storage efficiency. Moreover, a link tag mechanism based on the Learning with Errors problem is introduced, which enables effective association determination of signatures generated by the same signer while protecting the anonymity of the signer's identity. Under the random oracle model, on the basis of the hardness assumptions of the Small Integer Solution problem and the Learning with Errors problem, we prove that the scheme satisfies anonymity under full key exposure, unforgeability under internal corruption, linkability, and weak context hiding privacy. Theoretical analysis and experimental results show that, compared with existing schemes, our scheme has significant storage advantages when the ring size is large, with high verification efficiency, providing a feasible cryptographic foundation for building efficient, anonymous, and regulated postquantum secure data computing systems.