Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1803.00436 · IEEE Transactions on Information Theory

Optimal Accuracy-Privacy Trade-Off for Secure Computations

Patrick Ah-Fat, Michael Huth

Published Dec 12, 2018• 21 citations
arXivHTMLPDF

Abstract

The purpose of secure multi-party computation is to enable protocol participants to compute a public function of their private inputs while keeping their inputs secret, without resorting to any trusted third party. However, opening the public output of such computations inevitably reveals some information about the private inputs. We propose a measure generalizing both Rényi entropy and g -entropy so as to quantify this information leakage. In order to control and restrain such information flows, we introduce the notion of function substitution, which replaces the computation of a function that reveals sensitive information with that of an approximate function. We exhibit theoretical bounds for the privacy gains that this approach provides and experimentally show that this enhances the confidentiality of the inputs while controlling the distortion of computed output values. Finally, we investigate the inherent compromise between accuracy of computation and privacy of inputs and we demonstrate how to realize such optimal trade-offs.

DOI
10.1109/tit.2018.2886458

Related papers

Scalable Information Flow Analysis of Secure Three-Party Affine Computations

Patrick Ah-Fat, Michael Huth

Elaborate protocols in Secure Multi-party Computation enable several participants to compute a public function of their own private inputs while ensuring that no undesired information leaks about the private inputs, and without resorting to any trusted third party. However, the public output of the computation inevitably leaks some information about the private inputs. Recent works have introduced a framework and proposed some techniques for quantifying such information flow. Yet, owing to their complexity, those methods do not scale to practical situations that may involve large input spaces. The main contribution of the work reported here is to formally investigate the information flow captured by the min-entropy in the particular case of secure three-party computations of affine functions in order to make its quantification scalable to realistic scenarios. To this end, we mathematically derive an explicit formula for this entropy under uniform prior beliefs about the inputs. We show that this closed-form expression can be computed in time constant in the inputs sizes and logarithmic in the coefficients of the affine function. Finally, we formulate some theoretical bounds for this privacy leak in the presence of non-uniform prior beliefs.

arXiv:1901.00798•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•2 citations

Characterizing optimal security and round-complexity for secure OR evaluation

Amisha Jhanji, Hemanta K. Maji, Raphael A. Meyer

Secure multi-party computation allows mutually distrusting parties to compute securely over their private data. However, even in the semi-honest two-party setting, most interesting functions cannot be computed securely in the information-theoretic plain model. Intuitively, the objective of accurately evaluating the output of such functions is inherently inimical to the privacy concerns of the parties. Securely evaluating OR of the input bits of two parties is the simplest example, and captures the essence of the hardness in securely evaluating most functions. This work studies the interplay between accuracy and privacy of secure 2-party function evaluation in the information-theoretic plain model. We provide an optimal accuracy versus privacy tradeoff for computing OR(x, y), where x and y are, respectively, the private input bits of Alice and Bob. In particular, we construct a round-optimal two-party protocol for OR that has maximum semi-honest security in the information-theoretic plain model. Prior results exhibit only weak tradeoffs that are far from the optimal. We generalize our techniques to obtain a tight accuracy-versus-privacy tradeoff characterization for a stronger notion of security, namely differentially-private semi-honest security. The technical heart of our result is a new technique to derive inequalities for distributions of transcripts generated by protocols. This approach reduces the domain of the optimization problem from an unbounded number of transcripts to a constant size while preserving the optimal solution to the original problem. We believe that these techniques for analyzing protocols in the information-theoretic plain model will be of independent interest.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•0 citations

There Is Always an Exception: Controlling Partial Information Leakage in Secure Computation.

Máté Horváth, Levente Buttyán, Gábor Székely +1 more

Private Function Evaluation (PFE) enables two parties to jointly execute a computation such that one of them provides the input while the other chooses the function to compute. According to the traditional security requirements, a PFE protocol should leak no more information, neither about the function nor the input, than what is revealed by the output of the computation. Existing PFE protocols inherently restrict the scope of computable functions to a certain function class with given output size, thus ruling out the direct evaluation of such problematic functions as the identity map, which would entirely undermine the input privacy requirement. We observe that when not only the input x is confidential but certain partial information g(x) of it as well, standard PFE fails to provide meaningful input privacy if g and the function f to be computed fall into the same function class.

•Jan 1, 2019•0 citations

Lower bounds and optimal protocols for three-party secure computation

Sundara Rajan S, Shijin Rajakrishnan, Andrew Thangaraj +1 more

The problem of three-party secure computation, where a function of private data of two parties is to be computed by a third party without revealing information beyond respective inputs or outputs is considered. New and better lower bounds on the amount of communication required between the parties to guarantee zero probability of error in the computation and achieve information-theoretic security are derived. Protocols are presented and proved to be optimal in some cases by showing that they achieve the improved lower bounds.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•1 citation

Secure Two Party Computation

Kannan Balasubramanian

The goal of secure two-party computation is to enable two parties to cooperatively evaluate a function that takes private data from both parties as input without exposing any of the private data. At the end of the computation, the participants learn nothing more than the output of the function. The two-party secure computation systems have three properties: (1) the application involves inputs from two independent parties; (2) each party wants to keep its own data secret; and (3) the participants agree to reveal the output of the computation. That is, the result itself does not imply too much information about either party's private input. Informally, the security requirements are that nothing is learned from the protocol other than the output (privacy), and that the output is distributed according to the prescribed functionality (correctness). The threat models in the two-party computation assume the presence of three different types of adversaries: 1) Semi honest, 2) Malicious and 3) Covert.

Advances in information security, privacy, and ethics book series•Aug 16, 2017•2 citations

A Protocol of Comparing Information without Leaking

Jing Qin

At present, research on secure multi-party computation is of great interest in modern cryptography. It should be acknowledged that if any function can be computed securely, then it results in a very powerful tool. In fact, all natural protocols are, or can be rephrased to be, special cases of the multi-party computation problems. Design and analysis of the special multi-party computation protocols is meaningful and has attracted much interest in this field. Based on the combination of a public-key cryptosystem of the homomorphic encryption and on the theoretic construction relying on the F-hiding assumption, a protocol for comparing information of equality is proposed. The protocol needs only a single round of interaction and ensures fairness, efficiency and security. The protocol is fair, which means that one party knows the sound result of the comparison if and only if the other one knows the result. The protocol is efficient with the help of an oblivious third party for calculating. However, the third party cannot learn any information about the participant抯 private inputs and even about the comparison result, and cannot collude with any participant. The protocol is secure for the two participants, that is, any information about their secret input will not leak except the final computation result. A precise proof of security of the protocol is presented. Applications of this protocol may include private bidding and auctions, secret ballot elections, commercial business, identification in a number of scenarios and so on. It is believed that the protocol may be of practical significance for electronic transaction.

•Jan 1, 2004•24 citations
The purpose of secure multi-party computation is to enable protocol participants to compute a public function of their private inputs while keeping their inputs secret, without resorting to any trusted third party. However, opening the public output of such computations inevitably reveals some information about the private inputs. We propose a measure generalizing both Rényi entropy and g -entropy so as to quantify this information leakage. In order to control and restrain such information flows, we introduce the notion of function substitution, which replaces the computation of a function that reveals sensitive information with that of an approximate function. We exhibit theoretical bounds for the privacy gains that this approach provides and experimentally show that this enhances the confidentiality of the inputs while controlling the distortion of computed output values. Finally, we investigate the inherent compromise between accuracy of computation and privacy of inputs and we demonstrate how to realize such optimal trade-offs.
Elaborate protocols in Secure Multi-party Computation enable several participants to compute a public function of their own private inputs while ensuring that no undesired information leaks about the private inputs, and without resorting to any trusted third party. However, the public output of the computation inevitably leaks some information about the private inputs. Recent works have introduced a framework and proposed some techniques for quantifying such information flow. Yet, owing to their complexity, those methods do not scale to practical situations that may involve large input spaces. The main contribution of the work reported here is to formally investigate the information flow captured by the min-entropy in the particular case of secure three-party computations of affine functions in order to make its quantification scalable to realistic scenarios. To this end, we mathematically derive an explicit formula for this entropy under uniform prior beliefs about the inputs. We show that this closed-form expression can be computed in time constant in the inputs sizes and logarithmic in the coefficients of the affine function. Finally, we formulate some theoretical bounds for this privacy leak in the presence of non-uniform prior beliefs.
Secure multi-party computation allows mutually distrusting parties to compute securely over their private data. However, even in the semi-honest two-party setting, most interesting functions cannot be computed securely in the information-theoretic plain model. Intuitively, the objective of accurately evaluating the output of such functions is inherently inimical to the privacy concerns of the parties. Securely evaluating OR of the input bits of two parties is the simplest example, and captures the essence of the hardness in securely evaluating most functions. This work studies the interplay between accuracy and privacy of secure 2-party function evaluation in the information-theoretic plain model. We provide an optimal accuracy versus privacy tradeoff for computing OR(x, y), where x and y are, respectively, the private input bits of Alice and Bob. In particular, we construct a round-optimal two-party protocol for OR that has maximum semi-honest security in the information-theoretic plain model. Prior results exhibit only weak tradeoffs that are far from the optimal. We generalize our techniques to obtain a tight accuracy-versus-privacy tradeoff characterization for a stronger notion of security, namely differentially-private semi-honest security. The technical heart of our result is a new technique to derive inequalities for distributions of transcripts generated by protocols. This approach reduces the domain of the optimization problem from an unbounded number of transcripts to a constant size while preserving the optimal solution to the original problem. We believe that these techniques for analyzing protocols in the information-theoretic plain model will be of independent interest.
Private Function Evaluation (PFE) enables two parties to jointly execute a computation such that one of them provides the input while the other chooses the function to compute. According to the traditional security requirements, a PFE protocol should leak no more information, neither about the function nor the input, than what is revealed by the output of the computation. Existing PFE protocols inherently restrict the scope of computable functions to a certain function class with given output size, thus ruling out the direct evaluation of such problematic functions as the identity map, which would entirely undermine the input privacy requirement. We observe that when not only the input x is confidential but certain partial information g(x) of it as well, standard PFE fails to provide meaningful input privacy if g and the function f to be computed fall into the same function class.
The problem of three-party secure computation, where a function of private data of two parties is to be computed by a third party without revealing information beyond respective inputs or outputs is considered. New and better lower bounds on the amount of communication required between the parties to guarantee zero probability of error in the computation and achieve information-theoretic security are derived. Protocols are presented and proved to be optimal in some cases by showing that they achieve the improved lower bounds.
The goal of secure two-party computation is to enable two parties to cooperatively evaluate a function that takes private data from both parties as input without exposing any of the private data. At the end of the computation, the participants learn nothing more than the output of the function. The two-party secure computation systems have three properties: (1) the application involves inputs from two independent parties; (2) each party wants to keep its own data secret; and (3) the participants agree to reveal the output of the computation. That is, the result itself does not imply too much information about either party's private input. Informally, the security requirements are that nothing is learned from the protocol other than the output (privacy), and that the output is distributed according to the prescribed functionality (correctness). The threat models in the two-party computation assume the presence of three different types of adversaries: 1) Semi honest, 2) Malicious and 3) Covert.
At present, research on secure multi-party computation is of great interest in modern cryptography. It should be acknowledged that if any function can be computed securely, then it results in a very powerful tool. In fact, all natural protocols are, or can be rephrased to be, special cases of the multi-party computation problems. Design and analysis of the special multi-party computation protocols is meaningful and has attracted much interest in this field. Based on the combination of a public-key cryptosystem of the homomorphic encryption and on the theoretic construction relying on the F-hiding assumption, a protocol for comparing information of equality is proposed. The protocol needs only a single round of interaction and ensures fairness, efficiency and security. The protocol is fair, which means that one party knows the sound result of the comparison if and only if the other one knows the result. The protocol is efficient with the help of an oblivious third party for calculating. However, the third party cannot learn any information about the participant抯 private inputs and even about the comparison result, and cannot collude with any participant. The protocol is secure for the two participants, that is, any information about their secret input will not leak except the final computation result. A precise proof of security of the protocol is presented. Applications of this protocol may include private bidding and auctions, secret ballot elections, commercial business, identification in a number of scenarios and so on. It is believed that the protocol may be of practical significance for electronic transaction.