A stream cipher design based on embedding of random bits

A novel approach for design of stream ciphers based on a combination of pseudo-randomness and randomness is proposed. The core element of the approach is a pseudo-random embedding of the random bits into the ciphertext. This embedding plays a role of a homophonic encoding and implies an additional communications overhead. Before its output to the public communication channel the ciphertext with the embedded random bits is also intentionally degraded via its exposure to a moderate noise binary symmetric channel. The proposed design has potential of providing that complexity of recovering the secret key in the known plaintext attacking scenario is close to the complexity of recovering the secret key via the exhaustive search, i.e. close to the maximal possible one for the given size of secret key. Accordingly, the proposed approach can be considered as a trade-off between the increased security and decreased communications efficiency.