Biblio

This paper considers the covert identification problem in which a sender aims to reliably convey an identification (ID) message to a set of receivers via a binary-input discrete memoryless channel (BDMC), and simultaneously to guarantee that the communication is covert with respect to a warden who monitors the communication via another independent BDMC. We prove a square-root law for the covert identification problem. This states that an ID message of size exp(exp($\Theta$($\surd$ n)) can be transmitted over n channel uses. We then characterize the exact pre-constant in the $\Theta$($\cdot$) notation. This constant is referred to as the covert identification capacity. We show that it equals the recently developed covert capacity in the standard covert communication problem, and somewhat surprisingly, the covert identification capacity can be achieved without any shared key between the sender and receivers. The achievability proof relies on a random coding argument with pulse-position modulation (PPM), coupled with a second stage which performs code refinements. The converse proof relies on an expurgation argument as well as results for channel resolvability with stringent input constraints.

The construction of polar code refers to selecting K "most reliable polarizing channels" in N polarizing channels to WN(1)transmit information bits. For non-systematic polar code, Arikan proposed a method to measure the channel reliability for BEC channel, which is called Bhattacharyya Parameter method. The calculated complexity of this method is O(N) . In this paper, we find the complementarity of Bhattacharyya Parameter. According to the complementarity, the code construction under a certain channel condition can be quickly deduced from the complementary channel condition.

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.

Consider the problem of guessing a random vector X by submitting queries (guesses) of the form "Is X equal to x?" until an affirmative answer is obtained. A key figure of merit is the number of queries required until the right vector is guessed, termed the guesswork. The goal is to devise a guessing strategy which minimizes a certain guesswork moment. We study a universal, decentralized scenario where the guesser does not know the distribution of X, and is not allowed to prepare a list of words to be guessed in advance, or to remember its past guesses. Such a scenario is useful, for example, if bots within a Botnet carry out a brute-force attack to guess a password or decrypt a message, yet cannot coordinate the guesses or even know how many bots actually participate in the attack. We devise universal decentralized guessing strategies, first, for memoryless sources, and then generalize them to finite-state sources. For both, we derive the guessing exponent and prove its asymptotic optimality by deriving a matching converse. The strategies are based on randomized guessing using a universal distribution. We also extend the results to guessing with side information (SI). Finally, we design simple algorithms for sampling from the universal distributions.