Delegated multisignature scheme with document decomposition

Consider the case that a large document including different subjects can be decomposed into a disjoint set of subdocuments and is to be delegated to a group of signatories with different knowledge domains for signing. Based o n the intractability of the discrete logarithm problem, the authors propose a novel multisignature scheme, namely the delegated multisignature scheme in which each qualified signatory only signs a subset of the set of subdocu ments according to the justification that his/her knowledge domain complete ly covers these delegated subdocuments' subjects. Meanwhile, any verifier c an verify the multisignature of the document with only knowing the group's public key, i.e., the multisignature verification key, not necessarily to k now the results regarding document decomposition and subdocument delegation . The proposed scheme has the merit that the size of the subdocuments deleg ated to the qualified signatories can be further reduced and as "balanced" as possible. Besides, the proposed scheme is more realistic to practical as pects for multisignature construction and requires smaller communication ba ndwidth as compared to conventional multisignature schemes. (C) 2001 Elsevi er Science Inc. All rights reserved.