Lattice-Based Logarithmic-Size Non-Interactive Deniable Ring Signatures

Deniable ring signature can be regarded as group signature without group manager, in which a singer is capable of singing a message anonymously, but, if necessary, each ring member is allowed to confirm or disavowal its involvement in the signature via an interactive mechanism between the ring member and the verifier. This attractive feature makes the deniable ring signature find many applications in the real world. In this work, we propose an efficient scheme with signature size logarithmic to the cardinality of the ring. From a high level, we adapt Libert et al.'s zero-knowledge argument system (Eurocrypt 2016) to allow the prover to convince the verifier that its witness satisfies an additional condition. Then, using the Fait-Shamir transformation, we get a non-interactive deniable ring signature scheme that satisfies the anonymity, traceability, and non-frameability under the small integer solution assumption in the random oracle model.