Abstract 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 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.Abstract 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 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.

Designs Codes and CryptographyJul 1, 20260 citations

Private Branching Programs: On Communication-Efficient Cryptocomputing

Helger Lipmaa

Abstract We polish a recent cryptocomputing method of Ishai and Paskin from TCC 2007. More precisely, we show that every function can be cryptocomputed in communication, linear in the product of client’s input length and the length of the branching program, and computation, linear in the size of the branching program that computes it. The method is based on the existence of a communication-efficient (2, 1)-CPIR protocol. We give several nontrivial applications, including: (a) improvement on the communication of Lipmaa’s CPIR protocol, (b) a CPIR protocol with log-squared communication and sublinear server-computation by giving a secure function evaluation protocol for Boolean functions with similar performance, (c) a protocol for PIR-writing with low amortized complexity, (d) a selective private function evaluation (SPFE) protocol. We detail one application of SPFE that makes it possible to compute how similar is client’s input to an element in server’s database, without revealing any information to the server. For SPFE, we design a 4-message extension of the basic protocol that is efficient for a large class of functionalities.Abstract We polish a recent cryptocomputing method of Ishai and Paskin from TCC 2007. More precisely, we show that every function can be cryptocomputed in communication, linear in the product of client’s input length and the length of the branching program, and computation, linear in the size of the branching program that computes it. The method is based on the existence of a communication-efficient (2, 1)-CPIR protocol. We give several nontrivial applications, including: (a) improvement on the communication of Lipmaa’s CPIR protocol, (b) a CPIR protocol with log-squared communication and sublinear server-computation by giving a secure function evaluation protocol for Boolean functions with similar performance, (c) a protocol for PIR-writing with low amortized complexity, (d) a selective private function evaluation (SPFE) protocol. We detail one application of SPFE that makes it possible to compute how similar is client’s input to an element in server’s database, without revealing any information to the server. For SPFE, we design a 4-message extension of the basic protocol that is efficient for a large class of functionalities.

Jan 1, 200814 citations

\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 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.