Achievable Cost Region for Erasure of Distributed Information Using a Common Random Number

Confidential information held by companies and individuals is often stored on storage devices. When the migration or disposal of such devices is required, it is necessary to overwrite and erase the information from the devices. In order to avoid degradation or to reduce the erasure time, it is desirable to minimize the cost of information erasure, such as the number of overwriting locations. In this paper, we consider the case where confidential information is distributed and stored in multiple storage devices. To analyze the costs of information erasure for this setting, we consider the achievable cost region, i.e., the region of possible cost values. We then show that this region can be characterized using single-letter random variables of bounded cardinalities. Here, we assume that the confidential information is generated by a stationary memoryless source and that a common random number is available in storage devices for erasure.