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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
information hidingtwo-party computation
Contact author(s)
elaine @ cs cornell edu
History
2015-10-27: last of 4 revisions
2015-10-26: received
See all versions
Short URL
https://ia.cr/2015/1031
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1031,
      author = {Antonio Marcedone and Zikai Wen and Elaine Shi},
      title = {Secure Dating with Four or Fewer Cards},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1031},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1031}},
      url = {https://eprint.iacr.org/2015/1031}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.