研究成果

学術論文誌

  • 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
    出版社
    Springer
    発行年
    2022
    Online First (Open Access)
    Abstract

    Card-based cryptography is a variant of multi-party computation by using physical cards like playing cards. There are two models on card-based 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 card-based protocols were developed under the public model. Under the public model, 2n cards are necessary for every protocol with n-bit input since at least two cards are required to express a bit. In this paper, we propose n-bit input protocols with fewer than 2n cards by utilizing PP, which shows the power of PP. In particular, we show that a protocol for (n-bit 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 two-bit input protocols for logic gates can be realized with fewer than four cards. Furthermore, we construct a new protocol for three-input 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.