Paper 2017/423

Foundations for Actively Secure Card-based Cryptography

Alexander Koch and Stefan Walzer

Abstract

Card-based cryptography allows to do secure multiparty computation in simple and elegant ways, using only a deck of playing cards, as first proposed by den Boer (EUROCRYPT 1989). Many protocols as of yet come with an “honest-but-curious” disclaimer. However, a central goal of modern cryptography is to provide security also in the presence of malicious attackers. At the few places where authors argue for the active security of their protocols, this is done ad-hoc and restricted to the concrete operations needed, often even using additional physical tools, such as envelopes or sliding cover boxes. This paper provides the first systematic approach to active security in card-based protocols. We show how a large and natural class of shuffling operations, namely those which (opaquely) permute the cards according to a uniform distribution on a permutation group, can be implemented using only a linear number of helping cards. This ensures that any (information-theoretically) secure cryptographic protocol in the abstract model of Mizuki and Shizuya (Int. J. Inf. Secur., 2014), restricted to this natural class of shuffles, can be realized in an actively secure fashion. These shuffles already allow for securely computing any circuit (Mizuki and Sone, FAW 2009). In the process, we develop a more concrete model for card-based cryptographic protocols with two players, which we believe to be of independent interest.

Note: Restructured the paper, slight re-naming of definitions, more argumentation for the definition of active security. Minor corrections and updates.