Card-based Single-shuffle Protocols for Secure Multiple-input AND and XOR Computations
Card-based Single-shuffle Protocols for Secure Multiple-input AND and XOR Computations
复制标题
用于安全多输入 AND 和 XOR 计算的基于卡的单洗牌协议
DOI：
10.1145/3494105.3526236
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Mizuki Takaaki
中科院分区：
文献类型：
--
作者：
Kuzuma Tomoki;Isuzugawa Raimu;Toyoda Kodai;Miyahara Daiki;Mizuki Takaaki
在基于卡片的密码学中，卡片和洗牌的数量是用于安全计算的协议的复杂性度量，并且这些值越小越好。品川和努伊达在最小化后一个测度的最新研究中，基于姚的乱码电路的思想，展示了一个令人惊讶的结果，即任何n输入逻辑函数都可以安全地用一次洗牌来计算。当执行他们的协议时，所需的卡的数量是2n+24 q，其中要计算的n输入逻辑函数由q个门表示。例如，当应用于n输入AND和XOR函数时，门的数量为n-1，因此需要26 n-24个卡。在本文中，我们表明，所需的卡的数量可以减少，专注于这两个特定的功能。具体地说，我们构造了一个单洗牌协议的n-输入AND函数使用4 n-2卡，并构造了一个单洗牌协议的n-输入XOR函数使用2n卡。
In card-based cryptography, the numbers of cards and shuffles are the complexity measures of protocols for secure computations, and the smaller these values are, the better. As the state-of-the-art study to minimize the latter measure, Shinagawa and Nuida showed a surprising result that any n-input logical function can be securely computed with only one shuffle, based on the idea of Yao's garbled circuit. When executing their protocol, the number of required cards is 2n+24q, where the n-input logical function to be computed is represented by q gates. For example, when applied to the n-input AND and XOR functions, the number of gates is n-1, and hence, 26n-24 cards are required. In this paper, we show that the number of required cards can be reduced by focusing on these two specific functions. Specifically, we construct a single-shuffle protocol for the n-input AND function using 4n-2 cards, and construct a single-shuffle protocol for the n-input XOR function using 2n cards.