An Information-Theoretical Analysis of the Minimum Cost to Erase Information

Tetsunao MATSUTA  Tomohiko UYEMATSU  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.12   pp.2099-2109
Publication Date: 2018/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.2099
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Shannon theory
Keyword: 
data erasure,  distortion-rate function,  information erasure,  information spectrum,  random number generation,  

Full Text: PDF(751.9KB)
>>Buy this Article


Summary: 
We normally hold a lot of confidential information in hard disk drives and solid-state drives. When we want to erase such information to prevent the leakage, we have to overwrite the sequence of information with a sequence of symbols independent of the information. The overwriting is needed only at places where overwritten symbols are different from original symbols. Then, the cost of overwrites such as the number of overwritten symbols to erase information is important. In this paper, we clarify the minimum cost such as the minimum number of overwrites to erase information under weak and strong independence criteria. The former (resp. the latter) criterion represents that the mutual information between the original sequence and the overwritten sequence normalized (resp. not normalized) by the length of the sequences is less than a given desired value.