Computations with a deck of cards

AbstractA deck of cards can be used as a cryptographic tool (Advances in cryptology : CRYPTO’93, Lecture notes in Computer Science, Vol. 773, Springer, Berlin, 1994, pp. 319–330 [3]; Theoret. Comput. Sci. 191(1–2) (1998) 173–193 [6]). Using a protocol that securely computes the Boolean AND function, one can construct a protocol for securely computing any Boolean function. This, in turn, can be used for secure multiparty computations, solitary games, zero-knowledge proofs and other cryptographic schemes. We present a protocol for two people to securely compute the AND function using a deck of 2 types of cards. The protocol needs a total of only 8 cards, thus confirming the assumption of an open question Crépeau and Kilian (1994) [3] about the minimal number of values that are needed for this type of computation. To our knowledge, the protocol is also the first one of its kind that does not need to make copies of the inputs. We thus prove upper bounds for this type of computation. The protocol is much simpler, uses less cards, and is more efficient than the ones introduced in Crépeau and Kilian (1994) [3] and Niemi and Renvall (1998) [6]