A key exchange device includes an initial setup unit that generates a verification key that serves as a public key and a signature key based on a discretionary random tape, a session identifier based on a first random tape, and a secret key based on a second random tape; an arithmetic unit that generates an encrypted second random tape by an arithmetic operation of a pseudo-random function having the second random tape and the secret key as variables and an encrypted third random tape by an arithmetic operation of the pseudo-random function having a third random tape and the secret key as variables; a key encapsulation processing unit that generates a key-encapsulated public key and a key-encapsulated secret key based on the encrypted second random tape to transmit the key-encapsulated public key to an other party of key exchange and decrypts a session key using the key-encapsulated public key and a key-encapsulated ciphertext received from the other party of key exchange; and a verification processing unit t
