| Title | The Minimum Cost of Information Erasure for Stationary Memoryless Sources under Restriction on the Output Distribution |
| Publication Type | Conference Paper |
| Year of Publication | 2020 |
| Authors | Amada, N., Yagi, H. |
| Conference Name | 2020 54th Annual Conference on Information Sciences and Systems (CISS) |
| Keywords | compositionality, conditional resolvability, confidential information, Data Sanitization, general sources, Human Behavior, information erasure, information leakage, memoryless systems, minimum cost, output distribution, privacy, pubcrawl, random sequence, Random sequences, resilience, Resiliency, single-letter characterization, source coding, stationary memoryless sources, uniformly distributed sequences, unrelated sequence |
| Abstract | In order to erase data including confidential in-formation 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. |
| DOI | 10.1109/CISS48834.2020.1570617456 |
| Citation Key | amada_minimum_2020 |
The Minimum Cost of Information Erasure for Stationary Memoryless Sources under Restriction on the Output Distribution