Guessing based on length functions

Close relationships between guessing functions and length functions are established. Good length functions lead to good guessing functions. In particular, guessing in the increasing order of Lempel-Ziv lengths has certain universality properties for finite-state sources. As an application, these results show that hiding the parameters of the key-stream generating source in a private key crypto-system may not enhance the privacy of the system, the privacy level being measured by the difficulty in brute-force guessing of the key stream.

Guessing under source uncertainty with side information

We study the problem of guessing the realization of a finite alphabet source, when some side information is provided, in a setting where the only knowledge the guesser has about the source and the correlated side information is that the joint source is one among a family. We define a notion of redundancy, identify a quantity that measures this redundancy, and study its properties. We then identify good guessing strategies that minimize the supremum redundancy (over the family). The minimum value measures the richness of the uncertainty class.

The Shannon Cipher System with a Guessing Wiretapper: General Sources

The Shannon cipher system is studied in the context of general sources using a notion of computational secrecy introduced by Merhav & Arikan. Bounds are derived on limiting exponents of guessing moments for general sources. The bounds are shown to be tight for iid, Markov, and unifilar sources, thus recovering some known results. A close relationship between error exponents and correct decoding exponents formfixed rate source compression on the one hand and exponents for guessing moments on the other hand is established.

Guessing Revisited: A Large Deviations Approach

The problem of guessing a random string is revisited. A close relation between guessing and compression is first established. Then it is shown that if the sequence of distributions of the information spectrum satisfies the large deviation property with a certain rate function, then the limiting guessing exponent exists and is a scalar multiple of the Legendre-Fenchel dual of the rate function. Other sufficient conditions related to certain continuity properties of the information spectrum are briefly discussed. This approach highlights the importance of the information spectrum in determining the limiting guessing exponent. All known prior results are then re-derived as example applications of our unifying approach.

The Shannon Cipher System With a Guessing Wiretapper: General Sources

The Shannon cipher system is studied in the context of general sources using a notion of computational secrecy introduced by Merhav and Arikan. Bounds are derived on limiting exponents of guessing moments for general sources. The bounds are shown to be tight for i.i.d., Markov, and unifilar sources, thus recovering some known results. A close relationship between error exponents and correct decoding exponents for fixed rate source compression on the one hand and exponents for guessing moments on the other hand is established.

Guessing and compression subject to distortion

The problem of guessing a random string is revisited. The relation-ship between guessing without distortion and compression is extended to the case when source alphabet size is countably in¯nite. Further, similar relationship is established for the case when distortion allowed by establishing a tight relationship between rate distortion codes and guessing strategies.

On guessing the realization of an arbitrarily varying source

We present a method to guess the realization of an arbitrarily varying source. Let TU be the type of the unknown state sequence. Our method results in a guessing moment that is within Kn (TU) + O(log n=n) of the minimum attainable guessing moment with full knowledge of source statistics, i.e., with knowledge of the sequence of states sn. The quantity Kn (TU) + O(log n=n) can be interpreted as the penalty one pays for not knowing the sequence of states sn of the source. Kn (TU) by itself is the penalty one pays for guessing with the additional knowledge that the state sequence belongs to type TU. Conversely, given any guessing strategy, for every type TU, there is a state sequence belonging to this type whose corresponding source forces a guessing moment penalty of at least Kn (TU) ¡ O(log n=n).