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.

The use of tablet PCs is spreading rapidly, and accordingly users browsing and inputting personal information in public spaces can often be seen by third parties. Unlike conventional mobile phones and notebook PCs equipped with distinct input devices (e.g., keyboards), tablet PCs have touchscreen keyboards for data input. Such integration of display and input device increases the potential for harm when the display is captured by malicious attackers. This paper presents the description of reconstructing tablet PC displays via measurement of electromagnetic (EM) emanation. In conventional studies, such EM display capture has been achieved by using non-portable setups. Those studies also assumed that a large amount of time was available in advance of capture to obtain the electrical parameters of the target display. In contrast, this paper demonstrates that such EM display capture is feasible in real time by a setup that fits in an attaché case. The screen image reconstruction is achieved by performing a prior course profiling and a complemental signal processing instead of the conventional fine parameter tuning. Such complemental processing can eliminate the differences of leakage parameters among individuals and therefore correct the distortions of images. The attack distance, 2 m, makes this method a practical threat to general tablet PCs in public places. This paper discusses possible attack scenarios based on the setup described above. In addition, we describe a mechanism of EM emanation from tablet PCs and a countermeasure against such EM display capture.

A wireless LAN roaming system enables a user to access to a wireless network at a visiting institution with his/her account issued by his/her home institution. In the roaming system, an appropriate access privilege control is required. However, the conventional privilege authorization system gets unavailable because of some communication failures between institutions. In this work, we develop a fault-tolerant authorization system.