Paper 2019/380

A Single Shuffle Is Enough for Secure Card-Based Computation of Any Circuit

Kazumasa Shinagawa and Koji Nuida


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Discrete Applied Mathematics vol.289, pp.248–261
Card-based protocolsSecure computationsGarbled circuits
Contact author(s)
shinagawakazumasa @ gmail com
2021-02-03: last of 2 revisions
2019-04-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kazumasa Shinagawa and Koji Nuida},
      title = {A Single Shuffle Is Enough for Secure Card-Based Computation of Any Circuit},
      howpublished = {Cryptology ePrint Archive, Paper 2019/380},
      year = {2019},
      doi = {10.1016/j.dam.2020.10.013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.