Abstract Old Maid is a popular card game. While typically played with three or more players, it is less enjoyable with only two people. To address this, we propose a protocol to create a virtual player, Carol, by making use of card-based cryptography when only two people, Alice and Bob, are available to play Old Maid. Specifically, we design a card-based protocol to remove any pair of cards having the same number in Carol’s hand (namely, the virtual player’s hand) without leaking any information about Carol’s hand (more than necessary); our protocol uses additional cards aside from playing cards that are used in Old Maid. Using our protocol, without any third human player, Alice and Bob can have fun with Old Maid!

With the advancement of hardware security, combined attacks with techniques such as side-channel analysis (SCA) and fault analysis (FA) have prompted the development of combined countermeasures. However, these countermeasures often come with significant overhead. In this paper, we explore a solution to reduce the randomness requirement while maintaining security claims. We demonstrate the approach with Mask & Macs (M&M), a scheme that combines Boolean masking and MAC tag redundancy to provide SCA and DFA protection, addressing the challenge of high randomness requirement. We introduce a novel multiplicative masking scheme as a replacement for threshold implementation (TI) modules partially, leading to a reduction of over 50% in randomness requirement with minor increased FPGA resource overhead and latency. While the trade-off is beneficial, other limitations remain, and further research is needed to address these problems. This work provides a new perspective on improving combined countermeasures by exploring ways to reduce system overhead.

Suguru is a paper and pencil puzzle invented by Naoki Inaba. The goal of the game is to fill a grid with numbers between 1 and 5 while respecting three simple constraints. We first prove the NP-completeness of Suguru puzzle. For this we design gadgets to encode the PLANAR-CIRCUIT-SAT in a Suguru grid. We then design a physical Zero-Knowledge Proof (ZKP) protocol for Suguru. This ZKP protocol allows a prover to prove that he knows a solution of a Suguru grid to a verifier without leaking any information on the solution. To construct such a physical ZKP protocol, we only rely on a few physical cards and adapted encoding. For a Suguru grid with n cells, we only use 5n+5 cards. Moreover, we prove the three classical security properties of a ZKP: completeness, extractability, and zero-knowledge.

Abstract In 1989, den Boer presented the first card-based protocol, called the “five-card trick,” that securely computes the AND function using a deck of physical cards via a series of actions such as shuffling and turning over cards. This protocol enables a couple to confirm their mutual love without revealing their individual feelings. During such a secure computation protocol, it is important to keep any information about the inputs secret. Almost all existing card-based protocols are secure under the assumption that all players participating in a protocol are semi-honest or covert, i.e., they do not deviate from the protocol if there is a chance that they will be caught when cheating. In this paper, we consider a more malicious attack in which a player as an active adversary can reveal cards illegally without any hesitation. Against such an actively revealing card attack, we define the t-secureness, meaning that no information about the inputs leaks even if at most t cards are revealed illegally. We then actually design t-secure AND protocols. Thus, our contribution is the construction of the first formal framework to handle actively revealing card attacks as well as their countermeasures.

Imagine two cryptographers wishing to securely compute the AND value of their secret input bits. They are in the kitchen, where all they have are three saucepans with Borscht soup and some kinds of ingredients. Interestingly, by secretly putting ingredients in the saucepans depending on their inputs, they can find only the AND value from the taste of the cooked Borscht. Because cooking for secure computations is not so convenient, let us regard ingredients and saucepans (with Borscht soup) as balls and bags, respectively, which are easy to handle and also familiar tools for learning Probability in high school. Then, our problem is generalized as: Can we realize secure multiparty computations (MPCs) with balls and bags?There are techniques to realize MPCs with everyday objects, such as physical cards, coins, and a PEZ dispenser. We encode the input bits with such objects and securely compute some predetermined function using them. In this paper, we present a novel technique based on the physical properties of balls and bags. That is, our challenges are how to utilize an interesting feature that the balls become disordered immediately after they are put into a bag, namely they are “automatically shuffled”. We give the first framework of MPCs using balls and bags (namely, ball-based cryptography), and propose secure AND computation and general MPCs. Our protocols are realizations of usable security which helps people with understanding the principles of MPCs as well as solving social problems in daily life.

We propose a technique to construct physical Zero-Knowledge Proof (ZKP) protocols for puzzles that require a single loop draw feature. Our approach is based on the observation that a loop has only one hole and this property remains stable by some simple transformations. Using this trick, we can transform a simple big loop, which is visible to anyone, into the solution loop by using transformations that do not disclose any information about the solution. We illustrate our technique by applying it to construct physical ZKP protocols for two Nikoli puzzles: Slitherlink and Masyu.

In 2009, Gradwohl, Naor, Pinkas, and Rothblum proposed physical zero-knowledge proof protocols for Sudoku. That is, for a puzzle instance of Sudoku, their excellent protocols allow a prover to convince a verifier that there is a solution to the Sudoku puzzle and the prover knows it, without revealing any information about the solution. The possible drawback is that the existing protocols have an extractability error with a non-zero probability, or need special cards (such as scratch-off cards). Thus, in this study, we propose new protocols to perform zero-knowledge proof of knowledge for Sudoku using a normal deck of playing cards with no extractability error. Our protocols can be easily implemented by humans with a reasonable number of playing cards.

Consider a group of people who want to know the “rich list” among them, namely the ranking in terms of their total assets, without revealing any information about the actual value of their assets. This can be achieved by a “secure ranking computation,” which was first considered by Jiang and Gong (2006) [2]; they constructed a secure ranking computation protocol based on a public-key cryptosystem. In this paper, instead of using a public-key cryptosystem, we use a deck of physical cards to provide secure ranking computation protocols. Therefore, our card-based protocols do not rely on computers, and they are simple and easy for humans to implement. Specifically, we design four protocols considering tradeoffs between the number of cards and the number of shuffles required to execute the protocols. We also present a guide to choose an appropriate protocol according to the number of people participating in the protocol and the size of the input range. To be precise, whereas our protocols make all players know the rich list, the Jiang–Gong scheme makes each player know his/her rank only; to achieve the same task (as the Jiang–Gong scheme) using a deck of cards is an intriguing open problem.