Private computation

Each of two parties $P_\mathcal{X} $ and $P_\matcal{Y} $ holds an n-bit input, x and y, respectively. They wish to privately compute the value of $f( x,y )$ . That is, $P_\mathcal{X} $ should not learn any additional information about y (in the information-theoretic sense) other than what follows from its input x and the function value $f ( x,y )$ , and similarly, $P_\mathcal{Y} $ should not learn any additional information about x. In this paper, the two following basic questions in the theory of private computations are considered: 1. Which functions can be privately computed? 2. What is the communication complexity of protocols that privately compute a function f (in the case that such protocols exist)? A complete combinatorial characterization of privately computable functions is given. This characterization is used to derive tight bounds on the rounds complexity of any privately computable function and to design optimal private protocols that compute these functions. It is shown that for every $1 \leq g ( n ) \leq 2\cdot ( 2^n - 1)$ there are functions that can be privately computed with $g( n )$ -rounds of communication, but not with $( g ( n ) - 1 )$ -rounds of communication. This implies that the communication costs of private protocols can be exponentially higher than the communication costs of nonprivate protocols. Interestingly, randomization helps neither to increase the set of privately computable functions, nor to improve the rounds complexity of these functions.Each of two parties $P_\mathcal{X} $ and $P_\matcal{Y} $ holds an n-bit input, x and y, respectively. They wish to privately compute the value of $f( x,y )$. That is, $P_\mathcal{X} $ should not learn any additional information about y (in the information-theoretic sense) other than what follows from its input x and the function value $f ( x,y )$, and similarly, $P_\mathcal{Y} $ should not learn any additional information about x. In this paper, the two following basic questions in the theory of private computations are considered: 1. Which functions can be privately computed? 2. What is the communication complexity of protocols that privately compute a function f (in the case that such protocols exist)? A complete combinatorial characterization of privately computable functions is given. This characterization is used to derive tight bounds on the rounds complexity of any privately computable function and to design optimal private protocols that compute these functions. It is shown that for every $1 \leq g ( n ) \leq 2\cdot ( 2^n - 1)$ there are functions that can be privately computed with $g( n )$-rounds of communication, but not with $( g ( n ) - 1 )$-rounds of communication. This implies that the communication costs of private protocols can be exponentially higher than the communication costs of nonprivate protocols. Interestingly, randomization helps neither to increase the set of privately computable functions, nor to improve the rounds complexity of these functions.

SIAM Journal on Discrete MathematicsMay 1, 1992118 citations

Silent Secure Computation

Geoffroy Couteau

SpringerBriefs in information security and cryptographyJan 1, 20260 citations

Privacy and communication complexity

Eyal Kushilevitz Z

Each of two parties P/sub 1/ and P/sub 2/ holds an n-bit input, x and y, respectively. They wish to compute privately the value of f(x,y). Two questions are considered: (1) Which functions can be privately computed? (2) What is the communication complexity of protocols that privately compute a function f (in the case in which such protocols exist)? A complete combinatorial characterization of privately computable functions is given. This characterization is used to derive tight bounds on the rounds complexity of any privately computable function and to design optimal private protocols that compute these functions. It is shown that for every 1>Each of two parties P/sub 1/ and P/sub 2/ holds an n-bit input, x and y, respectively. They wish to compute privately the value of f(x,y). Two questions are considered: (1) Which functions can be privately computed? (2) What is the communication complexity of protocols that privately compute a function f (in the case in which such protocols exist)? A complete combinatorial characterization of privately computable functions is given. This characterization is used to derive tight bounds on the rounds complexity of any privately computable function and to design optimal private protocols that compute these functions. It is shown that for every 1>

Annual Symposium on Foundations of Computer ScienceJan 1, 1989160 citations

Quantum private set computing protocol based on measurement device independence

WANG QingLe, CHENG WenChuan, Guodong Li +3 more

Secure multi-party computation (SMC) is an important privacy-preserving technology with broad applications in fields such as data mining and cloud computing. As a significant branch of SMC, private set computation (PSC) allows the computation of the intersection or union of private datasets from two or more participants while protecting their data privacy. Quantum private set computation (QPSC) is a new direction that combines PSC with quantum mechanics and has recently garnered widespread attention. Most existing QPSC protocols rely on quantum measurements performed by participants or third parties, but the measurement devices used in practice may be vulnerable to side-channel attacks. To address this issue, this paper proposes a measurement-device-independent QPSC protocol. In this protocol, participants can utilize post-selected Greenberger-Horne-Zeilinger (GHZ) state entanglement to compute the private intersection and union of their datasets securely. Analysis shows that this protocol is correct and can resist potential external and internal attacks. Finally, the protocol's feasibility is verified through simulation on the HIQ quantum computing cloud platform using the MindSpore Quantum framework.Secure multi-party computation (SMC) is an important privacy-preserving technology with broad applications in fields such as data mining and cloud computing. As a significant branch of SMC, private set computation (PSC) allows the computation of the intersection or union of private datasets from two or more participants while protecting their data privacy. Quantum private set computation (QPSC) is a new direction that combines PSC with quantum mechanics and has recently garnered widespread attention. Most existing QPSC protocols rely on quantum measurements performed by participants or third parties, but the measurement devices used in practice may be vulnerable to side-channel attacks. To address this issue, this paper proposes a measurement-device-independent QPSC protocol. In this protocol, participants can utilize post-selected Greenberger-Horne-Zeilinger (GHZ) state entanglement to compute the private intersection and union of their datasets securely. Analysis shows that this protocol is correct and can resist potential external and internal attacks. Finally, the protocol's feasibility is verified through simulation on the HIQ quantum computing cloud platform using the MindSpore Quantum framework.

Zhongguo kexue. Wulixue Lixue TianwenxueJul 29, 20241 citation

Future Computation

The MIT Press eBooksMay 14, 20190 citations

Each of two parties $P_\mathcal{X} $ and $P_\matcal{Y} $ holds an n-bit input, x and y, respectively. They wish to privately compute the value of

f( x,y )

. That is, $P_\mathcal{X} $ should not learn any additional information about y (in the information-theoretic sense) other than what follows from its input x and the function value

f ( x,y )

, and similarly, $P_\mathcal{Y} $ should not learn any additional information about x. In this paper, the two following basic questions in the theory of private computations are considered: 1. Which functions can be privately computed? 2. What is the communication complexity of protocols that privately compute a function f (in the case that such protocols exist)? A complete combinatorial characterization of privately computable functions is given. This characterization is used to derive tight bounds on the rounds complexity of any privately computable function and to design optimal private protocols that compute these functions. It is shown that for every

1 \leq g ( n ) \leq 2\cdot ( 2^n - 1)

there are functions that can be privately computed with

g( n )

-rounds of communication, but not with

( g ( n ) - 1 )

-rounds of communication. This implies that the communication costs of private protocols can be exponentially higher than the communication costs of nonprivate protocols. Interestingly, randomization helps neither to increase the set of privately computable functions, nor to improve the rounds complexity of these functions.