Cryptology ePrint Archive: Report 2019/380

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

Kazumasa Shinagawa and Koji Nuida

Abstract: It is known that information-theoretically secure computation can be done by using a deck of physical cards. In card-based protocols, shuffles, which covertly rearrange the order of cards according to a permutation chosen randomly, are the heaviest operations. Due to this, the number of shuffles in a protocol is desired to be small. However, as far as we know, there are no general-purpose protocols with a constant number of shuffles. In this paper, we construct a general-purpose protocol with a constant number of shuffles; surprisingly, just one (somewhat complicated) shuffle. This is achieved by introducing the garbled circuit methodology. Moreover, to make our shuffle simpler, we also develop a novel technique for aggregating several pile-scramble shuffles (which are efficiently implementable) into one pile-scramble shuffle. Consequently, we also construct a general-purpose protocol with two pile-scramble shuffles. Both techniques may lead to many other applications in this area.

Category / Keywords: cryptographic protocols / Card-based protocols, Secure computations, Garbled circuits

Date: received 10 Apr 2019

Contact author: shinagawakazumasa at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190416:032706 (All versions of this report)

Short URL: ia.cr/2019/380


[ Cryptology ePrint archive ]