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
-
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}
}
