Securely Computing the $n$-Variable Equality Function with $2n$ Cards

Abstract

Research in the area of secure multi-party computation using a deck of playing cards, often called card-based cryptography, started from the introduction of the five-card trick protocol to compute the logical AND function by den Boer in 1989. Since then, many card-based protocols to compute various functions have been developed. In this paper, we propose two new protocols that securely compute the $n$-variable equality function (determining whether all inputs are equal) $E:\{0,1{\}}^n\to \{0,1\}$ using $2n$ cards. The first protocol can be generalized to compute any doubly symmetric function $f:\{0,1{\}}^n\to \mathbb{Z}$ using $2n$ cards, and any symmetric function $f:\{0,1{\}}^n\to \mathbb{Z}$ using $2n+2$ cards. The second protocol can be generalized to compute the $k$-candidate $n$-variable equality function $E:(\mathbb{Z}/k\mathbb{Z}{)}^n\to \{0,1\}$ using $2\lceil \lg k\rceil n$ cards.

A preliminary version of this paper has appeared at TAMC 2020

References in corpus (1)

• Securely Computing the $n$-Variable Equality Function with $2n$ Cards

Cited by in corpus (7)

• Securely Computing the $n$-Variable Equality Function with $2n$ Cards
• Using Five Cards to Encode Each Integer in $\mathbb{Z}/6\mathbb{Z}$
• The Landscape of Computing Symmetric $n$-Variable Functions with $2n$ Cards
• Card-Based Overwriting Protocol for Equality Function and Applications
• Simulating Virtual Players for UNO without Computers
• NP-Completeness and Physical Zero-Knowledge Proofs for Zeiger
• Balance-Based Cryptography: Physically Computing Any Boolean Function