A digital multisignature scheme using bijective public-key cryptosystems

Reviewer: James P. Anderson

The problem of multiple signatures in electronic data systems originated in the paper world, where even routine and ordinary correspondence requires various forms of counter-signatures and approval signatures (for example, look at the title pages of most technical or engineering reports produced by large corporations). Electronic documents require such signatures to the same extent. From earlier work (cited in the paper) the author provides a general schema for multiple electronic signatures that increases the message length by the length of the ciphertext of each added signature. The author then describes and analyzes a scheme in which the length in bits of a multisigned document is increased only by the length of a single signature, plus one bit for each additional signatory. Previous schemes increased the total message length by the length of a single signature times the number of signatories. The paper includes an example of the process using the RSA algorithm; Okamoto claims, however, that any bijective ciphering scheme is equally applicable. Proofs of the security properties of the proposed scheme are also presented. This carefully written paper is an excellent model of what technical papers should be. I recommend it to everyone working in the field of office automation (for the application) as well as to those working in public key cryptology. It is a nice, well-written piece of work.