A communication apparatus that encrypts a plurality of pieces that constitute a part of data and transmits the encrypted pieces stores an encrypted piece that is one of the pieces encrypted by another communication apparatus, and first decryption key information used for decrypting the encrypted piece, while keeping the encrypted piece and the first decryption key information in correspondence with each other. Further, the communication apparatus generates temporary information that can be different at each time of generation, further performs an encrypting process on the encrypted piece based on the temporary information, and outputs a new encrypted piece. The communication apparatus transmits the new encrypted piece, the first decryption key information that is stored in correspondence with the encrypted piece, and second decryption key information used for decrypting the encrypting process.