Securely computing the n-variable equality function with 2n cards

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 → { 0, 1 } using 2n cards. The first protocol can be generalized to compute any doubly symmetric function f: { 0, 1 } n → Z using 2n cards, and any symmetric function f: { 0, 1 } n → Z using 2 n + 2 cards. The second protocol can be generalized to compute the k-candidate n-variable equality function E: ( Z / k Z ) n → { 0, 1 } using 2 ⌈ lg ⁡ k ⌉ n cards.

Authors

• Suthee Ruangwises
• Toshiya Itoh

Keywords

• Card-based cryptography
• Secure multi-party computation
• Equality function
• Symmetric function
• Doubly symmetric function