Non-repudiation is a basic security requirement for electronic business applications to protect against a sender's false denial of having created and sent a message. Typically non-repudiation protocols are constructed based on digital signatures. However, there has been no theoretical treatment of such non-repudiation protocols. In this paper, we provide a formal security definition of non-repudiation protocols and analyze the security of a signature-based protocol. Our security definition and analysis are based on Canetti's framework of universally composable security.