Collusion-free (CF) and collusion-preserving (CP) protocols enrich the standard security offered by multi-party computation (MPC), to tackle settings where subliminal communication is undesirable. However, all existing solutions make arguably unrealistic assumptions on setups, such as physical presence of the parties, access to physical envelopes, or extreme isolation, where the only means of communication is a star-topology network. The above state of affairs remained a limitation of such protocols, which was even reinforced by impossibility results. Thus, for years, it has been unclear if and how the above setup assumptions could be relaxed towards more realistic scenarios. Motivated also by the increasing interest in using hardware tokens for cryptographic applications, in this work we provide the first solution to collusion preserving computation which uses weaker and more common assumptions than the state of the art, i.e., an authenticated broadcast functionality and access to honestly generated trusted hardware tokens. We prove that our protocol is collusion-preserving (in short, CP) secure as long as no parties abort. In the case of an aborting adversary, our protocol still achieves standard (G)UC security with identifiable (and unanimous) abort. Leveraging the above identifiability property, we augment our protocol with a penalization scheme which ensures that it is not profitable to abort, thereby obtaining CP security against incentive-driven attackers. To define (and prove) this latter result, we combine the Rational Protocol Design (RPD) methodology by Garay et al. [FOCS 2013] with the CP framework of Alwen et al. [CRYPTO 2012] to derive a definition of security in the presence of incentive-driven local adversaries which can be of independent interest. Similar to existing CP/CF solutions, our protocol preserves, as a fallback, security against monolithic adversaries, even when the setup (i.e., the hardware tokens) is compromised or corrupted. In addition, our fallback solution achieves identifiable and unanimous abort, which we prove are impossible in previous CP solutions.Collusion-free (CF) and collusion-preserving (CP) protocols enrich the standard security offered by multi-party computation (MPC), to tackle settings where subliminal communication is undesirable. However, all existing solutions make arguably unrealistic assumptions on setups, such as physical presence of the parties, access to physical envelopes, or extreme isolation, where the only means of communication is a star-topology network. The above state of affairs remained a limitation of such protocols, which was even reinforced by impossibility results. Thus, for years, it has been unclear if and how the above setup assumptions could be relaxed towards more realistic scenarios. Motivated also by the increasing interest in using hardware tokens for cryptographic applications, in this work we provide the first solution to collusion preserving computation which uses weaker and more common assumptions than the state of the art, i.e., an authenticated broadcast functionality and access to honestly generated trusted hardware tokens. We prove that our protocol is collusion-preserving (in short, CP) secure as long as no parties abort. In the case of an aborting adversary, our protocol still achieves standard (G)UC security with identifiable (and unanimous) abort. Leveraging the above identifiability property, we augment our protocol with a penalization scheme which ensures that it is not profitable to abort, thereby obtaining CP security against incentive-driven attackers. To define (and prove) this latter result, we combine the Rational Protocol Design (RPD) methodology by Garay et al. [FOCS 2013] with the CP framework of Alwen et al. [CRYPTO 2012] to derive a definition of security in the presence of incentive-driven local adversaries which can be of independent interest. Similar to existing CP/CF solutions, our protocol preserves, as a fallback, security against monolithic adversaries, even when the setup (i.e., the hardware tokens) is compromised or corrupted. In addition, our fallback solution achieves identifiable and unanimous abort, which we prove are impossible in previous CP solutions.

IEEE Computer Security Foundations Workshop (CSFW)Aug 1, 20225 citations

A Practical Privacy-Preserving Cooperative Computation Protocol without Oblivious Transfer for Linear Systems of Equations

Ju-Sung Kang, Dowon Hong

We propose several practical SMC protocols for privacy-preserving cooperative scientific computations. We consider two important scientific computations which involve linear equations: the linear systems of equations problem and the linear least-square problem. The protocols proposed in this paper achieve acceptable security in the sense of Du-Zhan's paradigm and t-wise collusion-resistance, and their communication complexity is O(tm), where t is a security parameter and m is the total number of participants. The complexity of our protocol is significantly better than the previous result O( $m^2/{\mu}$ ) of [4], in which the oblivious transfer protocol is used as an important building block.We propose several practical SMC protocols for privacy-preserving cooperative scientific computations. We consider two important scientific computations which involve linear equations: the linear systems of equations problem and the linear least-square problem. The protocols proposed in this paper achieve acceptable security in the sense of Du-Zhan's paradigm and t-wise collusion-resistance, and their communication complexity is O(tm), where t is a security parameter and m is the total number of participants. The complexity of our protocol is significantly better than the previous result O( $m^2/{\mu}$ ) of [4], in which the oblivious transfer protocol is used as an important building block.

Journal of Information Processing SystemsJun 30, 20076 citations

m^2/{\mu}

) of [4], in which the oblivious transfer protocol is used as an important building block.