Card-based protocols provide secure multi-party computation using a deck of physical cards via a series of operations, such as shuffling and turning over cards, that are executed by humans. Although almost all existing protocols have been designed to be perfectly secure, operative errors by humans can lead to information leakage. In this paper, we propose a technique for analyzing information leakage due to operative errors in card-based protocols. In particular, we introduce a concept, which we call a “probability trace,” and by enhancing the KWH diagram proposed by Koch, Walzer, and Härtel, we propose a diagrammatic representation for displaying the amount of information leaked. By applying our diagram to a card-based protocol with an operative error, we can precisely reveal the leakage of players' inputs from the protocol output. In addition, we discuss how to detect human errors when people execute the existing six-card AND protocol.

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.

Paral and Devadas introduced a simple key generation scheme with a physically unclonable function (PUF) that requires no error correction, e.g., by using a fuzzy extractor. Their scheme, called a pattern matching key generation (PMKG) scheme, is based on pattern matching between auxiliary data, assigned at the enrollment in advance, and a substring of PUF output, to reconstruct a key. The PMKG scheme repeats a round operation, including the pattern matching, to derive a key with high entropy. Later, to enhance the efficiency and security, a circular PMKG (C-PMKG) scheme was proposed. However, multiple round operations in these schemes make them impractical. In this paper, we propose a single-round circular PMKG (SC-PMKG) scheme. Unlike the previous schemes, our scheme invokes the PUF only once. Hence, there is no fear of information leakage by invoking the PUF with the (partially) same input multiple times in different rounds, and, therefore, the security consideration can be simplified. Moreover, we introduce another hash function to generate a check string which ensures the correctness of the key reconstruction. The string enables us not only to defeat manipulation attacks but also to prove the security theoretically. In addition to its simple construction, the SC-PMKG scheme can use a weak PUF like the SRAM-PUF as a building block if our system is properly implemented so that the PUF is directly inaccessible from the outside, and, therefore, it is suitable for tiny devices in the IoT systems. We discuss its security and show its feasibility by simulations and experiments.

A new model for a Client-Server Communication (CSC) system satisfying information theoretic security is proposed, and its fundamental properties are discussed. Our CSC allows n users to upload their respective messages to a server securely by using symmetric key encryptions with their own keys, and all ciphertexts are decrypted by the server. If we require all messages to be perfectly secure in CSC against the corrupted clients and adversaries without any keys, it is proved that a one time pad or more inefficient encryption must be used for each communication link between a client and the server. This means that, in order to realize more efficient CSC, it is necessary to leak out some information of each message. Based on these observations, we introduce a new model for such a secure CSC formally, and discuss its fundamental properties. In addition, we propose the optimal construction of CSC under several constraints on security parameters called security rates.