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 n-bit inputs, it is known that a protocol usingshuffles requires at least 2n 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 n-input protocol using privatepermutations would not even require n 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 ncards. Recently, Abe et al. extendedWatanabe et al.’s protocol and proposedan n-input majority voting protocol with n cards and n + [n?/2] + 1 privatepermutations. This paper proposes an n-input majority voting protocol with[n/?2] + 1 cards and 2n - 1 private permutations, which is also obtained byextending Watanabe et al.’s protocol. Compared with Abe et al.’s protocol,although the number of private permutations increases by about n?/2, thenumber of cards is reduced by about n?/2. In addition, unlike Abe et al.’sprotocol, our protocol includes Watanabe et al.’s protocol as a special casewhere n = 3.