Paper 2019/380

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

Kazumasa Shinagawa and Koji Nuida

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Discrete Applied Mathematics vol.289, pp.248–261
DOI
10.1016/j.dam.2020.10.013
Keywords
Card-based protocolsSecure computationsGarbled circuits
Contact author(s)
shinagawakazumasa @ gmail com
History
2021-02-03: last of 2 revisions
2019-04-16: received
See all versions
Short URL
https://ia.cr/2019/380
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/380,
      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},
      url = {https://eprint.iacr.org/2019/380}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.