In general, according to one embodiment, a storage device includes a data storage, a key storage, a receiver, an acquisition unit, a first computing unit, and a second computing unit. The data storage stores therein data. The key storage stores therein a plurality of device keys. The receiver receives identification information on an access device that accesses the data. The acquisition unit acquires an index specifying one of the device keys stored in the key storage. The first computing unit computes a second key based on the device key specified by the index and the identification information, the second key being used to perform an operation on key information acquired by performing an operation on a first key shared with the access device. The second computing unit computes the first key by performing an operation on the key information using the second key.