Card-Based Cryptographic Protocols Using a Minimal Number of Cards
Card-Based Cryptographic Protocols Using a Minimal Number of Cards
复制标题
使用最少数量的卡的基于卡的加密协议
DOI：
10.1007/978-3-662-48797-6_32
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Kevin Härtel
中科院分区：
文献类型：
--
作者：
Alexander Koch;Stefan Walzer;Kevin Härtel
安全的多方计算可以通过一副扑克牌来完成。例如，den Boer EUROCRYPTi?'89 设计了他著名的“五张牌技巧”，这是一种使用五张牌的安全两方 AND 协议。然而，该协议的输出在过程中被揭示，因此不适合具有隐藏中间结果的通用电路。为了克服这一限制，引入了承诺格式的协议，即具有隐藏输出的协议，其中包括 Mizuki 和 Sone 的六卡 AND 协议，FAWi?2009。在他们的论文中，作者询问六张卡对于承诺格式和协议是否是最少的。
我们对这个问题给出了一个全面的答案：存在一个预期运行时间有限的四卡 AND 协议，即拉斯维加斯协议，但没有运行时间有限的协议。此外，我们证明五张卡足以满足有限的运行时间。换句话说，改进了Mizuki、Kumamoto和Sone，ASIACRYPTi??2012“五张牌戏法可以用四张牌完成”，我们的结果可以表述为“五张牌戏法可以以承诺格式完成”，而且它“可以用拉斯维加斯承诺格式的四张牌完成”。
通过使用 2k 卡为任何 $$k$$-ary 布尔函数设计拉斯维加斯协议，我们解决了 Nishida 等人 (TAMCi?2015) 提出的开放性问题，即计算任何 $$k$$-ary 布尔函数是否需要 $$2k+6$$ 卡。为此，我们使用 Mizuki 和 Shizuya 的基于卡的协议的计算模型中引入的洗牌抽象，Int.i ?J.i ??Inf.i ?Secur.，2014。我们通过关于实现此类一般洗牌操作的讨论来增强这一结果。
Secure multiparty computation can be done with a deck of playing cards. For example, den Boer EUROCRYPTi¾?'89 devised his famous "five-card trick", which is a secure two-party AND protocol using five cards. However, the output of the protocol is revealed in the process and it is therefore not suitable for general circuits with hidden intermediate results. To overcome this limitation, protocols in committed format, i.e., with concealed output, have been introduced, among them the six-card AND protocol of Mizuki and Sone, FAWi¾?2009. In their paper, the authors ask whether six cards are minimal for committed format AND protocols.
We give a comprehensive answer to this problem: there is a four-card AND protocol with a runtime that is finite in expectation i.e., a Las Vegas protocol, but no protocol with finite runtime. Moreover, we show that five cards are sufficient for finite runtime. In other words, improving on Mizuki, Kumamoto and Sone, ASIACRYPTi¾?2012 "The Five-Card Trick can be done with four cards", our results can be stated as "The Five-Card Trick can be done in committed format" and furthermore it "can be done with four cards in Las Vegas committed format".
By devising a Las Vegas protocol for any $$k$$-ary boolean function using 2k cards, we address the open question posed by Nishida et al., TAMCi¾?2015 on whether $$2k+6$$ cards are necessary for computing any $$k$$-ary boolean function. For this we use the shuffle abstraction as introduced in the computational model of card-based protocols in Mizuki and Shizuya, Int.i¾?J.i¾?Inf.i¾?Secur., 2014. We augment this result by a discussion on implementing such general shuffle operations.