To me it seems that maybe we can prove that verification of a ring signature must be linear in the number of members, since we need to make sure each members component is correct and the ring is formed correctly.

Is there any proof of this statement, or a refutation?


1 Answer 1


In the most common definition of ring signatures, the verification algorithm obtains the list of public keys (the ring) and thus already requires linear time to read this input.

However, there are constructions based on accumulators (Dodis et al. EUROCRYPT'04, Libert et al. EUROCRYPT 2016, Derler et al. PQCRYPTO'18) which allow amortized sublinear verification costs. In patricular, there is some constant size representation of the ring (the accumulator), where on the first verification one checks if it represents the correct ring (linear time) and after that, verifications with respect to the same ring can take the accumulator instead of the ring and the computation depends only on the complexity of membership proofs in the accumulator (constant for the RSA accumulator in the first link and logarithmic in the ring size for the latter two).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.