Hide a Liar:
Card-Based ZKP Protocol for Usowan⋆Léo Robert1 , Daiki Miyahara2,4 , Pascal Lafourcade1 , and Takaaki
Mizuki3,4
1

University Clermont Auvergne, LIMOS, CNRS UMR 6158, Aubière France{leo.robert,pascal.lafourcade}@uca.fr
2
The University of Electro-Communications, Tokyo, Japanmiyahara@uec.ac.jp
3
Cyberscience Center, Tohoku University, Sendai, Japanmizuki+lncs@tohoku.ac.jp
4
National Institute of Advanced Industrial Science and Technology, Tokyo, Japan

Abstract. A Zero-Knowledge Proof (ZKP) protocol allows a participant to prove the knowledge of some secret without revealing any information about it. While such protocols are typically executed by computers, there exists a line of research proposing physical instances of ZKP
protocols. Up to now, many card-based ZKP protocols for pen-and-pencil
puzzles, like Sudoku, have been designed. Those games, mostly edited by
Nikoli, have simple rules, yet designing them in card-based ZKP protocols is non-trivial. This is partly due to the fact that the solution should
not be leaked during the protocol. In this work, we propose a card-based
protocol for Usowan, a Nikoli game. In Usowan, for each room of a puzzle instance, there is exactly one piece of false information. The goal of
the game is to detect this wrong data amongst the correct data and also
to satisfy the other rules. Designing a card-based ZKP protocol to deal
with the property of detecting a liar has never been done. In some sense,
we propose a physical ZKP for hiding of a liar.
Keywords: Zero-knowledge Proof, Pencil Puzzle, Card-based Cryptography, Usowan

1

Introduction

Usowan [1] is a pencil puzzle played with a rectangular grid composedof numbered cells and white cells delimited by regions (thick edges). The
goal is to fill (in black) some cells:⋆

This paper appears in Proceedings of TAMC 2022. This version of the contribution has been accepted for publication, after peer review but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/
978-3-031-20350-3_17. Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use: https://www.springernature.com/gp/
open-research/policies/accepted-manuscript-terms.

2

L. Robert et al.

1. The numbered cells must remain white.
2. The white cells form a connected shape.
3. The black cells cannot connect vertically or horizontally.
4. A numbered cell has the corresponding number of black cells aroundit (vertically or horizontally). However, each region has exactly one
liar i.e., the number of black cells is not equal to the numbered cell.1
We depict in Fig. 1 an initial Usowan grid with its solution.
1 3

1 3
1

0

1

3
1 4
1

0
1

3
1 4
1

1

Fig. 1. Initial Usowan grid and its solution taken from [1].

Suppose that someone has found a solution for a given Usowan instance. Is it possible to design a protocol to convince anyone that he/she
has the solution without revealing it? The answer can be found in thefield of cryptography. Indeed, a Zero-Knowledge Proof (ZKP) is a process where one party can prove the knowledge of information without
revealing it. A simple application to ZKP can be related to password authentication for a website; only the person with this password can accessto sensitive data but it is preferable never to reveal the password.
More formally, a ZKP protocol is between two parties: a prover P who
knows a solution s to a problem and a verifier V who wants to be sure that
P is indeed in possession of the solution. However, no information abouts should leak during the protocol (except the information recoverable
without the help of the protocol). The protocol must guarantee three
security properties:
Completeness: if P knows s then V is convinced when the protocol ends.
Soundness: if P does not have the solution, then V will detect it during
the protocol.
Zero-knowledge: V learns nothing about s.
Usually, ZKP protocols are executed by computers. We restrict ourselves by using only physical cards and envelopes. In this paper, we present
1

A numbered cell whose number is four (or more) is automatically a liar. Indeed, if
there are four black cells around a numbered cell, then the numbered cell cannot be
connected to other white cells.

Hide a liar: Card-Based ZKP Protocol for Usowan

3a physical ZKP protocol for Usowan. While the hardness of the resolution
for the underlying problem (here filling an Usowan grid) is not crucial
for a physical protocol, a usual ZKP protocol needs to be based on a
NP-complete problem (otherwise the verifier could compute the secret inpolynomial time). Hopefully, the NP-completeness of Usowan has been
proved in [13]. This result ensures that there exists a ZKP protocol.
Contributions. We construct a physical ZKP protocol for Usowan, giving
the first application to detecting if a puzzle has flaws (i.e., the liar rule)
while ensuring that the prover has the solution. It is the first physical
ZKP protocol to prove that some information is incorrect among correct
information. For this, we only use cards and envelopes. Moreover, we
propose a trick that uses the rules of a Usowan grid in order to provethat exactly one piece of information is wrong in each room. For this,we use several sub-protocols to verify the rules and propose a completely
novel ZKP protocol.
Related Work. Goldwasser et al. [10] proved that any NP-complete problem has its corresponding interactive ZKP protocol. Yet the generic approach has tremendous overhead leading to an impractical result. Workson implementing cryptographic protocols using physical objects are numerous, such as in [21]; or in [8] where a physical secure auction protocol was proposed. Other implementations have been studied using cards
in [4, 15], polarising plates [37], polygon cards [38], a standard deck ofplaying cards [18], using a PEZ dispenser [2, 3], using a dial lock [19],using a 15 puzzle [20], or using a tamper-evident seals [23–25]. ZKP’s forseveral other puzzles have been studied such as Sudoku [30,36], Akari [5],Takuzu [5, 16], Kakuro [5, 17], KenKen [5], Makaro [6, 35], Norinori [9],Nonogram [7, 29], Slitherlink [15], Suguru [28], Nurikabe [27], Ripple Effect [32], Numberlink [31], Bridges [33], and Cryptarithmetic [12].
Outline. In Sect. 2, we explain how to encode a grid with some cards
in order to be able to construct our ZKP protocol. We also recall theexisting card-based simple protocols of the literature that we use in ourconstruction. In Sect. 3, we present our ZKP protocol for Usowan. We
give in Sect. 4 the security proofs of our protocol.
Overview of our protocol. Before detailing our protocol and exisiting subprotocols involved, we present an intuition of our construction (see Fig. 2).
We represent a colored cell by placing colored cards on the cell. In theconnectivity phase, P and V construct a connected figure according to4

L. Robert et al.
Setup:
P and V prepare the grid.

Connectivity:
P constructs a shape according to the solution.
V only knows that the figure P constructed is connected (rule 2 is verified).
V reveals the colors of numbered cells (rule 1 checked).

Verification:
V verifies the remaining rules:• rule 3: each pair of adjacent cells is checked using a disjunction (white= 1 and black= 0).
• rule 4: sum the numbers of the neighbours around numbered cells.

Protocol: How to form a white polyomino (Sect. 2.4)

Protocol: Five-card trick (Sect. 2.3)
Protocol: Sum (Sect. 2.5)

Fig. 2. Overview of our protocol

P ’s solution without V knowing the exact shape. Thus, V is convincedthat the resulting face-down cards satisfy the rule 2 (and the rule 1 canbe easily verified by just revealing face-down cards on numbered cells).
Then, in the verification phase, V checks the two remaining rules. The
rule 3 forces two adjacent cells to be composed of at least one white cell;
this rule is verified by computing a disjunction of each possible pair. For
verifying the rule 4, P and V compute the number of blacks around a
given numbered cell. The result is represented as a sequence of face-downcards where the value is given by a position in the sequence. By revealing
the card of position equal to the number written on the cell, V checks if
the sum is equal or not (without knowing the exact value if different) to
the numbered cell.

2Preliminaries

We explain the notations and sub-protocols used in our construction;some of them are detailed in appendix while the general idea is given
below. We first introduce the general framework of card-based protocols.
Cards and Encoding. The cards consist of clubs ♣ and hearts ♡ whosebacks are identical ? . We encode three colors {black, white, red} withthe order of two cards as follows:♣ ♡ → black,♡ ♣ → white,♡ ♡ → red.

(1)

We call a pair of face-down cards ? ? corresponding to a color according to the above encoding rule a commitment to the respective color.
We also use the terms, a black commitment, a white commitment, and a
red commitment. We sometimes regard black and white commitments as
bit values, based on the following encoding:♣ ♡ → 0,♡ ♣ → 1.

(2)

Hide a liar: Card-Based ZKP Protocol for Usowan

5

For a bit x ∈ {0, 1}, if a pair of face-down cards satisfies the encoding (2),we say that it is a commitment to x, denoted by ? ? .
| {z }x
We also define two other encodings [34]:– ♣-scheme: for x ∈ Z/pZ, there are p cards composed of p − 1 ♡s andone ♣ at position (x + 1) from the left. For example, 2 is represented
as ♡ ♡ ♣ ♡ in Z/4Z.
– ♡-scheme: same encoding as above but the ♡ and ♣ are reversed. For
instance, 2 is represented as ♣ ♣ ♡ ♣ in Z/4Z.
2.1

Pile-shifting shuffle [26, 38]

This shuffling action means to shuffle piles of cards cyclically. More formally, given m piles, each of which consists of the same number of facedown cards, denoted by (p1 , p2 , . . . , pm ), applying a pile-shifting shuffle(denoted by ⟨·∥ · · · ∥·⟩) results in (ps+1 , ps+2 , . . . , ps+m ):
*
+
?
?
?
?
? ··· ?
|{z} |{z} · · · |{z} → |{z} |{z}|{z} ,p1
p2
pm
ps+1 ps+2
ps+m
where s is uniformly and randomly chosen from Z/mZ. We can simply
implement this shuffling action using physical cases that can store a pileof cards, such as boxes and envelopes. A player (or players) cyclically
shuffles them manually until everyone (i.e., P and V ) loses track of theoffset.
2.2

Mizuki–Sone Copy Protocol [22]The following protocol is used for copying commitments. We need it as
a commitment can be used for several destructive2 computations (herean addition). Given a commitment to a ∈ {0, 1} along with four cards♣ ♡ ♣ ♡ , the Mizuki–Sone copy protocol [22] outputs two commitments
to a. We specifically describe the protocol in Appendix A.
? ? ♣♡♣♡ → ? ? ? ? .
| {z }| {z } | {z }
a

2

a

a

This means that commitments used in the computation cannot be placed back with
its initial value. A non-destructive protocol is called input-preserving (see Sect. 2.3).

6

L. Robert et al.

2.3

Input-preserving five-card trick [16]This sub-protocol is used during the verification phase (see Sect. 3.3) forthe lonely black rule (rule 3). Given two commitments to a, b ∈ {0, 1}
based on the encoding rule (2), this sub-protocol [4, 16] reveals only thevalue of a ∨ b as well as restores commitments to a and b:? ? ? ? → a∨b & ? ? ? ? .
| {z } | {z }| {z } | {z }
a

b

a

b

The original sub-protocol [4, 16] was designed for AND (a ∧ b), but weadjust it to compute OR (a ∨ b). We give the detailed description in
Appendix B.
2.4

How to Form a White Polyomino [27]We introduce the idea of the generic method of [27] to perform the connectivity of colored cells without revealing any information about theresulting cells. We leave in Appendix C the details of the protocol.
First, all commitments on a grid of size p × q are black, and P chooses
a commitment to turn it white (without V knowing which cell); we use
the chosen-pile described in Appendix C.1 for this. Then P chooses acommitment next to the previous commitment to either turn it whiteor leave it black; V is ensured that both commitments are neighbours(i.e., two adjacent cells) using a sub-protocol described in Appendix C.2.
This step is repeated pq − 1 times to ensure that V does not know thenumber of white cells at the end of the protocol. Finally, each time awhite commitment is created, V only knows that it is adjacent to anotherwhite commitment; thus V is convinced that the figure composed of whitecommitments is connected without knowing the number of cells.
2.5

Sum in Z [34]We give an overview of the protocol described in [34] for adding elements
in Z/2Z with result in Z. This protocol is needed for the liar rule 4.
Given commitments to xi ∈ Z/2Z for i ∈ {1, . . . , n} along
Pn withone ♣ and one ♡ , the protocol produces their sum S =i=1 xi inZ/(n + 1)Z encoded in the ♡-scheme without revealing xi . The computation is performed inductively; when starting by the two first commitments to x1 and x2 , they are transformed into x1 − r and x2 + r encodedin the ♡-scheme and ♣-scheme, respectively, for uniformly random valuer ∈ Z/3Z. Then x2 + r is revealed (no information about x2 is revealedHide a liar: Card-Based ZKP Protocol for Usowan

7

because r is random), and x1 − r is shifted by x2 + r positions to encode(x1 − r) + (x2 + r) = x1 + x2 . Note that this result is in Z/(p + 1)Z (orsimply Z because the result is less than or equal to p) for elements x1 , x2
in Z/pZ.
Let us describe the protocol. First, notice that black cells are assumed
to be equal to 1 and white cells are equal to 0 (see Eqs. (1) and (2)). Twocommitments to x1 and x2 (either 0 or 1) will be changed to x1 + x2 :? ? ? ? ♣♡ → ? ? ? .
| {z } | {z }| {z }
x1

x2

x1+x2

1. Swap the two cards of the commitment to x1 and add a ♣ face down
to the right. Those three cards represent x1 in the ♡-scheme in Z/3Z:−→←−? ? ? → ? ? ? .
| {z } ♣| {z }
x1

x1

2. Add a ♡ on the right of the commitment to x2 . Those three cards
represent x2 in the ♣-scheme in Z/3Z: ? ? ? → ? ? ? .
| {z } ♡| {z }
x2

x2

3. Obtain three cards representing x1 + r and those representing x2 − r
for a uniformly random value r ∈ Z/3Z as follows.
(a) Place in reverse order the three cards obtained in Step 2 below
the three cards obtained in Step 1:? ? ?
| {z }? ? ? ? ? ? →| {z } | {z }
x1

x2

x1

? ? ?
| {z }2−x2(b) Apply a pile shifting shuffle as follows:


?
?

?
?

?
?

? ? ?
| {z }


→

x1 +r

? ? ?
| {z }
2−x2 +r

For a uniformly random value r ∈ Z/3Z, we obtain three cards
representing x1 + r and those representing 2 − x2 + r.
(c) Reverse the order of the three cards representing 2 − x2 + r to
obtain those representing x2 − r: ? ? ? ? ? ? .
| {z } | {z }
x1 +r

x2 −r

8

L. Robert et al.

4. Reveal the three cards representing x2 − r, and shift to the right thethree cards representing x1 + r to obtain those representing x1 + x2
in the ♡-scheme; apply the same routine for the remaining elements
to compute the final sum.
Notice that we described the protocol for a result in Z/3Z but it iseasily adaptable for a result in, let say, Z/qZ. Indeed, during the firststep, we add a single ♣ to the first commitment and a single ♡ to thesecond; thus for a sum that could be equal to q − 1, we add q − 2 ♣ s to
the first commitment and q − 2 ♡ s to the second.

3

ZKP protocol for Usowan

We present a card-based ZKP protocol for Usowan. Consider an Usowan
instance composed as a rectangular grid of size p × q.
3.1

Setup phase

The verifier V and prover P place black commitments on each cell of
the p × q grid (also on the numbered cells) and place red commitments(“dummy” commitments) on the left of the frst column and below thelast row so that we have (p + 1)(q + 1) commitments.
3.2

Connectivity phase

We apply the sub-protocol introduced in Sect. 2.4 to form a white connected figure. After this phase, V is convinced that the white commitments are connected (rule 2). Moreover, V reveals the commitments corresponding to numbered cells to check that they are indeed white (rule 1).
Notice that revealing directly those commitments does reveal information
about the solution (i.e., V learns that those cells are white), but this information is already known independently of the protocol.
3.3

Verification Phases

There are two rules to check: black commitments cannot touch horizontally nor vertically (rule 3) and each numbered cell has the corresponding
number of black cells around it except for one liar in each region (rule 4).

Hide a liar: Card-Based ZKP Protocol for Usowan

9

Lonely black. For each pair of adjacent commitments, V applies the fivecard trick introduced in Sect. 2.3 to the two commitments to compute
their disjunction. We consider here that a white commitment is equal to1 while a black commitment is equal to 0 (see the encoding (2)). Hence,
if the output is 1 then it means that at least one commitment is whiteso V continues, otherwise V aborts (because the only case of output 0 iswhen there are two black commitments).
Liar. V needs to check that each numbered cell has the corresponding
number of black cells around it except for exactly one liar in each region.
We cannot simply check the number of black cells because it leaks information. Instead, we compute the sum of black cells in Z/5Z introducedin Sect. 2.5 for all numbered cells in a region. However, we do not directly
reveal the result but just the (x − 1)-st card of the output sequence. This
ensures that the sum is equal or not to x instead of giving the actual sum.
It remains one sub-protocol to use because the addition is destructive;
thus, we need to copy commitments sharing a numbered cell. The copy
protocol is described in Sect. 2.2. We can now formally describe the liar
verification. For every region, apply the following steps:
1. For each cell that shares k > 1 numbered cells, apply the copy protocol(introduced in Sect. 2.2) k − 1 times.
2. For each numbered cell, compute the addition of its four neighbors3 .
Recall that the result is encoded as the ♡-scheme (see Sect. 2); thus,
the result of the sum has a ♡ in its corresponding position (and allother cards are ♣s).
3. For each sequence obtained in the previous step, pick the card in theposition that corresponds to the number written on the numberedcell. The result must be kept secret (i.e., keep the cards face-down).
Example:ba 3 c −→ a + b + c + d = ? ? ? ? ?
0 1 2 3 4d↑
4. Shuffle and reveal all the cards previously chosen. If exactly one clubis revealed, then continue (i.e., there is exactly one liar); otherwiseaborts.
3

For a numbered cell in the edge of the board, compute the addition of its three or
two neighbors.

10

L. Robert et al.

4

Security Proofs

Our protocol needs to verify three security properties given as theorems.
Note that the sub-protocols used from the literature have been provensecure i.e., they are correct, complete, sound and zero-knowledge.
Theorem 1 (Completeness). If P knows the solution of an Usowan
grid, then P can convince V .
Proof. P convinces V in the sense that the protocol does not abort whichmeans that all the rules are satisfied. The protocol can be split into twophases: (1) the connectivity phase and (2) the verification phase.
(1) Since P knows the solution, the white cells are connected and hence
P can always choose a black commitment at step 2 to swap it to white.
(2) For the lonely black verification, there is no configuration of two black
cells that are touching horizontally nor vertically hence for every pair ofadjacent cells, there is always at least one white cell.
For the liar verification, there is exactly (in each region) one numberedcell surrounded by a different number of black cells. Suppose, without lostof generality, that the liar cell is equal to i in a given region (the same
result could be applied for each other region). When the sum of the fourneighbours is done, the card at position (from left) i + 1 is ♣ otherwise
the numbered card is not a liar. Thus when revealing the cards at the laststep, there is always a ♣ card.
Theorem 2 (Soundness). If P does not provide a solution of the p × q
Usowan grid, P is not able to convince V .
Proof. Suppose that P does not provide a solution. If the white cells are
not connected, then P cannot choose a neighbor commitment that P
wants to change at step 3c. If there are two black commitments touching(or more), then the five-card trick will output 0; hence, V will abort.
Finally, if there is not one liar exactly in a given region, then the last stepof the verification will reveal either no ♣ or at least two ♣ s; hence, V
will abort.
Theorem 3 (Zero-knowledge). V learns nothing about P ’s solutionof the given grid G.
Proof. We use the same proof technique as in [11], namely the descriptionof an efficient simulator that simulates the interaction between an honest

Hide a liar: Card-Based ZKP Protocol for Usowan

11

prover and a cheating verifier. The goal is to produce an indistinguishable
interaction from the verifier’s view (with the prover). Notice that thesimulator does not have the solution but it can swap cards during shuffles.
Informally, the verifier cannot distinguish between the distributions of two
protocols, one that is run with the actual solution and one with random
commitments. The simulator acts as follows.
– The simulator constructs a random connected white polyomino.
– During the lonely black verification, the simulator replaces the cards
in the five-card trick introduced in Sect. 2.3 with ♡ ♣ ♡ ♣ ♡ . Whilethe latter sequence is randomly shifted, this ensure that the protocol
continues.
– During the liar verification, the simulator simply replaces, in the laststep, the cards to have exactly one ♣ and the rest as ♡ s. This ensurethat there is exactly one liar in a given region, meaning that the
protocol does not abort.
The simulated and real proofs are indistinguishable and hence V
learns nothing from the connectivity and verification phases. Finally, we
conclude that the protocol is zero-knowledge.

5Conclusion

We propose a physical ZKP protocol for Usowan, which has an interesting
rule: some information on the initial grid are incorrect. For verifying such
constraints without revealing knowledge about the solution, we constructa protocol based on computing the sum [34]. With this trick we are able
to prove that we can hide exactly one liar in each room. The next step
will be to see how we can propose a cryptographic ZKP protocol to provethat someone is lying. This is clearly not easy and might require complex
and modern cryptographic primitives while we are able to do it only withcards and envelopes in real life.
Acknowledgements. We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper. This work
was supported in part by JSPS KAKENHI Grant Numbers JP21K11881
and JP18H05289. This study was partially supported by the French ANR
project ANR-18-CE39-0019 (MobiS5). Other programs also fund to write
this paper, namely the French government research program “Investissements d´Avenir” through the IDEX-ISITE initiative 16-IDEX-0001 (CAP
20-25) and the IMobS3 Laboratory of Excellence (ANR-10-LABX-16-01).

12

L. Robert et al.

Finally, the French ANR project DECRYPT (ANR-18-CE39-0007) and
SEVERITAS (ANR-20-CE39-0009) also subsidize this work.

References
1. https://www.nikoli.co.jp/en/puzzles/usowan.html, Nikoli, Usowan.
2. Abe, Y., Iwamoto, M., Ohta, K.: Efficient private PEZ protocols for symmetricfunctions. In: Hofheinz, D., Rosen, A. (eds.) Theory of Cryptography. LNCS, vol.
11891, pp. 372–392. Springer, Cham (2019). https://doi.org/10.1007/978-3-03036030-6 15
3. Balogh, J., Csirik, J.A., Ishai, Y., Kushilevitz, E.: Private computation
using a PEZ dispenser. Theor. Comput. Sci. 306(1-3), 69–84 (2003).
https://doi.org/10.1016/S0304-3975(03)00210-X
4. den Boer, B.: More efficient match-making and satisfiability: The Five Card Trick.
In: Quisquater, J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434,
pp. 208–217. Springer, Berlin, Heidelberg (1989). https://doi.org/10.1007/3-54046885-4 23
5. Bultel, X., Dreier, J., Dumas, J., Lafourcade, P.: Physical zero-knowledge proofs
for Akari, Takuzu, Kakuro and KenKen. In: Demaine, E.D., Grandoni, F. (eds.)
Fun with Algorithms. LIPIcs, vol. 49, pp. 8:1–8:20. Schloss Dagstuhl, Dagstuhl(2016). https://doi.org/10.4230/LIPIcs.FUN.2016.8
6. Bultel, X., Dreier, J., Dumas, J., Lafourcade, P., Miyahara, D., Mizuki, T., Nagao,
A., Sasaki, T., Shinagawa, K., Sone, H.: Physical zero-knowledge proof for Makaro.
In: Izumi, T., Kuznetsov, P. (eds.) SSS 2018. LNCS, vol. 11201, pp. 111–125.
Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03232-6 8
7. Chien, Y.F., Hon, W.K.: Cryptographic and physical zero-knowledge proof:
From Sudoku to Nonogram. In: Boldi, P., Gargano, L. (eds.) Fun with Algorithms. LNCS, vol. 6099, pp. 102–112. Springer, Berlin, Heidelberg (2010).
https://doi.org/10.1007/978-3-642-13122-6 12
8. Dreier, J., Jonker, H., Lafourcade, P.: Secure auctions without cryptography. In:
Ferro, A., Luccio, F., Widmayer, P. (eds.) Fun with Algorithms. LNCS, vol. 8496,
pp. 158–170. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07890-8 14
9. Dumas, J.G., Lafourcade, P., Miyahara, D., Mizuki, T., Sasaki, T., Sone, H.: Interactive physical zero-knowledge proof for Norinori. In: Du, D.Z., Duan, Z., Tian,
C. (eds.) Computing and Combinatorics. LNCS, vol. 11653, pp. 166–177. Springer,
Cham (2019). https://doi.org/10.1007/978-3-030-26176-4 14
10. Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. In: STOC 1985. pp. 291–304. ACM, New York (1985).
https://doi.org/10.1145/22145.22178
11. Gradwohl, R., Naor, M., Pinkas, B., Rothblum, G.N.: Cryptographic and physicalzero-knowledge proof systems for solutions of Sudoku puzzles. Theory Comput.
Syst. 44(2), 245–268 (2009). https://doi.org/10.1007/s00224-008-9119-9
12. Isuzugawa, R., Miyahara, D., Mizuki, T.: Zero-knowledge proof protocol
for Cryptarithmetic using dihedral cards. In: Kostitsyna, I., Orponen, P.
(eds.) UCNC 2021. LNCS, vol. 12984, pp. 51–67. Springer, Cham (2021).
https://doi.org/10.1007/978-3-030-87993-8 4
13. Iwamoto, C., Haruishi, M.: Computational complexity of Usowan
puzzles.
IEICE
Trans.
Fundamentals
E101.A,
1537–1540(2018).
https://doi.org/10.1587/transfun.E101.A.1537

Hide a liar: Card-Based ZKP Protocol for Usowan

13

14. Koch, A., Walzer, S.: Foundations for actively secure card-based cryptography. In: Farach-Colton, M., Prencipe, G., Uehara, R. (eds.) Fun with Algorithms. LIPIcs, vol. 157, pp. 17:1–17:23. Schloss Dagstuhl, Dagstuhl (2021).
https://doi.org/10.4230/LIPIcs.FUN.2021.17
15. Lafourcade, P., Miyahara, D., Mizuki, T., Robert, L., Sasaki, T., Sone, H.: How toconstruct physical zero-knowledge proofs for puzzles with a “single loop” condition.
Theor. Comput. Sci. 888, 41–55 (2021). https://doi.org/10.1016/j.tcs.2021.07.019
16. Miyahara, D., Robert, L., Lafourcade, P., Takeshige, S., Mizuki, T., Shinagawa, K., Nagao, A., Sone, H.: Card-based ZKP protocols for Takuzu and Juosan. In: Farach-Colton, M., Prencipe, G., Uehara, R. (eds.) Fun with Algorithms. LIPIcs, vol. 157, pp. 20:1–20:21. Schloss Dagstuhl, Dagstuhl (2021).
https://doi.org/10.4230/LIPIcs.FUN.2021.20
17. Miyahara, D., Sasaki, T., Mizuki, T., Sone, H.: Card-based physical zero-knowledge
proof for Kakuro. IEICE Trans. Fundamentals 102-A(9), 1072–1078 (2019).
https://doi.org/10.1587/transfun.E102.A.1072
18. Mizuki, T.: Efficient and secure multiparty computations using a standard deck ofplaying cards. In: Foresti, S., Persiano, G. (eds.) Cryptology and Network Security.
LNCS, vol. 10052, pp. 484–499 (2016). https://doi.org/10.1007/978-3-319-489650 29
19. Mizuki, T., Kugimoto, Y., Sone, H.: Secure multiparty computations using adial lock. In: Cai, J., Cooper, S.B., Zhu, H. (eds.) Theory and Applicationsof Models of Computation. LNCS, vol. 4484, pp. 499–510. Springer (2007).
https://doi.org/10.1007/978-3-540-72504-6 45
20. Mizuki, T., Kugimoto, Y., Sone, H.: Secure multiparty computations using
the 15 puzzle. In: Dress, A.W.M., Xu, Y., Zhu, B. (eds.) Combinatorial Optimization and Applications. LNCS, vol. 4616, pp. 255–266. Springer (2007).
https://doi.org/10.1007/978-3-540-73556-4 28
21. Mizuki, T., Shizuya, H.: Practical card-based cryptography. In: Funwith Algorithms. LNCS, vol. 8496, pp. 313–324. Springer, Cham (2014).
https://doi.org/10.1007/978-3-319-07890-8 27
22. Mizuki, T., Sone, H.: Six-card secure AND and four-card secure XOR. In: Deng, X.,
Hopcroft, J.E., Xue, J. (eds.) FAW 2009. LNCS, vol. 5598, pp. 358–369. Springer,
Berlin, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02270-8 36
23. Moran, T., Naor, M.: Polling with physical envelopes: A rigorous analysis of a human-centric protocol. In: Vaudenay, S. (ed.) Advances in
Cryptology—EUROCRYPT 2006. LNCS, vol. 4004, pp. 88–108. Springer (2006).
https://doi.org/10.1007/11761679 7
24. Moran, T., Naor, M.: Split-ballot voting: everlasting privacy with distributed
trust. In: Ning, P., di Vimercati, S.D.C., Syverson, P.F. (eds.) ACM Conference on Computer and Communications Security. pp. 246–255. ACM (2007).
https://doi.org/10.1145/1315245.1315277
25. Moran, T., Naor, M.: Basing cryptographic protocols on tamper-evident seals.
Theor. Comput. Sci. 411(10), 1283 – 1310 (2010), https://doi.org/10.1016/j.
tcs.2009.10.023
26. Nishimura, A., Hayashi, Y., Mizuki, T., Sone, H.: Pile-shifting scramble forcard-based protocols. IEICE Trans. Fundamentals 101-A(9), 1494–1502 (2018).
https://doi.org/10.1587/transfun.E101.A.1494
27. Robert, L., Miyahara, D., Lafourcade, P., Mizuki, T.: Card-based ZKP for connectivity: Applications to Nurikabe, Hitori, and Heyawake. New Gener. Comput. 40,
149–171 (2022). https://doi.org/10.1007/s00354-022-00155-5

14

L. Robert et al.

28. Robert, L., Miyahara, D., Lafourcade, P., Libralesso, L., Mizuki, T.: Physical zeroknowledge proof and NP-completeness proof of Suguru puzzle. Inf. Comput. 285,
1–14 (2022), https://doi.org/10.1016/j.ic.2021.104858
29. Ruangwises, S.: An improved physical ZKP for Nonogram. In: Du, D.Z., Du, D.,
Wu, C., Xu, D. (eds.) COCOA 2021. LNCS, vol. 13135, pp. 262–272. Springer,
Cham (2021). https://doi.org/10.1007/978-3-030-92681-6 22
30. Ruangwises, S.: Two standard decks of playing cards are sufficient for a ZKP for
Sudoku. New Gener. Comput. 40, 49–65 (2022). https://doi.org/10.1007/s00354021-00146-y
31. Ruangwises, S., Itoh, T.: Physical zero-knowledge proof for Numberlink puzzle
and k vertex-disjoint paths problem. New Gener. Comput. 39(1), 3–17 (2021).
https://doi.org/10.1007/s00354-020-00114-y
32. Ruangwises, S., Itoh, T.: Physical zero-knowledge proof for Ripple Effect. Theor.
Comput. Sci. 895, 115–123 (2021). https://doi.org/10.1016/j.tcs.2021.09.034
33. Ruangwises, S., Itoh, T.: Physical ZKP for connected spanning subgraph: Applications to Bridges puzzle and other problems. In: Kostitsyna, I., Orponen,P. (eds.) UCNC 2021. LNCS, vol. 12984, pp. 149–163. Springer, Cham (2021).
https://doi.org/10.1007/978-3-030-87993-8 10
34. Ruangwises, S., Itoh, T.: Securely computing the n-variable equality function with 2n cards. Theor. Comput. Sci. 887, 99–110 (2021).
https://doi.org/10.1016/j.tcs.2021.07.007
35. Ruangwises, S., Itoh, T.: Physical ZKP for Makaro using a standard deck of cards.
In: Theory and Applications of Models of Computation. LNCS, Springer, Cham
(2022), to appear
36. Sasaki, T., Miyahara, D., Mizuki, T., Sone, H.: Efficient card-based zeroknowledge proof for Sudoku. Theor. Comput. Sci. 839, 135–142 (2020).
https://doi.org/10.1016/j.tcs.2020.05.036
37. Shinagawa, K., Mizuki, T., Schuldt, J.C.N., Nuida, K., Kanayama, N.,
Nishide, T., Hanaoka, G., Okamoto, E.: Secure computation protocols using polarizing cards. IEICE Trans. Fundamentals E99.A(6), 1122–1131 (2016).
https://doi.org/10.1587/transfun.E99.A.1122
38. Shinagawa, K., Mizuki, T., Schuldt, J.C.N., Nuida, K., Kanayama, N.,
Nishide, T., Hanaoka, G., Okamoto, E.: Card-based protocols using regular polygon cards. IEICE Trans. Fundamentals 100-A(9), 1900–1909 (2017).
https://doi.org/10.1587/transfun.E100.A.1900

A

Mizuki–Sone Copy Protocol [22]The protocol proceeds as follows.4
1. Turn over all face-up cards and put the commitment to a above thefour additional cards as follows:? ?
| {z }a? ? ♣♡♡♣ →| {z }? ? ? ? .
| {z } | {z }
a
0

4

1

This description is a compact version of the original one [22]. Here, we use a pileshifting shuffle in step 2 instead of using a random bisection cut invented in [22].

Hide a liar: Card-Based ZKP Protocol for Usowan

15

Note that black-to-red represents 0, and red-to-black represents 1 according to Eq. (2).
2. Apply a pile-shifting shuffle as follows:


?
?
?
?
→
? ?
? ?
? ? ? ? .
3. Reveal the two above cards and obtain two commitments to a asfollows (note that negating a commitment is easy).
(a) If they are ♣ ♡ , then the four bottom cards are ? ? ? ? .
| {z } | {z }aa(b) If they are ♡ ♣ , then the four bottom cards are ? ? ? ? .
| {z } | {z }aBaInput-preserving Five-card Trick [16]The sub-protocol proceeds as follows.
1. Add helping cards and swap the two cards of the commitment to a sothat we have the negation b, as follows:? ? ? ? → ? ? ♡ ? ? ♡ ♣ ♣ ♣ ♣.
| {z } | {z }| {z }| {z }abab

2. Rearrange the sequence of cards and turn over the face-up cards as:? ? ♡ ? ? → ? ? ♡ ? ?
? ? ♡ ? ? ♡♣♣♣♣ →♡♣♣♣♣? ? ? ? ? .
3. Regarding cards in the same column as a pile, apply a pile-shifting
shuffle to the sequence:


?
?
?
?
?
? ? ? ? ?
→
?
?
?
?
?
? ? ? ? ? .
4. Reveal all the cards in the above row.
(a) If the resulting sequence is ♣ ♣ ♡ ♡ ♡ (up to cyclic shifts), thena ∨ b = 0.
(b) If it is ♡ ♣ ♡ ♣ ♡ (up to cyclic shifts), then a ∨ b = 1.
5. After turning over all the face-up cards, apply a pile-shifting shuffle.
6. Reveal all the cards in the bottom row; then, the revealed cards should
include exactly one ♡ .
7. Shift the sequence of piles so that the leftmost card is the revealed ♡and swap the two cards of the commitment to b to restore commitments to a and b.

16C

L. Robert et al.

How to Form a White Polyomino

Before explaining the protocol, we need to describe two crucial subprotocols first, namely the chosen pile protocol and the 4-neighbour protocol.
C.1

Chosen Pile Protocol [9]This protocol allows P to choose a pile of cards without V knowing which
one it is. Some operations can be done on this pile while all the commitments are replaced in their initial order.
This protocol is an extended version of the “chosen pile cut” proposedin [14]. Given m piles (p1 , p2 , . . . , pm ) with 2m additional cards, the chosen pile protocol enables a prover P to choose the i-th pile pi (without
revealing the index i) and revert the sequence of m piles to their originalorder after applying other operations to pi .
1. Using m − 1 ♣ s and one ♡ , P places m face-down cards (denotedby row 2 ) below the given piles such that only the i-th card is ♡ . We
further put m cards (denoted by row 3 ) below the cards such that
only the first card is ♡ :?
? ... ?
?
? ... ?
|{z} |{z}|{z} |{z} |{z}
|{z}
p1

p2

pi−1

pi

pi+1

pm

?

? ... ?

?

? . . . ? ← row 2

♣

♣

♡

♣

?

? ... ?

?

? . . . ? ← row 3

♡

♣

♣

♣

♣
♣

♣
♣

2. Considering the cards in the same column as a pile, apply a pileshifting shuffle to the sequence of piles.
3. Reveal all the cards in row 2. Then, exactly one ♡ appears, and thepile above the revealed ♡ is the i-th pile (thus P can obtain pi ).
After this step is invoked, other operations are applied to the chosen
pile. Then, the chosen pile is placed back to the i-th position in thesequence.
4. Remove the revealed cards, i.e., the cards in row 2. (Note, therefore,that we do not use the card ♡ revealed in Step 3.) Then, apply apile-shifting shuffle.
5. Reveal all the cards in row 3. Then, one ♡ appears, and the pile above
the revealed ♡ is p1 . Therefore, by shifting the sequence of piles (suchthat p1 becomes the leftmost pile in the sequence), we can obtain asequence of piles whose order is the same as the original one without
revealing any information about the order of the input sequence.

Hide a liar: Card-Based ZKP Protocol for Usowan

C.2

17

Sub-protocol: 4-Neighbour Protocol [27]Given pq commitments placed on a p × q grid, a prover P has a commitment in mind, which we call a target commitment. The prover P wants toreveal the target commitment and another one that lies next to the target
commitment (without revealing their exact positions). Here, a verifier V
should be convinced that the second commitment is a neighbour of thefirst one (without knowing which one) as well as V should be able toconfirm the colours of both the commitments. To handle the case where
the target commitment is at the edge of the grid, we place commitments
to red (as “dummy” commitments) in the left of the first column and the
below of the last row to prevent P from choosing a commitment that is
not a neighbour. Thus, the size of the expanded grid is (p + 1) × (q + 1).5
This sub-protocol proceeds as follows.
1. P and V pick the (p + 1)(q + 1) commitments on the grid from leftto-right and top-to-bottom to make a sequence of commitments:
? ?

? ?

? ?

? ? ··· ? ? .

2. P uses the chosen pile protocol (Sect. 2) to reveal the target commitment.
3. P and V pick all the four neighbours of the target commitment. Sincea pile-shifting shuffle is a cyclic reordering, the distance between commitments are kept (up to a given modulo). That is, for a target commitment (not at the edge), the possible four neighbours are at distance one for the left or right one, and p + 1 for the bottom or top
one. Therefore, P and V can determine the positions of all the fourneighbours.
4. Among these four neighbours, P chooses one commitment using thechosen pile protocol and reveals it.
5. P and V end the second and first chosen pile protocols.
C.3

Full Protocol

Assume that there is a grid having p × q cells. Without loss of generality,
P wants to arrange white commitments on the grid such that they form awhite-polyomino while V is convinced that the placement of commitments
is surely a white-polyomino. The method is as follows.
5Here, we do not place dummy commitments in the row above the first one and in thecolumn right to the last one because in the expanded grid of size (p + 1)(q + 1) therow above the first one can be regarded as the last row, i.e., dummy commitments.
Thus, we do not need dummy commitments placed in the row above the first one,which also holds for the column right to the last one.

18

L. Robert et al.

1. P and V place a commitment to black (i.e., ♣ ♡ ) on every celland commitments to red as mentioned in Sect. 2.4 so that they have(p + 1)(q + 1) commitments on the board.
2. P uses the chosen pile protocol to choose one black commitment that
P wants to change.
(a) V swaps the two cards constituting the chosen commitment sothat it becomes a white commitment (recall the encoding (1)).
(b) P and V end the chosen pile protocol to return the commitments
to their original positions.
3. P and V repeat the following steps exactly pq − 1 times.
(a) P chooses one white commitment as a target and one black commitment among its neighbours using the 4-neighbour protocol; theneighbour is chosen such that P wants to make it white.
(b) V reveals the target commitment. If it corresponds to white, thenV continues; otherwise V aborts.
(c) V reveals the neighbour commitment (chosen by P ). If it corresponds to black, then P makes the neighbour white or keep it
black (depending on P ’s choice) by executing the following steps;
otherwise V aborts.
i. If P wants to change the commitment, P places face-downclub-to-heart pair below it; otherwise, P places a heart-to-clubpair:? ? → ? ? or ? ? .
? ?
? ?
♣

♡

♡

♣

ii. Regarding cards in the same column as a pile, V applies apile-shifting shuffle to the sequence of piles:


?
?

?
?


→

? ?
? ? .

iii. V reveals the two cards in the second row. If the revealed
right card is ♡ , then V swaps the two cards in the first row;otherwise V does nothing.
(d) P and V end the 4-neighbour protocol.
4. P and V remove all the red commitments (i.e., dummy commitments)
so that we have pq commitments on the board.
After this process, V is convinced that all the white commitments represent a white-polyomino. Therefore, this method allows a prover P to make

Hide a liar: Card-Based ZKP Protocol for Usowan

19

a solution that only P has in mind, guaranteed to satisfy the connectivity
constraint.
If the number of white cells in the final polyomino, say k, is public toa verifier V , it is sufficient that in Step 3, P and V repeat k − 1 times
and in Step 3c, and hence, V simply swaps the two cards constituting theneighbour commitment to make it white (without P ’s choice).