The Landscape of Computing Symmetric n-Variable Functions with 2n Cards
share
Secure multi-party computation using a physical deck of cards, often called card-based cryptography, has been extensively studied during the past decade. Many card-based protocols to securely compute various Boolean functions have been developed. As each input bit is typically encoded by two cards, computing an n-variable Boolean function requires at least 2n cards. We are interested in optimal protocols that use exactly 2n cards. In particular, we focus on symmetric functions, where the output only depends on the number of 1s in the inputs. In this paper, we formulate the problem of developing 2n-card protocols to compute n-variable symmetric Boolean functions by classifying all such functions into several NPN-equivalence classes. We then summarize existing protocols that can compute some representative functions from these classes, and also solve some of the open problems by developing protocols to compute particular functions in the cases n=4, 5, 6, and 7.
READ FULL TEXT