CONSTRAINED EMBEDDING PROBABILITY FOR TWO BINARY STRINGS
Jovan Dj · 1996
An exponentially small upper bound on the probability that a given binary string of length n can be embedded into a uniformly distributed random binary string of length 2n by inserting at most one bit between any two successive bits and an arbitrary number of bits at the end is analytically derived. This probability is important for a cryptanalytic problem of the initial state reconstruction of a binary clock-controlled shift register that is clocked either once or twice per each output symbol, given a segment of its output sequence. The developed approach may also be interesting for other problems of sequence comparison as well, especially for the codes for correcting synchronization errors. 1. Introduction. A cryptanalytic problem of the initial state reconstruction of a binary clock-controlled shift register that is clocked either once or twice per each output symbol is considered in (5), assuming that its output sequence is known. A more general case when the register is additively noised and the maximum number of consecutive clocks at a time is an arbitrary positive integer is examined in (3) using a generalization of the Levenshtein distance. In the zero-noise case the reconstruction is successful if the probability that a given binary string can be embedded into a random binary string of appropriate length decreases sufficiently fast with the string length. An exponentially decreasing upper bound on'the embedding probability derived in (5) shows that the required length of the output sequence is linear in the shift register length. The bound is obtained by direct counting based on some theoretical consid- erations. In this paper, the underlying combinatorial problem is solved analytically and an upper bound on the probability that a given binary string of length n can be embedded into a random binary string of length 2n by inserting at most one bit between any two successive bits and as many bits as needed at the end is thus derived. The bound is the tightest in the observed class and hence sharper than the one from (5). The combinatorial problems of this kind are also relevant for the codes capable