A Computationally Efficient Card-Based Majority Voting Protocol with Fewer Cards in the Private Model

摘要

Card-based cryptography realizes secure multiparty computationusing physical cards. In 2018, Watanabe et al. proposed a cardbasedthree-input majority voting protocol using three cards. In a card-basedcryptographic protocol with -bit inputs, it is known that a protocol usingshuffles requires at least 2 cards. In contrast, asWatanabe et al.’s protocol,a protocol using private permutations can be constructed with fewer cardsthan the lower bounds above. Moreover, an -input protocol using privatepermutations would not even require cards in principle since a privatepermutation depending on an input can represent the input without usingadditional cards. However, there are only a few protocols with fewer than cards. Recently, Abe et al. extended Watanabe et al.’s protocol and proposedan -input majority voting protocol with cards and + ? /2? + 1private permutations. This paper proposes an -input majority voting protocolwith ? /2? + 1 cards and 2 ? 1 private permutations, which is alsoobtained by extending Watanabe et al.’s protocol. Compared with Abe etal.’s protocol, although the number of private permutations increases byabout /2, the number of cards is reduced by about /2. In addition, unlikeAbe et al.’s protocol, our protocol includes Watanabe et al.’s protocol as aspecial case where = 3.