A data storage device includes one or more non-volatile, blockwise erasable data storage media and a mechanism for sanitizing the media in response to a single external stimulus or in response to a predetermined physical or logical condition. Optionally, only part of the media is sanitized, at a granularity finer than the blocks of the medium. Setting a flag in an auxiliary nonvolatile memory enables an interrupted sanitize to be detected and restarted. Optionally, a "death certificate" verifying the sanitizing is issued. Preferably, the media are configured in a manner that allows atomic operations of the sanitizing to be effected in parallel.