# BitFlip Collision Study

##### Automatic Collision Test

The BitFlip cipher assumes an alphabet comprised of t letters, where each letter is represented by a secret key in the form of a random string of n even bits. To communicate a letter from the alphabet, the transmitter will randomly flip f bits. Nominally f= 0.5n (half the size of each letter key), and thereby generate the respective cipher-letter. The receiver will recognize the transmitted cipher-letter by it having exactly f bits flipped when compared to the key of that letter. And having no other letter which is exactly f bits apart from the communicated string. The transmitter, therefore, will have to check the randomly created (randomly flipped) cipher-letter against "collision" -- namely against the possibility that the cipher-letter will have f bits apart from the letter it is supposed to encrypt, and having f bits apart from one or more other letters. Because in that case the receiver will be confused as to which letter the transmitter wishes to communicate. Illustration a=100111 and b=111011 have 3 bits apart (bits 2,3,4 counting from the left).

This brings up the question of the chance for a randomly generated (randomly flipped) cipher-letter to be in "collision" with another letter (which is to be avoided). Because BitFlip is ultra fast, it is not a big issue, if the transmitter has to try 5, 10, even 20 times before it gets a collision-free cipher-letter. In fact theoretical considerations conclude that the more difficult it is to get a collision-free cipher-letter, the more secure the cipher. Therefore ultra secure transmissions may be using a ratio of 100:1 of collision v. no-collision, to generate more security. While nominally one would flip exactly half of the bits in the letter key, this value may be varied, in order to reduce the frequency of collisions, in certain applications. The setting where f=n/2 is highly recommended because it maximizes the entropy. This means it increases the chance for equivocation which will render BitFlip unbreakable in a mathematical sense. In applications where the number of flipped bits varies from half point, this variance should be kept at minimum, and its value should be part of the shared secret key. In some cases it might be of advantage to dynamically change the value of f. One important advantage of the BitFlip cipher is that it empowers the user to determine how much security to use, by simply adjusting the randomness setting on the cipher.

In this test kit, the value of f is uniform with respect to the alphabet, but various applications may select a different (secret) value of f, for every letter in the alphabet, further increasing the cryptanalytic burden.

The BitFlip cipher replaces algorithmic complexity with a stream of high-quality randomness. So the size of the cipher-stream that transmits the message is much larger than the stored message, as evident from the size of the letter keys (which is also the size of the cipher-letters).

This BitFlip cipher must insure high quality randomness for the letter keys, as well as high-quality randomness for the flipping selection. One way to check the quality of a randomness source is to compare its results with the mathematics.