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.
Category / Keywords: card-based protocols, committed format, boolean AND, secure computation, cryptography without computers Original Publication (in the same form): IACR-ASIACRYPT-2015 Date: received 7 Sep 2015 Contact author: alexander koch at kit edu Available format(s): PDF | BibTeX Citation Version: 20150908:060358 (All versions of this report) Short URL: ia.cr/2015/865 Discussion forum: Show discussion | Start new discussion