We propose a novel group-oriented signature scheme, called a democratic group signature (DGS). In DGS the scheme setting is controlled on a contributory basis, i.e., without any centralized trusted authority (group manager). Group members agree on a common tracing trapdoor, i.e., every member can trace issued signatures individually. Members are able to sign on behalf of the group while remaining anonymous only to third parties. DGS supports dynamic changes of the group formation (joins and leaves of members). For security reasons the tracing trapdoor is updated after every dynamic change. The DGS model results from strong changes to the standard model of group signatures caused by elimination of the group manager's role and distribution of the tracing rights to individuals. DGS can be deployed in various group-oriented applications. We consider a use case of the shared financial control in a joint venture company (JVCo). JVCos are a popular way for partner companies to form strategic alliances for economic expansion. JVCo is an independent company which is set up to procure the joint project. Its financial control is done jointly by partner companies and is based on the"trust, but verify" relationship (TbV) followed from the natural objective of JV partners to get a higher profit from JVCo, sometimes at the expense of other partners. JVCo has an own budget to which every partner contributes. Every partner is allowed to issue (sign) payment orders from this budget to third parties on behalf of JVCo. If the issued payment amount exceeds the contribution of a partner then it is obliged to refund the difference to the budget later. In the context of TbV every partner should be able to reveal the current state of other partners' debts to the JVCo's budget independently. Thus, partners should be able to trace every signed order to its issuer. At the same time third parties which receive the payment should not be able to reveal which JVCo partner has issued the order. This is motivated by JVCo's wish for own independence, especially if it enters the market with its own trademark.  In the following we use a counter value t ≥ 0 in the subscript of the parameters to denote that the parameter is valid for the group formation after the t-th dynamic event. DGS consists of: a randomized protocol Setup between founding group members that outputs a public group key Y [0] , and to every member i its secret signing key x i [0] and a tracing trapdoorx [0] ; a randomized protocol Join between current group members and a joining member that outputs Y [t+1] , and to every member i (including the joined member) ; a randomized protocol Leave between remaining group members (after exclusion of a member) that outputs Y [t+1] , and to every remaining member i its [t] , and a message m outputs a signature σ; a deterministic algorithm Verify that on input σ, m, and Y [t] returns 1 if and only if σ was generated by a group member i using Sign on input x i [t] , Y [t] , and m; a randomized algorithm Trace that on input σ, m, Y [t] , and the tracing trapdoorx [t] returns the signer's identity i together with a proof π of this fact; a deterministic algorithm VerifyTrace that on input σ, m, Y [t] , i, π returns 1 if and only if i and π were returned by Trace on input σ, m,x [t] , Y [t] ; The public group key Y [t] should be published and updated authentically. All members share the same tracing trapdoor x [t] which allows individual tracing of signatures (as required for the monitoring of the accounting in JVCo). Note thatx [t] should be updated on every join and leave. DGS is secure if it satisfies the following (informal) requirements: Anonymity, i.e., there exists no PPT adversary A (nonmember of the current group formation) that, given access to Join, Leave, and Sign queries and all public parameters of DGS, can distinguish between two identities i0 and i1 for a given signature σi b , and Traceability, i.e., there exists no PPT adversary A (including collusion of group members) that, given access to Join, Leave, Sign, CorruptMember, and RevealTrapdoor queries, can output a forged signature that cannot be traced to one of the group members corrupted by A. Our description of anonymity subsumes unlinkability and the description of traceability subsumes well-known collusionresistance, framing and unforgeability requirements. In the full version we show differences between DGS and other group-oriented signatures, present its formal model, describe our realization based on two cryptographic primitives (contributory group key agreement (CGKA) protocols and signatures of knowledge (SK)), and prove its security in the random oracle model. A secure CGKA protocol is used to initialize and updatê x [t] , and SK allows members to preserve anonymity against third parties by making the signer's identity indistinguishable using a non-interactive zero-knowledge proof system for the knowledge of 1-out-of-n discrete logarithms.
Democratic group signatures (DGS) REF eliminates the role of a group manager by (i) allowing the group members themselves to initialize and setup the group, (ii) controlling it over dynamic changes in a collective manner, and (iii) distributing traceability rights to each group individual.