Cryptology ePrint Archive: Report 2015/1031

Secure Dating with Four or Fewer Cards

Antonio Marcedone and 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.

Category / Keywords: cryptographic protocols / information hiding, two-party computation

Date: received 23 Oct 2015, last revised 27 Oct 2015

Contact author: elaine at cs cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20151027:222513 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]