{'fraction_non_alphanumeric': 0.052496933590327664, 'fraction_numerical': 0.012160504643420361, 'mean_word_length': 4.289341983317887, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Secure Block Source Coding with Sequential Encoding

We introduce fundamental bounds on achievable cumulative rate distribution functions (CRDF) to characterize a sequential encoding process that ensures lossless or lossy reconstruction subject to an average distortion criterion using a non-causal decoder. The CRDF describes the rate resources spent sequentially to compress the sequence. We also include a security constraint that affects the set of achievable CRDF. The information leakage is defined sequentially based on the mutual information between the source and its compressed representation, as it evolves. To characterize the security constraints, we introduce the concept of cumulative leakage distribution functions (CLF), which determines the allowed information leakage as distributed over encoded sub-blocks. Utilizing tools from majorization theory, we derive necessary and sufficient conditions on the achievable CRDF for a given independent and identically distributed (IID) source and CLF. One primary result of this paper is that the concave-hull of the CRDF characterizes the optimal achievable rate distribution.


I. INTRODUCTION
In this paper, we consider a source coding problem with sequential encoding where a memoryless and independent and identically distributed (IID) source is communicated in chunks to a decoder, which uses lossless or lossy reconstruction, subject to a single-letter distortion constraint. The coding is done sequentially in sub-blocks, i.e., the whole source sequence is split into sub-blocks, which are sequentially observed by the encoder, while the decoder decodes all the sub-blocks at once. Hence, the encoding is causal in the sense that the encoder does not access future sub-blocks, whereas a joint decoding of all sub-blocks is considered for the decoder. We also consider security constraints on the sequential encoding to prevent the encoder from revealing too much information about the part of the IID source sequence that corresponds to the messages sent so far.
Sequential encoding the way we introduce it in this paper can be motivated by complexity, delay, or channel availability constraints. Consider, for instance, a system with low-end hardware for the encoder side so the encoder can only afford to process a limited amount of source information at a time because of storage or computational constraints. There may also be a delay constraint at the encoder side, in the sense that the encoder has to deliver a message within a specific time range. This latter scenario can be the case, for example, when the encoder works over a channel that is available only sporadically and at certain moments in time. Given available scheduling of the communication channel, corresponding to a particular cumulative rate distribution function (CRDF; see Definition 2), our new theory can tell whether this particular scheduling of the channel is achievable for source coding at a specified fidelity.
Practical scenarios for such scheduling problems include the case of a vehicle communicating time-series of measurements to the background radio access network following a resource management strategy taking varying coverage into account.
The information leakage constraint we introduce herein, corresponding to a given cumulative rate leakage function (CLF; see Definition 3), is motivated by the scenario where side information is available regarding the presence of an eavesdropper listening to the messages transmitted from the encoder so far. Alternatively, it can be motivated by a scenario where an eavesdropper is present throughout the transmission, and we wish to reveal information only according to the specific allowed patterns motivated by the application at hand. For example, in a sensor network, the source sequence can correspond to a long time-series of measurements to be communicated in sub-blocks at low cost to a central processing node. Such communication can happen over a relatively long time (hours or even days); so it may be beneficial to reveal the measurements, as little as possible, during the earlier times while allowing higher data leakage when the whole process is close to being finalized. Such a scenario can be motivated by not allowing a passive adversary to draw early conclusions that can pre-date the final decision made at the central processing node.
One major result of this paper is that the achievable CRDF subject to a certain given CLF reveals a fundamental rate allocation bound that depends only on the concave-hull of the rate profile. This result is useful in practice since it simplifies the design space for the optimization of resource allocation policies.
Literature Review: Classical rate-distortion theory was introduced in [2] and characterizes the fundamental trade-off between the achievable distortion and the rate of a non-causal encoder and decoder pair. An excellent overview of the classical results can be found, for instance, in [3].
A variant of classical rate-distortion function called the OPTA by causal codes was introduced in [4]. In that framework, reconstruction of the present source sample is restricted to be a function of the present and past source samples, while the code stream itself may be non-causal and have a variable rate. A generalization of [4] when the framework is allowed to have side information can be found in [5]. A subclass of causal source coding is zero-delay coding, where the encoder and decoder operate instantaneously, see, for example, [6]. Recently, causal and zero-delay source coding received particular attention by both information theorists and the control community.
The reason is that such compression schemes appear to be appropriate to derive fundamental performance limitations in closed-loop control systems, see, for example, [7], [8] and references therein. Causal and zero-delay source coding were also used in the context of source-channel coding applications, or source coding with finite memory, see, for example, [9]- [11]. Sequential source coding [12], [13] is also another kind of source coding, and it is similar to our framework when the number of the encoders tends to infinity. However, in contrast to that coding paradigm that aims to characterize the rate-region of finite encoders, here, besides the security constraint, we also characterize the rate profile of all the encoders when their number tends to infinity.
Shannon originally introduced the notion of security from an information-theoretical perspective in [14]. A few decades later, Wyner introduced the celebrated wiretap channel [15] and showed that it is possible to send information at a positive rate with perfect secrecy when eavesdropper's channel is a degraded version of the channel from the encoder to the decoder.
When it comes to secure communication via information-theoretic tools, often, two approaches are encountered in the literature. The first one presupposes that both encoder and decoder agree on a secret key before the transmission of the source. The second approach assumes that the decoder and the eavesdropper (sometimes the encoder as well) have different versions of side information, and thereby secrecy is achieved through this difference. For instance, Shannon, in [14], using the first approach, showed that the transmission of a discrete memoryless source is entirely secure if the rate of the key is at least as large as the entropy of the source. Yamamoto in [16] studied various secure source coding scenarios that include, among other results, an extension of Shannon's cipher system to combine secrecy with rate-distortion theory. Prabhakaran and Ramchandran in [17] considered lossless source coding with side information at both the decoder and the eavesdropper when there is no rate constraint between the encoder and the decoder. In [18], the authors considered a setup with side information at the encoder and coded side information at the decoder. Villard and Piantanida in [19] extended these works. The authors therein studied the problem of secure lossy source coding when one or both the receiver and the eavesdropper have side information. In [20], the authors considered secrecy in communication systems by the distortion that an adversary incurs. In their setups, both the transmitter and receiver share a secret key, which is used to encrypt communication and ensure distortion at the adversary. Kaspi and Merhav in [21] considered two source coding models combining causal or zero-delay source coding with secrecy constraints.
Majorization theory has been extensively used in communications and information theory. For instance, in [22], it was used to derive a broadcast approach for a single-user slow fading MIMO channel, and in [23], [24], it was used in the context of optimal rate allocation and transceiver design of vector-valued wireless communication systems. This paper is structured as follows. In Section II, we formally introduce CRDF, CLF, and our sequential source coding problems. We give our main results in Section III. In Section IV, we provide the derivations of the proofs. In Section V, we give some lemmas, which are utilized in the derivations of our main results. Finally, we draw conclusions in Section VI.
Notations: Sets, random variables (RVs) and their realizations are denoted by calligraphic, capital and lower case letters, respectively. The set of integer, rational and real numbers are denoted by N, Q and R, respectively. The probability mass function (PMF) of a random variable with realizations = defined on some alphabet X of finite cardinality |X| is denoted by ( ) or just ( ). Similarly, for two RVs and , the conditional PMF of given = is denoted by | ( | ) or just ( | ). The sequence ( , +1 , . . . , ), for , ∈ N, is denoted by . If = 1, we may use the notation instead of 1 . Also, 0 means ∅. The notation E[ ] means the expected value of RV . All logarithms are in base 2 unless otherwise stated. The term "w.r.t." is an abbreviation for "with respect to".

II. PROBLEM STATEMENT AND NEW DEFINITIONS
In this section, we define our problem formulation and some new definitions. As illustrated in Fig. 1  Because the function characterizes the cumulative rate, it is non-decreasing. There is no need to consider an available rate before the start of the sequence; so, it has zero initial value. We assume that the leakage is not reduced when time passes. It is also consistent with the definition of mutual information as the leakage (see Definitions 5, 6), i.e., ; ≥ ( −1) ; −1 . Hence, the leakage function is non-decreasing. Similar to CRDF, the leakage function has zero initial value.
Note that for a fixed number of sub-blocks , as → ∞, the samples of CRDF and CLF, at • a decoder, , that reconstructsˆbased on the output of the encoders, i.e., where ⊗ denotes the Cartesian product andX denotes the reconstruction domain.
Next, we introduce the definition of the achievable CRDFs for both lossless and lossy compression.
is a sequence of RVs, each with support X. A CRDF is said to be achievable to encode the sequence 1 , 2 , . . ., given CLF , in a lossless manner, if for any ∈ N, there exists a sequence of ( , , )-source codes for ∈ N, with output domainX = X, such that where (2) denotes the probability of error that tends to zero for any ∈ N as → ∞; (3) denotes the normalized amount of leakage of the first blocks, while the messages until the end of block have been measured.
Note that, there exist some CLF with no achievable CRDF. For example, for IID RVs, at least 1/( ) ≥ ( ) bits must be disclosed at the end of the whole block to satisfy (2) (due to the classical lossless source coding [25,Theorem 3.4]). Hence, if for a given CLF , we have (1) < ( ), then there is no feasible CRDF with CLF .
Definition 6 (Achievable CLF-secure CRDF for lossy compression). Assume that 1 , 2 , . . . is a sequence of RVs, each with support X. A CRDF is said to be achievable to encode the sequence 1 , 2 , . . ., given CLF and an average expected distortion level less than¯, if for any ∈ N, there exists a sequence of ( , , )-source codes, for ∈ N, with output supportX, such that where for the given distortion function : Similar to (3), (5) denotes the normalized amount of leakage of the first blocks, while the messages until the end of block have been measured.

III. MAIN RESULTS
In this section, we characterize the set of all achievable CRDFs for both lossless and lossy compression. We assume that the sequence of RVs is IID defined on a finite support domain. The essence of our sequential approach lies in that the rates available later can be used to compress previous source symbols; thus, the required rate to compress a sub-block can be split, and some parts can be sent later. To make this point clear, consider a rate profile { (1) } =1 that majorizes (for details on majorization, see Lemma 4) another rate profile { (2) } =1 , i.e., .
Then the achievability of { (1) } =1 implies the achievability of { (2) } =1 (see Lemma 2 for more details). Further, utilizing the fact that the rate-distortion function is convex, we use the majorization inequality (see Lemma 4) to show that if a rate profile is achievable, its concave-hull is also achievable.
The main idea behind the security constraint is that the encoder may not be allowed to use all the available rates at any time because more than allowed information would be revealed to the eavesdropper. Hence, the encoder must send some of the information later. Therefore, a given rate profile may not be effective in the sense that an amount of the allowable rate in some blocks must not be used to avoid revealing too much information. As a result, an effective CRDF is defined to identify the efficient amount of rate that can be used in the coding scheme with security constraints.
The following two theorems are the main results of this paper.
where is a RV with PMF ( ) over the finite domain X.
Proof: See Section IV-A.
Note that, for = 1 in (6), The idea on which the proof of Theorem 1 is based is that the amount of bits per symbol used to encode each block must be at least ( ). Hence, there is no need to use more than ( ) bits per symbol to compress the sequence in total. Therefore, we remove the rates of the first blocks, because the rates of the next blocks can compensate them (follows from Lemma 2).
We define effective CRDF¯e ff as The security constraint is also satisfied because¯e ff ( ) ≤ ( ) which follows from (6) (see the proof for the details). Hence, it should be possible to shift the rates of¯e ff such that ( ) bits per symbol are allocated to each block. Thus, the theorem follows.
In order to state the next theorem, we first need the following definitions. The ( ) and ( ) satisfy well-known functional and topological properties (see, for example [3], [27]). In the next remark, we state some of the most important of them as these properties used in the derivation of our main result.
Theorem 2 (Achievable region via lossy compression). Assume 1 , 2 , . . . is an IID sequence with PMF ( ) and the finite support X. Further, assume that a distortion function : X ×X → [0, ∞] is given and we have that the distortion-rate function, Then, the CRDF is achievable, given CLF , with distortion level¯, in the sense of Definition whereˆe ff : is the envelope of the function eff in the sense of Definition 7 and (·) is the distortion-rate function.
Proof: See Section IV-B.
In Fig. 2 we illustrate an example of the variables used in Theorem 2.
The idea behind Theorem 2 is that the minimum possible amount of distortion of each block, with˜available bits, is (˜). The amount of the leaked information is˜bits, which must be less than the CLF ; therefore, some rates of the CRDF must remain unused such that the effective rate becomes less than the CLF. Similar to Theorem 1, it follows from Lemma 2, that the best strategy is to remove the rates of the first blocks as the rates of the next blocks can compensate them. Therefore, the possible effective rate satisfying the security constraint is eff .
Regarding the distortion, since (·) is a convex function, utilizing the majorization inequality (see Lemma 4), it can be shown that the best possible rate profile, with causality constraint, iŝ eff , the concave-hull of the effective rate profile.
The next corollary states that, as expected, the result of Theorem 2 for Hamming distortion, with distortion 0, is the same as the result of Theorem 1. Corollary 1. An equivalent form of (6) in Theorem 1 is where eff is defined in (8). Further, (10) follows from (9)  Proof: See Section IV-C.
Based on Theorem 2, for a CRDF , only the concave hull of its effective rate,ˆe ff , is important. For instance, assume Hence, Therefore, both of them give the same result. So, in this case, due to the security constraint, increasing the rates does not help and they are redundant. Another example is as follows. Let However, we have thatˆe Thus, they have the same achievability results despite having different effective rate.
In what follows, we give two examples to demonstrate the utility of Theorem 2 and Corollary 1.
From Lemma 6, a CRDF is achievable, given CLF , with distortion¯, if and only if where eff is defined in (8). Intuitively, the result can be obtained from (11); to compress the source, with distortion¯≤ 1, we need to losslessly compress an arbitrary set of (1 −¯) symbols of the source, and do not compress the other symbols.
In our sequential framework, if eff is able to losslessly encode an arbitrary (1 −¯) symbols of the source, it is also able to encode the first (1 −¯) blocks of the source because the rates from last blocks can be used to encode the first blocks, but not the other way. Hence, the optimal way is to use all possible rates to losslessly encode the first (1 −¯) blocks.
Hence, from Corollary 1, we have where the first inequality follows from the fact that we use all eff (1) rates for the first (1 −¯) blocks; as a result, it is the same as having eff (1 −¯) = eff (1). An example is illustrated in for this problem is [28], [29] where is a RV with PMF ( ). From Lemma 6, we have that a CRDF is achievable, given CLF , with distortion¯, if and only if where eff is defined in (8). Intuitively, the result can be obtained from (12); to compress the source, with distortion¯≤ ( ), we need to send ( ) −¯bits per symbol of the source.
To do so, as we explained in the previous example, since the rates from last blocks can be used to encode the first blocks, but not the other way around, the optimal approach is to losslessly compress the first ( ( ) −¯)/ ( ) blocks of the source. Hence, from Corollary 1, we have where the first inequality follows from the fact that we use all eff (1)

IV. PROOFS
In this section, we prove the main results of the paper.

A. Proof of Theorem 1
First we prove the converse part, which claims that for any CRDF achievable with CLF , (6) must be satisfied. Then, we prove the achievability, which claims that if a CRDF satisfies (6), given CLF , then it is achievable.

B. Proof of Theorem 2
First we prove the converse part, which claims that if CRDF is achievable with CLF , then for any ∈ N, the sequence of ( , , )-source codes satisfying the distortion constraint must satisfy (9). After that, we prove the achievability part, which claims that if a CRDF satisfies (9) for a given CLF , then it is achievable. For the distortion, we use the following notation: Converse: The proof is divided in the following four steps. For an illustration, see Fig. 5. 1) In this step, we find a relation between the sequence˜, which characterizes the effective rate per block, i.e., the minimum rate needed to satisfy the distortion constraint of the corresponding block, and the sequence , which was defined in (1). We do not need to use all˜at the end of block and we can compress only a part of it at the end of the block and transfer the rates of the remaining part to the next blocks. This strategy helps to satisfy the leakage constraint. As a result, the sequence includes both a part˜, and the rates transfered from the previous blocks.
2) In this step, we find a relation between˜ and eff (which is defined later). The sequencẽ is generated from˜by increasing˜1 such that the sequence has the same total rate as the total effective rate of the sequence and by causally shifting the rates˜. Also, the sequence˜ satisfies the distortion constraint.
Formally, for any ∈ N, there exists a sequence˜ , for = 1, . . . , , such that where 3) In this step, we show that˜ majorizes the samples of the concave hull of eff ( / ) (denoted byˆ( / ) which is defined later). Then, using the majorization inequality (see Lemma 4), we show that the concave hull satisfies the distortion constraint.
Hence, by taking lim sup from both sides of (41), we obtain that where ( ) follows from the fact that, in the converse part, we assume that is achievable (see Definition 6).
Proof of (37): The claim follows from the following sequence of inequalities: where (42) follows since is independent of +1 , as a result, according to Definition 4, is independent of +1 ; the equality of (43) follows becauseˆ+ 1 is a function of ; the equality of (44) follows since the sequence { } is IID; the inequality of (45) follows based on the definition of (·) [27, p. 307]; and the inequality of (46) follows from the convexity of ( ) (see Corollary 1).
Proof of (38): The claim follows from the following sequence of inequalities: where, the equality of (47) follows since is independent of +1 , as a result, according to Definition 4, is independent of +1 ; (48) follows from the fact thatˆis a function of (see Definition 4); (49) follows from (5) Hence, we obtain Next, we define the sequence˜ , for = 1, . . . , , as Later, we show that Hence,˜ 1 ≥ 1 due to (53); as a result, {˜ } =1 is a valid sequence of rates.

Proof of (27): It follows from (55).
Proof of (28): Since the distortion-rate function (·) is non-increasing (see Remark 1),  (23), we obtain For = 1, . . . , − 1, from (22) and Definition 4, we obtain that, For = 0, first, note that where ( ) follows from (23). Hence, for = 0, it follows from (61) and the fact that with the abuse of notation that if + 1 > , the summation is assumed to be 0 and˜ 0 is an arbitrary finite number. Hence, from (26) and (27), we obtain that Hence, from (63), the definitions of and˜in (30) and (71), respectively, and the fact that eff is non-decreasing, we have that Since˜ 1 ≥ · · · ≥˜ ≥ 0, we obtain that the derivative of˜is non-increasing and non-negative; as a result,˜is concave and non-decreasing. Hence, from the definition of the envelope (see Definition 7), and the fact that˜is concave, we obtaiñ whereˆis the envelope of . By recalling Lemma 3, we obtain that Hence, utilizing (64) Therefore, for all = 1, . . . , − 1, we obtain where ( ) follows from (67) and the definition of˜in (71). Sinceˆis concave, we havê Therefore, utilizing the convexity of ( ) (see Remark 1) and the majorization inequality (see with the abuse of notation that if + 1 > , the summation is assumed to be 0 andˆ0 is an arbitrary finite number. Hence, where E is a set of the point at which the derivative ofˆe ff does not exist which is countable from Lemma 5. The reason that we removed the set of rational numbers is that it can be proved that the derivatives of are uniquely defined at all the irrational points and for all ∈ N.
Hence, E ∪ Q is countable and the dominated convergence theorem [30, Lemma 5.10] applies for this case.
Next, we prove that the limit of * exists and it converges to * as → ∞. First, we show show that, for any convergent subsequence, the limit of the subsequence is * because in this case lim sup →∞ * = lim inf →∞ * = * and the statement is proved.
Thus, without loss of generality, we assume that the convergent sequence is * itself, which it converges toˆ:ˆ= Therefore, utilizing (74), it suffices to show that as a result, since * is unique due to the existence and uniqueness of the derivative ofˆ( ), = * . From (75), we have that for all ≥ 0, * + ( * ) ≤ + ( ) where the ( ) follows from (73), and the fact that ( ) ≤ eff ( ) because (·) and, as a result, eff (·), are non-decreasing. Later, we show that Next, by taking the limit from both sides of the inequality and utilizing (76), we obtain that Therefore, to prove (77), it suffices to show that To this end, we make use of the following result which we prove later: Thus, we have that To prove (79), it is sufficient to show that If sup ∈[0,1] ( ) = (1), then it is clear that = 0 for all ; as a result claim is proved. Now, we study the case that sup ∈[0,1] ( ) > (1). Function is bounded because and are bounded. Therefore, Function is right continuous because both and are right continuous (see Definitions 2 and 3). Hence, It is clear that for all ≥ = 1/(2(min{1, + } − )) , there exist some ∈ N such that / ∈ [ , min{1, + }] (note that since < 1, the interval has infinite cardinality); as a result, | ( / ) − ( )| ≤ /2 for ≥ . Hence, where ( ) follows from the fact that ≤ | | for ∈ R. Thus, (82) follows from (83) and (84).

Otherwise, we consider three different cases
• Case 1 (ˆ= 1): Here we have that Consider the sequence = ( − 1)/ + 1/ . Therefore, we can write Thus, it is a contradiction with (87). Therefore, this case is not valid.
Thus, the derivation of the converse direction of the proof is complete.
Achievability: Utilizing Lemma 1, it is sufficient to prove that CRDF eff is achievable. We prove it in two steps: 1) CRDFˆe ff satisfies the distortion constraint (4), 2) CRDF eff satisfies both the leakage constraint (5) and distortion constraint (4).

Proof of
Step 1) For an arbitrary ∈ N, from Definition 4, we have for = 1, . . . , From the classical rate distortion theorem [25,Theorem 3.5], we obtain that there exists a memoryless encoder for each block such that Therefore, from (88) and (89) we obtain

Proof of
Step 2) From Lemma 2, we obtain that ifˆe ff satisfies the distortion constraint (4), then there exists a sequence of coding schemes satisfying (4) with CRDF eff . Hence, utilizing Step 1 of the achievability proof, we only need to show that eff satisfies the leakage constraint (5). To this end, we have that, for all ∈ {1, . . . , } and all ∈ N, where ( ) follows from the definition of eff in (8)  where ( ) follows by selecting = . Thus, the achievability is derived.

V. USEFUL LEMMAS
In this section, we state some lemmas utilized in the proofs of our results.
Proof: From Definition 2, it is clear that if 2 is a CRDF, 1 is a valid CRDF as well.
We assume that the decoder of ( 2 , , )-code is the same as the decoder of ( 1 , , )-code.
Hence, it only remains to prove (92).

From (91), it is clear that
. Therefore, {¯( 1) } =2 and {¯( 2) } =2 satisfy the induction assumption. As a result, there exists a set¯, for 2 ≤ ≤ ≤ such that To prove (92), we can write Thus, (92) and, as a result, the lemma is proved. . Hence, if we show thatˆ ( ) is concave, it will be a contradiction, and the result follows. We need to show that for all ≤ 1 < 2 ≤ and ∈ (0, 1) we haveˆ Hence, (93) follows from the concavity ofˆ.
Lemma 4 (Majorization Inequality). [31, p. 14] Consider two sequences 1 ≥ · · · ≥ and Then, for any convex function : Proof: We believe that the proof exists somewhere in the literature, but we did not find it.
Proof of (105): Sinceˆe ff is continuous and bounded, it has a maximum and is well-defined.

VI. CONCLUSIONS
In this work, we introduced the concept of achievable CRDF to characterize the rate profiles of the sequential encoding processes that ensure a secure lossless or lossy reconstruction subject to a fidelity criterion using a joint decoder. For IID sources, we derived a necessary and sufficient condition on the CRDF for a given IID source, which is characterized by the concave-hull of the CRDF. Further, we studied the case including a security constraint. The information leakage was defined sequentially based on the mutual information between the source and its compressed representation, as it evolves. To characterize the security constraints, we introduced the concept of CLF, which determines the allowed information leakage as distributed over encoded subblocks. Finally, we derived a necessary and sufficient condition on the achievable CRDF for a given IID source and CLF. We showed that the concave-hull of the effective CRDF, which is the amount of CRDF used in the compression, characterizes the optimal achievable rate distribution.