A storage device, a method of operating the storage device, and a method of operating a host device are provided. The storage device includes a nonvolatile memory (NVM) and a storage controller controlling the nonvolatile memory. The storage controller is configured to receive a command from a host device giving instructions to sanitize data with the use of a cryptographic erase. The storage controller is also configured to, in response to a request from the host device, transmit to the host device a first verification value indicative of whether a first media encryption key (MEK) stored in the NVM has been deleted and a second verification value indicative of whether a second MEK, which is different from the first MEK, has been generated and stored in the NVM.