国際会議

Efficient Private PEZ Protocols for Symmetric Functions
 著者
 Y. Abe, M. Iwamoto, and K. Ohta
 会議名
 TCC 2019
 巻
 LNCS 11891
 ページ
 372–392
 出版社
 Springer
 発行年
 2019
 発表日
 Dec. 3, 2019
Abstract
A private PEZ protocol is a variant of secure multiparty computation performed using a (long) PEZ dispenser. The original paper by Balogh et al. presented a private PEZ protocol for computing an arbitrary function with n inputs. This result is interesting, but no followup work has been presented since then, to the best of our knowledge. We show herein that it is possible to shorten the initial string (the sequence of candies filled in a PEZ dispenser) and the number of moves (a player pops out a specified number of candies in each move) drastically if the function is symmetric. Concretely, it turns out that the length of the initial string is reduced from O(2^{n}!) for general functions in Balogh et al.’s results to O(n·n!)$ for symmetric functions, and 2^{n} moves for general functions are reduced to n^{2} moves for symmetric functions. Our main idea is to utilize the recursive structure of symmetric functions to construct the protocol recursively. This idea originates from a new initial string we found for a private PEZ protocol for the threeinput majority function, which is different from the one with the same length given by Balogh et al. without describing how they derived it.