58
V. Mikhalev et al.
3.4 Randomized Encryption Employing Homophonic Coding
3.4.1 Background
In [503], several approaches to including randomness in encryption techniques
are discussed, mainly in the context of block and stream ciphers. Randomized
encryption is described [503] as a procedure which enciphers a message by
randomly choosing a ciphertext from a set of ciphertexts corresponding to the
message under the current encryption key.
Homophonic coding was introduced in [249] as a source coding technique which
transforms a stream of message symbols with an arbitrary frequency distribution
into a uniquely decodable stream of symbols which all have the same frequency. The
universal homophonic coding approach [397] is based on an invertible transformation of the source information vector with embedded random bits, and this approach
does not require knowledge of the source statistics. The source information vector
can be recovered from the homophonic coder output without knowledge of the
random bits by passing the codeword to the decoder (inverter) and then discarding
the random bits.
A number of randomized encryption techniques have been reported: In [234],
a probabilistic private-key encryption scheme named LPN-C whose security can
be reduced to the hardness of the LPN problem was proposed and analysed.
An approach for the design of stream ciphers employing error-correction coding
and certain additive noise degradation of the keystream was reported in [201]. A
message is encoded before the encryption so that the decoding, after mod 2 addition
of the noiseless keystream sequence and the ciphertext, provides its correct recovery.
Resistance of this approach against a number of general techniques for cryptanalysis, was also considered in [201]. Joint employment of randomness and dedicated
coding has been studied for enhancing the security of the following block-by-block
encryption schemes: (1) in [418], where the basic keystream generator security is
enhanced by employing a particular homophonic coding based on embedding of
random bits; (2) in [413, 419] and [414] randomness and dedicated coding were
employed for enhancing the security of the compact generators of pseudorandom
vectors; (3) in [322] and [577] channel coding was employed to increase the security
of a DES block cipher operating in the ciphertext feedback (CFB) mode. Also,
certain issues of randomized encryption were considered in [321, 570] and [313].
3.4.2 Encryption and Decryption
The ciphering technique given in this section originates from the schemes reported
in [322, 414, 418], and it corresponds to the randomized encryption schemes
proposed and discussed in [452]. The design assumes the availability of a source of
pure randomness (for example, as an efficient hardware module) and that a suitable
V. Mikhalev et al.
3.4 Randomized Encryption Employing Homophonic Coding
3.4.1 Background
In [503], several approaches to including randomness in encryption techniques
are discussed, mainly in the context of block and stream ciphers. Randomized
encryption is described [503] as a procedure which enciphers a message by
randomly choosing a ciphertext from a set of ciphertexts corresponding to the
message under the current encryption key.
Homophonic coding was introduced in [249] as a source coding technique which
transforms a stream of message symbols with an arbitrary frequency distribution
into a uniquely decodable stream of symbols which all have the same frequency. The
universal homophonic coding approach [397] is based on an invertible transformation of the source information vector with embedded random bits, and this approach
does not require knowledge of the source statistics. The source information vector
can be recovered from the homophonic coder output without knowledge of the
random bits by passing the codeword to the decoder (inverter) and then discarding
the random bits.
A number of randomized encryption techniques have been reported: In [234],
a probabilistic private-key encryption scheme named LPN-C whose security can
be reduced to the hardness of the LPN problem was proposed and analysed.
An approach for the design of stream ciphers employing error-correction coding
and certain additive noise degradation of the keystream was reported in [201]. A
message is encoded before the encryption so that the decoding, after mod 2 addition
of the noiseless keystream sequence and the ciphertext, provides its correct recovery.
Resistance of this approach against a number of general techniques for cryptanalysis, was also considered in [201]. Joint employment of randomness and dedicated
coding has been studied for enhancing the security of the following block-by-block
encryption schemes: (1) in [418], where the basic keystream generator security is
enhanced by employing a particular homophonic coding based on embedding of
random bits; (2) in [413, 419] and [414] randomness and dedicated coding were
employed for enhancing the security of the compact generators of pseudorandom
vectors; (3) in [322] and [577] channel coding was employed to increase the security
of a DES block cipher operating in the ciphertext feedback (CFB) mode. Also,
certain issues of randomized encryption were considered in [321, 570] and [313].
3.4.2 Encryption and Decryption
The ciphering technique given in this section originates from the schemes reported
in [322, 414, 418], and it corresponds to the randomized encryption schemes
proposed and discussed in [452]. The design assumes the availability of a source of
pure randomness (for example, as an efficient hardware module) and that a suitable