The Landscape of Optimal Card-Based Protocols

Abstract

In card-based cryptography – initiated by the “Five-Card Trick” of den Boer (EUROCRYPT 1989) for securely computing the AND of two players’ bits – one devises simple protocols for secure multiparty computation using a deck of playing cards of two symbols (♥ and ♣) with indistinguishable backs. These protocols can be run if no trusted computer is available, or in classroom settings to illustrate secure computations. We give two AND protocols which are card-minimal w.r.t. specific requirements, and show card-minimality of the COPY protocol (necessary for computing arbitrary circuits) of Mizuki and Sone (FAW 2009) and the AND protocol of Abe et al. (APKC 2018). By this, we completely determine the landscape of card-minimal protocols with respect to running time requirements (finite runtime or Las Vegas behavior with/without restarts) and practicality demands on the shuffling operations. For this, we systematize and extend techniques for lower bounds results in card-based cryptography.