Balogh et al. proposed deterministic secure multiparty computation called private PEZ protocols. In their work, a general construction of private PEZ protocols for computing an arbitrary function with n inputs is presented, but the function’s inputs must be binary. Binary domains are sufficient for computing functions with arbitrary domains because we can use the binary expansion of the inputs. However, such an expansion makes the protocol inefficient because unnecessary privacy is considered among the expanded bits of each input. Hence, we remove the binary expansion technique in this paper and propose a new private PEZ protocol directly applicable to functions with arbitrary domains. The proposed private PEZ protocol for an arbitrary function is much more efficient than Balogh et al.’s protocol. Concretely, an efficiency measure called the length of an initial string is exponentially improved in the domain size m: the order obtained from our construction is <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathcal {O}((2m)^{m^{n-1}})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mn>2</mn> <mi>m</mi> <mo stretchy="false">)</mo> </mrow> <msup> <mi>m</mi> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msup> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, while the construction of Balogh et al. yields <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathrm {\Omega }\bigg (\bigg (2^{\frac{m}{2}}\bigg )^{m^{n-1}}\bigg )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mrow> <mo maxsize="2.047em" minsize="2.047em" stretchy="true">(</mo> </mrow> <mrow> <mo maxsize="2.047em" minsize="2.047em" stretchy="true">(</mo> </mrow> <msup> <mn>2</mn> <mfrac> <mi>m</mi> <mn>2</mn> </mfrac> </msup> <msup> <mrow> <mo maxsize="2.047em" minsize="2.047em" stretchy="true">)</mo> </mrow> <msup> <mi>m</mi> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msup> </msup> <mrow> <mo maxsize="2.047em" minsize="2.047em" stretchy="true">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. The key idea of our protocol is called the divide and cue strategy, based on a recursive structure of views in private PEZ protocols.

Efficient private PEZ protocols without binary-input restrictions

期刊论文
出版模式：

开放获取
发表日期：

2026年7月3日

查看全文

Yoshiki Abe,
Mitsugu Iwamoto,
Kazuo Ohta

摘要

Balogh et al. proposed deterministic secure multiparty computation called private PEZ protocols. In their work, a general construction of private PEZ protocols for computing an arbitrary function with n inputs is presented, but the function’s inputs must be binary. Binary domains are sufficient for computing functions with arbitrary domains because we can use the binary expansion of the inputs. However, such an expansion makes the protocol inefficient because unnecessary privacy is considered among the expanded bits of each input. Hence, we remove the binary expansion technique in this paper and propose a new private PEZ protocol directly applicable to functions with arbitrary domains. The proposed private PEZ protocol for an arbitrary function is much more efficient than Balogh et al.’s protocol. Concretely, an efficiency measure called the length of an initial string is exponentially improved in the domain size m: the order obtained from our construction is $\mathcal {O}((2m)^{m^{n-1}})$ $O ({(2 m)}^{m^{n - 1}})$ , while the construction of Balogh et al. yields $\mathrm {\Omega }\bigg (\bigg (2^{\frac{m}{2}}\bigg )^{m^{n-1}}\bigg )$ $Ω ((2^{\frac{m}{2}})^{m^{n - 1}})$ . The key idea of our protocol is called the divide and cue strategy, based on a recursive structure of views in private PEZ protocols.