学術論文誌

Secure Computation for Threshold Functions with Physical Cards: Power of Private Permutations
 著者
 T. Nakai, S. Shirouchi, Y. Tokushige, M. Iwamoto, and K. Ohta
 雑誌名
 New Generation Computing
 巻
 40
 号
 95–113
 出版社
 Ohmsha and Springer
 発行年
 2022
Open AccessAbstract
Cardbased cryptography is a variant of multiparty computation by using physical cards like playing cards. There are two models on cardbased cryptography, called public and private models. The public model assumes that all operations are executed publicly, while the private model allows the players private operations called private permutations (PP, for short). Much of the existing cardbased protocols were developed under the public model. Under the public model, 2n cards are necessary for every protocol with nbit input since at least two cards are required to express a bit. In this paper, we propose nbit input protocols with fewer than 2n cards by utilizing PP, which shows the power of PP. In particular, we show that a protocol for (nbit input) threshold function can be realized with only n+1 cards by reducing the threshold function to the majority voting. Toward this end, we first offer that twobit input protocols for logic gates can be realized with fewer than four cards. Furthermore, we construct a new protocol for threeinput majority voting with only four cards by observing the relationship between AND/OR operations. This protocol can be easily extended to more participants, and to the protocol for threshold functions.