Few-helping-card Protocols for Some Wider Class of Symmetric Boolean Functions with Arbitrary Ranges
Hayato Shikata, Daiki Miyahara, Takaaki Mizuki · 2023
In card-based cryptography, which uses a physical deck of cards to realize secure multiparty computations, a one-bit value is usually encoded by a pair of cards. Thus, when performing a secure computation of an n-input Boolean function, a sequence of 2n cards representing n bits is needed for input, and some helping cards are typically added to form a protocol. In 2020, Ruangwises and Itoh constructed a card-based protocol for a symmetric Boolean function with an arbitrary range using two helping cards. (Note that a symmetric Boolean function depends only on the number of 1s in its input). At the same time, they showed that the helping cards can be eliminated if the target function is limited to “doubly symmetric” Boolean functions (also known as symmetric self-anti-dual functions). A doubly symmetric Boolean function satisfies the following for all k: when inputting exactly a number k of 1s, the output is the same as the output when inputting exactly a number n − k of 1s. In this paper, we loosen the restriction on doubly symmetric Boolean functions by fixing k = 0, and construct new protocols which require less than two helping cards for that wider class of symmetric Boolean functions. Specifically, we design a one-helping-card protocol for any n > 4, and helping-card-free protocols for n = 3 and n = 4.