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 and comprehensive 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 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. For this, we develop an alternative computational model for card-based cryptography, which we believe to be of independent interest.