Threshold Ring Signatures and Applications to Ad-hoc Groups (Full version)

Abstract

In this paper, we investigate the recent paradigm for group signatures proposed by Rivest et al. at Asiacrypt '01. We rst improve on their ring signature paradigm by showing that it holds under a strictly weaker assumption, namely the random oracle model rather than the ideal cipher. Then we provide extensions to make ring signatures suit- able in practical situations, such as threshold schemes or ad-hoc groups. Finally we propose an ecient scheme for threshold scenarios based on a combinatorial method and provably secure in the random oracle model.