Shrinkable Ring Signatures: It Wasn’t Them!
摘要
Ring signatures facilitate a signer to arbitrarily form a set of ring members and produce a signature on their behalf without exposing his own identity. Once signed, the signature is fixed to these particular participants. However, what if, in the future, due to problems with other members, the signatory wants to exclude them from the initial ring, making the signature represent fewer members? For instance, an entrepreneur wishes to remove his arrested business partners from his previously signed ring signatures to stay out of trouble; he desires to prove that it wasn’t them who signed the signatures while keeping himself anonymous among the remaining ring members. Unfortunately, no existing variants of ring signatures can provide a feasible solution for this situation. To address this issue, we introduce a new notion of Shrinkable Ring Signature (SRS), which allows a signatory to prove later that his already signed signature is actually on behalf of a smaller ring than the original one. We also formalize the syntax and security models for SRS. In terms of construction, we design a generic framework for an SRS from a Merkle-tree-based accumulator, a collision-resistant one-way function, a public key encryption scheme, a string commitment scheme, and a non-interactive zero-knowledge argument system. We show that our scheme is anonymous, unforgeable and shrinkable under the random oracle model. With regards to efficiency, the size of the produced signature only grows logarithmically with the number of ring members. Additionally, we present a concrete instantiation from lattices whose security relies on the SIS and LWE assumptions.