Single-Letter Characterizations for Information Erasure under Restriction on the Output Distribution

Naruaki AMADA  Hideki YAGI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E104-A   No.5   pp.805-813
Publication Date: 2021/05/01
Publicized: 2020/11/09
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2020EAP1014
Type of Manuscript: PAPER
Category: Information Theory
information erasure,  single-letter characterization,  data sanitization,  conditional resolvability,  lossy source coding,  

Full Text: PDF(1.4MB)>>
Buy this Article

In order to erase data including confidential information stored in storage devices, an unrelated and random sequence is usually overwritten, which prevents the data from being restored. The problem of minimizing the cost for information erasure when the amount of information leakage of the confidential information should be less than or equal to a constant asymptotically has been introduced by T. Matsuta and T. Uyematsu. Whereas the minimum cost for overwriting has been given for general sources, a single-letter characterization for stationary memoryless sources is not easily derived. In this paper, we give single-letter characterizations for stationary memoryless sources under two types of restrictions: one requires the output distribution of the encoder to be independent and identically distributed (i.i.d.) and the other requires it to be memoryless but not necessarily i.i.d. asymptotically. The characterizations indicate the relation among the amount of information leakage, the minimum cost for information erasure and the rate of the size of uniformly distributed sequences. The obtained results show that the minimum costs are different between these restrictions.