Secure Computation Protocols Using Polarizing Cards

Kazumasa SHINAGAWA  Takaaki MIZUKI  Jacob C. N. SCHULDT  Koji NUIDA  Naoki KANAYAMA  Takashi NISHIDE  Goichiro HANAOKA  Eiji OKAMOTO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.6   pp.1122-1131
Publication Date: 2016/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.1122
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
card-based protocols,  polarizing cards,  secure computation,  boolean circuits,  recreational cryptography,  

Full Text: PDF(1.7MB)>>
Buy this Article

It is known that, using just a deck of cards, an arbitrary number of parties with private inputs can securely compute the output of any function of their inputs. In 2009, Mizuki and Sone constructed a six-card COPY protocol, a four-card XOR protocol, and a six-card AND protocol, based on a commonly used encoding scheme in which each input bit is encoded using two cards. However, up until now, there are no known results to construct a set of COPY, XOR, and AND protocols based on a two-card-per-bit encoding scheme, which all can be implemented using only four cards. In this paper, we show that it is possible to construct four-card COPY, XOR, and AND protocols using polarizing plates as cards and a corresponding two-card-per-bit encoding scheme. Our protocols use a minimum number of cards in the setting of two-card-per-bit encoding schemes since four cards are always required to encode the inputs. Moreover, we show that it is possible to construct two-card COPY, two-card XOR, and three-card AND protocols based on a one-card-per-bit encoding scheme using a common reference polarizer which is a polarizing material accessible to all parties.