167
the computational cost by counting the number of dominant operations involved.
Typically these operations include private key encryption and decryption, hash-
ing, modulo addition, multiplication, division (inversion), and more importantly,
exponentiation. In addition to computational cost, digital signature and encryp-
tion based on public key cryptography also require extra bits to be appended
to a message. We call these extra "redundant" bits the communication over-
head involved. We say that a message delivery method is superior to another if
(the aggregated value of) the computational cost and communication overhead
required by the former is less than that by the latter.
The firs.t part of Table 2 indicates the computational cost and coinlnuni-
cation overhead of "Schnorr signature-then-E1Gamal encryption" against that
of "DSS-then-E1Gamal ene13rption" and "RSA signature-then-RSA encryption'.
Note that, although not shown in the table, other combinations such as "Schnorr
signature-then-RSA encryption" and "RSA signature-then-EIGamal encryption"
may also be used in practice. As discussed in [21], with the current state of the
art, computing discrete logarithm on GF(p) and factoring a composite n of the
same size are equally difficult. This simplifies our comparison of the efficiency of
a cryptographic scheme based on RSA against that based on discrete logarithm,
as we can assume that the moduli n and p are of the same size.
We close this section by examining the increasingly disproportionate cost for
secure and authenticated message delivery in the currently standard signature-
then-encryption approach, with an example text of 10000 bits (which corre-
sponds roughly to a 15-line email message). For current and low security level
applications, when RSA is used, the computational cost is centered around the
execution of four (4) exponentiations modulo 512-bit integers, and the commu-
nication overhead is 1024 bits. When Schnorr signature and E1Gamal encryption
are used, the computational cost consists mainly of six (6) exponentiations mod-
ulo 512-bit integers, and the communication overhead is about 750 bits.
However, if the contents of the text are highly sensitive, or a text of the
same length will be transmitted in 2010, then very large moduli, say of 5120
bits, might have to be employed. In such a situation, if RSA is used, four (4)
exponentiations modulo (very large!) 5120-bit integers have to be invested in
computation z, and the communication overhead is 10240 bits, which is now
longer than the original 10000-bit text ! If, instead, Schnorr signature and E1Ga-
mal encryption is used, then the computational cost is six (6) exponentiations
modulo (again very large!) 5120-bit integers, and the communication overhead
of about 5560 bits is more than half of the length of the original message. From
this example, one can see that in the signature-then-encryption approach, the
cost, especially comnmnication overhead, for secure and authenticated message
delivery, is becoming disproportionately large for future, or current but high-
level security, applications. This observation serves as further justification on
the necessity of inventing a new and more economical method for secure and
authenticated inessage delivery.
2 The number of bit operations required by exponentiation modulo an integer is a
cubic function of the size of the modulo.