Our approach Markowitch™s

1. Number of steps in main protocol 3 4

2. Number of steps in sub-protocol 2 (¬nish) 2 (if recovered or early)

2 (cancel) 4 (if not recovered yet)

3. Timeliness Async Sync

4. Items to be stored in the TTP P+1 1

5. Additional interrogation needed in

the dispute resolution process Yes No

6. TTP network access (reliability

in the inverse direction) No Yes

7. Timely drawbacks No Yes (stop main protocol)

8. Transparency Yes No

Table 4.4 General Off-line Solution Comparison

Our approach Markowitch™s

1. O™s main protocol 4+2P+N 4+2P

2. Ri ™s main protocol 3 4

3. O™s cancel/recovery protocol 2+P (cancel) 1 (recovery)

4. Ri ™s ¬nish protocol 2 2

5. TTP™s cancel protocol 2 (once) -

6. TTP™s ¬nish protocol 5 5

Table 4.5 Public Key Operations Comparison

In Table 4.4, we can observe that generally and when possible, our protocol im-

proves Markowitch™s version. Note that, for instance, it is not possible to reduce the

number of items the TTP needs to store as a consequence of dealing with differ-

ent messages and, thus, different evidence of receipt (since we maintain the trans-

parency property for O). This storage capacity request could be easily avoided by

allowing the TTP to issue an af¬davit for ¬nished entities, but then, transparency

would be lost. There is an improvement on the number of steps needed in the main

protocol, which fortunately will be the most frequently used, but the cost is the need

of rarely having to interrogate an additional entity in case of disputes.

4.1 MPNR Protocol for Different Messages 71

In Table 4.5, we can observe how, in general, our protocol seems to perform

worse. But if we analyze the table, we will discover that this is due to the new

functionality introduced and thus, unavoidable. Speci¬cally, operations of O™s main

protocol are augmented in N because the number of different messages to be sent.

For the same reason mentioned above, O needs to verify P different evidence of

receipt from honest entities which contacted the TTP for ¬nishing the protocol on

time. For the rest of steps, both protocols perform in a similar way.

4.1.3 Fairness vs. Collusion

As it has been introduced in this book, there exist different levels of fairness. This

protocol provides two different levels of fairness depending on the initial assump-

tions and thus, depending on these assumptions the applications which will make

use of them vary.

In the description of the previous protocols we assume that no collusion is possi-

ble between recipients. This will preserve a strong fairness property and applications

bene¬ted of these kind of protocols can be of any type.

Nevertheless, Ri could get ci in the initial steps of the protocol and quit. Then,

colluding with any other party and getting the unique key k, it could decrypt ci

without providing any evidence of receipt. Note that this issue is very dif¬cult to

solve as it is not possible to prevent one (semi) honest entity from sharing a secret

once it decrypts the secret. However, it is also important to note that when a recipient

misbehaves and colludes with a (semi) honest recipient in order to get the key and

thus (only) the message intended to him, it will not in any case obtain evidence

of origin, unless the originator obtains evidence of receipt. This is what has been

de¬ned as light fairness.

There are multiple applications which only need light fairness in their transac-

tions. A common feature in these applications is that it is more important for the

exchange of evidence than the message content itself. That is, it is critical that both

or none of the entities obtain evidence. For instance, some noti¬cation systems only

need light fairness. This happens when the message itself is known by the recip-

ient (e.g. birthday certi¬cate) but in the noti¬cation, the receiver wants to be able

to demonstrate to a third party its origin (e.g. of¬cial administration of¬ce) and the

originator wants to be able to demonstrate if necessary that the message was indeed

delivered to the intended receiver.

4.1.4 Further Discussions

The proposed approaches for multi-party non-repudiation protocols considerably

improve the number of messages exchanged as well as the amount of evidence col-

lected by the ¬nal entities involved. However, they are only the ¬rst effort to gen-

72 4 New Design Approaches for MPNR

eralize the non-repudiation service to multiple entities and messages, and might be

reviewed to further improve their ef¬ciency.

4.1.4.1 Group Encryption

Along the description of the protocols presented previously, we have been using

the notation ER (k) to de¬ne an encryption operation over the key k intended for

a group R . In the multi-party non-repudiation protocol proposed in [87], a group

encryption scheme proposed by Chiou and Chen [45] is used. It is based on a pub-

lic key encryption scheme and on the Chinese Remainder Theorem (CRT). As the

authors explained, it is ef¬cient only when the number of users is small, since the

time to compute the CRT and its length (hence transmission time) is proportional

to the number of users. This method is generic because it can use any public key

cryptosystem.

• Let uRi and uRi be the public and private keys of Ri , respectively (where i corre-

sponds to all parties that belong to R ).

• Each recipient of R receives a random integer Pi > EuRi (k) such that all Pi are

pair-wise relatively prime. (When choosing randomly large primes or multipli-

cations of distinct primes for example, the probability of obtaining two numbers

that are not relatively primes is negligible.)

• O computes X ≡ EuRi (k) mod Pi . Because all of Pi are prime integers, using the

CRT, only one solution is obtained from this equation. Hence, ER (k) ≡ X. Each

recipient Ri can obtain k by computing X ≡ EuRi (k) mod Pi using her private key

uRi .

From a computational point of view, we know that the CRT is an additional effort

to the encryption with each user™s public key. Analyzing the CRT properties we

realize that X can be of the same magnitude as ∏m Pi with m the number of users

i=1

in the group R . Besides, from the second step above we know that Pi > EuRi (k)

for every i, so the length of the message distributed to the recipients is still long.

Although it is straightforward to prove that the length of a message M such that

M = M1 M2 · · · Mn (a simple concatenation of messages) with Mi of the same length

is greater than M such that M = M1 — M2 — · · · Mn , it is also true that Pi needs to

be much greater than EuRi (k) to avoid possible problems in future encryptions, thus

making M and M approximately of the same size.

As a result, the distribution length improvement of message X with the CRT-

based group encryption, if any, is not signi¬cant. Furthermore, in that scheme, the

authors assume a model in which each recipient Ri has already got the random num-

bers Pi . However, if we assume that the originator had no prior contact with the

recipients, the random numbers have to be distributed by the originator in each pro-

tocol run, thus losing any possible advantage. For these reasons we remove the CRT

operations and de¬ne the group encryption operation as a straightforward concate-

nation of public key encryptions to each ¬nal recipient as follows.

4.1 MPNR Protocol for Different Messages 73

ER (k) = EuR1 (k), EuR2 (k), · · · , EuRm (k)

Furthermore, the reason proposed by Chiou and Chen for which a group encryp-

tion scheme using the CRT is needed instead of a simple concatenation of asymmet-

ric encryptions is that the latter needs a way for recipients to identify their message

and thus some kind of labels. This would increase the length of the message. Never-

theless, and as analyzed, we do not consider this a suf¬cient reason for introducing

the associated overhead into a MPNR protocol.