Unpredictable Binary Strings
Richard M. Low, Mark Stamp, R. Craigen, Gabriel Faucher · San José State University ScholarWorks (San Jose State University) · 2005
Abstract. We examine a class of binary strings arising from considerations about stream cipher encryption: to what degree can one guarantee that the number of pairs of entries distance k apart that disagree is equal to the number that agree, for all small k? In a certain sense, a keystream with such a property achieves a degree of unpredictability. The problem is also restated combinatorially in terms of seating arrangements. We examine sequences s of length 2n in which this property holds for all k ≤ Mn, where Mn is the largest number for which this is possible among strings of length 2n. Wegive upper and lower bounds for Mn, and give optimal sequences of all lengths up to n = 26. We also show how to obtain classes of special orthogonal arrays and balanced sign graphs from such sequences. 1. Background A stream cipher cryptosystem is illustrated in Figure 1. The original message, or plaintext, is encrypted by adding (elementwise modulo 2) a pseudo–random sequence of bits to the message. This pseudo–random sequence of bits is known as a keystream. The resulting ciphertext can then be transmitted over insecure lines. The recipient can recover the plaintext by adding, modulo 2, the same keystream to the ciphertext. Stream ciphers are a natural generalization of the one–time pad, or Vernam cipher. With a one–time pad, a “random ” string of bits, or pad, is used to encrypt, and this pad can only be used once. While the one–time pad is provably secure [12], the drawbacks are many. For example, the random pad is the same length as the message, and the pad must be securely transmitted to the recipient before the ciphertext can be decrypted. Stream ciphers replace the random sequence of the one–time pad with a pseudo–random string of bits that are generated from a short secret key. The result is a more practical cipher since only the short secret key needs to be securely transmitted before using the system. The tradeoff is that the stream cipher does not inherit the provable security of the one–time pad.