Refinements and Extensions of Ziv’s Model of Perfect Secrecy for Individual Sequences

Abstract

We refine and extend Ziv’s model and results regarding perfectly secure encryption of individual sequences. According to this model, the encrypter and the legitimate decrypter share a common secret key that is not shared with the unauthorized eavesdropper. The eavesdropper is aware of the encryption scheme and has some prior knowledge concerning the individual plaintext source sequence. This prior knowledge, combined with the cryptogram, is harnessed by the eavesdropper, who implements a finite-state machine as a mechanism for accepting or rejecting attempted guesses of the plaintext source. The encryption is considered perfectly secure if the cryptogram does not provide any new information to the eavesdropper that may enhance their knowledge concerning the plaintext beyond their prior knowledge. Ziv has shown that the key rate needed for perfect secrecy is essentially lower bounded by the finite-state compressibility of the plaintext sequence, a bound that is clearly asymptotically attained through Lempel–Ziv compression followed by one-time pad encryption. In this work, we consider some more general classes of finite-state eavesdroppers and derive the respective lower bounds on the key rates needed for perfect secrecy. These bounds are tighter and more refined than Ziv’s bound, and they are attained using encryption schemes that are based on different universal lossless compression schemes. We also extend our findings to the case where side information is available to the eavesdropper and the legitimate decrypter but may or may not be available to the encrypter.

1. Introduction

Theoretical frameworks focusing on individual sequences and finite-state encoders and decoders have undergone extensive exploration, diverging from the conventional probabilistic paradigm used in modeling sources and channels. This divergence has been particularly evident across various information-theoretic domains, such as data compression [1,2,3,4,5,6,7], source/channel simulation [8,9], classification [10], prediction [11,12,13,14], denoising [15], and even channel coding [16,17,18]. These references merely scratch the surface of a vast body of literature. Conversely, the realm of information-theoretic security, from Shannon’s seminal contribution [19] to more contemporary research [20,21,22,23,24], remains almost totally entrenched in the probabilistic framework. While these works represent a mere fraction of the extensive literature, they exemplify the nearly exclusive reliance on probabilistic models within this field.

To the best of the author’s knowledge, there are only two exceptions to this prevailing paradigm, documented in an unpublished memorandum by Ziv [25] and a subsequent work [26]. Ziv’s memorandum presents a unique approach wherein the plaintext source, to be encrypted using a secret key, is treated as an individual sequence. The encrypter is modeled as a general block encoder, while the eavesdropper employs a finite-state machine (FSM) as a message discriminator. The memorandum postulates that the eavesdropper possesses certain prior knowledge about the plaintext, expressed as a set of “acceptable messages”, hereafter referred to as the acceptance set. In other words, before observing the cryptogram, the eavesdropper’s uncertainty about the plaintext sequence is that it could be any member of this set of acceptable messages.

This assumption about the prior knowledge available to the eavesdropper is fairly realistic in real life. Consider, for example, the case where the plaintext alphabet is the Latin alphabet, but the eavesdropper knows that the plaintext must be a piece of text in the Italian language. In this case, their prior knowledge allows them to reject every candidate string of symbols that includes the letters ‘j’, ‘k’, ‘w’, ‘x’, and ‘y’, which are not used in Italian. Another example, which is common to English and some other languages, is that the letter ‘q’ must be followed by ‘u’. In the same spirit, some additional rules of grammar can be invoked, like limitations on the number of successive consonants (or vowels) in a word, limitations on the length of a word, and so on.

Now, according to Ziv’s approach, perfectly secure encryption amounts to a situation where the presence of the cryptogram does not reduce the uncertainty associated with the acceptance set. In other words, having intercepted the cryptogram, the eavesdropper learns nothing about the plaintext that they did not know before. The size of the acceptance set can be thought of as a quantifier of the level of uncertainty: a larger set implies greater uncertainty. The aforementioned FSM is used to discriminate between acceptable and unacceptable strings of plaintext symbols that can be obtained by examining various key bit sequences. Accordingly, perfect security amounts to maintaining the size of the acceptance set unchanged, and consequently, the uncertainty level, in the presence of the cryptogram. The principal finding in Ziv’s work is that the asymptotic key rate required for perfectly secure encryption, according to this definition, cannot be lower (up to asymptotically vanishing terms) than the Lempel–Ziv (LZ) complexity of the plaintext source [7]. Clearly, this lower bound is asymptotically achieved by employing one-time pad encryption (that is, bit-by-bit XOR with key bits) of the bit-stream obtained from LZ data compression of the plaintext source, mirroring Shannon’s classical probabilistic result, which asserts that the minimum required key rate equals the entropy rate of the source.

In the subsequent work [26], the concept of perfect secrecy for individual sequences was approached differently. Instead of a finite-state eavesdropper with predefined knowledge, it was assumed that the encrypter could be realized by an FSM, which is sequentially fed by the plaintext source and random key bits. A notion of “finite-state encryptability” was introduced (in the spirit of the analogous finite-state compressibility in [7]), which designates the minimum key rate that must be consumed by any finite-state encrypter, such that the probability law of the cryptogram would be independent of the plaintext input, and hence be perfectly secure. Among the main results in [26], it was asserted and proven that the finite-state encryptability of an individual sequence is essentially bounded from below by its finite-state compressibility, a bound that is once again attained asymptotically through LZ compression followed by one-time pad encryption.

In this work, we revisit Ziv’s approach to perfect secrecy for individual sequences [25]. After presenting his paradigm in detail, we proceed to refine and generalize his findings in certain aspects. First, we consider several more general classes of finite-state discriminators that can be employed by the eavesdropper. These will lead to tight lower bounds on the minimum key rate to be consumed by the encrypter, which will be matched by encryption schemes that are based on some other universal data compression schemes. The resulting gaps between the lower bounds and the corresponding upper bounds (i.e., the redundancy rates) would converge faster. Among these more general classes of finite-state machines, we will consider finite-state machines that are equipped with counters, as well as periodically time-varying finite-state machines with counters. Another direction of generalizing Ziv’s findings is the incorporation of side information (SI) available to both the eavesdropper and the legitimate decrypter, but which may or may not be available to the encrypter.

The outline of this article is as follows. In Section 2, we formulate the model setting, establish the notations, and provide a more detailed background on Ziv’s model and results in [25]. In Section 3, which is the main section of this article, we present the refinements and extensions to other types of FSMs, including FSMs with counters (Section 3.1), shift-register FSMs with counters (Section 3.2), and periodically time-varying FSMs with counters (Section 3.3). Finally, in Section 4, we further extend some of our findings to the case where SI is available to both the legitimate decrypter and the eavesdropper but not necessarily to the encrypter.

2. Formulation, Notations, and Background

Consider the following version of Shannon’s cipher system model, adapted to the encryption of individual sequences, as proposed by Ziv [25]. An individual (deterministic) plaintext sequence, $\mathit{x}=(x_0,\dots ,x_{n-1})$ (n—positive integer), is encrypted using a random key K, whose entropy is $H\left(K\right)$, to generate a cryptogram, $W=T(\mathit{x},K)$, where the mapping $T(·,K)$ is invertible given K, namely x can be reconstructed by the legitimate decoder, who has access to K, by applying the inverse function, $\mathit{x}=T^{-1}(W,K)$. The plaintext symbols, $x_i$, $i=0,1,2,\dots ,n-1$, take on values in a finite alphabet, $\mathcal{X}$, of size $\alpha$. Thus, x is a member of ${\mathcal{X}}^n$, the n-th Cartesian power of $\mathcal{X}$, whose cardinality is ${\alpha }^n$. Without essential loss of generality, we assume that K is a uniformly distributed random variable taking on values in a set $\mathcal{K}$, whose cardinality is $2^{H\left(K\right)}$. Sometimes, it may be convenient to consider $\mathcal{K}$ as the set $\{0,1,\dots ,2^{H\left(K\right)}-1\}$. A specific realization of the key, K, is denoted by k.

An eavesdropper who knows the mapping, T, but not the realization of the key, K, is in the quest of learning as much as possible about x upon observing W. It is assumed that the eavesdropper also has some prior knowledge about x, even before observing W. In particular, the eavesdropper knows that the plaintext source string x must be a member of a certain subset of ${\mathcal{X}}^n$, denoted as ${\mathcal{A}}_n$, which is referred to as the acceptance set.

Ziv models the eavesdropper by a cascade of a guessing decrypter and a finite-state message discriminator, which work together as follows. At each step, the eavesdropper examines a certain key, $k\in \mathcal{K}$, by generating an estimated plaintext, $\widehat{\mathit{x}}=T^{-1}(W,k)$, and then feeding $\widehat{\mathit{x}}$ into the message discriminator to examine whether $\widehat{\mathit{x}}\in {\mathcal{A}}_n$. If the answer is affirmative, $\widehat{\mathit{x}}$ is accepted as a candidate; otherwise, it is rejected. Upon completing this step, the eavesdropper moves on to the next key, $k+1$, and repeats the same process. The message discriminator is modeled as a finite-state machine, which implements the following recursive equations for $i=0,1,2,\dots ,n-1$:

$$\begin{array}{ccc}\hfill u_i& =& f(z_i,{\widehat{x}}_i)\hfill \end{array}$$

(1)

$$\begin{array}{ccc}\hfill z_{i+1}& =& g(z_i,{\widehat{x}}_i),\hfill \end{array}$$

(2)

where $z_0,z_1,z_2,\dots ,z_{n-1}$ is a sequence of states; $z_i\in \mathcal{S}$, $i=0,1,2,\dots ,n-1$; $\mathcal{S}$ is a set of s states (and with the initial state, $z_0$, as a fixed member of $\mathcal{S}$); $u_0,u_1,\dots ,u_{n-1}$ is a binary output sequence that indicates acceptance or rejection; $f:\mathcal{S}\times \mathcal{X}\to \{0,1\}$ is the output function; and $g:\mathcal{S}\times \mathcal{X}\to \mathcal{S}$ is the next-state function. If $u_0,u_1,u_2,\dots ,u_{n-1}$ is the all-zero sequence, $\widehat{\mathit{x}}$ is accepted, namely $\widehat{\mathit{x}}\in {\mathcal{A}}_n$; otherwise, as soon as $u_i=1$ for some $0\le i\le n-1$, $\widehat{\mathit{x}}$ is rejected. In other words, ${\mathcal{A}}_n$ is defined as the set of all $\left\{\widehat{\mathit{x}}\right\}$, for which the response of the finite-state discriminator is the all-zero sequence, $\mathit{u}=(0,0,\dots ,0)$.

Example 1.

Let $\mathcal{X}=\{0,1\}$, and suppose that the membership of x in ${\mathcal{A}}_n$ forbids the appearance of more than two successive zeroes. Then, a simple discriminator can detect a violation of this rule using the finite-state machine defined by $\mathcal{S}=\{0,1,2\}$ and

$$\begin{array}{ccc}\hfill g(z,\widehat{x})& =& \left\{\begin{array}{cc}(z+1)\mathrm{mod}3\hfill & \widehat{x}=0\hfill \\ 0\hfill & \widehat{x}=1\hfill \end{array}\right.\hfill \end{array}$$

(3)

$$\begin{array}{ccc}\hfill f(z,\widehat{x})& =& \left\{\begin{array}{cc}1\hfill & z=2and\widehat{x}=0\hfill \\ 0\hfill & otherwise\hfill \end{array}\right.\hfill \end{array}$$

(4)

with the initial state being $z_0=0$. More generally, consider the set of binary sequences that comply with the so-called $(d,k)$ constraints, well known in the literature on magnetic recording (see, e.g., [27] and the references therein). These are binary sequences, where the runs of successive zeroes must be of length at least d and at most k, where d and k (not to be confused with the notation of the encryption key) are positive integers with $d\le k$. We return to this example later.

Ziv defines perfect secrecy for individual sequences as a situation where, even upon observing W, the eavesdropper’s uncertainty about x is not reduced. In mathematical terms, let us denote

$$T^{-1}\left(W\right)\stackrel{▵}{=}\{T^{-1}(W,k),k\in \mathcal{K}\},$$

(5)

and

$${\mathcal{A}}_n\left(W\right)\stackrel{▵}{=}{\mathcal{A}}_n\bigcap T^{-1}\left(W\right),$$

(6)

and then perfect secrecy is defined as a situation where

$${\mathcal{A}}_n\left(W\right)={\mathcal{A}}_n,$$

(7)

or equivalently,

$${\mathcal{A}}_n\subseteq T^{-1}\left(W\right).$$

(8)

To demonstrate these concepts, consider the following example.

Example 2.

Let $n=4$, $\mathcal{X}=\{0,1\}$, $\mathit{x}=\left(1111\right)$, $2^{H\left(K\right)}=8$, and $k=\left(1111\right)$. Then, for a one-time pad encrypter,

$$W=T(\mathit{x},k)=\mathit{x}\oplus k=\left(1111\right)\oplus \left(1111\right)=\left(0000\right),$$

(9)

where ⊕ denotes bit-wise XOR (modulo 2 addition). Let the set $\mathcal{K}$ of all eight possible key strings be given by

$$\mathcal{K}=\left\{\begin{array}{c}1111\\ 1000\\ 1100\\ 1001\\ 0000\\ 0111\\ 0011\\ 0110\end{array}\right\}.$$

(10)

Obviously, the decryption is given by $T^{-1}(W,k)=W\oplus k$. Since $W=\left(0000\right)$, then $T^{-1}\left(W\right)=\mathcal{K}$. Following Example 1, suppose that ${\mathcal{A}}_4$ is the set of all binary vectors of length $n=4$, which do not contain runs of more than two zeroes. There are only three binary vectors of length 4 that contain a succession of more than 2 (i.e., 3 or 4) zeroes, namely $\left(0000\right)$, $\left(1000\right)$, and $\left(0001\right)$. Thus, $|{\mathcal{A}}_4|=2^4-3=13$. On the other hand,

$$|{\mathcal{A}}_4\left(W\right)|=|{\mathcal{A}}_4\bigcap T^{-1}\left(W\right)|\le |T^{-1}\left(W\right)|=|\mathcal{K}|=8<13,$$

(11)

where the notation $\left|\mathcal{E}\right|$ for a generic finite set $\mathcal{E}$ denotes its cardinality. This means that this encryption system is not perfectly secure. The reason for this is that the key space, $\mathcal{K}$, is not large enough.

Clearly, in the quest to minimize $H\left(K\right)$ without compromising perfect secrecy, the optimal approach is to design the encrypter in such a way that

$$T^{-1}\left(W\right)={\mathcal{A}}_n,$$

(12)

for every cryptogram W that can possibly be obtained from some combination of x and k. Conceptually, this can be obtained by mapping ${\mathcal{A}}_n$ to the set of all binary sequences of length $H\left(K\right)$ utilizing a fixed-rate data compression scheme and applying one-time pad encryption to the compressed sequence. Here, and throughout the following discussion, we neglect integer length constraints associated with large numbers, so $H\left(K\right)$ is assumed to be an integer without essential loss of generality and optimality.

Remark 1.

For readers familiar with the concepts and the terminology of coding for systems with $(d,k)$ constraints (other readers may skip this remark without loss of continuity), it is insightful to revisit the second part of Example 1: If ${\mathcal{A}}_n$ is the set of binary n-sequences that satisfy a certain $(d,k)$ constraint, then optimal encryption for ${\mathcal{A}}_n$ pertains to compression using the inverse mapping of a channel encoder for the same $(d,k)$ constraint, namely the corresponding channel decoder, which is followed by one-time pad encryption. The minimum key rate needed is then equal to the capacity of the constrained system, which can be calculated either algebraically, as the logarithm of the Perron–Frobenius eigenvalue of the state adjacency matrix of the state transition diagram, or probabilistically, as the maximum entropy among all stationary Markov chains that are supported by the corresponding state transition graph [27].

Ziv’s main result in [25] was that for a finite-state discriminator, if $\mathit{x}\in {\mathcal{A}}_n$, the cardinality of ${\mathcal{A}}_n$ cannot be exponentially smaller than $2^{LZ\left(\mathit{x}\right)}$ (see Appendix A for the proof), where $LZ\left(\mathit{x}\right)$ is the length (in bits) of the compressed version of x, using the 1978 version of the Lempel–Ziv algorithm (the LZ78 algorithm) [7]. Therefore, the key rate needed to completely encrypt all members of ${\mathcal{A}}_n$ is lower bounded by

$$\begin{array}{cc}\hfill R& \stackrel{▵}{=}\frac{H\left(K\right)}{n}\hfill \\ \hfill & =\frac{log|T^{-1}\left(W\right)|}{n}\hfill \\ \hfill & \ge \frac{log|{\mathcal{A}}_n|}{n}\hfill \\ \hfill & \ge \frac{LZ\left(\mathit{x}\right)}{n}-{ϵ}_n,\hfill \end{array}$$

(13)

where ${ϵ}_n$ is a positive sequence tending to zero as $n\to \infty$ at the rate of $\frac{log(log n)}{log n}$. The first inequality of (13) follows from (8). Obviously, this bound is essentially attained through LZ78 compression of x, followed by one-time pad encryption using $LZ\left(\mathit{x}\right)$ key bits. As can be seen, the gap, ${ϵ}_n$, between the upper bound and the lower bound on R is $O\left(\frac{log(log n)}{log n}\right)$, which tends to zero rather slowly.

Remark 2.

For an infinite sequence $\mathit{x}=x_0,x_1,x_2,\dots$, asymptotic results were obtained in [25] through a two-stage limit process: First, consider a finite sequence of total length $m·n$, which is divided into m non-overlapping n-blocks. The mechanism described above is applied to each n-block separately. The asymptotic minimum key rate is obtained by taking a double limit superior, first for $m\to \infty$ for a given n, and then for $n\to \infty$. In this work, we consider a similar double limit, although we do not explicitly mention it on every relevant occasion. Instead, we focus on the behavior of a single n-block.

3. More General Finite-State Discriminators

This section, which is the main section of this article, is devoted to describing several more general classes of finite-state discriminators, along with derivations of their respective more refined bounds.

3.1. FSMs with Counters

While Ziv’s model for a finite-state discriminator is adequate for rejecting sequences with certain forbidden patterns (like a succession of more than two zeroes in the above examples), it is not sufficient to handle situations like the following. Suppose that the encrypter applies a universal lossless compression algorithm for memoryless sources, followed by one-time pad encryption. Suppose also that the universal compression scheme is a two-part code, where the first part encodes the index of the type class of x, using a number of bits that is proportional to $log n$, and the second part represents the index of x within the type class, assuming that the encoder and the decoder have agreed on some ordering ahead of time. In this case, the length of the cryptogram (in bits), which is equal to the length of the compressed data, is about

$$L=H\left(K\right)\approx n\widehat{H}\left(\mathit{x}\right)+\frac{\alpha -1}{2}·log n,$$

(14)

where $\widehat{H}\left(\mathit{x}\right)$ is the empirical entropy of x (see, e.g., [3] and the references therein). The eavesdropper, being aware of the encryption scheme, observes the length L of the cryptogram and immediately concludes that x must be a sequence whose empirical entropy is

$$H_0=\frac{1}{n}·\left(L-\frac{\alpha -1}{2}·logn\right).$$

(15)

In other words, in this case,

$${\mathcal{A}}_n\left(W\right)={\mathcal{A}}_n=\left\{\widehat{\mathit{x}}:\widehat{H}\left(\widehat{\mathit{x}}\right)=H_0\right\}.$$

(16)

Therefore, every sequence whose empirical distribution pertains to empirical entropy different from $H_0$ should be rejected. To this end, our discriminator should be able to gather empirical statistics, namely to count occurrences of symbols (or, more generally, count combinations of symbols and states) and not just detect a forbidden pattern that might have occurred just once in x.

This motivates us to broaden the class of finite-state discriminators to be considered in the following way. We consider discriminators that consist of a next-state function,

$$z_{i+1}=g(z_i,{\widehat{x}}_i),$$

(17)

as before, but instead of the binary output function, f, as in [25], these discriminators are equipped with a set of $\alpha ·s$ counters that count the number of joint occurrences of all $(x,z)\in \mathcal{X}\times \mathcal{S}$ for $i=0,1,2,\dots ,n-1$, i.e.,

$$n(x,z)=\sum _{i=0}^{n-1}\mathcal{I}\{{\widehat{x}}_i=x,z_i=z\},x\in \mathcal{X},z\in \mathcal{S},$$

(18)

where $\mathcal{I}\left\{A\right\}$, for a generic event A, denotes its indicator function, namely $\mathcal{I}\left\{A\right\}=1$ if A is true; otherwise, $\mathcal{I}\left\{A\right\}=0$. A sequence $\widehat{\mathit{x}}$ is accepted (resp. rejected) if the matrix of counts, $\left\{n\right(x,z),x\in \mathcal{X},z\in \mathcal{S}\}$, satisfies (resp. violates) a certain condition. In the example in the previous paragraph, a sequence is accepted if

$$\widehat{H}\left(\widehat{\mathit{x}}\right)=\sum _{x\in \mathcal{X}}\frac{n\left(x\right)}{n}log\left(\frac{n}{n\left(x\right)}\right)=H_0,$$

(19)

where $n\left(x\right)={\sum }_{z\in \mathcal{S}}n(x,z)$. Ziv’s discriminator model is clearly a special case of this model: let $(x_{★},z_{★})$ be any combination of input and state such that $f(z_{★},x_{★})=1$ in Ziv’s model (that is, a “forbidden” combination). Then, in terms of the proposed extended model, a sequence is rejected whenever $n(x_{★},z_{★})\ge 1$.

Clearly, since $\mathit{x}\in {\mathcal{A}}_n$ and since membership in ${\mathcal{A}}_n$ depends solely on the matrix of counts, $\left\{n\right(x,z),x\in \mathcal{X},z\in \mathcal{S}\}$, it follows that all $\left\{\widehat{\mathit{x}}\right\}$ that share the same counts as those of x must also be members of ${\mathcal{A}}_n$. The set of all $\left\{\widehat{\mathit{x}}\right\}$ of length n with the same counts, $\left\{n\right(x,z),x\in \mathcal{X},z\in \mathcal{S}\}$, as those of x is called the finite-state type class with respect to the FSM g (see also [3]), and it is denoted by ${\mathcal{T}}_g\left(\mathit{x}\right)$. Since ${\mathcal{A}}_n\supseteq {\mathcal{T}}_g\left(\mathit{x}\right)$,

$$|{\mathcal{A}}_n|\ge |{\mathcal{T}}_g\left(\mathit{x}\right)|.$$

(20)

It was proven in [3] (in Lemma 3), that if $n(x,z)\ge n\left(z\right)\delta \left(n\right)$ for every $(x,z)\in \mathcal{X}\times \mathcal{S}$, where $\delta \left(n\right)>0$ may even be a vanishing sequence, then

$$|{\mathcal{T}}_g\left(\mathit{x}\right)|\ge {exp}_2\left\{n\widehat{H}\left(X\right|Z)-\frac{s(\alpha -1)}{2}·log\left(2\pi n\right)\right\},$$

(21)

where

$$\widehat{H}\left(X\right|Z)=-\sum _{x\in \mathcal{X}}\sum _{z\in \mathcal{S}}\frac{n(x,z)}{n}log\frac{n(x,z)}{n\left(z\right)},$$

(22)

with $n\left(z\right)={\sum }_{x\in \mathcal{X}}n(x,z)$ and with the conventions that $0log0\stackrel{▵}{=}0$ and $0/0\stackrel{▵}{=}0$. Therefore, it follows that the key rate needed for perfect secrecy is lower bounded by

$$\begin{array}{cc}\hfill R& =\frac{H\left(K\right)}{n}\hfill \\ \hfill & \ge \frac{log|{\mathcal{A}}_n|}{n}\hfill \\ \hfill & \ge \frac{log|{\mathcal{T}}_g\left(\mathit{x}\right)|}{n}\hfill \\ \hfill & \ge \widehat{H}\left(X\right|Z)-\frac{s(\alpha -1)}{2}·\frac{log\left(2\pi n\right)}{n}.\hfill \end{array}$$

(23)

This lower bound can be asymptotically attained through an encrypter that applies universal lossless compression for finite-state sources with the next-state function g, followed by one-time pad encryption. This universal lossless compression scheme is based on a conceptually simple extension of the above-mentioned universal scheme for the class of memoryless sources: one applies a two-part code, where the first part includes a code for the index of the type class with respect to g (using a number of bits that is proportional to $log n$), and the second part encodes the index of the location of $\widehat{\mathit{x}}$ within ${\mathcal{T}}_g\left(\mathit{x}\right)$ according to a predefined order agreed upon between the encoder and the decoder (see [3] for more details). More precisely, the compression ratio that can be achieved, which is also the key rate consumed, is upper bounded by (see Section III in [3]):

$$R\le \widehat{H}\left(X\right|Z)+\frac{s(\alpha -1)}{2}·\frac{log n}{n}+O\left(\frac{1}{n}\right),$$

(24)

which tells us that the gap between the lower bound and the achievability is proportional to $\frac{log n}{n}$, which decays much faster than the aforementioned $O\left(\frac{log(log n)}{log n}\right)$ convergence rate of the gap in Ziv’s approach. Moreover, for most sequences in most type classes, $\left\{{\mathcal{T}}_g\left(\mathit{x}\right)\right\}$, the coding rate (which is also the key rate in one-time pad encryption) of $\widehat{H}\left(X\right|Z)+\frac{s(\alpha -1)}{2}·\frac{log n}{n}$ is smaller than $LZ\left(\mathit{x}\right)/n$ since the former quantity is essentially also a lower bound to the compression ratio of any lossless compression scheme for most individual sequences in ${\mathcal{T}}_g\left(\mathit{x}\right)$ for almost all such type classes (see Theorem 1 in [3]). The converse inequality between $\widehat{H}\left(X\right|Z)$ and $LZ\left(\mathit{x}\right)/n$, which follows from Ziv’s inequality (see [28,29] (Lemma 13.5.5 in [28])) holds up to an $O\left(\frac{log(log n)}{log n}\right)$ term again.

Remark 3.

To put Ziv’s result in perspective, one may wish to envision a class of discriminators defined by a given dictionary of c distinct ‘words’, which are the c phrases in Ziv’s derivation [25] (see also Appendix A). A possible definition of such a discriminator is that it accepts only n-sequences of plaintext that are formed by concatenating words from the given dictionary, allowing repetitions. These are no longer finite-state discriminators. In this case, Ziv’s derivation is applicable under the minor modification that the various phrases should be classified only in terms of their length but without further partitioning according to initial and final states (z and $z^{\prime }$ in the derivation in Appendix A). This is equivalent to assuming that $s=1$, and accordingly, the term $\frac{2clog s}{n}$ in the last equation in Appendix A should be omitted. Of course, the resulting bound can still be matched through LZ78 compression, followed by one-time pad encryption.

3.2. Shift-Register Machines with Counters

Since the eavesdropper naturally does not cooperate with the encrypter, the latter might not know the particular FSM, g, used by the former, and therefore, it is instructive to derive key-rate bounds that are independent of g. To this end, consider the following. Given x and a fixed positive integer ℓ ($\mathsf{\ell }\ll n$), let us observe the more refined joint empirical distribution,

$${\widehat{P}}_{X^{\mathsf{\ell }+1}{Z}^{\mathsf{\ell }+1}}(a_0,\dots ,a_{\mathsf{\ell }},s_0,\dots ,s_{\mathsf{\ell }})=\frac{1}{n}\sum _{i=0}^{n-1}\mathcal{I}\{x_i=a_0,\dots ,x_{i\oplus \mathsf{\ell }}=a_{\mathsf{\ell }},z_i=s_0,\dots ,z_{i\oplus \mathsf{\ell }}=s_{\mathsf{\ell }}\},$$

(25)

as well as all partial marginalizations derived from this distribution, where ⊕ denotes addition modulo n so as to create a periodic extension of x (hence, redefining $z_0=g(z_{n-1},x_{n-1})$). Accordingly, the previously defined empirical conditional entropy, $\widehat{H}\left(X\right|Z)$, is now denoted as $\widehat{H}\left(X_1\right|Z_1)$, which is also equal to $\widehat{H}\left(X_2\right|Z_2)$, etc., due to the inherent shift-invariance property of the empirical joint distribution extracted under the periodic extension of x. Consider now the following chain of inequalities:

$$\begin{array}{ccc}& & \widehat{H}\left(X_{\mathsf{\ell }}\right|X_0,X_1,\dots ,X_{\mathsf{\ell }-1})-\widehat{H}\left(X_{\mathsf{\ell }}\right|Z_{\mathsf{\ell }})\hfill \end{array}$$

$$\begin{array}{ccc}& \le & \frac{1}{\mathsf{\ell }+1}\sum _{j=0}^{\mathsf{\ell }}[\widehat{H}\left(X_j\right|X_0,\dots ,X_{j-1})-\widehat{H}\left(X_j\right|X_0,\dots ,X_{j-1},Z_0)]\hfill \end{array}$$

(26)

$$\begin{array}{ccc}& =& \frac{1}{\mathsf{\ell }+1}[\widehat{H}(X_0,\dots ,X_{\mathsf{\ell }})-\widehat{H}(X_0,\dots ,X_{\mathsf{\ell }}|Z_0)]\hfill \end{array}$$

(27)

$$\begin{array}{ccc}& =& \frac{\widehat{I}(Z_0;X_0,\dots ,X_{\mathsf{\ell }})}{\mathsf{\ell }+1}\hfill \end{array}$$

(28)

$$\begin{array}{ccc}& \le & \frac{\widehat{H}\left(Z_0\right)}{\mathsf{\ell }+1}\hfill \end{array}$$

(29)

$$\begin{array}{ccc}& \le & \frac{logs}{\mathsf{\ell }+1},\hfill \end{array}$$

(30)

where $\widehat{I}(·;·)$ denotes empirical mutual information, and where in the second line, the term corresponding to $j=0$ should be understood to be $[\widehat{H}\left(X_0\right)-\widehat{H}\left(X_0\right|Z_0)]$. The first inequality follows because given $(X_0,\dots ,X_{j-1},Z_0)$, one can reconstruct $Z_1,Z_2,\dots ,Z_j$ through j recursive applications of the next-state function, g. Therefore,

$$\begin{array}{ccc}\hfill \widehat{H}\left(X_j\right|X_0,\dots ,X_{j-1},Z_0)& =& \widehat{H}\left(X_j\right|X_0,\dots ,X_{j-1},Z_0,Z_1,\dots ,Z_j)\hfill \end{array}$$

$$\begin{array}{ccc}& \le & \widehat{H}\left(X_j\right|Z_j)\hfill \end{array}$$

(31)

$$\begin{array}{ccc}& =& \widehat{H}\left(X_{\mathsf{\ell }}\right|Z_{\mathsf{\ell }}).\hfill \end{array}$$

(32)

Equivalently,

$$\widehat{H}\left(X_{\mathsf{\ell }}\right|Z_{\mathsf{\ell }})\ge \widehat{H}\left(X_{\mathsf{\ell }}\right|X_0,\dots ,X_{\mathsf{\ell }-1})-\frac{logs}{\mathsf{\ell }+1},$$

(33)

and by combining this with Equations (20) and (21), we obtain

$$log|{\mathcal{A}}_n|\ge n\left[\widehat{H}\left(X_{\mathsf{\ell }}\right|X_0,\dots ,X_{\mathsf{\ell }-1})-\frac{logs}{\mathsf{\ell }+1}\right]-\frac{s(\alpha -1)}{2}·log\left(2\pi n\right).$$

(34)

The advantage of this inequality is that it is independent of the arbitrary next-state function g. In fact, we actually replaced the arbitrary FSM, g, with a particular FSM—the shift-register FSM—whose state is $z_i=(x_{i-\mathsf{\ell }},x_{i-\mathsf{\ell }+1},\dots ,x_{i-1})$ at the cost of a gap of $\frac{logs}{\mathsf{\ell }+1}$, which can be kept arbitrarily small if the size of the shift-register, ℓ, is sufficiently large compared to the memory size, $logs$, of g.

Remark 4.

The fact that $\widehat{H}\left(X_{\mathsf{\ell }}\right|X_0,\dots ,X_{\mathsf{\ell }-1})$ cannot be much larger than $\widehat{H}\left(X_{\mathsf{\ell }}\right|Z_{\mathsf{\ell }})$ for large enough ℓ actually suggests that whatever the state of any FSM g can possibly “remember” from the past of x is essentially captured by the recent past, not by the remote past. While this is not surprising in the context of the probabilistic setting, especially if the underlying random process is ergodic and hence has a vanishing memory of the remote past, this finding is not quite trivial when it comes to arbitrary individual sequences.

Returning to our derivations, in view of the first three lines of (13), the key rate needed for perfect secrecy is lower bounded by

$$R\ge \frac{log|{\mathcal{A}}_n|}{n}\ge \widehat{H}\left(X_{\mathsf{\ell }}\right|X_0,\dots ,X_{\mathsf{\ell }-1})-\frac{logs}{\mathsf{\ell }+1}-\frac{s(\alpha -1)}{2n}·log\left(2\pi n\right),$$

(35)

and since this holds for any ℓ in some fixed range $1\le \mathsf{\ell }\le l$ (i.e., where l is independent of n),

$$R\ge \underset{1\le \mathsf{\ell }\le l}{max}\left[\widehat{H}\left(X_{\mathsf{\ell }}\right|X_0,\dots ,X_{\mathsf{\ell }-1})-\frac{logs}{\mathsf{\ell }+1}\right]-\frac{s(\alpha -1)}{2n}·log\left(2\pi n\right).$$

(36)

Note that if x is an “${\mathsf{\ell }}_0$-th order Markovian sequence” in the sense that $\widehat{H}\left(X_{\mathsf{\ell }}\right|X_0,\dots ,X_{\mathsf{\ell }-1})$ is almost fixed for all ${\mathsf{\ell }}_0\le \mathsf{\ell }\le l$ with $l\gg logs$, then ${\mathsf{\ell }}_0$ is the preferred choice for ℓ as it essentially captures the best attainable key rate.

This lower bound can be asymptotically attained through universal lossless compression for ℓ-th order Markov types [30,31,32] (see Section VII.A in [32]), followed by one-time pad encryption, where the achieved rate is

$$R\le \widehat{H}\left(X_{\mathsf{\ell }}\right|X_0,\dots ,X_{\mathsf{\ell }-1})+\frac{{\alpha }^{\mathsf{\ell }-1}(\alpha -1)}{2}·\frac{log n}{n}+O\left(\frac{1}{n}\right).$$

(37)

In this case, ${\mathcal{A}}_n$ is the ℓ-th order Markov type of x, and the finite-state discriminator of the eavesdropper is a shift-register machine, which checks whether the ℓ-th order Markov type of each $\widehat{\mathit{x}}$ has the matching empirical conditional entropy of order ℓ.

In this result, there is compatibility between the converse bound and the achievability bound in the sense that both are given in terms of FSMs with a fixed number of states that do not grow with n. Among all possible finite-state machines, we have actually singled out the shift-register machine universally with a controllable asymptotic gap of $\frac{logs}{\mathsf{\ell }+1}$. However, the bound is otherwise explicit, and it is clear how to approach it. If we wish to keep this gap below a given $ϵ>0$, we select $\mathsf{\ell }=\lceil (logs)/ϵ\rceil -1$. In this sense, it is another refinement of Ziv’s result.

3.3. Periodically Time-Varying FSMs with Counters

So far, we have considered time-invariant FSMs, where the function g remains fixed over time. We now expand the scope to consider the class of discriminators implementable by periodically time-varying FSMs, defined as follows:

$$\begin{array}{ccc}\hfill z_{i+1}& =& g(z_i,{\widehat{x}}_i,i\mathrm{mod}l),\hfill \end{array}$$

(38)

where $i=0,1,2,\dots$ and l is a positive integer that designates the period of the time-varying finite-state machine. Conceptually, this is not really more general than the ordinary, time-invariant FSM defined earlier because the state of the modulo-ℓ clock can be considered part of the entire state. In other words, this is a time-invariant FSM with $s·l$ states, indexed by the ordered pair $(z_i,imodl)$. The reason it makes sense to distinguish between the state $z_t$ and the state of the clock is that the clock does not store any information regarding past input data. This is to say that in the context of time-varying finite-state machines, we distinguish between the amount of memory of past input ($logs$ bits) and the period l. Both parameters manifest the richness of the class of machines but in different manners. Indeed, the parameters s and l play very different and separate roles in the converse bound derived below.

Remark 5.

Clearly, the earlier considered time-invariant finite-state machine is obtained as a special case through $l=1$, or through the case where l is arbitrary, but the next-state functions, $g(·,·,0),g(·,·,1),\dots ,g(·,·,l-1)$, are all identical.

First, observe that a periodic FSM with period l can be viewed as a time-invariant FSM at the level of l-blocks, $\{x_{il},x_{il+1},\dots ,x_{il+l-1}\}$, $i=0,1,\dots$, and hence also at the level of ℓ-blocks, where ℓ is an integer multiple of l. Accordingly, let ℓ be an arbitrary integer multiple of l, but at the same time, assume that ℓ divides n. Denote $m=n/\mathsf{\ell }$, and define the counts,

$$m(z,z^{\prime },x^{\mathsf{\ell }})=\sum _{i=0}^{n/\mathsf{\ell }-1}\mathcal{I}\{z_{i\mathsf{\ell }}=z,z_{i\mathsf{\ell }+\mathsf{\ell }}=z^{\prime },{\widehat{x}}_{i\mathsf{\ell }}^{i\mathsf{\ell }+\mathsf{\ell }-1}=x^{\mathsf{\ell }}\},z,z^{\prime }\in \mathcal{S},x^{\mathsf{\ell }}\in {\mathcal{X}}^{\mathsf{\ell }}.$$

(39)

In fact, there is a certain redundancy in this definition because $z^{\prime }$ is a deterministic function of $(z,x^{\mathsf{\ell }})$ obtained through ℓ recursive applications of the (time-varying) next-state function g. Concretely, $m(z,z^{\prime },x^{\mathsf{\ell }})=m(z,x^{\mathsf{\ell }})$ if $z^{\prime }$ matches $(z,x^{\mathsf{\ell }})$ and $m(z,z^{\prime },x^{\mathsf{\ell }})=0$ otherwise. Nonetheless, we adopt this definition for the sake of clarity of combinatorial derivation to be carried out shortly. In particular, our derivation is based on grouping together all $\left\{x^{\mathsf{\ell }}\right\}$, which, for a given z, yields the same $z^{\prime }$. Accordingly, we also denote $m(z,z^{\prime })={\sum }_{x^{\mathsf{\ell }}\in {\mathcal{X}}^{\mathsf{\ell }}}m(z,z^{\prime },x^{\mathsf{\ell }})$.

Suppose that the acceptance/rejection criterion that defines ${\mathcal{A}}_n$ is based on the counts, $\{m(z,z^{\prime },x^{\mathsf{\ell }}),z,z^{\prime }\in \mathcal{S},x^{\mathsf{\ell }}\in {\mathcal{X}}^{\mathsf{\ell }}\}$, and then the smallest ${\mathcal{A}}_n$ that contains x is the type class of x pertaining to $\{m(z,z^{\prime },x^{\mathsf{\ell }}),z,z^{\prime }\in \mathcal{S},x^{\mathsf{\ell }}\in {\mathcal{X}}^{\mathsf{\ell }}\}$. The various sequences in this type class are obtained by permuting distinct ℓ-tuples $\{{\widehat{x}}_{i\mathsf{\ell }}^{i\mathsf{\ell }+\mathsf{\ell }-1},i=0,1,\dots ,m-1\}$ that begin at the same state, z, and end at the same state, $z^{\prime }$. Let us define the empirical distribution as

$$\widehat{P}(z,z^{\prime },x^{\mathsf{\ell }})=\frac{m(z,z^{\prime },x^{\mathsf{\ell }})}{m},z,z^{\prime }\in \mathcal{S},a^{\mathsf{\ell }}\in {\mathcal{X}}^{\mathsf{\ell }},$$

(40)

and the joint entropy as

$$\widehat{H}(Z,Z^{\prime },X^{\mathsf{\ell }})=-\sum _{z,z^{\prime },x^{\mathsf{\ell }}}\widehat{P}(z,z^{\prime },x^{\mathsf{\ell }})log\widehat{P}(z,z^{\prime },x^{\mathsf{\ell }}),$$

(41)

and let

$$\widehat{H}\left(X^{\mathsf{\ell }}\right|Z,Z^{\prime })=\widehat{H}(Z,Z^{\prime },X^{\mathsf{\ell }})-\widehat{H}(Z,Z^{\prime }),$$

(42)

where $\widehat{H}(Z,Z^{\prime })$ is the marginal empirical entropy of $(Z,Z^{\prime })$. Then, using the method of types [32], we have:

$$\begin{array}{ccc}\hfill |{\mathcal{A}}_n|& \ge & \prod _{z,z^{\prime }\in \mathcal{S}}\frac{m(z,z^{\prime })!}{{\prod }_{x^{\mathsf{\ell }}\in {\mathcal{X}}^{\mathsf{\ell }}}m(z,z^{\prime },x^{\mathsf{\ell }})!}\hfill \end{array}$$

(43)

$$\begin{array}{ccc}& \ge & \prod _{z,z^{\prime }\in \mathcal{S}}\left[{(m+1)}^{-{\alpha }^{\mathsf{\ell }}}·{exp}_2\left\{\sum _{x^{\mathsf{\ell }}}m(z,z^{\prime },x^{\mathsf{\ell }})log\frac{m(z,z^{\prime })}{m(z,z^{\prime },x^{\mathsf{\ell }})}\right\}\right]\hfill \end{array}$$

(44)

$$\begin{array}{ccc}& \ge & {(m+1)}^{-s^2{\alpha }^{\mathsf{\ell }}}·2^{m\widehat{H}\left(X^{\mathsf{\ell }}\right|Z,Z^{\prime })}\hfill \end{array}$$

(45)

$$\begin{array}{ccc}& =& {(m+1)}^{-s^2{\alpha }^{\mathsf{\ell }}}·2^{m[\widehat{H}\left(X^{\mathsf{\ell }}\right)-I(Z,Z^{\prime };X^{\mathsf{\ell }})]}\hfill \end{array}$$

(46)

$$\begin{array}{ccc}& \ge & {(m+1)}^{-s^2{\alpha }^{\mathsf{\ell }}}·2^{m[\widehat{H}\left(X^{\mathsf{\ell }}\right)-H(Z,Z^{\prime })]}\hfill \end{array}$$

(47)

$$\begin{array}{ccc}& \ge & {(m+1)}^{-s^2{\alpha }^{\mathsf{\ell }}}·2^{m[\widehat{H}\left(X^{\mathsf{\ell }}\right)-2logs]}\hfill \end{array}$$

(48)

$$\begin{array}{ccc}& =& {exp}_2\left\{n\left[\frac{\widehat{H}\left(X^{\mathsf{\ell }}\right)}{\mathsf{\ell }}-\frac{2logs}{\mathsf{\ell }}-\frac{s^2{\alpha }^{\mathsf{\ell }}}{n}log\left(\frac{n}{\mathsf{\ell }}+1\right)\right]\right\},\hfill \end{array}$$

(49)

and so

$$R\ge \frac{log|{\mathcal{A}}_n|}{n}\ge \frac{\widehat{H}\left(X^{\mathsf{\ell }}\right)}{\mathsf{\ell }}-\frac{2logs}{\mathsf{\ell }}-\frac{s^2{\alpha }^{\mathsf{\ell }}}{n}log\left(\frac{n}{\mathsf{\ell }}+1\right),$$

(50)

which, for $\mathsf{\ell }\gg 2logs$, can be essentially matched through universal compression for block-memoryless sources and one-time pad encryption using exactly the same ideas as before. Once again, we have derived a lower bound that is free of dependence on the particular FSM, g. Recall that ℓ divides n and that it is also a multiple of l, but otherwise, ℓ is arbitrary. Hence we may maximize this lower bound with respect to ℓ subject to these constraints. Alternatively, we may rewrite the lower bound as

$$R\ge \underset{\{qdividesn/l\}}{max}\left\{\frac{\widehat{H}\left(X^{ql}\right)}{ql}-\frac{2logs}{ql}-\frac{s^2{\alpha }^{ql}}{n}log\left(\frac{n}{ql}+1\right)\right\}.$$

(51)

Clearly, in view of Remark 5, the above lower bound also applies to the case of a time-invariant FSM, g, but then there would be some mismatch between the upper and lower bounds because to achieve the lower bound, one must gather more detailed empirical statistics, namely empirical statistics of blocks together with states, rather than just single symbols with states.

4. Side Information

Some of the results presented in the previous sections extend to the case where side information (SI) is available to both the legitimate decrypter and the eavesdropper. In principle, it may or may not be available to the encrypter, and we consider first the case where it is available. We assume the SI sequence to be of length n, denoted by $\mathit{y}=(y_0,y_1,\dots ,y_{n-1})$, where $y_i\in \mathcal{Y}$, $i=0,1,\dots ,n-1$. It is related to the plaintext, x, to be encrypted, but like x, it is a deterministic, individual sequence. The SI alphabet $\mathcal{Y}$ is finite, and its cardinality, $\left|\mathcal{Y}\right|$, is denoted by $\beta$. Here, the acceptance set depends on y and is denoted accordingly by ${\mathcal{A}}_n\left(\mathit{y}\right)$. The encrypter is, therefore, a mapping $W=T(\mathit{x},\mathit{y},K)$, which is invertible given $(\mathit{y},K)$, allowing the decrypter to reconstruct $\mathit{x}=T^{-1}(W,\mathit{y},K)$.

Consider first a natural extension of Ziv’s model for a finite-state discriminator, which for $i=0,1,\dots ,n-1$, implements the recursion,

$$\begin{array}{ccc}\hfill u_i& =& f(z_i,{\widehat{x}}_i,y_i)\hfill \end{array}$$

(52)

$$\begin{array}{ccc}\hfill z_{i+1}& =& g(z_i,{\widehat{x}}_i,y_i).\hfill \end{array}$$

(53)

Similarly as before, the acceptance set, ${\mathcal{A}}_n\left(\mathit{y}\right)$ is the set of all $\left\{\mathit{x}\right\}$ that, in the presence of the given y, yield the all-zero output sequence, $\mathit{u}=(u_0,u_1,\dots ,u_{n-1})=(0,0,\dots ,0)$.

Let $c(\mathit{x},\mathit{y})$ denote the number of joint parsing phrases of

$$(\mathit{x},\mathit{y})=((x_0,y_0),(x_1,y_1),\dots ,(x_{n-1},y_{n-1}))$$

into distinct phrases, and let $c_l\left(\mathit{x}\right|\mathit{y})$ denote the number of occurrences of $\mathit{y}\left(l\right)$—the l-th distinct phrase of y—which is also the number of different phrases of x that appear jointly with $\mathit{y}\left(l\right)$. Let $c\left(\mathit{y}\right)$ denote the number of different $\left\{\mathit{y}\right(l\left)\right\}$, that is, ${\sum }_{l=1}^{c\left(\mathit{y}\right)}{c}_l\left(\mathit{x}\right|\mathit{y})=c(\mathit{x},\mathit{y})$. Finally, let $c_{lz{z}^{\prime }}\left(\mathit{x}\right|\mathit{y})$ denote the number of x-phrases that are aligned with $\mathit{y}\left(l\right)$, beginning at state z and ending at state $z^{\prime }$. Then, similarly as in the derivation in [25] (see also Appendix A),

$$|{\mathcal{A}}_n\left(\mathit{y}\right)|\ge \prod _{l=1}^{c\left(\mathit{y}\right)}\prod _{z,z^{\prime }}{c}_{lz{z}^{\prime }}{\left(\mathit{x}\right|\mathit{y})}^{c_{lz{z}^{\prime }}\left(\mathit{x}\right|\mathit{y})},$$

(54)

and so, defining the auxiliary RVs $(Z_l,Z_l^{\prime })$, $l=1,\dots ,c\left(\mathit{y}\right)$, as being jointly distributed according to

$$Q_l(z,z^{\prime })=\frac{c_{lz{z}^{\prime }}\left(\mathit{x}\right|\mathit{y})}{c_l\left(\mathit{x}\right|\mathit{y})},z,z\in \mathcal{S},$$

(55)

we have

$$\begin{array}{cc}\hfill log|{\mathcal{A}}_n\left(\mathit{y}\right)|& \ge \sum _{l=1}^{c\left(\mathit{y}\right)}\sum _{z,z^{\prime }}{c}_{lz{z}^{\prime }}\left(\mathit{x}\right|\mathit{y})log{c}_{lz{z}^{\prime }}\left(\mathit{x}\right|\mathit{y})\hfill \\ \hfill & =\sum _{l=1}^{c\left(\mathit{y}\right)}{c}_l\left(\mathit{x}\right|\mathit{y})\sum _{z,z^{\prime }}\frac{c_{lz{z}^{\prime }}\left(\mathit{x}\right|\mathit{y})}{c_l\left(\mathit{x}\right|\mathit{y})}\left[log\frac{c_{lz{z}^{\prime }}\left(\mathit{x}\right|\mathit{y})}{c_l\left(\mathit{x}\right|\mathit{y})}+log{c}_l\left(\mathit{x}\right|\mathit{y})\right]\hfill \\ \hfill & =\sum _{l=1}^{c\left(\mathit{y}\right)}{c}_l\left(\mathit{x}\right|\mathit{y})log{c}_l\left(\mathit{x}\right|\mathit{y})-\sum _{l=1}^{c\left(\mathit{y}\right)}{c}_l(\mathit{x},\mathit{y})H(Z_l,Z_l^{\prime })\hfill \\ \hfill & \ge \sum _{l=1}^{c\left(\mathit{y}\right)}{c}_l\left(\mathit{x}\right|\mathit{y})log{c}_l\left(\mathit{x}\right|\mathit{y})-2·\sum _{l=1}^{c\left(\mathit{y}\right)}{c}_l(\mathit{x},\mathit{y})logs\hfill \\ \hfill & =\sum _{l=1}^{c\left(\mathit{y}\right)}{c}_l\left(\mathit{x}\right|\mathit{y})log{c}_l\left(\mathit{x}\right|\mathit{y})-2c(\mathit{x},\mathit{y})logs\hfill \\ \hfill & \ge \sum _{l=1}^{c\left(\mathit{y}\right)}{c}_l\left(\mathit{x}\right|\mathit{y})log{c}_l\left(\mathit{x}\right|\mathit{y})-\frac{2nlogs}{(1-{ϵ}_n)logn},\hfill \end{array}$$

(56)

where the last inequality follows from [7] (see also Lemma 13.5.3 in [28]), with ${ϵ}_n=O\left(\frac{log(log n)}{log n}\right)$. This lower bound can be asymptotically attained through the conditional version of the LZ algorithm (see [33,34]), followed by one-time pad encryption. If y is unavailable to the encrypter, x can still be compressed into about

$$u\left(\mathit{x}\right|\mathit{y})=\sum _{l=1}^{c\left(\mathit{y}\right)}{c}_l\left(\mathit{x}\right|\mathit{y})log{c}_l\left(\mathit{x}\right|\mathit{y})$$

(57)

bits before one-time pad encryption, using Slepian–Wolf encoding (Section 15.4 in [28]) and reconstructing (with high probability) after decryption using a universal decoder that uses $u\left(\mathit{x}\right|\mathit{y})$ as a decoding metric (see [35]).

Unfortunately, and somewhat surprisingly, a direct extension of the results in Section 3.1 and Section 3.2 to the case with SI turns out to be rather elusive. The reason is the lack of a single-letter formula for the exponential growth rate of the cardinality of a finite-state conditional type class of x-vectors that is defined by joint counts of the form $n(x,y,z)={\sum }_{i=0}^{n-1}\mathcal{I}\{x_i=x,y_i=y,z_i=z\}$, even in the simplest special case where $z_i=x_{i-1}$. In a nutshell, this quantity depends on y in a complicated manner, which cannot be represented in terms of an empirical distribution of fixed dimension that does not grow with n. However, we can obtain at least a lower bound if we treat these cases as special cases of periodically time-varying FSMs with counters in view of Remark 5.

Finally, consider the class of discriminators implementable by periodically time-varying FSMs with SI, defined as follows:

$$\begin{array}{ccc}\hfill z_{i+1}& =& g(z_i,{\widehat{x}}_i,y_i,i\mathrm{mod}l),\hfill \end{array}$$

(58)

where $i=0,1,2,\dots$ and l is as in Section 3.3. The extension of the derivation in Section 3.3 is quite straightforward—one has to count the permutations of the ℓ-vectors of x that not only share the same initial and final states but are also aligned to the same ℓ-blocks of y. The resulting bound is given by:

$$R\ge \frac{log|{\mathcal{A}}_n\left(\mathit{y}\right)|}{n}\ge \frac{\widehat{H}\left(X^{\mathsf{\ell }}\right|Y^{\mathsf{\ell }})}{\mathsf{\ell }}-\frac{2logs}{\mathsf{\ell }}-\frac{s^2{\alpha }^{\mathsf{\ell }}{\beta }^{\mathsf{\ell }}}{n}log\left(\frac{n}{\mathsf{\ell }}+1\right),$$

(59)

which, for $\mathsf{\ell }\gg 2logs$, can be essentially matched through universal compression for block-memoryless sources in the presence of SI and one-time pad encryption. In the absence of SI at the encrypter, one may use universal Slepian–Wolf coding for block-memoryless sources, which is a direct extension of universal Slepian–Wolf coding for memoryless sources (see, e.g., [36]).