Search papers, labs, and topics across Lattice.
This paper investigates the concept of 0-cyclic equalizability in binary words, focusing on whether inserting 0s at matching positions can render two sequences indistinguishable under cyclic shifts. The authors establish that two binary words of equal length are 0-cyclically equalizable if and only if they possess equal Hamming weight, demonstrating that equal Hamming weight is both a necessary and sufficient condition. Their constructive proof utilizes a novel encoding technique that simplifies the equalizability condition, providing a clear method for achieving the desired insertion of 0s.
Equal Hamming weight is not just necessary but also sufficient for making binary sequences indistinguishable through 0-insertion, reshaping our understanding of cyclic equalizability.
The random cut is one of the most fundamental shuffles in card-based cryptography: it rotates a sequence of face-down cards by a secret amount. Under this shuffle, two sequences of cards are indistinguishable if and only if they are cyclic shifts of each other. This motivates the question of whether, given two sequences of cards, inserting cards at matching positions can make them indistinguishable. A previous study shows that such an insertion is always possible when any cards may be inserted, as long as the two words are permutations of each other. This paper considers a stronger restriction: if the cards are binary, carrying only 0 or 1, can we insert only 0s to make the sequences indistinguishable? We call two words 0-cyclically equalizable if one can insert 0s into both sequences at matching positions so that the resulting words are cyclic shifts of each other. Our main result is that two binary words of equal length are 0-cyclically equalizable if and only if they have equal Hamming weight, that is, the same number of 1-bits. Since equal Hamming weight is clearly necessary, the content of the paper is to show that it is also sufficient. Our proof is constructive: we encode a pair of binary words as a single word over the four-letter alphabet {A, B, X, O}, reduce equalizability to a simpler condition in this encoding, and build the required insertion explicitly.
