Publications

Journal Articles

  • A single shuffle is enough for secure card-based computation of any Boolean circuit
    Author(s)
    K. Shinagawa and K. Nuida
    Journal
    Discrete Applied Mathematics
    Vol.
    289
    Pages
    248–261
    Publisher
    Elsevier
    Publication Year
    2021
    Abstract

    Secure computation enables a number of players each holding a secret input value to compute a function of the inputs without revealing the inputs. It is known that secure computation is possible physically when the inputs are given as a sequence of physical cards. This research area is called card-based cryptography. One of the important problems in card-based cryptography is to minimize the number of cards and shuffles, where a shuffle is the most important (and somewhat heavy) operation in card-based protocols. In this paper, we determine the minimum number of shuffles for achieving general secure computation. Somewhat surprisingly, the answer is just one, i.e., we design a protocol which securely computes any Boolean circuit with only a single shuffle. The number of cards required for our protocol is proportional to the size of the circuit to be computed.