Stronger Notions and a More Efficient Construction of Threshold Ring Signatures

TY - GEN

T1 - Stronger Notions and a More Efficient Construction of Threshold Ring Signatures

AU - Munch-Hansen, Alexander

AU - Orlandi, Claudio

AU - Yakoubov, Sophia

N1 - Conference code: 7

PY - 2021

Y1 - 2021

N2 - We consider threshold ring signatures (introduced by Bresson et al. [BSS02]), where any t signers can sign a message while anonymizing themselves within a larger (size- n ) group. The signature proves that t members of the group signed, without revealing anything else about their identities. Our contributions in this paper are two-fold. First, we strengthen existing definitions of threshold ring signatures in a natural way; we demand that a signer cannot be de-anonymized even by their fellow signers. This is crucial, since in applications where a signer’s anonymity is important, we do not want that anonymity to be compromised by a single insider. Our definitions demand non-interactive signing, which is important for anonymity, since truly anonymous interaction is difficult or impossible in many scenarios. Second, we give the first rigorous construction of a threshold ring signature with size independent of n, the number of users in the larger group. Instead, our signatures have size linear in t, the number of signers. This is also a very important contribution; signers should not have to choose between achieving their desired degree of anonymity (possibly very large n ) and their need for communication efficiency.

AB - We consider threshold ring signatures (introduced by Bresson et al. [BSS02]), where any t signers can sign a message while anonymizing themselves within a larger (size- n ) group. The signature proves that t members of the group signed, without revealing anything else about their identities. Our contributions in this paper are two-fold. First, we strengthen existing definitions of threshold ring signatures in a natural way; we demand that a signer cannot be de-anonymized even by their fellow signers. This is crucial, since in applications where a signer’s anonymity is important, we do not want that anonymity to be compromised by a single insider. Our definitions demand non-interactive signing, which is important for anonymity, since truly anonymous interaction is difficult or impossible in many scenarios. Second, we give the first rigorous construction of a threshold ring signature with size independent of n, the number of users in the larger group. Instead, our signatures have size linear in t, the number of signers. This is also a very important contribution; signers should not have to choose between achieving their desired degree of anonymity (possibly very large n ) and their need for communication efficiency.

U2 - 10.1007/978-3-030-88238-9_18

DO - 10.1007/978-3-030-88238-9_18

M3 - Article in proceedings

SN - 9783030882372

T3 - Lecture Notes in Computer Science

SP - 363

EP - 381

BT - Progress in Cryptology – LATINCRYPT 2021

A2 - Longa, Patrick

A2 - Ràfols, Carla

PB - Springer

T2 - 7th International Conference on Cryptology and Information Security in Latin America

Y2 - 6 October 2021 through 8 October 2021

ER -