International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 08 September 2015

Alexander Koch, Stefan Walzer, Kevin Härtel
ePrint Report ePrint Report
Secure multiparty computation can be done with a deck of playing cards. For example, den Boer (EUROCRYPT \'89) devised his

famous \"five-card trick\", which is a secure two-party AND protocol using five cards. However, the output of the protocol is revealed in the process and it is therefore not suitable for general circuits with

hidden intermediate results. To overcome this limitation, protocols in committed format, i.e., with concealed output, have been introduced, among them the six-card AND protocol of (Mizuki and Sone, FAW 2009). In their paper, the authors ask whether six cards are minimal for committed format AND protocols.

We give a comprehensive answer to this problem: there is a four-card AND protocol with a runtime that is finite in expectation (i.e., a Las Vegas protocol), but no protocol with finite runtime. Moreover, we show that five cards are sufficient for finite runtime. In other words, improving on (Mizuki, Kumamoto and Sone, ASIACRYPT 2012) \"The Five-Card Trick can be done with four cards\", our results can be stated as \"The Five-Card Trick can be done in committed format\" and furthermore it \"can be done with four cards in Las Vegas committed format\".

By devising a Las Vegas protocol for any $k$-ary boolean function using $2k$ cards, we address the open question posed by

(Nishida et al., TAMC 2015) on whether $2k+6$ cards are necessary for computing any $k$-ary boolean function. For this we use the shuffle abstraction as introduced in the computational model of card-based protocols in (Mizuki and Shizuya, Int.~J.~Inf.~Secur., 2014). We augment this result by a discussion on implementing such general shuffle operations.

Expand

Additional news items may be found on the IACR news page.