Abstract: The security attributes of certified e-mail protocol include confidentiality, non-repudiation, fairness. Aiming at to remedy the lack of confidentiality and non-repudiation of the a typical certified mail protocol, an improved certified mail protocol with transparent semi-trusted third party is proposed. To improve the protocol efficiency, a method applying Kailar logic in compositional analysis is proposed for analyzing the improved protocol. The analysis results indicate the improved protocol can meet confidentiality and non-repudiation.