# An Encryption Technique for Provably Secure Transmission from a High Performance Computing Entity to a Tiny One

Authors: Miodrag J. Mihaljević; Aleksandar Kavčić; Kanta Matsuura
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

An encryption/decryption approach is proposed dedicated to one-way communication between a transmitter which is a computationally powerful party and a receiver with limited computational capabilities. The proposed encryption technique combines traditional stream ciphering and simulation of a binary channel which degrades channel input by inserting random bits. A statistical model of the proposed encryption is analyzed from the information-theoretic point of view. In the addressed model an attacker faces the problem implied by observing the messages through a channel with random bits insertion. The paper points out a number of security related implications of the considered channel. These implications have been addressed by estimation of the mutual information between the channel input and output and estimation of the number of candidate channel inputs for a given channel output. It is shown that deliberate and secret key controlled insertion of random bits into the basic ciphertext provides security enhancement of the resulting encryption scheme.


---

## Body

## 1. Introduction

It is well recognized that communications should be secure and accordingly encrypted in order to avoid misuse of the transmitted information. Consequently, contemporary cryptographic algorithms for encryption play a very important role in data communication systems for various areas of applications. A particular challenge is related to addressing the resource constrained environments, where the requirements include lightweight algorithms and hardware designs. To select a suitable encryption algorithm for an application or an environment, the algorithmic requirements as well as the implementation constraints have to be taken into account. This is also in line with a discussion recently reported in [1].On the other hand, in a number of scenarios the communication parties are with very different capabilities: one party could be with a tiny capability and the other with much higher ones. As an illustration, we point to a communication scenario over the Internet of Things (IoT) where a tiny machine (a tiny sensor, e.g.) should communicate with a more powerful one (sink of a sensor network or a gate, e.g.). According to the current state of the art, the following two problems appear as the still open ones: (i) developing encryption/decryption techniques which take into account asymmetric capabilities of the entities involved in encryption/decryption and (ii) enhancing cryptographic security of encryption in a lightweight and provable manner.Consequently, in this paper we consider the problem of designing a dedicated encryption/decryption algorithm which fits into the communications scenarios which include the following: (i) a high performance computing party should deliver encrypted messages in a one-way communication scenario to a number of parties which have tiny computational capabilities; (ii) implementation limitations at the tiny entity imply employment of a lightweight keystream generator (from certain reported lightweight stream ciphers); (iii) developed encryption scheme should have enhanced security in comparison with the one offered by the employed keystream generator.A certain number of reported encryption approaches jointly employ elements of traditional stream ciphers and elements of coding theory as well as features of certain communication channels (see, e.g., [2–8]), and this paper follows the same track. We consider an encryption approach which involves a communication channel with the synchronization errors which appear in the form ofinserted bits. In this approach, the transmitting/encrypting side requires a source of random bits and capability to insert them between message bits. Under the assumption that the transmitter has a method to inform the intended receiver about thelocations (and not necessarily the values) of the inserted random bits, the intended receiver can perform decimation (i.e., discard the inserted bits) of the obtained sequence so that it can be a subject of simple traditional decryption.Summary of the Results. This paper focuses on the following two issues which have not been addressed in the literature: (i) developing of an encryption/decryption technique which has asymmetric implementation complexity and provides lightweight decryption and (ii) security enhancement of the involved keystream generator employing paradigm of the binary channels with random insertions. An encryption/decryption technique for data transfer between a computationally powerful party and a party with limited computational capabilities is proposed which provides a trade-off between implementation complexities at the involved parties: the implementation overhead is reduced at the low-capability party at the expense of a higher (but still moderate) one at the party with high capabilities. In order to achieve security enhancement of the employed traditional keystream generator the proposed encryption technique at the transmitting side involves a simulator of the binary channel with synchronization errors. Security enhancement of encryption archived by the proposed scheme in comparison with the security of the employed keystream generator is based on the design paradigm and results on the mutual information between inputs and outputs of the channels with bit insertion.Organization. The paper is organized as follows. In Section 2, we give the underlying ideas for the design and proposal of an encryption/decryption framework. In Section 3, we provide some information-theoretic results for the proposed scheme; that is, we mostly derive various mutual information rates of interest for the security evaluation. In Section 4, we provide the cryptographic security evaluation based on implications which link the information-theoretic quantities to computational complexity based ones. Accordingly, Sections 5 and 6 provide evaluation of the computational complexity security enhancement employing numerical estimation of the mutual information and enumeration of input candidates for the given output after a binary channel with insertion of random bits, respectively. (Also note that this paper is a significantly revised and expanded version of [8].)


## 2. A Proposal of a Dedicated Encryption Technique

This section proposes an encryption/decryption technique which provides asymmetric implementation complexity at the communicating parties and provably enhanced cryptographic security. Both asymmetric implementation complexity and enhanced security appear as a consequence of the design based on employment of a simulator for binary channels with insertion errors.


### 2.1. Underlying Ideas

Our main design goals/approaches could be summarized as follows:(i)
Enhance security based on information-theoretic and coding results over channels with synchronization errors.
(ii)
Assuming that Party I is more powerful than Party II move the more complex operations to the side of Party I without implications on the cryptographic security.This paper proposes a stream cipher developed based on the following two construction principles: (i) adjustment of the construction to the asymmetric capabilities of the involved parties; (ii) employment of the results regarding binary channels with insertion errors for enhancing security. The goals are that the party with more powerful resources performs more complex operations and that the entire scheme provides a highly and provably secure level of cryptographic security resulting from the employment of the insertion communications channel paradigm.Our design is based on employment of the following building blocks:(i)
a lightweight binary keystream generator;
(ii)
a block for insertion (embedding)t random bits into a given n-dimensional binary vector;
(iii)
a block for decimation of a given(
n
+
t
)-dimensional binary vector which selects certain n-bits.Accordingly, we assume that the employed keystream generator outputs certain pseudo-random sequences denoted asC
n and G
′
n. Also, we assume that a deterministic mapping exists which maps a given G
′
n into G
n. We assume that the message M
n is additively combined (i.e., encrypted) with the shared pseudo-randomness C
n to obtain X
n, that is,(1)
X
n
=
M
n
⊕
C
n
,and X
n is subject of further mapping by a simulated binary channel with random insertions where positions of random bits embedding are specified by G
n so that the channel outputs Y
(
n
). The intended receiver (Bob), knowing both C
n and G
n, can easily decimate Y
(
n
) to obtain X
n and further perform M
n
=
X
n
⊕
C
n, to obtain the message M
n.Since Bob can easily recover the transmitted message using a simple decimation technique, the system requires no special hardware overhead for decryption. This is especially useful if the intended receiver is a low-power device. On the transmitter’s side encryption requires simulation of a binary channel with insertion errors and the transmitter needs to send(
1
-
i
)
-
1 times more symbols than it otherwise would, which means that the power consumption of the transmitter goes up by a factor of (
1
-
i
)
-
1. Hence, it may be reasonable to use this scheme when the transmitter is a high computational/power device and the receiver is a low computation/power device. In essence, a properly adjusted synchronization error scheme (an insertion scheme) seems to be well suited for a resources-asymmetric communication scenario in which a base station has ample resources while each of the numerous distributed nodes has severely constrained resources.


### 2.2. Framework for Encryption and Decryption

This section proposes an encryption/decryption technique for one-way communication from a transmitting party with high computational and other resources towards a receiving party with limited computational capabilities. Accordingly, the design follows the asymmetric implementation and execution constraints and the requirement regarding provable security.As usual, it is assumed that encryption and decryption parties share a secret key and that before a transmission session, based on the common secret key and the public data, both parties (encryption and decryption ones) establish a session key to be used for the transmission session.The encryption/decryption technique is designed employing the following components:(a)
Encryption side:
(i)
a lightweight stream cipher (keystream generator);
(ii)
a block which provides deterministic mapping (see Figure1) of a given keystream segment of dimension n
+
t into a vector with predetermined weight equal to t, that is, with a number of ones equal to t which determines positions of the embedded bits;
(iii)
a simulator of a binary channel with random bits insertions controlled by keystream generator which performs mapping{
0,1
}
n
→
{
0,1
}
n
+
t.
(b)
Decryption side:
(i)
a lightweight stream cipher (keystream generator);
(ii)
a block for deterministic mapping of a given keystream segment into a vector with predetermined weight, that is, the number of ones, the same as that at the encryption side;
(iii)
a block for decimation controlled by keystream generator which performs mapping{
0,1
}
n
+
t
→
{
0,1
}
n.Figure 1
Encryption/decryption technique for scenarios with one-way communications between the entities with high performance computing capabilities and the very tiny ones.We assume that implementation and execution complexity of a keystream controlled simulator of a binary channel with random insertions is highly dominant in the considered encryption/decryption scheme.Assuming thatn and t are the parameters, for specification of the proposed encryption/decryption, the following notation is employed:(i)
M is n-dimensional binary vector of data which should be encrypted;
(ii)
C is n-dimensional binary vector of keystream for stream ciphering;
(iii)
G
′ is (
n
+
t
)-dimensional binary vector of keystream nonoverlapping with C;
(iv)
G is (
n
+
t
)-dimensional binary vector of the weight exactly t obtained by a deterministic mapping of G
′;
(v)
X is n-dimensional binary vector defined as X
=
M
⊕
C;
(vi)
Y is (
n
+
t
)-dimensional binary vector which is equal to X with t inserted random bits.The proposed encryption/decryption is displayed in Figure1.


## 2.1. Underlying Ideas

Our main design goals/approaches could be summarized as follows:(i)
Enhance security based on information-theoretic and coding results over channels with synchronization errors.
(ii)
Assuming that Party I is more powerful than Party II move the more complex operations to the side of Party I without implications on the cryptographic security.This paper proposes a stream cipher developed based on the following two construction principles: (i) adjustment of the construction to the asymmetric capabilities of the involved parties; (ii) employment of the results regarding binary channels with insertion errors for enhancing security. The goals are that the party with more powerful resources performs more complex operations and that the entire scheme provides a highly and provably secure level of cryptographic security resulting from the employment of the insertion communications channel paradigm.Our design is based on employment of the following building blocks:(i)
a lightweight binary keystream generator;
(ii)
a block for insertion (embedding)t random bits into a given n-dimensional binary vector;
(iii)
a block for decimation of a given(
n
+
t
)-dimensional binary vector which selects certain n-bits.Accordingly, we assume that the employed keystream generator outputs certain pseudo-random sequences denoted asC
n and G
′
n. Also, we assume that a deterministic mapping exists which maps a given G
′
n into G
n. We assume that the message M
n is additively combined (i.e., encrypted) with the shared pseudo-randomness C
n to obtain X
n, that is,(1)
X
n
=
M
n
⊕
C
n
,and X
n is subject of further mapping by a simulated binary channel with random insertions where positions of random bits embedding are specified by G
n so that the channel outputs Y
(
n
). The intended receiver (Bob), knowing both C
n and G
n, can easily decimate Y
(
n
) to obtain X
n and further perform M
n
=
X
n
⊕
C
n, to obtain the message M
n.Since Bob can easily recover the transmitted message using a simple decimation technique, the system requires no special hardware overhead for decryption. This is especially useful if the intended receiver is a low-power device. On the transmitter’s side encryption requires simulation of a binary channel with insertion errors and the transmitter needs to send(
1
-
i
)
-
1 times more symbols than it otherwise would, which means that the power consumption of the transmitter goes up by a factor of (
1
-
i
)
-
1. Hence, it may be reasonable to use this scheme when the transmitter is a high computational/power device and the receiver is a low computation/power device. In essence, a properly adjusted synchronization error scheme (an insertion scheme) seems to be well suited for a resources-asymmetric communication scenario in which a base station has ample resources while each of the numerous distributed nodes has severely constrained resources.


## 2.2. Framework for Encryption and Decryption

This section proposes an encryption/decryption technique for one-way communication from a transmitting party with high computational and other resources towards a receiving party with limited computational capabilities. Accordingly, the design follows the asymmetric implementation and execution constraints and the requirement regarding provable security.As usual, it is assumed that encryption and decryption parties share a secret key and that before a transmission session, based on the common secret key and the public data, both parties (encryption and decryption ones) establish a session key to be used for the transmission session.The encryption/decryption technique is designed employing the following components:(a)
Encryption side:
(i)
a lightweight stream cipher (keystream generator);
(ii)
a block which provides deterministic mapping (see Figure1) of a given keystream segment of dimension n
+
t into a vector with predetermined weight equal to t, that is, with a number of ones equal to t which determines positions of the embedded bits;
(iii)
a simulator of a binary channel with random bits insertions controlled by keystream generator which performs mapping{
0,1
}
n
→
{
0,1
}
n
+
t.
(b)
Decryption side:
(i)
a lightweight stream cipher (keystream generator);
(ii)
a block for deterministic mapping of a given keystream segment into a vector with predetermined weight, that is, the number of ones, the same as that at the encryption side;
(iii)
a block for decimation controlled by keystream generator which performs mapping{
0,1
}
n
+
t
→
{
0,1
}
n.Figure 1
Encryption/decryption technique for scenarios with one-way communications between the entities with high performance computing capabilities and the very tiny ones.We assume that implementation and execution complexity of a keystream controlled simulator of a binary channel with random insertions is highly dominant in the considered encryption/decryption scheme.Assuming thatn and t are the parameters, for specification of the proposed encryption/decryption, the following notation is employed:(i)
M is n-dimensional binary vector of data which should be encrypted;
(ii)
C is n-dimensional binary vector of keystream for stream ciphering;
(iii)
G
′ is (
n
+
t
)-dimensional binary vector of keystream nonoverlapping with C;
(iv)
G is (
n
+
t
)-dimensional binary vector of the weight exactly t obtained by a deterministic mapping of G
′;
(v)
X is n-dimensional binary vector defined as X
=
M
⊕
C;
(vi)
Y is (
n
+
t
)-dimensional binary vector which is equal to X with t inserted random bits.The proposed encryption/decryption is displayed in Figure1.


## 3. Information-Theoretic Analysis

This section yields an information-theoretic analysis of a (statistical) model of the considered encryption displayed in Figure1.A random variable is denoted by an uppercase letter (e.g.,X) and its realization is denoted by a lowercase letter (e.g., x). An index (subscript) denotes discrete time. A discrete-time sequence of n random variables, for example, X
1
,
X
2
,
…
,
X
n, is shortly denoted by X
n
=
X
1
,
X
2
,
…
,
X
n. Since our channel has synchronization errors, we have a need to distinguishstrings fromsequences. We denote a random string (indexed by discrete-time k) as Y
(
k
). The string Y
(
k
) may not have a fixed length, and we denote its length (which is a random variable if the string itself is a random variable) as L
Y
(
k
). A concatenation of two strings a and b is denoted by a
∥
b. As short notation, we denote the concatenation of n strings Y
(
1
) through Y
(
n
) as Y
(
n
)
=
Y
(
1
)
∥
Y
(
2
)
∥
⋯
∥
Y
(
n
). The entropy of a random object X is denoted by H
(
X
), and the mutual information between two random objects X and Y is denoted by I
(
X
;
Y
). The binary entropy function is denoted by h
(
p
)
=
-
p
log
2
⁡
p
-
1
-
p
log
2
⁡
(
1
-
p
).Let the channel inputX
k be a binary random variable drawn from the alphabet X
=
0,1. The vector of all channel inputs up to time n is denoted by X
n
≜
X
1
,
X
2
,
…
,
X
n. The transmitter (Alice) observes the pseudo-random sequence G
n
≜
G
1
,
G
2
,
…
,
G
n provided by a shared source of randomness (shared with Bob) and uses it to create a channel output (ciphertext) Y
(
n
). Even though G
n is a pseudo-random sequence, we assume that the variables G
k are statistically indistinguishable from independent and identically distributed (iid)geometric random variables with parameter i; that is, for any integer l
≥
0, we have(2)
P
r
G
k
=
l
=
1
-
i
i
l
.Here, the parameter i denotes theinsertion probability. Namely, between any two symbols X
k and X
k
+
1, Alice inserts a string B
(
k
) that consists of Bernoulli-1
/
2 random variables, such that the length of B
(
k
) equals L
B
(
k
)
=
G
k. Since G
n is a sequence of iid geometric random variables with parameter i, it is clear that Alice’s transmission scheme is equivalent to randomly inserting a Bernoulli-1
/
2 random variable at any point of time during the communication. Formally, we state that Alice creates astring
Y
(
n
) obtained as aconcatenation of individual strings Y
(
1
)
,
Y
(
2
)
,
…
,
Y
(
n
), that is, (3)
Y
n
=
Y
1
∥
Y
2
∥
⋯
∥
Y
n
,where each individual string Y
(
k
) is obtained as(4)
Y
k
=
X
k
∥
B
k
.The length of the string Y
(
n
) equals(5)
L
Y
n
=
n
+
∑
k
=
1
n
G
k
,
E
L
Y
n
=
n
1
-
i
;that is, on average, Alice inserts i
/
1
-
i Bernoulli-1
/
2 random variables between any two symbols X
k and X
k
+
1.Eve (the eavesdropper) and Bob (the intended receiver) both receive the stringY
(
n
) containing the randomly inserted symbols. The eavesdropper, not having access to the shared source of randomness G
n, cannot easily parse the string Y
(
n
) to recover X
n. The intended receiver, on the other hand, has access to G
n, and since G
k represents the length of the inserted string between any two symbols X
k and X
k
+
1, the intended receiver (Bob) can easily remove the inserted symbols B
_
k from Y
(
n
) (i.e., decimate Y
(
n
)) to recover X
n. In other words, by sharing the source of randomness G
n, Bob can resynchronize himself with Alice; see Figure 1.The sequenceC
n is a pseudo-random sequence, but for the purpose of computing information-theoretic quantities, we assume that C
n is modeled to be statistically indistinguishable from a sequence of iid Bernoulli-1
/
2 random variables. (It should not be understood that C
n implements a one-time pad. The variables C
k are onlystatistically modeled as Bernoulli-1
/
2 for the purposes of deriving (and computing) some information-theoretic quantities that we later use to derive a cryptographic security measure.)Here, no assumptions are made on the statistical properties of the messageM
n, but because C
n is iid Bernoulli-1
/
2, we have that X
n is also iid Bernoulli-1
/
2. Hence, the information-theoretic quantity of interest is theiud information rate defined as the information rate between X
n and Y
(
n
) when the symbols X
k are independent and uniformly distributed (iud):(6)
I
i
u
d
X
;
Y
≜
l
i
m
n
→
∞
1
n
I
X
n
;
Y
n
p
x
n
=
2
-
n
.The information rate I
i
u
d
X
;
Y represents the amount of information that the eavesdropper can “learn,” on average, about X after observing Y. The information rate I
i
u
d
X
;
Y is not computable in closed-form but is attainable using Monde Carlo techniques. For example, known bounds are [10](7)
I
i
u
d
X
;
Y
≥
1
n
I
X
n
;
Y
n
p
x
n
=
2
-
n
-
1
n
H
L
Y
n
,
(8)
I
i
u
d
X
;
Y
≤
1
n
I
X
n
;
Y
n
p
x
n
=
2
-
n
.For large n, the correction term 1
/
n
H
L
Y
(
n
) in (7) equals(9)
1
n
H
L
Y
n
=
1
2
n
log
2
⁡
2
π
e
·
i
·
n
1
-
i
2
+
O
n
-
2
.If our desired accuracy of computing (bounding) I
i
u
d
X
;
Y is 1
0
-
4 and if i
=
0.95, considerations of (7)–(9) dictate that n
≥
1.5
·
1
0
5. For details on how to compute I
i
u
d
X
;
Y using “rhomboidal” trellis techniques such that both the desired correction term (9) and the confidence interval are kept under a predetermined accuracy (e.g., 1
0
-
4), see [10]. Here, we only give numerical results in Figure 2, which reveal that the information rate I
i
u
d
X
;
Y is only a small fraction of the entropy rate H
(
X
k
)
=
1, especially when i
>
0.5. These results are very favorable for secret communication because only a small fraction of the uncertainty in X
n can be learned from observing Y
(
n
), as the next section demonstrates.Figure 2
Information rateI
i
u
d
X
;
Y as a function of insertion probability i.We already established that learningX after observing Y is extremely unfavorable for the eavesdropper because the information rate I
i
u
d
X
;
Y is low for large insertion probabilities i. However, the eavesdropper may adopt a strategy in which she first attempts tolearn the sequence G
n and then attempt to crack X
n. To study the effects of this strategy, let us define the following quantities:(10)
I
i
u
d
G
;
Y
≜
lim
n
→
∞
⁡
1
n
I
G
n
;
Y
n
p
x
n
=
2
-
n
,
I
i
u
d
X
,
G
;
Y
≜
lim
n
→
∞
⁡
1
n
I
X
n
,
G
n
;
Y
n
p
x
n
=
2
-
n
,
I
i
u
d
X
;
Y
∣
G
≜
lim
n
→
∞
⁡
1
n
I
X
n
;
Y
n
∣
G
n
p
x
n
=
2
-
n
,
I
i
u
d
G
;
Y
∣
X
≜
lim
n
→
∞
⁡
1
n
I
G
n
;
Y
n
∣
X
n
p
x
n
=
2
-
n
.Proposition 1.
Consider(11)
I
i
u
d
G
;
Y
=
0
,
(12)
I
i
u
d
X
;
Y
∣
G
=
1
,
(13)
I
i
u
d
X
,
G
;
Y
=
1
,
(14)
I
i
u
d
G
;
Y
∣
X
=
1
-
I
i
u
d
X
;
Y
.Proof.
First, notice that(15)
lim
n
→
∞
⁡
H
Y
n
n
=
1
1
-
ibecause Y
(
n
) is a string of Bernoulli-1
/
2 random variables whose length is L
Y
(
n
), and as n
→
∞, we have(16)
lim
n
→
∞
⁡
L
Y
n
n
=
w
p
1
E
L
Y
n
n
=
1
1
-
i
.Next, we also have (17)
lim
n
→
∞
⁡
H
Y
n
∣
G
n
n
=
n
+
E
∑
k
=
1
n
G
k
n
=
1
1
-
i
,and (11) is now a direct consequence of (15) and (17). Equality (12) follows from the fact that X
n is uniquely determined (by decimation) if G
n and Y
(
n
) are known; that is, H
X
n
∣
G
n
,
Y
(
n
)
=
0. Finally, (13) follows by adding (11) to (12) and applying the chain rule for mutual information, and (14) follows from (13) also using the chain rule.By equality (11) of Proposition 1, it is clear that the eavesdropper cannot learn G
n simply by observing Y
(
n
). Also, from Figure 2, it is clear that, from the eavesdropper’s perspective, learning X
n from Y
(
n
) is extremely unfavorable because she can only learn a small fraction I
i
u
d
X
;
Y of H
(
X
)
≜
H
(
X
k
)
=
1 by observing Y
(
n
). However, equality (12) of Proposition 1 reveals a potential vulnerability in that if the eavesdropper were to somehow learn G
n, then secrecy would be lost because I
i
u
d
X
;
Y
∣
G
=
H
(
X
)
=
1. Since learning either G
n or X
n
individually is not favorable to the eavesdropper, the eavesdropper’s strategy could be to go after the pair (
X
,
G
). Indeed, equality (13) of Proposition 1 reveals that, theoretically, the eavesdropper could gain substantial knowledge of the pair (
X
,
G
) by observing Y
(
n
). Even for large i, this posterior knowledge of the pair (
X
,
G
), quantified as I
i
u
d
X
,
G
;
Y, is not a negligible fraction of the entropy(18)
H
X
,
G
≜
H
X
k
+
H
G
k
=
1
+
h
i
1
-
i
.In the next section, we further explore the cryptographic implications by studying the connection between computational complexity and the information-theoretic quantities.


## 4. Generic Framework for the Security Evaluation

Note that the above information-theoretic analysis is based on modeling the pseudo-random sequenceC
n as a random sequence. In this section, we now take into account the fact that the sequence is indeed pseudo-random. We show that the considered encryption (see Figure 1) based on employing the binary insertion channel X
n
→
Y
(
n
) provides enhanced security compared to the basic scheme that outputs only X
n.


### 4.1. Preliminaries: Security Notation

A definition of security consists of two distinct components: a specification of the assumed power of the adversary and a description of what constitutes a “break” of the scheme. Generally speaking, a cryptographic scheme is secure in a computational sense, if, for every probabilistic polynomial-time adversaryA carrying out an attack of some specified type and for every polynomial p
(
n
), there exists an integer N such that the probability that A succeeds in this attack (where success is also well defined) is less than 1
/
p
(
n
) for every n
>
N. Accordingly, the following two definitions specify a security evaluation scenario and a security statement.Definition 2.
The adversarial indistinguishability experiment consists of the following steps:(1)
The adversaryA chooses a pair of messages (
m
0
;
m
1
) of the same length n and passes them onto the encryption system for encrypting.
(2)
A bitb
∈
{
0,1
} is chosen uniformly at random, and only one of the two messages (
m
0
;
m
1
), precisely m
b, is encrypted into ciphertext E
n
c
(
m
b
) and returned to A.
(3)
Upon observingE
n
c
(
m
b
), and without knowledge of b, the adversary A outputs a bit b
0.
(4)
The experiment output is defined to be 1 ifb
0
=
b, and 0 otherwise; if the experiment output is 1, denoted shortly as the event (
A
→
1
), one says that A has succeeded.Definition 3.
An encryption scheme provides indistinguishable encryptions in the presence of an eavesdropper, if for all probabilistic polynomial-time adversariesA
(19)
P
r
A
⟶
1
∣
E
n
c
m
b
≤
1
2
+
ϵ
,where ϵ
=
n
e
g
l
(
n
) is a negligibly small function.Definitions2 and 3 are more precisely discussed in [11].


### 4.2. Evaluation of the Security Gain Based on the Mutual Information

We consider the encryption system displayed in Figure1 taking into account the fact that the legitimate parties share pseudo-random secret sequences instead of random ones. Our goal is to estimate the advantage of A in the indistinguishability game specified by Definition 2 when y
←
E
n
c
(
m
b
), where y is a particular realization of Y
(
n
), assuming that the advantage of A is known when m
0 and m
1 are two chosen realizations of M
n and the corresponding realization of X
n is known.Proposition 4.
Let the encrypted mapping ofM
n into X
n be such that 1
/
2
+
ϵ equals the advantage of the adversary A (specified by Definition 3) to win the indistinguishability game (specified by Definition 2), and let the mutual information I
i
u
d
(
X
;
Y
) be known. Under these assumptions, for large n, (20)
P
r
A
⟶
1
∣
Y
n
=
y
=
1
2
+
ϵ
·
δ
,
w
h
e
r
e
δ
≜
P
r
X
n
=
x
b
∣
Y
n
=
y
<
1
n
+
1
n
I
X
n
,
Y
n
p
x
n
=
2
-
n
.Proof.
Note that, for simplicity of the proof, Proposition4 addresses a restricted case where it is assumed that 1
/
2
+
ϵ equals the advantage of the adversary A (specified by Definition 3) to win the indistinguishability game. Let the index b of the selected message be realization of the random variable B whose distribution reflects that of the output of adversary A. The probability P
r
(
B
=
b
∣
Y
(
n
)
=
y
) that A wins the game is determined by the following:(21)
P
r
B
=
b
∣
Y
n
=
y
=
P
r
B
=
b
,
Y
n
=
y
P
r
Y
n
=
y
=
∑
x
P
r
B
=
b
,
Y
n
=
y
,
X
n
=
x
P
r
Y
n
=
y
=
∑
x
P
r
⁡
B
=
b
∣
Y
n
=
y
,
X
n
=
x
P
r
Y
n
=
y
,
X
n
=
x
P
r
Y
n
=
y
=
∑
x
P
r
B
=
b
∣
X
n
=
x
P
r
Y
n
=
y
,
X
n
=
x
P
r
Y
n
=
y
.According to the proposition assumption we have(22)
P
r
B
=
b
∣
X
n
=
x
b
=
1
2
+
ϵ
,where x
b corresponds to the selected m
b, and(23)
P
r
⁡
B
=
b
∣
X
n
=
x
=
1
2
f
o
r
a
n
y
x
≠
x
b
.Consequently,(24)
P
r
⁡
B
=
b
∣
Y
n
=
y
=
Pr
⁡
B
=
b
∣
X
n
=
x
b
Pr
⁡
Y
n
=
y
,
X
n
=
x
b
Pr
⁡
Y
n
=
y
+
∑
x
:
x
≠
x
b
Pr
⁡
B
=
b
∣
X
n
=
x
Pr
⁡
Y
n
=
y
,
X
n
=
x
Pr
⁡
Y
n
=
y
,
P
r
B
=
b
∣
Y
n
=
y
=
1
/
2
+
ϵ
P
r
Y
n
=
y
,
X
n
=
x
b
-
1
/
2
P
r
Y
n
=
y
,
X
n
=
x
b
P
r
Y
n
=
y
+
1
/
2
∑
x
P
r
Y
n
=
y
,
X
n
=
x
P
r
Y
n
=
y
=
1
2
+
ϵ
·
P
r
X
n
=
x
b
∣
Y
n
=
y
.Next, we have the following general upper bound on the entropy (see [12] or [13], e.g.):(25)
H
X
n
∣
Y
n
≤
h
P
e
r
r
+
P
e
r
r
log
2
⁡
2
n
-
1
,where h
(
·
)
≤
1 is the binary entropy function and P
e
r
r
=
1
-
P
r
(
x
b
∣
y
), implying(26)
δ
≜
P
r
X
n
=
x
b
∣
Y
n
=
y
<
1
n
+
1
-
1
n
H
X
n
∣
Y
n
=
1
n
+
1
n
I
X
n
,
Y
n
p
x
n
=
2
-
n
.


## 4.1. Preliminaries: Security Notation

A definition of security consists of two distinct components: a specification of the assumed power of the adversary and a description of what constitutes a “break” of the scheme. Generally speaking, a cryptographic scheme is secure in a computational sense, if, for every probabilistic polynomial-time adversaryA carrying out an attack of some specified type and for every polynomial p
(
n
), there exists an integer N such that the probability that A succeeds in this attack (where success is also well defined) is less than 1
/
p
(
n
) for every n
>
N. Accordingly, the following two definitions specify a security evaluation scenario and a security statement.Definition 2.
The adversarial indistinguishability experiment consists of the following steps:(1)
The adversaryA chooses a pair of messages (
m
0
;
m
1
) of the same length n and passes them onto the encryption system for encrypting.
(2)
A bitb
∈
{
0,1
} is chosen uniformly at random, and only one of the two messages (
m
0
;
m
1
), precisely m
b, is encrypted into ciphertext E
n
c
(
m
b
) and returned to A.
(3)
Upon observingE
n
c
(
m
b
), and without knowledge of b, the adversary A outputs a bit b
0.
(4)
The experiment output is defined to be 1 ifb
0
=
b, and 0 otherwise; if the experiment output is 1, denoted shortly as the event (
A
→
1
), one says that A has succeeded.Definition 3.
An encryption scheme provides indistinguishable encryptions in the presence of an eavesdropper, if for all probabilistic polynomial-time adversariesA
(19)
P
r
A
⟶
1
∣
E
n
c
m
b
≤
1
2
+
ϵ
,where ϵ
=
n
e
g
l
(
n
) is a negligibly small function.Definitions2 and 3 are more precisely discussed in [11].


## 4.2. Evaluation of the Security Gain Based on the Mutual Information

We consider the encryption system displayed in Figure1 taking into account the fact that the legitimate parties share pseudo-random secret sequences instead of random ones. Our goal is to estimate the advantage of A in the indistinguishability game specified by Definition 2 when y
←
E
n
c
(
m
b
), where y is a particular realization of Y
(
n
), assuming that the advantage of A is known when m
0 and m
1 are two chosen realizations of M
n and the corresponding realization of X
n is known.Proposition 4.
Let the encrypted mapping ofM
n into X
n be such that 1
/
2
+
ϵ equals the advantage of the adversary A (specified by Definition 3) to win the indistinguishability game (specified by Definition 2), and let the mutual information I
i
u
d
(
X
;
Y
) be known. Under these assumptions, for large n, (20)
P
r
A
⟶
1
∣
Y
n
=
y
=
1
2
+
ϵ
·
δ
,
w
h
e
r
e
δ
≜
P
r
X
n
=
x
b
∣
Y
n
=
y
<
1
n
+
1
n
I
X
n
,
Y
n
p
x
n
=
2
-
n
.Proof.
Note that, for simplicity of the proof, Proposition4 addresses a restricted case where it is assumed that 1
/
2
+
ϵ equals the advantage of the adversary A (specified by Definition 3) to win the indistinguishability game. Let the index b of the selected message be realization of the random variable B whose distribution reflects that of the output of adversary A. The probability P
r
(
B
=
b
∣
Y
(
n
)
=
y
) that A wins the game is determined by the following:(21)
P
r
B
=
b
∣
Y
n
=
y
=
P
r
B
=
b
,
Y
n
=
y
P
r
Y
n
=
y
=
∑
x
P
r
B
=
b
,
Y
n
=
y
,
X
n
=
x
P
r
Y
n
=
y
=
∑
x
P
r
⁡
B
=
b
∣
Y
n
=
y
,
X
n
=
x
P
r
Y
n
=
y
,
X
n
=
x
P
r
Y
n
=
y
=
∑
x
P
r
B
=
b
∣
X
n
=
x
P
r
Y
n
=
y
,
X
n
=
x
P
r
Y
n
=
y
.According to the proposition assumption we have(22)
P
r
B
=
b
∣
X
n
=
x
b
=
1
2
+
ϵ
,where x
b corresponds to the selected m
b, and(23)
P
r
⁡
B
=
b
∣
X
n
=
x
=
1
2
f
o
r
a
n
y
x
≠
x
b
.Consequently,(24)
P
r
⁡
B
=
b
∣
Y
n
=
y
=
Pr
⁡
B
=
b
∣
X
n
=
x
b
Pr
⁡
Y
n
=
y
,
X
n
=
x
b
Pr
⁡
Y
n
=
y
+
∑
x
:
x
≠
x
b
Pr
⁡
B
=
b
∣
X
n
=
x
Pr
⁡
Y
n
=
y
,
X
n
=
x
Pr
⁡
Y
n
=
y
,
P
r
B
=
b
∣
Y
n
=
y
=
1
/
2
+
ϵ
P
r
Y
n
=
y
,
X
n
=
x
b
-
1
/
2
P
r
Y
n
=
y
,
X
n
=
x
b
P
r
Y
n
=
y
+
1
/
2
∑
x
P
r
Y
n
=
y
,
X
n
=
x
P
r
Y
n
=
y
=
1
2
+
ϵ
·
P
r
X
n
=
x
b
∣
Y
n
=
y
.Next, we have the following general upper bound on the entropy (see [12] or [13], e.g.):(25)
H
X
n
∣
Y
n
≤
h
P
e
r
r
+
P
e
r
r
log
2
⁡
2
n
-
1
,where h
(
·
)
≤
1 is the binary entropy function and P
e
r
r
=
1
-
P
r
(
x
b
∣
y
), implying(26)
δ
≜
P
r
X
n
=
x
b
∣
Y
n
=
y
<
1
n
+
1
-
1
n
H
X
n
∣
Y
n
=
1
n
+
1
n
I
X
n
,
Y
n
p
x
n
=
2
-
n
.


## 5. Evaluation of the Security Gain Based on Numerical Estimation of the Mutual Information

Theorem 5.
Let the encrypted mapping ofM
n into X
n be such that 1
/
2
+
ϵ equals the advantage of the adversary A (specified by Definition 3) to win the indistinguishability game (specified by Definition 2), and let the mutual information I
i
u
d
(
X
;
Y
) be known (see Figure 2, e.g.). Under these assumptions, for large n,(27)
P
r
A
⟶
1
∣
Y
n
=
y
=
1
2
+
ϵ
·
δ
,
w
h
e
r
e
δ
<
I
i
u
d
X
;
Y
+
l
o
g
2
8
π
e
·
i
·
n
/
1
-
i
2
2
n
+
O
n
-
2
.Proof.
Consider(28)
δ
≜
Pr
⁡
x
b
∣
y
<
1
n
+
1
-
1
n
H
X
n
∣
Y
n
=
1
n
+
1
n
I
X
n
,
Y
n
p
x
n
=
2
-
n
.Substitution of (7) and (9) into (28) finalizes the proof.Accordingly, the encryption mappingM
n
→
Y
(
n
) enhances security by a factor δ in comparison to the encryption mapping M
n
→
X
n because the probability that A wins the game becomes closer to 1
/
2, which corresponds to random guessing.


## 6. Evaluation of the Security Enhancement Employing Enumeration of Channel Input Candidates for the Given Output

### 6.1. Preliminaries

LetZ
∈
{
0,1
}
l be a binary string of length l, and let t
≤
l be a parameter. Recently, in [9], improved bounds on the number of subsequences obtained from a binary string Z of length l under t deletions have been reported. It is known that the number of subsequences in this setting strongly depends on the number of runs in the string Z, where a run is a maximal substring of the same character. The improved bounds are obtained by a structural analysis of the family of r-run strings Z, an analysis in which the extremal strings with respect to the number of subsequences have been identified. Specifically, for every r, r-run strings with the minimum (resp., maximum) number of subsequences under any t deletions have been considered, an exact analysis of the number of subsequences of these extremal strings has been presented, and it has been shown that this number can be calculated in polynomial time.LetD
t
(
Z
) be a set of subsequences of Z that can be obtained from Z after t deletions. The analysis of D
t
(
Z
) and its size are challenging as the number of subsequences of a string Z obtained by deletions not only depends on its length l and the number t of deletions, but also strongly depends on its structure. For example, D
t
(
0
l
) is of size 1 and equals the single string 0
l
-
t. Clearly, D
t
Z is at most 2
l
-
t (as after t deletions we remain with a binary string of length l
-
t). It has been shown that the number of subsequences D
t
Z strongly depends on thenumber of runs
r in the string. Here, a run is a maximal substring of the same character, and the number of runs r
=
ρ
(
·
) in a given string Z is denoted by ρ
(
Z
). It has been proven that (29)
ρ
Z
-
t
+
1
t
≤
D
t
Z
≤
ρ
Z
+
t
-
1
t
.Also, it has been shown that the maximal number of subsequences is obtained from certain strings Z, known as cyclic strings Z
l
C, in which |
Z
|
=
ρ
(
Z
), and it has been shown that(30)
ρ
Z
-
t
+
1
t
≤
D
t
Z
≤
D
t
Z
l
C
,which has been further improved so that the following has been shown:(31)
∑
i
=
1
t
ρ
Z
-
t
i
=
D
t
Z
r
C
≤
D
t
Z
,
D
t
Z
≤
D
t
Z
l
C
=
∑
i
=
1
t
l
-
t
i
,where Z
r
C is a string of length r with r runs.In [9], also a family of strings, named unbalanced strings, has been defined. A string is called unbalanced, if all of the runs of symbols in the string are of length 1, except for one run. Let U
l
,
r
(
i
) be a binary string of length l with r runs, in which all runs are of length 1, except for the ith run which is of length l
-
r
+
1. Due to symmetry D
t
U
l
,
r
1
=
D
t
U
l
,
r
r, and consequently define(32)
u
l
,
r
,
t
=
D
t
U
l
,
r
1
=
D
t
U
l
,
r
r
.It has been shown in [9] that these extreme cases have the least number of subsequences among the unbalanced strings and also that they have the least number of subsequences among all strings. The following theorem has been proven in [9].Theorem 6 (Theorem3 [9]: closed-form formula for u
(
l
,
r
,
t
)).
For allt
<
l, 2
<
r
≤
l, (i)
whenr
>
t,(33)
u
l
,
r
,
t
=
d
r
,
t
+
∑
i
=
t
+
r
-
l
-
1
t
-
2
d
r
-
2
,
i
,
(ii)
whenr
≤
t,(34)
u
l
,
r
,
t
=
2
+
∑
i
=
t
+
r
-
l
-
1
r
-
3
d
r
-
2
,
i
,where(35)
d
r
,
i
=
D
i
Z
r
C
=
∑
j
=
0
i
r
-
i
jassuming that d
(
r
,
0
)
=
1 and, for i
<
0, d
(
r
,
i
)
=
0 and that the following conventions are employed:(36)
∑
i
=
j
k
a
i
=
0
w
h
e
n
j
>
k
,
l
i
=
0
w
h
e
n
i
<
0
o
r
i
>
l
.A numerical illustration of Theorem6 is displayed in Figure 3.Figure 3
Number (N
o) of different subsequence of length l which can be obtained from a binary sequence of length l
+
t: a numerical illustration of the statement of Theorem 3 [9].


### 6.2. Estimation of the Security Enhancement

Traditionally, as introduced in [14], the main information-theoretic security metric is the average information leaked, that is, the mutual information I
(
M
;
Y
) between the message M and the related sample Y, or, equivalently, the uncertainty, that is, the equivocation H
(
M
∣
Y
). Recently, certain information-theoretic security measures have been considered in [15] implying that, in our case, as a strong security metric the average mutual information I
-
(
M
,
Y
) should be addressed and 1
/
n
I
-
(
M
,
Y
) as a corresponding weak one.Theorem 7.
Assuming that the employed keystream generator is such that the following is valid,(37)
I
M
;
C
=
0
,
I
M
;
G
=
0
,
I
C
;
G
=
0
,
I
M
;
X
≤
ϵ
,the simulator of binary channel with random insertions provides (38)
1
n
I
M
;
Y
≤
α
·
ϵ
n
,
α
=
1
-
1
n
log
2
⁡
u
n
+
t
,
r
,
t
,where u
(
n
+
t
,
r
,
t
) is the number of certain equally likely subsequences.Sketch of the Proof.
The uncertainty about the input (the argument) into a binary channel with random insertions given its output (the image) depends on the number of equally likely candidate arguments which can generate the given image. A lower bound on the number of these candidates can be obtained based on the lower bound on the number of the subsequences which can be obtained from the given one employing Theorem6 (i.e., Theorem 3 from [9]). By adapting this result to the considered particular case we have the following. A lower bound on the number of the argument candidates u
(
n
+
t
,
r
,
t
), where r is a parameter, is given by (39) and (40):(i)
whenr
>
t,(39)
u
n
+
t
,
r
,
t
=
d
r
,
t
+
∑
i
=
r
-
n
-
1
m
-
2
d
r
-
2
,
i
,
(ii)
whenr
≤
t:(40)
u
n
+
t
,
r
,
t
=
2
+
∑
i
=
r
-
n
-
1
r
-
3
d
r
-
2
,
i
,where(41)
d
r
,
i
=
∑
j
=
0
i
r
-
i
jassuming that d
(
r
,
0
)
=
1 and, for i
<
0, d
(
r
,
i
)
=
0. Particularly note that the above enumerated subsequences are obtained from a sequence where all of the runs of symbols are of length 1, except for one run, and that the assumed decimation is a random one, and in addition, for simplicity of the evaluation we assume that the subsequences appear equally likely.
Consequently, the uncertaintyH
(
X
∣
Y
) is lower-bounded as follows:(42)
H
X
∣
Y
≥
log
2
⁡
u
n
+
t
,
r
,
tnoting that u
(
n
+
t
,
r
,
t
) is at most 2
n
=
H
(
X
) as after t deletions we remain with a binary string of length n. Taking into account that (43)
1
n
I
X
;
Y
=
1
n
H
X
-
H
X
∣
Ywe obtain(44)
1
n
I
M
;
Y
≤
1
n
I
M
;
X
1
-
1
n
log
2
⁡
u
n
+
t
,
r
,
tand accordingly the theorem statement.Figure4 yields numerical illustrations of coefficient α which determines the security gain.Figure 4
Numerical examples related to Theorem7: illustration of the security gain implied by a binary channel with embedding of random bits noting that smaller α means higher security enhancement.Note that, in order to achieve a desired high enhancement of the security, the insertion rate should be high enough as illustrated in Figure4. When the insertion rate is low, the security enhancement is low as well, and this is analytically shown in the next corollary.Corollary 8.
Consider(45)
1
n
I
M
;
Y
≤
1
n
I
M
;
X
·
1
-
log
2
⁡
1
+
5
2
r
nwhen the parameters of the considered encryption fulfil the following constraints:(46)
n
>
1
+
5
2
r
,
t
∈
p
∗
r
,
n
+
t
-
r
1
-
p
∗
f
o
r
p
∗
∈
0.276,0.278
.Sketch of the Proof.
For large values oft and r, the following approximation can be employed:(47)
u
n
+
t
,
r
,
t
≈
∑
i
=
0
m
i
n
r
,
t
d
r
,
i
,where x
≈
y means that x is approximately y if x
/
y is a polynomial function of r and t. Accordingly,(48)
d
r
,
p
r
=
∑
i
=
0
p
r
r
-
p
r
i
≈
2
r
-
p
r
f
o
r
p
≥
1
3
,
r
-
p
r
p
r
f
o
r
p
<
1
3
.Using the fact reported in [9] we have the following. Let p
∗
=
a
r
g
m
a
x
p
d
(
r
,
p
r
). Numerical calculations reported in [9] show that p
∗
∈
[
0.276,0.278
]. Consequently, it is shown in [9] that for even r
(49)
d
r
,
p
∗
r
≈
1
+
5
2
r
.The above imply the corollary statement.


## 6.1. Preliminaries

LetZ
∈
{
0,1
}
l be a binary string of length l, and let t
≤
l be a parameter. Recently, in [9], improved bounds on the number of subsequences obtained from a binary string Z of length l under t deletions have been reported. It is known that the number of subsequences in this setting strongly depends on the number of runs in the string Z, where a run is a maximal substring of the same character. The improved bounds are obtained by a structural analysis of the family of r-run strings Z, an analysis in which the extremal strings with respect to the number of subsequences have been identified. Specifically, for every r, r-run strings with the minimum (resp., maximum) number of subsequences under any t deletions have been considered, an exact analysis of the number of subsequences of these extremal strings has been presented, and it has been shown that this number can be calculated in polynomial time.LetD
t
(
Z
) be a set of subsequences of Z that can be obtained from Z after t deletions. The analysis of D
t
(
Z
) and its size are challenging as the number of subsequences of a string Z obtained by deletions not only depends on its length l and the number t of deletions, but also strongly depends on its structure. For example, D
t
(
0
l
) is of size 1 and equals the single string 0
l
-
t. Clearly, D
t
Z is at most 2
l
-
t (as after t deletions we remain with a binary string of length l
-
t). It has been shown that the number of subsequences D
t
Z strongly depends on thenumber of runs
r in the string. Here, a run is a maximal substring of the same character, and the number of runs r
=
ρ
(
·
) in a given string Z is denoted by ρ
(
Z
). It has been proven that (29)
ρ
Z
-
t
+
1
t
≤
D
t
Z
≤
ρ
Z
+
t
-
1
t
.Also, it has been shown that the maximal number of subsequences is obtained from certain strings Z, known as cyclic strings Z
l
C, in which |
Z
|
=
ρ
(
Z
), and it has been shown that(30)
ρ
Z
-
t
+
1
t
≤
D
t
Z
≤
D
t
Z
l
C
,which has been further improved so that the following has been shown:(31)
∑
i
=
1
t
ρ
Z
-
t
i
=
D
t
Z
r
C
≤
D
t
Z
,
D
t
Z
≤
D
t
Z
l
C
=
∑
i
=
1
t
l
-
t
i
,where Z
r
C is a string of length r with r runs.In [9], also a family of strings, named unbalanced strings, has been defined. A string is called unbalanced, if all of the runs of symbols in the string are of length 1, except for one run. Let U
l
,
r
(
i
) be a binary string of length l with r runs, in which all runs are of length 1, except for the ith run which is of length l
-
r
+
1. Due to symmetry D
t
U
l
,
r
1
=
D
t
U
l
,
r
r, and consequently define(32)
u
l
,
r
,
t
=
D
t
U
l
,
r
1
=
D
t
U
l
,
r
r
.It has been shown in [9] that these extreme cases have the least number of subsequences among the unbalanced strings and also that they have the least number of subsequences among all strings. The following theorem has been proven in [9].Theorem 6 (Theorem3 [9]: closed-form formula for u
(
l
,
r
,
t
)).
For allt
<
l, 2
<
r
≤
l, (i)
whenr
>
t,(33)
u
l
,
r
,
t
=
d
r
,
t
+
∑
i
=
t
+
r
-
l
-
1
t
-
2
d
r
-
2
,
i
,
(ii)
whenr
≤
t,(34)
u
l
,
r
,
t
=
2
+
∑
i
=
t
+
r
-
l
-
1
r
-
3
d
r
-
2
,
i
,where(35)
d
r
,
i
=
D
i
Z
r
C
=
∑
j
=
0
i
r
-
i
jassuming that d
(
r
,
0
)
=
1 and, for i
<
0, d
(
r
,
i
)
=
0 and that the following conventions are employed:(36)
∑
i
=
j
k
a
i
=
0
w
h
e
n
j
>
k
,
l
i
=
0
w
h
e
n
i
<
0
o
r
i
>
l
.A numerical illustration of Theorem6 is displayed in Figure 3.Figure 3
Number (N
o) of different subsequence of length l which can be obtained from a binary sequence of length l
+
t: a numerical illustration of the statement of Theorem 3 [9].


## 6.2. Estimation of the Security Enhancement

Traditionally, as introduced in [14], the main information-theoretic security metric is the average information leaked, that is, the mutual information I
(
M
;
Y
) between the message M and the related sample Y, or, equivalently, the uncertainty, that is, the equivocation H
(
M
∣
Y
). Recently, certain information-theoretic security measures have been considered in [15] implying that, in our case, as a strong security metric the average mutual information I
-
(
M
,
Y
) should be addressed and 1
/
n
I
-
(
M
,
Y
) as a corresponding weak one.Theorem 7.
Assuming that the employed keystream generator is such that the following is valid,(37)
I
M
;
C
=
0
,
I
M
;
G
=
0
,
I
C
;
G
=
0
,
I
M
;
X
≤
ϵ
,the simulator of binary channel with random insertions provides (38)
1
n
I
M
;
Y
≤
α
·
ϵ
n
,
α
=
1
-
1
n
log
2
⁡
u
n
+
t
,
r
,
t
,where u
(
n
+
t
,
r
,
t
) is the number of certain equally likely subsequences.Sketch of the Proof.
The uncertainty about the input (the argument) into a binary channel with random insertions given its output (the image) depends on the number of equally likely candidate arguments which can generate the given image. A lower bound on the number of these candidates can be obtained based on the lower bound on the number of the subsequences which can be obtained from the given one employing Theorem6 (i.e., Theorem 3 from [9]). By adapting this result to the considered particular case we have the following. A lower bound on the number of the argument candidates u
(
n
+
t
,
r
,
t
), where r is a parameter, is given by (39) and (40):(i)
whenr
>
t,(39)
u
n
+
t
,
r
,
t
=
d
r
,
t
+
∑
i
=
r
-
n
-
1
m
-
2
d
r
-
2
,
i
,
(ii)
whenr
≤
t:(40)
u
n
+
t
,
r
,
t
=
2
+
∑
i
=
r
-
n
-
1
r
-
3
d
r
-
2
,
i
,where(41)
d
r
,
i
=
∑
j
=
0
i
r
-
i
jassuming that d
(
r
,
0
)
=
1 and, for i
<
0, d
(
r
,
i
)
=
0. Particularly note that the above enumerated subsequences are obtained from a sequence where all of the runs of symbols are of length 1, except for one run, and that the assumed decimation is a random one, and in addition, for simplicity of the evaluation we assume that the subsequences appear equally likely.
Consequently, the uncertaintyH
(
X
∣
Y
) is lower-bounded as follows:(42)
H
X
∣
Y
≥
log
2
⁡
u
n
+
t
,
r
,
tnoting that u
(
n
+
t
,
r
,
t
) is at most 2
n
=
H
(
X
) as after t deletions we remain with a binary string of length n. Taking into account that (43)
1
n
I
X
;
Y
=
1
n
H
X
-
H
X
∣
Ywe obtain(44)
1
n
I
M
;
Y
≤
1
n
I
M
;
X
1
-
1
n
log
2
⁡
u
n
+
t
,
r
,
tand accordingly the theorem statement.Figure4 yields numerical illustrations of coefficient α which determines the security gain.Figure 4
Numerical examples related to Theorem7: illustration of the security gain implied by a binary channel with embedding of random bits noting that smaller α means higher security enhancement.Note that, in order to achieve a desired high enhancement of the security, the insertion rate should be high enough as illustrated in Figure4. When the insertion rate is low, the security enhancement is low as well, and this is analytically shown in the next corollary.Corollary 8.
Consider(45)
1
n
I
M
;
Y
≤
1
n
I
M
;
X
·
1
-
log
2
⁡
1
+
5
2
r
nwhen the parameters of the considered encryption fulfil the following constraints:(46)
n
>
1
+
5
2
r
,
t
∈
p
∗
r
,
n
+
t
-
r
1
-
p
∗
f
o
r
p
∗
∈
0.276,0.278
.Sketch of the Proof.
For large values oft and r, the following approximation can be employed:(47)
u
n
+
t
,
r
,
t
≈
∑
i
=
0
m
i
n
r
,
t
d
r
,
i
,where x
≈
y means that x is approximately y if x
/
y is a polynomial function of r and t. Accordingly,(48)
d
r
,
p
r
=
∑
i
=
0
p
r
r
-
p
r
i
≈
2
r
-
p
r
f
o
r
p
≥
1
3
,
r
-
p
r
p
r
f
o
r
p
<
1
3
.Using the fact reported in [9] we have the following. Let p
∗
=
a
r
g
m
a
x
p
d
(
r
,
p
r
). Numerical calculations reported in [9] show that p
∗
∈
[
0.276,0.278
]. Consequently, it is shown in [9] that for even r
(49)
d
r
,
p
∗
r
≈
1
+
5
2
r
.The above imply the corollary statement.



---

*Source: 7920495-2016-05-12.xml*