Search

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

Consider an election where there are two candidates and several voters. Such an election usually requires the same number of ballot papers as the number of voters. In this paper, we show that such an election can be conducted using only a logarithmic number of cards with two suits—black and red—with identical backs. That is, we can securely compute the summation of a number of inputs (0s and 1s) using a logarithmic number of cards with respect to the number of inputs.

The "five-card trick" invented by Boer allows Alice and Bob to securely compute the AND function of their secret inputs using five cards--three black cards and two red cards--with identical backs. This paper shows that such a secure computation can be done with only four cards. Specifically, we give a protocol to achieve a secure computation of AND using only four cards--two black and two red. Our protocol is optimal in the sense that the number of required cards is minimum.

This paper presents radiation mechanism behind Electromagnetic Analysis (EMA) from remote locations. It has been widely known that electromagnetic radiation from a cryptographic chip could be exploited to conduct side-channel attacks, yet the mechanism behind the radiation has not been intensively studied. In this paper, the mechanism is explained from the view point of Electromagnetic Compatibility (EMC): electric fluctuation released from a cryptographic chip can conduct to peripheral circuits based on ground bounce, resulting in radiation. We demonstrate the consequence of the mechanism through experiments. For this purpose, Simple Electromagnetic Analysis (SEMA) and Differential Electromagnetic Analysis (DEMA) are conducted on FPGA implementations of RSA and AES, respectively. In the experiments, radiation from power and communication cables attached to the FPGA platform is measured. The result indicates, the information leakage can extend beyond security boundaries through such cables, even if the module implements countermeasures against invasive attacks to deny access at its boundary. We conclude that the proposed mechanism can be used to predict circuit components that cause information leakage. We also discuss advanced attacks and noise suppression technologies as countermeasures.

A minimum ESOP (Exclusive-OR Sum-of-Products) form of a logic function f is an AND-EXOR 2-level expression of f having the minimum number of product terms. In the paper we deal with multiple-valued 2-input logic functions f , and give an algorithm to find a minimum ESOP form of a given function f in polynomial time.

There have existed several "card-based protocols" for secure computations of a Boolean function such as AND and XOR. The best result currently known is that AND and XOR can be securely computed using 8 cards and 10 cards, respectively. In this paper, we improve the result: we design a 6-card AND protocol and a 4-card XOR protocol. Thus, this paper succeeds in reducing the number of required cards for secure computations.

This paper first considers the use of the "15 puzzle," which is one of the most famous sliding-block puzzles, to provide secure multiparty computations. That is, we design a class of 15-puzzle-based protocols for securely computing Boolean functions. Specifically, we show that any function of 4 variables (or less) and any symmetric function of 14 variables (or less) can be securely computed by a 15-puzzle-based protocol; furthermore, we present a 5-variable function and a 15-variable symmetric function, both of which cannot be securely computed by any protocol in the class.

This paper investigates collusion-secure fingerprinting codes for digital data. Most previous works assume the threshold number of collusive users. Whereas, in order to treat a more general non-threshold collusion, we first introduce a notion of a potentially collusive family. Furthermore, we develop a novel way to measure collusion-secure codes according to combinatorial properties in a natural way. Our measurement immediately implies the definition of optimal codes. We then actually illustrate an optimal code. Finally, we give a necessary and sufficient condition for a code to be optimal by using a new notion of family-intersecting codes.

This paper deals with secure computations in a minimal model, and gives a protocol which securely computes every function by means of the techniques of exclusive-or sum-of-products (ESOP) expressions. The communication complexity of our protocol is proportional to the size of an obtained multiple-valued-input ESOP expression. Since the historical research on minimizing ESOP expressions is now still active, our protocol will turn to an efficient one as this research progresses. Thus, this paper gives an application of ESOP expressions to designing cryptographic protocols, and we hope that it would motivate further research on minimizing ESOP expressions.

Digital watermarking used for fingerprinting may receive a collusion attack; two or more users collude, compare their data, find a part of embedded watermarks, and make an unauthorized copy by masking their identities. In this paper, assuming that at most c users collude, we give a characterization of the fingerprinting codes that have the best security index in a sense of “(c,p/q)-secureness” proposed by Orihara et al. The characterization is expressed in terms of intersecting families of sets. Using a block design, we also show that a distributor of data can only find asymptotically a set of c users including at least one culprit, no matter how good fingerprinting code is used.

The transformation protocol can make two players share a secret key using a random deal of cards. A sufficient condition on the number of cards for the transformation protocol to succeed was known. However, it has been an open problem to obtain a necessary and sufficient condition. This paper improves the transformation protocol and gives a necessary and sufficient condition for the improved transformation protocol to succeed.

Suppose that there are players in two hierarchical groups and a computationally unlimited eavesdropper. Using a random deal of cards, a player in the higher group wishes to send a one-bit message information-theoretically securely either to all the players in her group or to all the players in the two groups. This can be done by the socalled 2-level key set protocol. In this paper we give a necessary and su.cient condition for the 2-level key set protocol to succeed.

Using a random deal of cards to players and a computationally unlimited eavesdropper, all players wish to share a common one-bit secret key which is information-theoretically secure from the eavesdropper. This can be done by the so-called key set protocol. In this paper we give a necessary and sufficient condition for a key set protocol to be "optimal," that is, to succeed always in sharing a one-bit secret key.

Using a random deal of cards to players and a computationally unlimited eavesdropper, all players wish to share a one-bit secret key which is information-theoretically secure from the eavesdropper. This can be done by a protocol to make several pairs of players share one-bit secret keys so that all these pairs form a spanning tree over players. In this paper we obtain a necessary and sufficient condition on the number of cards for the existence of such a protocol. Our condition immediately yields an efficient linear-time algorithm to determine whether there exists a protocol to achieve such a secret key sharing.

Designing a protocol to exchange a secret key is one of the most fundamental subjects in cryptography. Using a random deal of cards, pairs of card players (agents) can share information-theoretically secure keys that are secret from an eavesdropper. In this paper we first introduce the notion of an Eulerian secret key exchange, in which the pairs of players sharing secret keys form an Eulerian circuit passing through all players. Along the Eulerian circuit any designated player can send a message to the rest of players and the message can be finally returned to the sender. Checking whether the returned message is the same as the original one, the sender can know whether the message circulation has been completed without any false alteration. We then give three efficient protocols to realize such an Eulerian secret key exchange. Each of the three protocols is optimal in a sense. The first protocol requires the minimum number of cards under a natural assumption that the same number of cards are dealt to each player. The second requires the minimum number of cards dealt to all players when one does not make the assumption. The third forms the shortest Eulerian circuit, and hence the time required to send the message to all players and acknowledge the secure receipt is minimum in this case.