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

Subcontracted Rational SFE

Matthew Lepinski, Silvio M. Micali

Published Nov 2, 2005• 0 citations
OpenAlex

Abstract

In their paper, "Rational Secure Computation and Ideal Mechanism Design," Izmalkov, Lepinski and Micali show that any one-shot mediated game can be simulated by the players themselves, without the help of a trusted mediator, using physical envelopes and a ballot-box. We show that communication between the players is not essential to the ILM protocol. That is, we provide a protocol for rational secure function evaluation (Rational SFE) where the players just send a set of envelopes to a referee who simply performs a sequence of publicly verifiable actions. That is, the players can "subcontract" all of the computation to an untrusted referee. In addition to providing a communication structure that more closely matches the ideal game, our protocol also enables us to better simulate mediated games in which abort is not a dominated action.

Related papers

The Security Power of the Ballot Box

Matt Lepinski, Sergei Izmalkov

We show that any function f can be securely evaluated by a pro-tocol with ballots and a ballot box. That is, n mutually suspicious players, each player i possessing a secret input xi, can use ballots and ballot boxes to jointly evaluate f(x1,..., xn) = (y1,..., yn), so that (no matter how many players may collude and deviate from their pre-scribed instructions, and no matter how long they compute!) each player i learns exactly yi with the same privacy and correctness as if all players privately handed their secret inputs to a trusted party, who privately evaluates f and privately returns yi to each player i. Our protocol is (1) efficient, (2) enjoys perfect privacy, (3) guaran-tees perfect correctness, (4) is universally composable in the sense of [DoMi00] and [Can01], and (5) is always collusion-free in the sense of [LMS05], even for games with secret actions. 1 Main Theorem For any function f, mapping n private inputs to a single public output, there exists an n party protocol for a ballot-box network with public opening that securely evaluates f. We now procedure to define (1) a ballot-box network, (2) a ballot-box network with public opening and (3) the notion of securely evaluating a function. In a subsequent version of this work, we will provide a proof of our main theorem, generalize our results to functions with n inputs and n outputs and explore applications to economic mechanisms.

•Feb 2, 2005•0 citations

On the Communication Complexity of Secure Function Evaluation with Long Output

Pavel Hubáček, Daniel Wichs

We study the communication complexity of secure function evaluation (SFE). Consider a setting where Alice has a short input χA, Bob has an input χB and we want Bob to learn some function y = f(χA, χB) with large output size. For example, Alice has a small secret decryption key, Bob has a large encrypted database and we want Bob to learn the decrypted data without learning anything else about Alice's key. In a trivial insecure protocol, Alice can just send her short input χA to Bob. However, all known SFE protocols have communication complexity that scales with size of the output y, which can potentially be much larger. Is such 'output-size dependence' inherent in SFE'

Conference on Innovations in Theoretical Computer Science•Jan 11, 2015•132 citations

Rationality and Adversarial Behavior in Multi-party Computation (Extended Abstract)

Anna Lysyanskaya, Nikos Triandopoulos

We study multi-party computation in the model where none of n participating parties are honest: they are either rational, acting in their selfish interest to maximize their utility, or adversarial, acting arbitrarily. In this new model, which we call the mixed-behavior model, we define a class of functions that can be computed in the presence of an adversary using a trusted mediator. We then give a protocol that allows the rational parties to emulate the mediator and jointly compute the function such that (1) assuming that each rational party prefers that it learns the output while others do not, no rational party has an incentive to deviate from the protocol; and (2) the rational parties are protected from a malicious adversary controlling ⌈n/2⌉ − 2 of the participants: the 2 adversary can only either cause all rational participants to abort (so no one learns the function they are trying to compute), or can only learn whatever information is implied by the output of the function.

•Jan 1, 2006•4 citations

Revisiting Secure Two-Party Computation with Rational Players

Arpita Maitra, Goutam Paul, Asim Kumar Pal

•Jan 1, 2015•1 citation

On unconditionally secure multiparty computation for realizing correlated equilibria in games

Ye Wang, Shantanu D. Rane, Prakash Sharma Ishwar

In game theory, a trusted mediator acting on behalf of the players can enable the attainment of correlated equilibria, which may provide better payoffs than those available from the Nash equilibria alone. We explore the approach of replacing the trusted mediator with an unconditionally secure sampling protocol that jointly generates the players' actions. We characterize the joint distributions that can be securely sampled by malicious players via protocols using error-free communication. This class of distributions depends on whether players may speak simultaneously (“cheap talk”) or must speak in turn (“polite talk”). In applying sampling protocols toward attaining correlated equilibria with rational players, we observe that security against malicious protocols may be much stronger than necessary. We propose the concept of secure sampling by rational players, and show that many more distributions are feasible given certain utility functions. However, the payoffs attainable via secure sampling by malicious players are a dominant subset of the rationally attainable payoffs.

arXiv:1311.1490•IEEE Global Conference on Signal and Information Processing•Dec 1, 2013•1 citation

Fairplay—a secure two-party computation system

Dahlia Malkhi, Noam Nisan, Benny Pinkas B +1 more

Advances in modern cryptography coupled with rapid growth in processing and communication speeds make secure two-party computation a realistic paradigm. Yet, thus far, interest in this paradigm has remained mostly theoretical. This paper introduces Fairplay [28], a full-fledged system that implements generic secure function evaluation (SFE). Fairplay comprises a high level procedural definition language called SFDL tailored to the SFE paradigm; a compiler of SFDL into a one-pass Boolean circuit presented in a language called SHDL; and Bob/Alice programs that evaluate the SHDL circuit in the manner suggested by Yao in [39]. This system enables us to present the first evaluation of an overall SFE in real settings, as well as examining its components and identifying potential bottlenecks. It provides a test-bed of ideas and enhancements concerning SFE, whether by replacing parts of it, or by integrating with it. We exemplify its utility by examining several alternative implementations of oblivious transfer within the system, and reporting on their effect on overall performance. 1

USENIX Security Symposium•Aug 13, 2004•782 citations
In their paper, "Rational Secure Computation and Ideal Mechanism Design," Izmalkov, Lepinski and Micali show that any one-shot mediated game can be simulated by the players themselves, without the help of a trusted mediator, using physical envelopes and a ballot-box. We show that communication between the players is not essential to the ILM protocol. That is, we provide a protocol for rational secure function evaluation (Rational SFE) where the players just send a set of envelopes to a referee who simply performs a sequence of publicly verifiable actions. That is, the players can "subcontract" all of the computation to an untrusted referee. In addition to providing a communication structure that more closely matches the ideal game, our protocol also enables us to better simulate mediated games in which abort is not a dominated action.
We show that any function f can be securely evaluated by a pro-tocol with ballots and a ballot box. That is, n mutually suspicious players, each player i possessing a secret input xi, can use ballots and ballot boxes to jointly evaluate f(x1,..., xn) = (y1,..., yn), so that (no matter how many players may collude and deviate from their pre-scribed instructions, and no matter how long they compute!) each player i learns exactly yi with the same privacy and correctness as if all players privately handed their secret inputs to a trusted party, who privately evaluates f and privately returns yi to each player i. Our protocol is (1) efficient, (2) enjoys perfect privacy, (3) guaran-tees perfect correctness, (4) is universally composable in the sense of [DoMi00] and [Can01], and (5) is always collusion-free in the sense of [LMS05], even for games with secret actions. 1 Main Theorem For any function f, mapping n private inputs to a single public output, there exists an n party protocol for a ballot-box network with public opening that securely evaluates f. We now procedure to define (1) a ballot-box network, (2) a ballot-box network with public opening and (3) the notion of securely evaluating a function. In a subsequent version of this work, we will provide a proof of our main theorem, generalize our results to functions with n inputs and n outputs and explore applications to economic mechanisms.
We study the communication complexity of secure function evaluation (SFE). Consider a setting where Alice has a short input χA, Bob has an input χB and we want Bob to learn some function y = f(χA, χB) with large output size. For example, Alice has a small secret decryption key, Bob has a large encrypted database and we want Bob to learn the decrypted data without learning anything else about Alice's key. In a trivial insecure protocol, Alice can just send her short input χA to Bob. However, all known SFE protocols have communication complexity that scales with size of the output y, which can potentially be much larger. Is such 'output-size dependence' inherent in SFE'
We study multi-party computation in the model where none of n participating parties are honest: they are either rational, acting in their selfish interest to maximize their utility, or adversarial, acting arbitrarily. In this new model, which we call the mixed-behavior model, we define a class of functions that can be computed in the presence of an adversary using a trusted mediator. We then give a protocol that allows the rational parties to emulate the mediator and jointly compute the function such that (1) assuming that each rational party prefers that it learns the output while others do not, no rational party has an incentive to deviate from the protocol; and (2) the rational parties are protected from a malicious adversary controlling ⌈n/2⌉ − 2 of the participants: the 2 adversary can only either cause all rational participants to abort (so no one learns the function they are trying to compute), or can only learn whatever information is implied by the output of the function.
In game theory, a trusted mediator acting on behalf of the players can enable the attainment of correlated equilibria, which may provide better payoffs than those available from the Nash equilibria alone. We explore the approach of replacing the trusted mediator with an unconditionally secure sampling protocol that jointly generates the players' actions. We characterize the joint distributions that can be securely sampled by malicious players via protocols using error-free communication. This class of distributions depends on whether players may speak simultaneously (“cheap talk”) or must speak in turn (“polite talk”). In applying sampling protocols toward attaining correlated equilibria with rational players, we observe that security against malicious protocols may be much stronger than necessary. We propose the concept of secure sampling by rational players, and show that many more distributions are feasible given certain utility functions. However, the payoffs attainable via secure sampling by malicious players are a dominant subset of the rationally attainable payoffs.
Advances in modern cryptography coupled with rapid growth in processing and communication speeds make secure two-party computation a realistic paradigm. Yet, thus far, interest in this paradigm has remained mostly theoretical. This paper introduces Fairplay [28], a full-fledged system that implements generic secure function evaluation (SFE). Fairplay comprises a high level procedural definition language called SFDL tailored to the SFE paradigm; a compiler of SFDL into a one-pass Boolean circuit presented in a language called SHDL; and Bob/Alice programs that evaluate the SHDL circuit in the manner suggested by Yao in [39]. This system enables us to present the first evaluation of an overall SFE in real settings, as well as examining its components and identifying potential bottlenecks. It provides a test-bed of ideas and enhancements concerning SFE, whether by replacing parts of it, or by integrating with it. We exemplify its utility by examining several alternative implementations of oblivious transfer within the system, and reporting on their effect on overall performance. 1