International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Yoshiki Abe

Publications

Year
Venue
Title
2019
TCC
Efficient Private PEZ Protocols for Symmetric Functions
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.

Coauthors

Yoshiki Abe (1)
Mitsugu Iwamoto (1)
Kazuo Ohta (1)