0-Cyclic Equalizability of Binary Words Characterized by Hamming Weight Sarunyu Thongjarast1⋆
arXiv:2607.18452v1 [cs.CR] 20 Jul 2026
Massachusetts Institute of Technology, Cambridge, MA, USA [email protected]
Abstract. 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 [7] 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.
1
Introduction
Card-based cryptography studies how to carry out secure computations using only a deck of physical cards, with no computer involved. The field began with den Boer’s five-card trick [1], which lets two players compute the logical and of their private bits. The procedure reveals nothing more than the AND value. It was later placed on a rigorous footing by the computational model of Mizuki and Shizuya [4]. In a typical protocol, players arrange face-down cards and then apply a shuffle: a randomized operation that scrambles the cards so that, once they are turned face up, the visible arrangement reveals the intended output but nothing about the individual inputs (unless it can be implied by the intended output). Among these shuffles, the random cut is the simplest and most widely used. It cyclically rotates the sequence by an amount that no participant knows. Two ⋆
Corresponding author
2
S. Thongjarast
sequences of cards that are cyclic shifts of each other become indistinguishable. This property makes many random cut protocols secure. This motivates a combinatorial question. Suppose two card sequences encode two situations that a protocol must keep indistinguishable. When can we pad them — by inserting extra helping cards at the same positions in both — so that the padded sequences are indistinguishable after a random cut? Modeling a sequence of two-colored cards as a binary word, a random cut as a cyclic shift, and the simultaneous padding of both sequences as a simultaneous insertion of identical letters at identical positions, we say that two words are cyclically equalizable if some simultaneous insertion makes them cyclic shifts of one another. Because a simultaneous insertion adds the same letters to both words, it preserves the difference between their letter counts, and cyclic shifts have equal letter counts. Equal letter counts are therefore necessary for equalizability, regardless of which symbols one is allowed to insert. The interesting direction is sufficiency. Shinagawa and Nuida [6] proved that for binary words this single obstruction is also sufficient: two binary words are cyclically equalizable if and only if they have equal Hamming weight. This was later generalized to arbitrary alphabets, where the characterizing invariant becomes the full vector of letter counts; equivalently, the two words must be permutations of each other [7]. In all of this prior work, the inserted helping cards may be of any type. From the standpoint of an actual protocol this is a hidden cost, since each distinct symbol corresponds to a distinct kind of helping card that must be supplied. It is therefore natural to ask how restricted the inserted symbols can be. In this paper we push the restriction to its extreme and permit insertions of only one symbol, which we take to be 0. We call two binary words 0-cyclically equalizable if they can be made cyclic shifts of each other by simultaneously inserting only 0s. Our main result is that this most economical form of padding is already as powerful as the general one. Main Theorem (see Theorem 3). Two binary words of equal length are 0-cyclically equalizable if and only if they have the same Hamming weight. That is, a single type of helping card always suffices; one never needs the other symbol. Necessity is immediate, so the work lies in showing that equal Hamming weight lets us realize the equalization using 0s alone, and our argument does so constructively, producing an explicit insertion.1 The proof encodes the two input words into one. To each position we assign a letter of the alphabet {A, B, X, O} recording the pair of bits carried there: A and B mark the two ways the words can disagree (A when the bit of the first word is 0 and the bit of the second word is 1, and B otherwise), X marks a shared 1, and O marks a shared 0. Under this encoding, equal Hamming weight becomes the condition |s|A = |s|B ; the requirement that one word be a cyclic shift of the 1
A Python implementation of the construction is available at https://github.com/ SThongjarast/Binary-Equalization.
0-Cyclic Equalizability of Binary Words Characterized by Hamming Weight
3
other becomes a local shift-compatibility condition; and inserting a 0 into both words becomes inserting the single letter O. This reduction lets us argue entirely about one four-letter sequence. We then build the insertion in stages of increasing generality. We first treat sequences over {A, B}. After rotating the sequence to begin at a valley, an index from which every cyclic prefix has at least as many As as Bs, we pair each A with a B using an interleaving family of arcs, and then insert Os so that every arc spans the same length d; once the arcs are equal, the sequence is shift-compatible with offset d. We extend this to sequences containing X by expanding each X into the pair BA, running the {A, B} construction, and contracting the pairs back. Finally, we handle sequences containing O by removing the existing Os, equalizing the remainder, and reinserting the Os into the gaps the construction provides. Related Work Cyclic equalizability was introduced by Shinagawa and Nuida [6], who studied it for binary words. The extension to arbitrary alphabets was given in [7]. Both works focus on the Parikh vector, the tuple of letter multiplicities of a word. Words with the same Parikh vector are called abelian equivalent, and their study forms the area of abelian combinatorics on words [2]. Our problem is also tied to the classical notion of conjugacy (cyclic equivalence) of words, studied extensively in combinatorics on words [3].
2
Preliminaries
In this section, we recall the basic notions used throughout the paper. Our terminology follows [6, 7], with the σ-restricted variants of simultaneous insertion and cyclic equalizability adapted to our setting. Let n be a positive integer. We denote by Zn the set {0, 1, . . . , n − 1}, and we identify i mod n with the unique element j ∈ Zn such that i ≡ j (mod n). Let Σ be a finite alphabet. A word over Σ is a finite sequence of letters in Σ. We denote by Σ ∗ the set of all words over Σ, and by ε the empty word. For a word w ∈ Σ ∗ , we denote its length by |w| and its i-th letter by w(i) , using zero-indexing. That is, if |w| = n, then w = w(0) w(1) · · · w(n−1) . Definition 1 (Number of Occurrences). Let Σ be a finite alphabet, let c ∈ Σ, and let w ∈ Σ ∗ . We define |w|c to be the number of occurrences of c in w. Definition 2 (Hamming Weight). Let w be a binary word. The Hamming weight of w is |w|1 . Definition 3 (Cyclic Equivalence). Let w1 , w2 be two words of equal length n. We say that w1 and w2 are cyclically equivalent if there exists an integer d (i) (i+d mod n) such that w1 = w2 for all i = 0, 1, . . . , n − 1. In that case, we say that w2 is a cyclic shift of w1 with offset d. Definition 4 (Simultaneous Insertion). Let k ≥ 2 and let w1 , . . . , wk ∈ Σ n be words of equal length n and let σ be a subset of Σ. A σ-simultaneous insertion
4
S. Thongjarast
is an operation that transforms each word wi = ai,0 ai,1 · · · ai,n−1 into the word u0 ai,0 u1 ai,1 · · · un−1 ai,n−1 un , where each uj is a word in σ ∗ . That is, every word receives identical insertions at identical positions. When σ = Σ, we simply call this a simultaneous insertion. Definition 5 (Cyclic Equalizability). Let k ≥ 2 and let w1 , . . . , wk ∈ Σ ∗ be words of equal length and let σ ⊆ Σ. We say these words are σ-cyclically equalizable if there exist words w1′ , . . . , wk′ ∈ Σ ∗ such that 1. Each wi′ is obtained from wi by a σ-simultaneous insertion, and 2. The words w1′ , . . . , wk′ are cyclically equivalent. When σ = Σ, we simply say these words are cyclically equalizable. In the following examples, bold and underlined letters indicate inserted letters. For example, the words 1234 and 2143 are cyclically equalizable, since we can simultaneously insert letters to obtain 142324
and
241423.
The transformed words are cyclically equivalent with offset 2. Similarly, the words 0110 and 1010 are 0-cyclically equalizable, since we can simultaneously insert 0 to obtain 01010
and
10010.
The transformed words are cyclically equivalent with offset 2. In contrast, one can verify that the words 012 and 021 are not 1-cyclically equalizable: we cannot insert 1 into both words at the same position to make them cyclically equivalent. However, the words are 0-cyclically equalizable since we can simultaneously insert 0 to obtain 0102
and
0201.
The transformed words are cyclically equivalent with offset 2.
3
Known Properties of Cyclic Equalizability
In this section, we review known results on cyclic equalizability that motivate our work. Theorem 1 ([6]). Let u, v ∈ {0, 1}n be binary words of equal length. Then, u and v are cyclically equalizable if and only if |u|1 = |v|1 . Theorem 2 ([7]). Let Σ be a finite alphabet, and let u, v ∈ Σ n be words of equal length. Then, u and v are cyclically equalizable if and only if |u|c = |v|c for all c ∈ Σ.
0-Cyclic Equalizability of Binary Words Characterized by Hamming Weight
4
5
Reformulation of 0-Cyclic Equalizability of Two Binary Words
In this section, we state our main result and provide a reformulation of the problem that will be used throughout. Theorem 3 (Main Theorem). Let w1 , w2 ∈ {0, 1}n be binary words. Then, w1 and w2 are 0-cyclically equalizable if and only if they have the same Hamming weight. The necessity direction is straightforward. Suppose that w1 and w2 are 0cyclically equalizable. Then we can simultaneously insert 0 to obtain w1′ and w2′ so that w1′ and w2′ are cyclically equivalent. Because inserting 0s does not change the Hamming weight, we have |w1 |1 = |w1′ |1 and |w2 |1 = |w2′ |1 . Since w1′ and w2′ are cyclically equivalent, they have equal Hamming weight, and hence |w1 |1 = |w2 |1 . 4.1
Reformulating the Problem
Our goal now is to show the sufficient condition: if w1 , w2 are two binary words of equal length and Hamming weight, then they are 0-cyclically equalizable. We will begin our proof by encoding the two words into one. Definition 6 (Encoding). Let w1 , w2 ∈ {0, 1}n be binary words. We define the encoding of (w1 , w2 ) as the word s ∈ {A, B, X, O}n of length n where (i) (i) A, if w1 = 0 and w2 = 1 (i) (i) B, if w1 = 1 and w2 = 0 s(i) = (i) (i) X, if w1 = 1 and w2 = 1 (i) (i) O, if w1 = 0 and w2 = 0. Definition 7 (ABXO-sequence). Let s be a word over {A, B, X, O}. We say s is an ABXO-sequence if |s|A = |s|B . Similarly, we define AB-sequences, ABX-sequences, and ABO-sequences as words over {A, B}, {A, B, X}, and {A, B, O}, respectively, satisfying the same condition |s|A = |s|B . Proposition 1. Let w1 , w2 ∈ {0, 1}n be two binary words, and s be their encoding. Then, w1 and w2 have the same Hamming weight if and only if |s|A = |s|B . Proof. Notice that |w1 |1 = |s|B + |s|X |w2 |1 = |s|A + |s|X . Therefore, the Hamming weights of w1 and w2 are equal if and only if |s|B +|s|X = |s|A + |s|X , which can be simplified as |s|A = |s|B . ⊔ ⊓
6
S. Thongjarast
Example 1. Let n = 6 and take the words w1 = 011010 and w2 = 110010. This gives s = AXBOXO. Here |s|A = |s|B = 1, matching the equal Hamming weights |w1 |1 = |w2 |1 = 3. Definition 8 (Shift-Compatible and Shift-Equalizable). Let s be an ABXOsequence of length n and let d be an integer. We call s shift-compatible with offset d if for all i = 0, 1, . . . , n − 1, we have • if s(i) ∈ {A, X}, then s(i+d mod n) ∈ {X, B}, and • if s(i) ∈ {B, O}, then s(i+d mod n) ∈ {A, O}. Additionally, if we can obtain s′ by inserting O into an ABXO-sequence s so that s′ is shift-compatible, we call s O-shift-equalizable. At this point, the shift-compatibility condition looks complicated. In fact, it is simpler than it looks: Theorem 9 shows that the second condition follows automatically from the first. Proposition 2. Let w1 , w2 ∈ {0, 1}n be two binary words, let s be their encoding, and let d be an integer. Then, w2 is a cyclic shift of w1 with offset d if and only if s is shift-compatible with offset −d. Proof. Suppose that w2 is a cyclic shift of w1 with offset d. For each i, if s(i) ∈ (i) (i−d mod n) {A, X}, then w2 = 1. Thus, w1 = 1, implying that s(i−d mod n) ∈ {X, B}. (i) (i−d mod n) (i) Similarly, if s ∈ {B, O}, then w2 = 0. Thus, w1 = 0, implying that (i−d mod n) s ∈ {A, O}. By definition, s is shift-compatible with offset −d. The forward direction is proven. (i) Suppose that s is shift-compatible with offset −d. For each i, if w2 = 0, then (i−d mod n) (i) s(i) ∈ {B, O}, so s(i−d mod n) ∈ {A, O} and w1 = 0. Similarly, if w2 = 1, (i−d mod n) (i) (i−d mod n) then s ∈ {A, X}, so s ∈ {X, B} and w1 = 1. This implies that w1 is a cyclic shift of w2 with offset −d, which is equivalent to saying that w2 is a cyclic shift of w1 with offset d. The backward direction is proven. ⊔ ⊓ Proposition 3. Let w1 , w2 ∈ {0, 1}n be two binary words of equal Hamming weight and let s be their encoding. Then, w1 and w2 are 0-cyclically equalizable if and only if s is O-shift-equalizable. Proof. Inserting 0 simultaneously into w1 and w2 at the same position corresponds exactly to inserting O at that position in s, since 0 encodes as O in both words. The result then follows from Proposition 2. ⊔ ⊓ Example 2. Let w1 = 011010 and w2 = 110100. Note that w2 is a cyclic shift of w1 with offset 5. The encoding gives s = AXBABO. We check that s is shiftcompatible with offset 1: 012345 AXBABO s(i+1 mod 6) X B A B O A i s(i)
Each column obeys the rule: A → X, X → B, B → A, A → B, B → O, and O → A.
0-Cyclic Equalizability of Binary Words Characterized by Hamming Weight
7
With Propositions 1 and 3, we can shift our focus from binary words to ABXOsequences, as shown in the following theorem, which is equivalent to the sufficiency direction of Theorem 3. Theorem 4 (Reformulated Main Theorem). Let s be an ABXO-sequence. Then, s is O-shift-equalizable.
5
Construction of Insertion for AB-Sequences
In this section, we prove that every AB-sequence is O-shift-equalizable. That is, we handle the case where the initial sequence contains only As and Bs. 5.1
Intuition and Construction Overview
Let s be an AB-sequence. Suppose we obtain s′ (an ABO-sequence) of length n′ by inserting O into s so that s′ is shift-compatible with offset d. Because there are (i) (i+d mod n′ ) no Xs in s′ , if s′ = A, it must follow that s′ = B. This establishes a bijection between As and Bs in s′ , and hence in s. Therefore, our proof has two main steps: 1. Construct a bijection between As and Bs in s. 2. Insert Os into s so that each corresponding A-B pair in s′ is separated by the same offset d.
A
O
A
B
A
B
O
B
0
1
2
3
4
5
6
7
′
(a) After inserting two Os we obtain s = AOABABOB. Every A maps to a B exactly 3 positions to its right, so s′ is shift-compatible with offset d = 3.
A
A
B
A
B
B
0
1
2
3
4
5
(b) The original sequence s = AABABB carries the same A-B bijection. The arcs are now of unequal length; inserting Os stretches each one to the common offset.
Fig. 1: Equalizing s = AABABB. The bijection between As and Bs is fixed first (b); inserting Os then stretches every arc to the common offset d = 3 (a).
5.2
Cyclic Shift of the Initial Sequence
Note that if s1 and s2 are cyclic shifts of each other, then s1 is O-shift-equalizable if and only if s2 is. Therefore, without loss of generality, we may replace s by
8
S. Thongjarast
any of its cyclic shifts. In this section, we identify a cyclic shift of s that will be convenient for our construction. Definition 9 (Valley). Let s be an AB-sequence of length n. An index a ∈ Zn is called a valley if for every k = 0, 1, 2, . . . , n − 1, the substring s(a) s(a+1 mod n) . . . s(a+k−1 mod n) contains at least as many As as Bs. Lemma 1. Every AB-sequence has at least one valley. Proof. Let s be an AB-sequence of length n. Define s[a:b] as s(a) s(a+1 mod n) . . . s(b−1 mod n) . Define f (i) = |s[0:i] |A − |s[0:i] |B . Let a be an index where f achieves its minimum. We claim that a is a valley. That is, |s[a:a+k] |A − |s[a:a+k] |B ≥ 0 for all k ∈ Zn . If a + k < n, then |s[a:a+k] |A − |s[a:a+k] |B = f (a + k) − f (a), which is non-negative because f (a) = mina′ ∈Zn f (a′ ). If a + k ≥ n, then since f (n) = 0 (as s is an AB-sequence), |s[a:a+k] |A − |s[a:a+k] |B = (f (n) − f (a)) + f (a + k − n) = f (a + k − n) − f (a), which is non-negative for the same reason. Therefore, a is indeed a valley.
⊓ ⊔
Example 3. Consider the AB-sequence s = ABABBABA of length 8. Reading each A as a step of +1 and each B as a step of −1, the prefix-sum function f (i) = |s[0:i] |A − |s[0:i] |B takes the values i 01234 5 6 7 8 f (i) 0 1 0 1 0 −1 0 −1 0 shown below as a path that rises on each A and falls on each B. The minimum value −1 is attained at i = 5 and i = 7. Therefore, both indices 5 and 7 are valleys. A
B
A
B
B
A
B
A
1
0 −1 valley 0
1
2
3
4
5
valley 6
7
8
0-Cyclic Equalizability of Binary Words Characterized by Hamming Weight
5.3
9
Bijection Construction
In this section, we construct a bijection between As and Bs in s. To motivate the construction, consider arranging the letters of s′ on a circle. Since s′ is shiftcompatible, each A is paired with a B at a fixed offset d, and we can draw a chord connecting each such pair. One can observe that these chords cross each other in an interleaving manner. The same crossing structure must therefore appear in s before any Os are inserted. First, we formalize what a chord is in the following definition. Definition 10 (Arcs). Let n be a positive integer and let i, j ∈ Zn . The arc from i to j, denoted rn (i, j), is the set of indices rn (i, j) = {i mod n, i + 1 mod n, . . . , j − 1 mod n}, and i and j are called the start and end of that arc, respectively. We say that arc rn (i1 , j1 ) is contained in arc rn (i2 , j2 ) if rn (i1 , j1 ) ⊆ rn (i2 , j2 ). Next, we define how chords interleave each other. Definition 11 (Interleaving Arcs). Let s be an ABO-sequence of length n with n′ /2−1 |s|A + |s|B = n′ . We say that a sequence of arcs R = (rn (ik , jk ))k=0 is interleaving if it satisfies the following conditions: (i) For each k = 0, 1, . . . , n′ /2 − 1, we have ik < jk . That is, the arc does not wrap around the word. (ii) i0 < i1 < · · · < in′ /2−1 and j0 < j1 < · · · < jn′ /2−1 . (iii) Each letter A is the start of an arc in R, and each letter B is the end of an arc in R. n′ /2−1
Notice that a sequence of interleaving arcs R = (rn (ik , jk ))k=0 establishes a bijection between As and Bs in s. More specifically, s(ik ) corresponds to s(jk ) for k = 0, 1, . . . , n′ /2 − 1. Note that Os are not parts of the bijection. Next, we show the existence of a sequence of interleaving arcs. Theorem 5. Let s be an AB-sequence of length n such that 0 is a valley. Then, there is a sequence of interleaving arcs corresponding to s. More specifically, the following algorithm returns an interleaving sequence of arcs for s. Algorithm 1 Constructing the Interleaving Arcs 1: Let a0 < a1 < · · · < an/2−1 be the indices of A in s 2: Let b0 < b1 < · · · < bn/2−1 be the indices of B in s n/2−1 3: return (rn (ak , bk ))k=0
Proof. Because 0 is a valley, any prefix substring contains at least as many As as Bs. That is, the first bk + 1 letters of s contain exactly k + 1 copies of B, so the first bk letters of s contain at least k + 1 copies of A, implying that ak < bk for all k. Thus, the first condition for interleaving arcs is satisfied. The second and third conditions for interleaving arcs follow directly from the algorithm. ⊓ ⊔
10
S. Thongjarast
Finally, we show that if there is a sequence of interleaving arcs for s such that all arcs have equal size, then s is shift-compatible. Theorem 6. Let d be a positive integer and let s be an ABO-sequence where there exist interleaving arcs R such that each arc has size equal to d. Then, s is shift-compatible with offset d. Proof. Since s does not contain X, the shift-compatible condition becomes If s(i) = A then s(i+d mod n) = B If s
(i)
= B or s
(i)
= O then s
(i+d mod n)
= A or s
(*) (i+d mod n)
=O
(**)
Since each arc rn (ik , jk ) has size d, we have jk = ik + d for all k. By condition (iii) of interleaving arcs, s(ik ) = A and s(jk ) = B, so s(i) = A if and only if s(i+d mod n) = B. The condition (∗) is satisfied directly. The contrapositive of condition (∗∗) is that if s(i+d mod n) = B, then s(i) = A, which is true too. ⊓ ⊔ 5.4
Constructing Insertion of Os
In this section, we describe an algorithm for inserting Os into an AB-sequence, given an interleaving sequence of arcs, so that all arcs have equal size. Since a similar construction applies when s is an ABX- or ABXO-sequence with additional restrictions, we introduce the following definition. Definition 12 (Inverted Indices). Let s be an ABXO-sequence of length n. We call an index t ∈ Zn inverted if s(t) = B and s(t+1 mod n) = A. Theorem 7. Let s be an AB-sequence of length n such that 0 is a valley. Let n/2−1 n/2−1 R = (rn (ik , jk ))k=0 be a sequence of interleaving arcs for s. Let (ck )k=0 be a sequence of integers. Then, there is a sequence of non-negative integers b0 , b1 , . . . , bn−1 and a common non-negative integer d such that ck +
jX k −1
bl = d
l=ik
for all k = 0, 1, 2, . . . , n/2 − 1, and for all inverted indices t, we have bt = 0. Remark 1. In the AB-sequence case, taking ck = jk −ik (the size of arc rn (ik , jk )), the theorem implies that we can insert bi copies of O between s(i) and s(i+1) for each i = 0, 1, . . . , n − 1, so that all arcs in R have equal length d. Proof. Step 1: Find a Particular Solution This step finds a solution that allows bi to be negative. Fix d = 0. Since j0 < j1 < · · · < jn/2−1 , each equation for rn (ik , jk ) introduces a new free variable bjk −1 not appearing in any previous equation. We can
0-Cyclic Equalizability of Binary Words Characterized by Hamming Weight
11
therefore solve inductively to obtain an integer solution b′ = (b′0 , b′1 , . . . , b′n−1 ) satisfying jX k −1 ck + b′l = 0 l=ik
for all k = 0, 1, . . . , n/2 − 1. Notably, only b′jk −1 is nonzero for each k. If b′t ̸= 0 where t is an inverted index, we have that t + 1 = jk for some k. Thus, s(t+1) = B. However, since t is an inverted index, s(t+1) = A, which is a contradiction. Therefore, b′t = 0 for all inverted indices t. Step 2: Find a Homogeneous Solution with Non-negative Coefficients Consider the following system of equations jX k −1
(h)
bl
= εh
l=ik
for all k = 0, 1, . . . , n/2−1, where εh ∈ {0, 1} is a common value for all equations. For each non-inverted index h, we find a solution to that system of equations (h) (h) (h) (h) (h) b(h) = (b0 , b1 , . . . , bn−1 ) such that bh ≥ 1 and bt = 0 for all inverted indices t using the following algorithm. If some arc contains h, the algorithm returns a solution with εh = 1; otherwise, it returns a solution with εh = 0. Algorithm 2 Finding Homogeneous Solution for Column h (h)
(h)
1: bl ← 0 for all l; bh ← 1 2: Find k′ such that h ∈ rn (ik′ , jk′ ) (if multiple exist, choose any one; if none exists, skip the loop and return b(h) ) 3: for k ̸= k′ in order k′ − 1, k′ − 2, . . . , 0, k′ + 1, k′ + 2, . . . , n/2 − 1 do Pjk −1 (h) = 0 then 4: if l=ik bl (h)
5: bik ← 1 if k < k′ , 6: end if 7: end for 8: return b(h)
(h)
bjk −1 ← 1 if k > k′
(h)
If no arc contains h, the returned vector has bh = 1 as its only nonzero entry, so every arc sum is 0 and the system is satisfied with εh = 0. Otherwise, the algorithm is correct by the following observation. At each iteration k, the Pjk −1 (h) equation for arc rn (ik , jk ) is satisfied (i.e., l=i bl = 1). Moreover, it remains k satisfied in all subsequent iterations. This is because later iterations k ′′ only (h) (h) modify bik′′ or bjk′′ −1 , which lie outside rn (ik , jk ). Hence the sum over rn (ik , jk ) is not affected. (h) (h) Notably, only bik and bjk −1 can be nonzero. By the same argument as in (h)
Step 1, bt = 0 for all inverted indices t. Step 3: Find a Positive Integer Solution Pjk −1 Let the system of n/2 linear equations ck + l=i bl = d be written as k Ab + c = d1, where A ∈ {0, 1}n/2×n is the interval matrix of the arcs (its k-th
12
S. Thongjarast n/2−1
n row indicates rn (ik , jk )), b = (bi )n−1 ∈ Zn/2 , d ∈ Z, and i=0 ∈ Z , c = (ck )k=0 n/2 1∈Z is the all-ones vector. The first step shows that there exists b′ ∈ Zn such that Ab′ +c = 0 and b′t = 0 for all inverted indices t. The second step shows that for each non-inverted index (h) h there exists b(h) ∈ Nn0 such that Ab(h) = εh 1 with εh ∈ {0, 1}, bh ≥ 1, and (h) bt = 0 for all inverted indices t. P Let dm = maxi |b′i |. Consider b∗ = b′ + dm ( h not inverted b(h) ). If i is not an inverted index, then X (h) b∗i = b′i + dm bi ≥ b′i + dm ≥ b′i + |b′i | ≥ 0. h not inverted
If i is an inverted index, then b∗i = 0. Thus, b∗ has non-negative elements and Ab∗ + c = 0 + dm nt 1 = dm nt 1 where nt is the number of non-inverted indices h with εh = 1. Setting d∗ = dm nt , the pair (b∗ , d∗ ) solves the system of equations. (h) Moreover, since b′t and bt are always zero for all inverted indices t, we have that b∗t is also zero. As a result, b∗ satisfies the theorem requirement. ⊔ ⊓ Finally, we finish the construction for equalization of s. Theorem 8. Let s be an AB-sequence. Then, s is O-shift-equalizable. Proof. From Lemma 1, we can construct sv , which is a cyclic shift of s such that 0 is a valley. From Theorem 5, sv has a sequence of interleaving arcs. By choosing ck = jk − ik , Theorem 7 shows that we can obtain s′ by inserting Os into sv so that all arcs have equal size d. Finally, by Theorem 6, s′ is shift-compatible. Since sv is a cyclic shift of s and s′ is obtained from sv by inserting Os, we conclude that s is O-shift-equalizable. ⊓ ⊔ Remark 2. After the insertion, the length of s′ can be bounded by O(n3 2n/2 ). More specifically, |b′jk −1 | ≤ |ck | +
jX k −2 l=ik
|b′l | ≤ |ck | +
k−1 X
|b′jl −1 |
l=0
Pk−1 By induction, we have |b′jk −1 | ≤ |ck | + l=0 2l |ck−1−l |. Since |ck | ≤ n for all k, we have |b′jk −1 | ≤ n2k . Thus dm ≤ n2n/2 , so the offset is d∗ = dm nt = O(n2 2n/2 ). Since each gap holds at most d∗ copies of O, the output length is O(n · d∗ ) = O(n3 2n/2 ). Remark 3. We present a stronger bound for this problem, with a less constructive P proof: using the matrix setup, there is a solution b, d with offset d ≤ n k |ck | = O(n3 ). Since each gap holds at most d copies of O, the output length is O(n · d) = O(n4 ). The proof is given in Appendix A.
0-Cyclic Equalizability of Binary Words Characterized by Hamming Weight
13
Example 4. We run the complete construction on s = ABABBABA. Step 1 (shift to a valley). Since 5 is a valley index of s, we shift it so that index 0 is a valley: sv = ABAABABB. Step 2 (interleaving arcs). Applying Theorem 5 to sv , we get a collection of interleaving arcs R = {r8 (0, 1), r8 (2, 4), r8 (3, 6), r8 (5, 7)}
A
B
A
A
B
A
B
B
0
1
2
3
4
5
6
7
Fig. 2: Interleaving arcs for sv = ABAABABB: the k-th A is paired with the k-th B, giving (0, 1), (2, 4), (3, 6), (5, 7). The A endpoints increase from left to right, and so do the B endpoints, so the arcs interleave. Step 3 (insert Os to equalize). Using Theorem 7, we can insert O so that each arc has equal length, as shown in the following figure. That is, we can insert Os into sv to obtain s′ = AOOBAOABABOB, which is shift-compatible. This implies that s is O-shift-equalizable.
A
O
O
B
A
O
A
B
A
B
O
B
0
1
2
3
4
5
6
7
8
9
10
11
Fig. 3: After inserting Os into sv (two after index 0, one after index 2, one after index 6), we obtain s′ = AOOBAOABABOB. Every arc now has length 3, so s′ is shift-compatible with offset 3.
6
Construction for ABX-Sequences
In this section, we provide the construction of insertion for ABX-sequences. Intuitively, we replace each X in s with BA and proceed as if s were an AB-sequence. We will prove why this works. Theorem 9. Let d be a positive integer and let s be an ABXO-sequence of length n such that if s(i) ∈ {A, X}, then s(i+d mod n) ∈ {X, B}. Then, s is shift-compatible with offset d. This theorem shows that the second condition for shift-compatibility (if s(i) ∈ {B, O}, then s(i+d mod n) ∈ {A, O}) follows automatically from the first condition.
14
S. Thongjarast
Proof. Consider the directed graph G = (V, E) where V = {0, 1, . . . , n − 1} and E = {(i, i + d (mod n)) | s(i) ∈ {A, X}}. Consequently, if an index has non-zero in-degree, it must be either X or B. Notice that this is a subgraph of G′ = (V, E ′ ) where E ′ = {(i, i + d mod n) | i ∈ Zn }, which contains only cycles. Therefore, each connected component of G must be a chain (a component with at least one edge that is not a cycle), a cycle, or an isolated vertex. • If it is a cycle, every vertex must have non-zero in-degree and out-degree. The only possibility is that all vertices are indices of X. That is because other letters either have zero in-degree, zero out-degree, or both. • If it is an isolated vertex, it has zero in-degree and zero out-degree, so its letter must be B or O. We will see below that it must in fact be O. • If that connected component is a chain, the last vertex must be an index of B because of its zero out-degree but non-zero in-degree. Moreover, A must be the start of a chain because of its zero in-degree but non-zero out-degree. Hence, |s|A ≤ the number of chains ≤ |s|B . Because |s|A = |s|B from the definition of ABXO-sequence, the equality holds, so every chain starts with A and ends with B. In particular, every B is the end of a chain, so no B is an isolated vertex. This implies that, if s(i+d mod n) ∈ {X, B}, we have that s(i) ∈ {A, X}. The second shift-compatibility condition follows by contrapositive. ⊔ ⊓ Theorem 10. Let s be an ABX-sequence. Then, s is O-shift-equalizable. Proof. Suppose that |s|X = m and the length of s is n. Let se (the expansion of s) be the AB-sequence constructed by replacing each X in s with BA. Thus, the length of se is ne = n + m. Similar to the construction for AB-sequences, Lemma 1 guarantees that there is a cyclic shift sev of se such that 0 is a valley of sev . Let t0 < t1 < · · · < tm−1 be the inverted indices of sev caused by expanding X to BA in the earlier step. Call those m indices induced inverted indices. ne /2−1 From Theorem 5, sev has a sequence of interleaving arcs Re = (rne (iek , jke ))k=0 . Let vk be the number of induced inverted indices in rne (iek , jke ). By choosing ck = jke − iek − vk , there is a way to obtain sev ′ by inserting Os into sev so that the length of each arc minus the number of induced inverted indices contained in that arc is the same for all arcs and no Os are inserted after induced inverted indices. After that, we obtain s′v by reducing the pairs BA in sev ′ that we expanded earlier to be X. This reduction is possible because we did not insert any O between those pairs. Because of this reduction, the sequence of interleaving arcs Re induces a collection of arcs R in s′v . ne /2−1 Notice that R = (rn (ik , jk ))k=0 is generally similar to a sequence of interleaving arcs, except that at most one arc may wrap around index 0. More specifically, R has the following property:
0-Cyclic Equalizability of Binary Words Characterized by Hamming Weight
15
• Each letter A is the start of an arc in R, each letter B is the end of an arc in R, and each letter X is both the start of one arc and the end of another arc. • Each arc in R has cyclic length exactly d, that is, jk ≡ ik +d (mod n), where d is the common value from Theorem 7. • At most one arc wraps around index 0. This happens only when an induced pair itself wraps around the word, that is, its B is at the last index and its A is at index 0. In that case, the arc ending at that B now ends at the merged X at index 0. All other arcs satisfy ik < jk . The first condition is true because X functions as both A and B. The second condition is true because of the choice of ck : reducing an induced pair contained in an arc shortens that arc by exactly one, and no O was inserted between the letters of a pair. The wrapping pair is never contained in any arc, since every arc’s index set ends at jk − 1 ≤ ne − 2; reducing it moves the last position onto index 0 without changing the cyclic length of any arc. From Theorem 9, the existence of R implies that the word s′v is shiftcompatible. So far, given s, we expand it to se and cyclically shift it to sev . We insert Os into sev to obtain sev ′ without separating any BA pairs, and we reduce it to s′v . The operations ensure that we can insert Os into s so that it is cyclically equivalent to s′v . Therefore, s is O-shift-equalizable. Remark 4. Note that the proof also works when the valley is an index of A created by the expansion of X. Example 5. We run the construction on the ABX-sequence s = AXBABX. Step 1 (expand each X to BA). Replacing both Xs gives se = ABABABBA. Shifting so that the first index is a valley, we obtain sev = AABABABB. Step 2 (find arcs and insert O). The interleaving arcs of sev are R = {r8 (0, 2), r8 (1, 4), r8 (3, 6), r8 (5, 7)}, Inserting O gives sev ′ = AAOBABABOB. Note that this sequence is not shift-compatible yet.
16
S. Thongjarast
A
A
B
A
B
A
B
B
0
1
2
3
4
5
6
7
induced pair wraps
Fig. 4: Step 2 for sev = AABABABB: arcs (0, 2), (1, 4), (3, 6), (5, 7). Notice that this induced pair wraps around the end and the start of the word. This does not break our algorithm.
A
A
O
B
A
B
A
B
O
B
0
1
2
3
4
5
6
7
8
9
induced pair wraps
Fig. 5: After inserting O (at indices 2, 8): sev ′ = AAOBABABOB, with arc lengths 3, 4, 3, 3. The long arc (1, 5) still holds the middle induced pair, so the word is not yet shift-compatible. Step 3 (collapse BA back to X). Collapsing both induced pairs to X shrinks the long arc to match the rest and yields s′ = XAOXBABO, which is shift-compatible with offset 3. Hence s is O-shift-equalizable.
7
Construction for ABXO-Sequences
Finally, we provide the construction for equalizing any ABXO-sequence. Theorem 11. Let s be an ABXO-sequence. Then, s is O-shift-equalizable. Proof. If s only contains the letter O, the theorem is trivial. Thus, assume that s has at least one non-O letter. Because a cyclic shift does not affect the shiftequalizability, without loss of generality, s starts with a non-O letter. Let ℓO be the length of the longest run of O in s. Let sr be the ABX-sequence obtained by removing all O from s. By Theorem 10, we can insert O into sr to obtain s′r so that s′r is shift-compatible with offset d.
0-Cyclic Equalizability of Binary Words Characterized by Hamming Weight
17
Then, we obtain s′ by inserting ℓO copies of O after each character in s′r (i) (i×(ℓO +1)) (including the end). That is, s′r = s′ . This construction implies that ′ s is shift-compatible with offset (ℓO + 1) × d: a step of size d in s′r corresponds to a step of size (ℓO + 1) × d in s′ . By the maximality of ℓO , the original Os in s can be accommodated within the inserted copies, so s′ is obtained from s by inserting Os. Therefore, s is O-shift-equalizable, as desired. Example 6. We run the construction on the ABXO-sequence s = AOXBOAOOBX. Step 1 (remove every O). Deleting all O leaves the ABX-sequence sr = AXBABX. Step 2 (equalize sr ). By the previous example, inserting O into sr gives s′r = XAOXBABO, shift-compatible with offset d = 3. Step 3 (pad with O). The longest O-run in s is OO, so ℓO = 2. Insert two Os after each character of s′r : s′ = XOO AOO OOO XOO BOO AOO BOO OOO = XOOAOOOOOXOOBOOAOOBOOOOO, shift-compatible with offset (ℓO + 1) d = 3 × 3 = 9. The original Os of s fit inside the inserted copies, so s is O-shift-equalizable.
8
Consequences
The Main Theorem (Theorem 3) can be restated as follows: any two binary words that are permutations of each other can be made cyclically equivalent by a single 0-simultaneous insertion. The same statement holds for 1-insertion, by complementing both words. The construction is explicit, so it also bounds the length of the resulting words. By Remark 2, equalizing an AB-sequence yields output length O(n3 2n/2 ), which remains exponential through the ABX and ABXO stages. The sharper analysis of Appendix A removes the exponential factor: an AB-sequence has offset d = O(n3 ) and hence output length O(n · d) = O(n4 ); expanding X preserves this degree, and the O-runs of length O(n) then give output length O(n5 ) for an ABXO-sequence. We do not claim this bound is tight.
9
Application to Card-Based Cryptography
We return to the card model that motivated the theorem. In the standard twocolored setting [1, 4], a ♣ encodes 0 and a ♡ encodes 1, so a face-down sequence is a binary word, and a random cut applies a uniformly random cyclic shift. Two
18
S. Thongjarast
sequences are thus indistinguishable after a random cut if and only if they are cyclic shifts of each other. Our result is a tool for protocol designers. Our theorem shows which card configurations a designer can make indistinguishable, and at what cost. Let C1 and C2 be two sequences of equal length. • If they contain the same number of ♡ cards, they can always be made indistinguishable under a random cut, using a single type of helping card (♣). • If they contain different numbers of ♡ cards, no insertion can achieve this, regardless of how many cards or types are used. The construction may insert many ♣ cards, up to O(n5 ) for sequences of length n. Reducing this number remains open.
10
Open Problems
We close with two questions left open by this work. 10.1
Sharpness of the length bound
Our construction equalizes two binary words of length n while increasing their length to O(n5 ) (Appendix A). We do not know whether this polynomial bound is sharp. Problem 1. What is the exact, non-asymptotic length needed to equalize two binary words of length n? In particular, is there a family of words that requires Ω(n3 ) inserted symbols, and can the O(n5 ) upper bound be lowered to meet such a lower bound? 10.2
Discarding a letter over larger alphabets
Our binary result shows that one letter is never needed: the letter 1 can be discarded. We ask whether one letter can always be discarded over larger alphabets. The discarded letter cannot be fixed in advance. Over Σ = {0, 1, 2}, the words 012 and 021 are permutations of each other, but they are not {1, 2}-equalizable: each word contains a single 0, so the two 0s must align, and the other letters can thus never be made to match. Problem 2. Let Σ be an alphabet of size at least 3. Let u and v be words over Σ that are permutations of each other. Must there exist a letter c ∈ Σ such that u and v are (Σ \ {c})-equalizable?
Acknowledgements The author is grateful to Suthee Ruangwises for introducing him to this line of research and for his advice on publication venues.
0-Cyclic Equalizability of Binary Words Characterized by Hamming Weight
A
19
Polynomial Length Bound
We now give a sharper bound on the amount of insertion. Remark 2 bounds the output length of an AB-sequence by O(n3 2n/2 ), an exponential quantity. Using linear algebra, we replace the exponential factor by a polynomial one. The construction is exactly that of Theorem 7; only the particular solution of Step 1 is chosen differently. Theorem 12. Let s be an AB-sequence of length n such that 0 is a valley, let R = (rn (ik , jk ))m−1 k=0 be a sequence of interleaving arcs for s with m = n/2, and let A ∈ {0, 1}m×n be the matrix whose k-th row indicates the arc rn (ik , jk ), that is, Ak,ℓ = 1 if and only if ik ≤ ℓ < jk (the interval matrix of Theorem 7). For m n any c = (ck )m−1 k=0 ∈ Z , there exist b ∈ N0 and d ∈ N0 such that Ab + c = d 1m , Pm−1 with d ≤ n k=0 |ck |.
and
bt = 0 for every inverted index t,
Proof. Let T ⊆ Zn be the set of inverted indices, and let AR be the m × (n − |T |) matrix obtained by deleting from A the columns indexed by T . Then AR is again an interval matrix, since deleting columns leaves each row a block of consecutive 1s. We show that AR still has full row rank. By Step 1 of the proof of Theorem 7, column jk − 1 is the unique pivot of row k, and the index jk − 1 is not inverted: if it were, then s(jk ) = A, contradicting s(jk ) = B. Hence no pivot column is deleted, so each row of AR still has its own pivot, and the rows of AR remain linearly independent. Append to AR the standard basis row eℓ for each non-pivot column ℓ, forming a square invertible matrix A′R ∈ {0, 1}(n−|T |)×(n−|T |) . Since A′R is still an interval −1 matrix, it is totally unimodular [5]; consequently every entry of A′R lies in {0, +1, −1}. −1 Let cp be c padded with zeros to length n − |T |, and put b′p = −A′R cp ∈ −1 has magnitude at Zn−|T | , so that A′R b′p + cp = 0. Because each entry of A′R most 1, m−1 X X X −1 |b′p,i | = (A′R )ij cp,j ≤ |cp,j | = |ck |. j
j
k=0
Discarding the appended rows of A′R and the padded zeros of cp leaves AR b′p +c = 0. Inserting a zero into b′p at each inverted index gives b′ ∈ Zn with Ab′ + c = 0 and b′t = 0 for all inverted indices t. Exactly as in Steps 2 and 3 of the proof of Theorem 7, adding a non-negative homogeneous solution makes all entries non-negative without altering the values on T , producing b∗ ∈ N0n with b∗t = 0 for all t ∈ T and Ab∗ +c = dm nt 1m , where dm = maxi |b′i | and nt ≤ n is as in Step 3 of that proof. Setting d∗ = dm nt , the pair (b∗ , d∗ ) solves the system, and d∗ = dm nt ≤ n max |b′i | ≤ n i
m−1 X k=0
|ck |.
20
S. Thongjarast
⊔ ⊓ Taking ck = jk − ik as in Remark 2 gives k |ck | = k (jk − ik ) = O(n2 ), so the offset satisfies d = O(n3 ), replacing the exponential offset of Remark 2 by a polynomial one. Since each gap holds at most d copies of O, the output length of an AB-sequence is O(n · d) = O(n4 ); the O-runs of the ABXO construction then multiply this by O(n), giving output length O(n5 ). P
P
References 1. Bert den Boer. More efficient match-making and satisfiability: The five card trick. In Advances in Cryptology — EUROCRYPT ’89, volume 434 of Lecture Notes in Computer Science, pages 208–217. Springer, 1990. 2. Gabriele Fici and Svetlana Puzynina. Abelian combinatorics on words: a survey. Computer Science Review, 47, 2023. 3. M. Lothaire. Combinatorics on Words. Cambridge University Press, 2nd edition, 1997. 4. Takaaki Mizuki and Hideaki Shizuya. A formalization of card-based cryptographic protocols via abstract machine. International Journal of Information Security, 13(1):15–23, 2014. 5. Alexander Schrijver. Theory of Linear and Integer Programming. Wiley, 1986. 6. Kazumasa Shinagawa and Koji Nuida. Cyclic equalizability of words and its application to card-based cryptography. In Proceedings of the 25th International Symposium on Fundamentals of Computation Theory (FCT), pages 406–419, 2025. 7. Sarunyu Thongjarast, Sarit Pasiphol, and Suthee Ruangwises. Cyclic equalizability characterized by Parikh vectors, 2025.