Paper 2019/1069 Original: eprint.iacr.org/2019/1069 ↗
Efficient Private PEZ Protocols for Symmetric Functions
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.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2019-09-23: last updated
- 2019-09-23: published
- Short URL
- https://ia.cr/2019/1069
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2019/1069,
author = {Yoshiki Abe and Mitsugu Iwamoto and Kazuo Ohta},
title = {Efficient Private PEZ Protocols for Symmetric Functions},
howpublished = {Cryptology {ePrint} Archive, Paper 2019/1069},
year = {2019},
url = {https://eprint.iacr.org/2019/1069}
}