According to one embodiment, a storage device that has a nonvolatile semiconductor memory includes an authentication information storage unit that previously stores first apparatus authentication information to authenticate an authorized host device and first user authentication information to authenticate an authorized user. The storage device executes apparatus authentication on the basis of second apparatus authentication information received from a newly connected host device and the first apparatus authentication information in the authentication information storage unit and executes an invalidation process of user data stored in the nonvolatile semiconductor memory, when the apparatus authentication is failed.