研究成果

Card-based cryptography refers to a secure computation with physical cards, and the number of cards and shuffles measures the efficiency of card-based protocols. This paper proposes new card-based protocols for any Boolean circuits with only a single shuffle. Although our protocols rely on Yao’s garbled circuit as in previous single-shuffle card-based protocols, our core construction idea is to encode truth tables of each Boolean gate with fewer cards than previous works while being compatible with Yao’s garbled circuit. As a result, we show single-shuffle card-based protocols with six cards per gate, which are more efficient than previous single-shuffle card-based protocols.

Card-based cryptography is a cryptographic technique that realizes Multi-Party Computation (MPC) using physical cards. Although various protocols have been studied in card-based cryptography, there is no research on card-based Private Set Intersection (PSI). PSI is one of the well-studied MPC protocols which enables parties to compute the set intersection while keeping their data sets secret. This paper focuses on PSI in card-based cryptography for the first time, and shows several card-based PSI protocols. In card-based cryptography, there are two operation models: one assumes that all operations are performed publicly, and the other allows private operations. We propose PSI protocols under each model. We first show that PSI can be realized under each model by utilizing the existing card-based AND protocols. Furthermore, we propose more efficient PSI protocols than the PSI protocols based on AND protocols under each model.

Research in the area of secure multi-party computation with an unconventional method of using a physical deck of playing cards began in 1989 when den Boar proposed a protocol to compute the logical AND function using five cards. Since then, the area has gained interest from many researchers and several card-based protocols to compute various functions have been developed. In this paper, we propose a card-based protocol called the overwriting protocol that can securely compute the k-candidate n-variable equality function f: {0,1,…,k−1}^{n} \to {0,1}. We also apply the technique used in this protocol to compute other similar functions.