Cyclic Equalizability of Words and Its Application to Card-Based Cryptography

Kazumasa Shinagawa, Koji Nuida · 2025

Read Cyclic Equalizability of Words and Its Application to Card-Based Cryptography by Kazumasa Shinagawa, Koji Nuida (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04916.txt.

Introduction

Kazumasa Shinagawa and Koji Nuida wrote a 2025 paper that links card-based cryptography to the mathematics of words. Card-based cryptography does computations and checks with a plain deck, in full view. The field has grown close to group mathematics in recent years. Words had not been linked to it until now.

The core idea is this: a set of words can be made to match when read in a ring, a cyclic order. The trick is to insert the same letters into all words at once, repeatedly, until the ring readings match. The main result shows that two words over a two-letter alphabet, of equal length and equal count of each letter, can always be matched in this way. That result is then put to work in card cryptography. It serves an erasure problem, and a protocol where one cut reveals all cards at once.

Catalog record

CREATORKazumasa Shinagawa, Koji Nuida
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-04916

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Cyclic Equalizability of Words and Its Application to Card-Based Cryptography Kazumasa Shinagawa, Koji Nuida Abstract Card-based cryptography is a research area to implement cryptographic procedures using a deck of physical cards. In recent years, it has been found to be related to finite group theory and algebraic combinatorics, and is becoming more and more closely connected to the field of mathematics. In this paper, we discuss the relationship between card-based cryptography and combinatorics on words for the first time. In particular, we focus on cyclic equality of words. We say that a set of words are cyclically equalizable if they can be transformed to be cyclically equal by repeated simultaneous insertion of letters. The main result of this paper is to show that two binary words of equal length and equal Hamming weight are cyclically equalizable. As applications of cyclic equalizability to card-based cryptography, we describe its applications to the information erasure problem and to single-cut full-open protocols. 1 Introduction 1.1 Background Suppose that n players P_{1},P_{2},\ldots,P_{n} each having inputs x_{1},x_{2},\ldots,x_{n}\in\{0,1\} , respectively, wish to compute the output value f(x_{1},x_{2},\ldots,x_{n})\in\{0,1\} for some function f\colon\{0,1\}^{n}\rightarrow\{0,1\} . This is called distributed computing. Secure computation is a kind of distributed computing where the inputs are not leaked from the protocol execution more than what is computed from the output value. It has many practical applications, e.g., a voting for two candidates: given a candidate 0 and a candidate 1, each player inputs one bit as a vote, and the output value is the index of the candidate who receives a majority of votes. Although secure computation is usually implemented on electronic computers, there is a line of research that implements secure computation using a deck of physical cards, and such a research area is called card-based cryptography [ 1 , 2 , 11 ] . In card-based cryptography, we usually use a deck of cards whose faces are either or and whose backs are the same symbol ? . Here, the cards with the same symbol are assumed to be indistinguishable. We use a pair of cards to encode one bit information by \raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}=0 and \raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}=1 , and a pair of face-down cards ? ? encoding x\in\{0,1\} is called a commitment to x . Given n commitments to x_{1},x_{2},\ldots,x_{n}\in\{0,1\} , a protocol for f:\{0,1\}^{n}\rightarrow\{0,1\} computes the output value f(x_{1},x_{2},\ldots,x_{n}) without revealing the inputs beyond the output by performing a sequence of physical operations such as shuffling. The history of card-based cryptography began with the five-card trick proposed by den Boer [ 1 ] in 1989. The purpose of den Boer’s paper itself was to construct a cryptographic protocol, which is assumed to be implemented on electronic computers, and physical cards were used to illustrate the idea of the protocol. In 1994, Crépeau and Kilian [ 2 ] showed the feasibility of card-based protocol for any function and developed the basic theory of card-based cryptography. The turning point in card-based cryptography was the proposal of a rigorous computational model of card-based protocols known as the Mizuki–Shizuya model by Mizuki and Shizuya [ 11 ] . After Mizuki–Shizuya’s paper, this research field was revitalized as it became actively studied both in terms of protocol construction (e.g., [ 14 ] ) and impossibility proofs regarding the number of cards and the number of operations (e.g., [ 7 , 5 ] ). In recent years, the connection with mathematical fields has been deepening such as finite group theory [ 4 , 12 ] , algebraic combinatorics [ 15 ] , and formal method [ 6 ] . However, such an attempt has only just begun, and the development of new connections with other mathematical fields is important for the further development of this field. In this paper, we focus on combinatorics on words [ 8 , 9 , 10 ] and study a new notion of cyclic equalizability of words. As discussed in Section 1.2 , this concept appears naturally in card-based cryptography, but has never been studied. This is the first study to discuss card-based cryptography and combinatorics on words, and our main contribution is to bring these two fields together. We believe that this paper will lead to the development of the relation between card-based cryptography and combinatorics on words. 1.2 Cyclic Equalizability from Card-Based Cryptography In this section, we see that cyclic equalizability appears naturally in card-based cryptography by observing a protocol called the five-card trick [ 1 ] , which uses a random cut . A random cut is a shuffling operation that cyclically shifts a sequence of face-down cards a random number of times. For a sequence of face-down cards (c_{0},c_{1},\ldots,c_{n-1}) , we obtain (c_{r},c_{r+1},\ldots,c_{r+n-1}) , where r\in\mathbb{Z}_{n} is a secret number chosen uniformly at random and the subscript is modulo n . Here, the secret number r is hidden from all players and nobody can guess it. We use \langle\cdot\rangle to denote the application of a random cut to a sequence of cards. Random cuts are considered to be the simplest shuffling operation proposed so far, since they can be easily performed by a well-known shuffling method called Hindu shuffle . The five-card trick is a protocol for the AND function a\wedge b using a random cut. A secure computation protocol for the AND function can be used in the following situation: Alice and Bob are going to decide if they want to go on a date this weekend. However, Alice and Bob are very shy and embarrassed to tell each other directly whether they want to go on a date or not. This can be especially awkward if one of them wants to go on a date and the other does not. Is there any way to know just whether they both want to go on a date or not? If we assume that “1” means “I want to go on a date” and “0” means “I don’t want to go on a date”, and Alice and Bob each have inputs a,b\in\{0,1\} , then this problem can be solved by secure computation for the AND function a\wedge b . The five-card trick computing the AND function proceeds as follows. 1. Make the input commitments to a,b\in\{0,1\} . \underbrace{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}_{a}\,\underbrace{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}_{b}\,. 2. Swap the left and right cards of the commitment to a . \underbrace{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}_{a}\,\underbrace{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}_{b}~\rightarrow~\underbrace{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}_{\overline{a}}\,\underbrace{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}_{b}\,. 3. Insert a face-down card in the center. \underbrace{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}_{\overline{a}}\,\underbrace{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}_{b}~\rightarrow~\underbrace{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}_{\overline{a}}\,\underset{\heartsuit}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\underbrace{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}_{b}\,. 4. Apply a random cut. \Bigl\langle\;\overset{1}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{2}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{3}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{4}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{5}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\;\Bigr\rangle~\rightarrow~\begin{cases}\overset{1}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{2}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{3}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{4}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{5}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}&\mbox{w.p. $1/5$;}\\ \overset{2}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{3}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{4}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{5}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{1}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}&\mbox{w.p. $1/5$;}\\ \overset{3}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{4}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{5}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{1}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{2}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}&\mbox{w.p. $1/5$;}\\ \overset{4}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{5}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{1}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{2}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{3}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}&\mbox{w.p. $1/5$;}\\ \overset{5}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{1}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{2}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{3}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}\,\overset{4}{\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){\bf?}}}&\mbox{w.p. $1/5$.}\end{cases} 5. Open all cards. Output 0 if it is the left case and 1 if it is the right case. \begin{tabular}[]{ccc}$\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}$&&$\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}$\\ $\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}$&&$\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}$\\ $\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}$&&$\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}$\\ $\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}$&&$\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}$\\ $\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}$&&$\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\heartsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}\,\raisebox{-2.58334pt}{\pic@makebox@{\framebox}{framed=true}(11.0,13.0){${\scriptstyle\clubsuit}$}}$\end{tabular}. The security of the five-card trick follows from the fact that for any given input (a,b) such that a\wedge b=0 , the resulting sequence is chosen uniformly at random from five patterns on the left side due to the effect of the random cut. Indeed, if a\wedge b=0 , a sequence of cards just after Step 2 is given as follows: (a,b)=(0,0) ; (a,b)=(0,1) ; (a,b)=(1,0) . Then, a sequence of cards just after Step 3 is given as follows: (a,b)=(0,0) ; (a,b)=(0,1) ; (a,b)=(1,0) . Since these sequences are cyclically equal (see Definition 2.1 ), they become indistinguishable after a random cut is applied. We get three cyclically

Read the complete text