## CryptoDB

### Paper: Efficient Private PEZ Protocols for Symmetric Functions

Authors: Yoshiki Abe Mitsugu Iwamoto Kazuo Ohta DOI: 10.1007/978-3-030-36030-6_15 Search ePrint Search Google 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 $\mathcal {O}(2^n!)$ for general functions in Balogh et al.’s results to $\mathcal {O}(n\cdot 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.
##### BibTeX
@article{tcc-2019-29979,
title={Efficient Private PEZ Protocols for Symmetric Functions},
booktitle={Theory of Cryptography},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11891},
pages={372-392},
doi={10.1007/978-3-030-36030-6_15},
author={Yoshiki Abe and Mitsugu Iwamoto and Kazuo Ohta},
year=2019
}