Card-based cryptography allows multiple players to compute a function of their inputs without revealing any information on the inputs beyond the output value. In card-based protocols, although a bit value is usually encoded as a pair of cards (which we call a two-card encoding), a single-card encoding that encodes a bit value to a single card can be naturally considered. In 1998, Niemi and Renvall designed a COPY protocol that takes a single-card encoding of \(x \in \{0,1\}\) and outputs k copies of the encoding of x without revealing the input value x. However, as the authors claim in the paper, the security of the COPY protocol is not perfect: There is some “failure” probability of revealing the input value x. In 2014, Mizuki and Shizuya showed that there exists no perfectly-secure COPY protocol with single-card encoding, i.e., the failure of the Niemi–Renvall’s COPY protocol is unavoidable. In this paper, we design single-card encoding protocols with a failure probability. First, we show that every Boolean function can be computed based on the Niemi–Renvall’s COPY protocol and existing protocols with two-card encoding. Second, we propose AND and XOR protocols, both of which have a lower failure probability compared to the general protocol.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Card-Based Protocols with Single-Card Encoding

  • Kazumasa Shinagawa

摘要

Card-based cryptography allows multiple players to compute a function of their inputs without revealing any information on the inputs beyond the output value. In card-based protocols, although a bit value is usually encoded as a pair of cards (which we call a two-card encoding), a single-card encoding that encodes a bit value to a single card can be naturally considered. In 1998, Niemi and Renvall designed a COPY protocol that takes a single-card encoding of \(x \in \{0,1\}\) and outputs k copies of the encoding of x without revealing the input value x. However, as the authors claim in the paper, the security of the COPY protocol is not perfect: There is some “failure” probability of revealing the input value x. In 2014, Mizuki and Shizuya showed that there exists no perfectly-secure COPY protocol with single-card encoding, i.e., the failure of the Niemi–Renvall’s COPY protocol is unavoidable. In this paper, we design single-card encoding protocols with a failure probability. First, we show that every Boolean function can be computed based on the Niemi–Renvall’s COPY protocol and existing protocols with two-card encoding. Second, we propose AND and XOR protocols, both of which have a lower failure probability compared to the general protocol.