Forcing out a confession threshold discernible ring signatures

Ring signature schemes (Rivest et al., 2001) enable a signer to sign a message and remain hidden within an arbitrary group A of n people, called a ring. The signer may choose this ring arbitrarily without any setup procedure or the consent of anyone in A. Among several variations of the notion, step out ring signatures introduced in (Klonowski et al., 2008) address the issue of a ring member proving that she is not the original signer of a message, in case of dispute. First we show that the scheme in (Klonowski et al., 2008) has several flaws and design a correct scheme and prove formally the security of the same. Then we use the basic constructs of our scheme to design a protocol for a new problem, which we refer to as threshold discernible ring signatures. In threshold discernible ring signatures, a group B of t members can co-operate to identify the original signer of a ring signature that involved a group A of n alleged signers, where B C A and n > t. This is the first time that this problem is considered in the literature and we formally prove the security of our novel scheme in the random oracle model.