A scheme for message delivery which can guarantee an authenticity of a user, a reliability of message delivery, and an authenticity of the message deliver, while preventing an illegal act, and which can prove them at later time. In this scheme, when the user requests a delivery of a message to the information provider, the information provider carries out a user authentication of the user according to a zero knowledge interactive proof protocol using check bits E, transmits a ciphertext C in which a message M is enciphered according to a secret key cryptosystem by using a work key W, as a part of the check bits E, and delivers the message to the user in units of one bit or a plurality of bits. Then the information provider carries out a record management of a log data H for the zero knowledge interactive proof protocol. In addition, the information provider generates and transmits the check bits E by using at least the work key W, and the user takes out the work key W by using at least the check bits E, and obtains the message M by deciphering the ciphertext C according to the secret key cryptosystem by using the work key W.