60
V. Mikhalev et al.
linear block code designed to work over a binary symmetric channel with crossover
probability p could be employed. There are a lot of these coding schemes reported
in the literature and one which best fits into a particular implementation scenario
(hardware or software oriented) could be selected. We consider a communication
system displayed in Fig. 3.2 where some message a = [a i ] l
i=1 ∈ {0, 1} l is sent to a
transmitter over a noisy channel and the following operations at the transmitter and
receiver.
At the Transmitter To ensure reliable communication, a linear error-correcting
encoder C ECC (·) is used, that maps an m-bit message to a codeword of n > m bits,
using an m×n binary code generator matrix G ECC . A homophonic encoder C H (·) is
added prior to C ECC (·), which requires the use of a vector u = [u i ]
m−l
i=1 ∈ {0, 1} m−l
of pure randomness, i.e., each u i is the realization of a random variable U i with
distribution Pr(U i = 1) = Pr(U i = 0) = 1/2. The encoding C H (a||u) may be
described by an m × m binary matrix G H such that
C H (a||u) = [a||u]G H , G H =
⎡
⎢
⎢
⎢
⎣
h 1
. . .
h l
G C
⎤
⎥
⎥
⎥
⎦
(3.2)
where G C is an (m−l)×m generator matrix for an (m, m−l) linear error-correction
code C, and h 1 , h 2 , . . . , h l are l linearly independent row vectors from {0, 1} m \C.
We get a joint encoding a ∈ {0, 1} l → C ECC (C H (a||u)) ∈ {0, 1} n , which may
alternatively be written as
C ECC (C H (a||u)) = C ECC ([a||u]G H ) = [a||u]G H G ECC = [a||u]G
(3.3)
where G = G H G ECC is an m × n binary matrix containing the two successive
encoders at the transmitter.
The codeword sent is finally an encrypted version y of C ECC (C H (a||u)) given
by y = y(k) = C ECC (C H (a||u)) ⊕ x where x = x(k) = [x i ]
n
i=1 ∈ {0, 1} n
is a pseudorandom vector needed for encryption, which is generated by either a
keystream generator, or by a block cipher working in the cipher feedback mode
(CFB) as in [322] and [577]. Notice the important dependency of x = x(k) in the
secret key k. Also note that, for simplicity of the exposition, the data employed
for generation of the pseudorandom vectors x, which are publicly known (like a
public seed and a synchronization parameter) are not explicitly shown. Finally,
the model includes the assumption that the concatenation of the binary vectors x
appears as a pseudorandom binary sequences and from a statistical point of view is
indistinguishable from a random binary sequence.
At the Receiver The noisy communication channel is modeled by the addition
of a noise vector v = [v i ]
n
i=1 ∈ {0, 1} n , where each v i is the realization of a
random variable V i with Pr(V i = 1) = p and Pr(V i = 0) = 1 − p. The
V. Mikhalev et al.
linear block code designed to work over a binary symmetric channel with crossover
probability p could be employed. There are a lot of these coding schemes reported
in the literature and one which best fits into a particular implementation scenario
(hardware or software oriented) could be selected. We consider a communication
system displayed in Fig. 3.2 where some message a = [a i ] l
i=1 ∈ {0, 1} l is sent to a
transmitter over a noisy channel and the following operations at the transmitter and
receiver.
At the Transmitter To ensure reliable communication, a linear error-correcting
encoder C ECC (·) is used, that maps an m-bit message to a codeword of n > m bits,
using an m×n binary code generator matrix G ECC . A homophonic encoder C H (·) is
added prior to C ECC (·), which requires the use of a vector u = [u i ]
m−l
i=1 ∈ {0, 1} m−l
of pure randomness, i.e., each u i is the realization of a random variable U i with
distribution Pr(U i = 1) = Pr(U i = 0) = 1/2. The encoding C H (a||u) may be
described by an m × m binary matrix G H such that
C H (a||u) = [a||u]G H , G H =
⎡
⎢
⎢
⎢
⎣
h 1
. . .
h l
G C
⎤
⎥
⎥
⎥
⎦
(3.2)
where G C is an (m−l)×m generator matrix for an (m, m−l) linear error-correction
code C, and h 1 , h 2 , . . . , h l are l linearly independent row vectors from {0, 1} m \C.
We get a joint encoding a ∈ {0, 1} l → C ECC (C H (a||u)) ∈ {0, 1} n , which may
alternatively be written as
C ECC (C H (a||u)) = C ECC ([a||u]G H ) = [a||u]G H G ECC = [a||u]G
(3.3)
where G = G H G ECC is an m × n binary matrix containing the two successive
encoders at the transmitter.
The codeword sent is finally an encrypted version y of C ECC (C H (a||u)) given
by y = y(k) = C ECC (C H (a||u)) ⊕ x where x = x(k) = [x i ]
n
i=1 ∈ {0, 1} n
is a pseudorandom vector needed for encryption, which is generated by either a
keystream generator, or by a block cipher working in the cipher feedback mode
(CFB) as in [322] and [577]. Notice the important dependency of x = x(k) in the
secret key k. Also note that, for simplicity of the exposition, the data employed
for generation of the pseudorandom vectors x, which are publicly known (like a
public seed and a synchronization parameter) are not explicitly shown. Finally,
the model includes the assumption that the concatenation of the binary vectors x
appears as a pseudorandom binary sequences and from a statistical point of view is
indistinguishable from a random binary sequence.
At the Receiver The noisy communication channel is modeled by the addition
of a noise vector v = [v i ]
n
i=1 ∈ {0, 1} n , where each v i is the realization of a
random variable V i with Pr(V i = 1) = p and Pr(V i = 0) = 1 − p. The