A non-repudiation protocol from party S to party R performs two tasks. First, the protocol enables party S to send to party R some text x along with sufficient evidence (that can convince a judge) that x was indeed sent by S. Second, the protocol enables party R to receive text x from S and to send to S sufficient evidence (that can convince a judge) that x was indeed received by R. The first generation of non-repudiation protocols were published in the period 1996-2000. In this dissertation, we design a second generation of non-repudiation protocols that enjoy several interesting properties.

First, we identify in this dissertation a special class of non-repudiation protocols, called two-phase protocols. The two parties, S and R, in each two-phase protocol execute the protocol as specified until one of the two parties receives its needed proof. Then and only then does this party refrain from sending any more message specified by the protocol because these messages only help the other party complete its proof. We show that the execution of each two-phase protocol is deterministic and does not require synchronized real-time clocks. We also show that each two-phase protocol needs to involve a trusted third party T beside the two original parties, S and R.

Second, we show that if party R in a two-phase protocol has a real-time clock and knows an upper bound on the round trip delay from R to S and back to R, then the two-phase protocol does not need to involve a trusted third party T.

Third, we design a non-repudiation protocol for transferring file F from a sender S to a receiver R over a cloud C. This protocol is designed such that there is no direct communication between parties S and R. Rather all communications between S and R are carried out through cloud C. In this protocol parties S and R do not need to store a local copy of file F and the proofs that are needed by the two parties S and R (the only copy of file F and the proofs is stored in cloud C).

Fourth, we design a new non-repudiation protocol from S to R over C where some of the proofs stored in cloud C get lost. This new protocol has an interesting stabilization property which ensures that when some of the proofs get lost, and one party can get the needed proofs but the other party cannot get its needed proofs from cloud C, then eventually, neither party is able to receive its needed proofs from cloud C.

Fifth, we design a non-repudiation protocol for transferring files from a sender S to a subset of potential receivers {R.1, R.2, ..., R.n} over a cloud C. The protocol guarantees that after each file F is transferred from sender S to a subset of the potential receivers, then (1) each receiver R.i in the subset ends up with a proof that file F was indeed sent by sender S to R.i, and (2) sender S ends up with a proof that file F was indeed received from S by each receiver R.i in the subset.