Paper 2015/1031

Secure Dating with Four or Fewer Cards

Antonio Marcedone, Zikai Wen, and Elaine Shi

Abstract

In Cornell's “CS4830: Introduction to Cryptography” offered Fall 2015, students are asked to devise a physical secure two-party protocol for computing AND, using 4 cards or fewer. An elegant 5-card scheme was first proposed by Boer et al. Recently, in Asiacrypt 2012, Mizuki et al. were the first to improve the scheme to 4 cards. Although they mention that 4 cards is the minimum -- the minimum only holds when users must encode their input each with two cards. Given the collective wisdom of our Cornell CS4830 students, we demonstrate an array of creative schemes using from 1 to 4 cards. Our students documented these solutions in a homework assignment, many of which are unanticipated by the instructor and the TAs. We had fun with students' solutions and therefore would like to share them. Several of the students solutions are simpler than the standard textbook version by Boer et al., and we imagine that they could be useful for pedagogical purposes.