Kakuro is a popular logic puzzle, in which a player fills in all empty squares with digits from 1 to 9 so that the sum of digits in each (horizontal or vertical) line is equal to a given number, called a clue, and digits in each line are all different. In 2016, Bultel, Dreier, Dumas, and Lafourcade proposed a physical zero-knowledge proof protocol for Kakuro using a deck of cards; their proposed protocol enables a prover to convince a verifier that the prover knows the solution of a Kakuro puzzle without revealing any information about the solution. One possible drawback of their protocol would be that the protocol is not perfectly extractable, implying that a prover who does not know the solution can convince a verifier with a small probability; therefore, one has to repeat the protocol to make such an error become negligible. In this paper, to overcome this, we design zero-knowledge proof protocols for Kakuro having perfect extractability property. Our improvement relies on the ideas behind the copy protocols in the field of card-based cryptography. By executing our protocols with a real deck of physical playing cards, humans can practically perform an efficient zero-knowledge proof of knowledge for Kakuro.

Card-based cryptographic protocols provide secure multi-party computations using a deck of physical cards. The most important primitive of those protocols is the shuffling operation, and most of the existing protocols rely on uniform cyclic shuffles (such as the random cut and random bisection cut) in which each possible outcome is equally likely and all possible outcomes constitute a cyclic subgroup. However, a couple of protocols with non-uniform and/or non-cyclic shuffles were proposed by Koch, Walzer, and Härtel at Asiacrypt 2015. Compared to the previous protocols, their protocols require fewer cards to securely produce a hidden AND value, although to implement of such unconventional shuffles appearing in their protocols remains an open problem. This paper introduces “pile-shifting scramble,” which can be a secure implementation of those shuffles. To implement such unconventional shuffles, we utilize physical cases that can store piles of cards, such as boxes and envelopes. Therefore, humans are able to perform the shuffles using these everyday objects. Furthermore, we show that a certain class of non-uniform and/or non-cyclic shuffles having two possible outcomes can be implemented by the pile-shifting scramble. This also implies that we can improve upon the known COPY protocol using three card cases so that the number of cases required can be reduced to two.

Card-based protocols enable us to easily perform cryptographic tasks such as secure multiparty computation using a deck of physical cards. Since the first card-based protocol appeared in 1989, many protocols have been designed. A protocol is usually described with a series of somewhat intuitive and verbal descriptions, such as “turn over this card,” “shuffle these two cards,” “apply a random cut to these five cards,” and so on. On the other hand, a formal computational model of card-based protocols via abstract machine was constructed in 2014. By virtue of the formalization, card-based protocols can be treated more rigorously; for example, it enables one to discuss the lower bounds on the number of cards required for secure computations. In this paper, an overview of the computational model with its applications to designing protocols and a survey of the recent progress in card-based protocols are presented.

It is known that, using just a deck of cards, an arbitrary number of parties with private inputs can securely compute the output of any function of their inputs. In 2009, Mizuki and Sone constructed a six-card COPY protocol, a four-card XOR protocol, and a six-card AND protocol, based on a commonly used encoding scheme in which each input bit is encoded using two cards. However, up until now, there are no known results to construct a set of COPY, XOR, and AND protocols based on a two-card-per-bit encoding scheme, which all can be implemented using only four cards. In this paper, we show that it is possible to construct four-card COPY, XOR, and AND protocols using polarizing plates as cards and a corresponding two-card-per-bit encoding scheme. Our protocols use a minimum number of cards in the setting of two-card-per-bit encoding schemes since four cards are always required to encode the inputs. Moreover, we show that it is possible to construct two-card COPY, two-card XOR, and three-card AND protocols based on a one-card-per-bit encoding scheme using a common reference polarizer which is a polarizing material accessible to all parties.

Assume that Alice, Bob, and Carol, each of whom privately holds a one-bit input, want to learn the output of some Boolean function, say the majority function, of their inputs without revealing more of their own secret inputs than necessary. In this paper, we show that such a secure three-input function evaluation can be performed with a deck of real cards; specifically, the three players can learn only the output of the function using eight physical cards — four black and four red cards — with identical backs.