**Efficient Private PEZ Protocols for Symmetric Functions**

*Yoshiki Abe and Mitsugu Iwamoto and Kazuo Ohta*

**Abstract: **A private PEZ protocol is a variant of secure multi-party
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
follow-up 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 three-input majority
function, which is different from the one with the same length given by
Balogh et al. without describing how they derived it.

**Category / Keywords: **cryptographic protocols / Private PEZ protocol, Multiparty computation, Symmetric functions, Threshold functions

**Original Publication**** (with minor differences): **IACR-TCC-2019

**Date: **received 20 Sep 2019, last revised 20 Sep 2019

**Contact author: **yoshiki at uec ac jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20190923:071437 (All versions of this report)

**Short URL: **ia.cr/2019/1069

[ Cryptology ePrint archive ]