Card-Based Majority Voting Protocols with Three Inputs Using Three Cards

摘要

Private operations (private permutations) were independently introduced by Nakai et al. and Marcedone et al. for implementing card-based cryptographic protocols efficiently. Recently, Nakai et al. showed that, if the private operations are available, secure computations of AND and OR operations for two inputs can be realized simultaneously by using four cards, and the protocol is applied to four-card majority voting protocol with three inputs. In this paper, it is shown that only three cards are sufficient to construct the majority voting protocol with three inputs. Specifically, we propose two constructions of three-input majority voting protocols. First, assuming that players are allowed to announce their outputs, we show that one card can be reduced from Nakai et al.'s protocol without any additional private operations and communications. Our second construction requires two more private operations and communications, whereas it removes the assumption on announcement from the first construction.