A MULTIPLE SIGNATURE PROTOCOL
FOR PUBLIC-KEY CRYPTOSYSTEMS
Frank Rubin
August 6, 1997

Abstract:   This paper describes a protocol whereby several individuals may digitally sign a message in a public-key cryptosystem. The message cannot be modified by an outsider, no subset of the signers can fake a message, and no signer can deny signing the message.

Keywords:   cryptography, public-key cryptosystem, RSA cryptosystem, quadratic residue, digital signature, data security, message authentication, prime number, factorization, hashing, checksum.


INTRODUCTION

       Suppose that a group of people wish to send a message so that the receiver knows for certain that the message came from those specific people, and can later prove this to an impartial third party. For example, the message might be a contract requiring the signatures of several corporate officers, or a legal document requiring witnesses and notarization. The procedure for producing the signature should guarantee that nobody else can forge the signature or modify the signed message, and that no signer can later deny signing. Even if another, possibly larger, group of corporate officers wanted to change the message, or masquerade as the actual signers, they should be unable to do that unless the group included all of the actual signers.

       One possible way to achieve this would be to have each party append a separate digital signature to the message. This means a message requiring n signatures would be increased in length by about n times as much as for one signature. For economy, it would be preferable to have a joint signature about the same length as a single signature, provided that it does not take significantly more execution time to produce it than n separate signatures.

       This paper will show a method to achieve this goal in two common public-key cryptosystems. It is an extension of a method I described in an earlier paper [8] for single digital signatures. The method consists of two steps: first construct a secure hashing or digest of the message, then build a signature from that hash value. I will describe this for both of the leading public-key cryptosystems, the RSA system, and the Quadratic Residue system.

       In the RSA cryptosystem, it takes slightly less time to produce the joint signature than the n separate signatures. In the Quadratic Residue cryptosystem it may take longer to produce the joint signature than n separate signatures, depending on the relative sizes of the signers' public keys.

       There are many other signature methods, such as Schnorr's scheme [9] (which is based on the ElGamal cryptosystem [4]), the Lamport scheme [3], and its modified version by Bos and Chaum [2]. Meijer and Akl [5] presented 4 signature schemes. This paper is not intended as a survey of signature methods, and it will not try to extend any of these others to handle multiple signers.

RSA CRYPTOSYSTEM

       In an RSA (Rivest-Shamir-Adleman) cryptosystem [6], each user of the system has a public key that anyone can use for encrypting messages to that user, and a private key for reading those messages. The public key consists of two numbers, N and E. N is the user's modulus, and E is the user's enciphering exponent. A message is divided into blocks, each block being an integer in the range 0 to N-1. To encipher a block B the sender raises B to the E-th power modulo N. The receiver can recover B by raising B^E to the D-th power, where D is the receiver's private deciphering key. By choosing N to be the product of two large primes p and q, the user can determine D from N and E, but no other user of the system can determine D.

QUADRATIC RESIDUES

       In a quadratic residue public-key cryptosystem [1], each user has a public key which is an integer N. This integer is again the product of two large primes. A message to a receiver R is enciphered by choosing a random initial value and successively squaring it modulo N. A low-order portion of each successive square, or quadratic residue, is exclusive-ored to the next block of the message. The quadratic residue following the last block of the message is appended to the message. If the prime factors of N have been chosen in a particular way, this allows the receiver to reconstruct the initial value, and thence the entire sequence of quadratic residues.

A SECURE HASH

       The basis for the digital signature is a secure hashing function, or message digest. This means a hash function where any change to the message almost certainly changes the hash value, and nobody can modify a message in such a way that the hash value remains unchanged. A suitable hash function is described in [8]. Let the message M consist of the blocks B₁, B₂, ..., B_k. The message can be hashed in the following way:

    H₀ = Q,
    H_i = D·H_i-1 + J_i   (mod N),
    H   = H_k.

where Q is some fixed large number used as a seed, D is a fixed multiplier, and J_i is defined as

    J_i =    B_i²     if   B_i < N/2,
    J_i = N-B_i²     if   B_i > N/2.

Since N is odd, B_i cannot equal N/2. If N has b bits, then each message block B_i will be b-1 bits long, except possibly the last block.

       Changing any block of the message will almost certainly change the value of the hash. If the prime factors p and q of N are chosen so that either p or q or both are =3(mod 4) then changing any one block of the message will step the value of H through half of the values 0 to N-1 twice each (plus one additional value that occurs only once). This is because one quarter of the values from 1 to N-1 are quadratic residues, and one quarter are of the form (N - quadratic residue).

       In the previous paper [8], the hashing modulus N was the sender's modulus. This choice meant that nobody except the sender could create a message which has the same hash value as the genuine message. That was perfectly secure in a single-sender single-signature situation. However, here we have multiple signatories, each of whom is responsible for the contents of the message. We can use neither a sender's modulus, nor the receiver's modulus, for this would allow that person to substitute another message for the genuine message.

       I propose that the cryptosystem have an additional public modulus specifically for the purpose of constructing this hash. The factorization of this modulus would be known only to some trusted central authority, or perhaps to nobody at all. This could be arranged by using a computer program that generated two large primes and reported their product, but not the primes themselves. The choice of these primes could depend on physical events that could never be replicated, such as the exact timing of keystrokes from several mutually isolated keyboards.

       Since this master modulus or master key will be the basis for signed documents throughout the communications network, anyone who factored the master key could alter documents at will. To assure this does not happen, the master key must be chosen to make factoring difficult beyond anything that can be achieved today or in the foreseeable future. I suggest that the master key N be the product of two primes p and q satisfying p>10¹⁰⁰, q>10¹⁰⁰ and abs(p-q)>10⁵⁰N^1/4. They should be of the form p=2p'+1 and q=2q'+1 with p' and q' prime. A convenient size for the product N=pq would be 1024 bits, corresponding to 308 to 309 decimal digits. As computers get faster, and factoring algorithms improve, this size should be revised upwards to stay at least 5-10 years ahead of the state of the art.

A JOINT SIGNATURE

       Suppose that the signers are S₁, S₂, ..., S_n numbered so that their public moduli are in ascending order, namely N₁ < N₂ < ... < N_n.

       Consider the RSA case first. The first signer constructs a signature by deciphering the hash value H using the modulus N₁ and the secret key D₁. If the hash value is larger than the modulus N₁ it may be reduced modulo N₁. This gives a new value which the second signer deciphers using the modulus N₂ and the secret key D₂. And so forth.

       The receiver can then verify the joint signature by reversing these steps. First the signature is enciphered using S_n's public keys, N_n and E_n. The operations of enciphering and deciphering are commutative in the RSA cryptosystem, so the result will be the signature produced by S_n-1. This is then enciphered using the public keys N_n-1 and E_n-1. And so forth. If the result matches the hash value H modulo N₁, then the joint signature is verified.

       This process assumes that the receiver knows who has signed the message. The text of the message may specify this, but we must be prepared for messages that do not specify. If the sending organization has d authorized signers, and n signatures are required, then the receiver could conceivably try all P(d,n) = d!/(d-n)! permutations, potentially a large number. This can be avoided by appending a d-bit tag following the signature, with a 1 for each signer. The tag also determines the length of the signature, making it easy to separate the message from the signature, which must be done before the receiver can compute the hash value.

QUADRATIC RESIDUE

       The situation is more complex in a Quadratic Residue or Double Quadratic Residue [7] public key cryptosystem. A signer in a QR system produces a signature by taking the square root of the hash value modulo the sender's public modulus. However, not all values have square roots. Only quadratic residues have square roots, and only about 1/4 of all residues are quadratic residues. Thus it would appear that there is only a 1/4 chance of being able to produce a signature for each signer.

       With a single signer, this problem is solved by appending an extra byte to the hash value. This byte is initially set to 0, and the signer tries to obtain a square root. If this value is not a quadratic residue, then the byte is stepped to 1, then 2, and so forth. The extra byte allows 256 tries, making success 99.999999% certain.

       With multiple signers, the first signer would pass the signature, that is, the square root of the hash value, to the second signer, who would calculate the square root modulo N₂. Again, this would have a 1/4 chance of being a quadratic residue. If it were not, the first signer could step the low-order byte and try again. Thus it would appear that 16 tries would be needed with 2 signers, 64 tries with 3 signers, and so forth. The chance of success would seem to drop precipitously as the number of signers increased.

       Fortunately, the situation is not really this bad. The public moduli N_i of the signers are likely of different sizes. Suppose, in particular that 2^kN_i<N_i+1<2^k+1N_i. Then it is possible to append k bits to the signature of S_i before S_i+1 begins the signature process. This gives the next signer 2^k tries to find a square root before S_i must try again.

       If the potential signers can arrange so that each successive modulus is at least 3 bits longer than the preceding one, then each signer will have at least 8 tries, so there will be at most a 10% chance of needing to backtrack after each signature attempt.

       If this cannot be arranged, then there is a more general procedure that will solve the problem. Instead of appending a fixed number of bits to the hash value, append a variable number of bits depending on the number of signers and the relative sizes of their public moduli. A rule of thumb might be 6 bits for the first signer, plus 2 additional bits for each additional signer, reduced by the extra bits allowed by their moduli.

       Let e_i be the number of extra bits that may be added after S_i-1 signs and before S_i signs. Let

    b₁ = 6,
    b_i = b_i-1 + 2 - e_i.
The number of bits that must be added is

    max (b₁, b₂, ..., b_n).

With this number of bits, the chance of obtaining a joint signature is at least 99.9999887%, regardless of the number of signers. In the worst case all e_i will be zero, requiring 2n+4 added bits.

       Actually, since the master key is probably a good deal larger than any of the signers' public keys, the entire hash value would not be used in any case, so these added bits do not increase the size of the hash value (which could potentially mean the signature would have to be done as two or more blocks). Instead, the hash value would be truncated to the length of the first signer's public key, less one bit, less the number of added bits determined above. Then the added bits would restore the length to one less than the length of first signer's key.

       The amount of work required to produce the joint signature depends on whether each signer finds a square root, or whether it is necessary to backtrack. This, in turn, depends on the values of e_i. With e_i=0, there is a 75% chance of needing to backtrack, for e_i=1 a 56% chance, for e_i=2 a 32% chance, for e_i=3 a 10% chance, and so forth.

       If a group of people frequently sign digital documents together, excessive backtracking can be avoided by choosing the public moduli so that e_i > 3.

       In both the RSA and Quadratic Residue signature schemes it is possible for a signer to claim that a signature was forged by publishing the factorization of the public modulus. It is required that each signer uses the same modulus for signatures as for encrypted messages. Thus publishing the factorization would potentially reveal the contents of all encrypted messages the signer had ever received. It is assumed that this is sufficient to deter such publication. (If not, then the document may be protected by registering its time of receipt with a trusted authority.)

SUMMARY

       A message can be signed by n signatories by hashing the message, and then successively decrypting the hash value with the public keys of the signers. For the RSA cryptosystem, the amount of work is actually less than the work needed to produce n separate signatures. For the Quadratic Residue cryptosystem, several tries at producing a joint signature may be needed, so the work may be slightly to substantially greater than the work to produce n signatures. Substantial extra work may be prevented by choosing public moduli of sufficiently different lengths. For both systems, the length of the joint signature is only slightly greater than the length of a single signature.

       The joint signature is secure in the sense that no party or parties can fake the signature, nor can any signers deny that they signed. The signature can be proved to a third party, such as a court of law.


REFERENCES

1	L. Blum, M. Blum and M. Shub 1986. A Simple Unpredictable Pseudorandom Number Generator. SIAM J. Compu. 15: 364-383.
2	J. N. E. Bos and D. Chaum 1993. Provably Unforgeable Signatures. Lect. Notes in Compu. Sci. 740: 1-14.
3	W. Diffie and M. E. Hellman 1976. Multiuser Cryptographic Techniques. AFIPS Conf. Proc. 45: 109-112.
4	T. ElGamal 1985. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans. on Info. Theory 31: 469-472.
5	H. Meijer and S. Akl 1982. Digital Signature Schemes. Cryptologia 6: 329-338.
6	R. L. Rivest, A. Shamir and L. Adleman 1978. A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Comm. ACM 21: 120-126.
7	F. Rubin 1995. The Quadratic and Double Quadratic Residue Ciphers. Cryptologia 19: 275-283.
8	F. Rubin 1995. Message Authentication Using Quadratic Residues. Cryptologia 19: 397-404.
9	C. P. Schnorr 1991. Efficient Signature Generation by Smart Cards. J. Cryptology 3: 161-174.