Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden.
powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden.
powered by
Abstract
The dual execution paradigm of Mohassel and Franklin (PKC’06) and Huang, Katz and Evans (IEEE ’12) shows how to achieve the notion of 1-bit leakage security at roughly twice the cost of semi-honest security for the special case of two-party secure computation. To date, there are no multi-party computation (MPC) protocols that offer such a strong trade-off between security and semi-honest performance.
Our main result is to address this shortcoming by designing 1-bit leakage protocols for the multi-party setting, albeit for a special class of functions. We say that function f(x, y) is efficiently verifiable byg if the running time of g is always smaller than f and \(g(x,y,z)=1\) if and only if \(f(x,y)=z\).
In the two-party setting, we first improve dual execution by observing that the “second execution” can be an evaluation of g instead of f, and that by definition, the evaluation of g is asymptotically more efficient.
Our main MPC result is to construct a 1-bit leakage protocol for such functions from any passive protocol for f that is secure up to additive errors and any active protocol for g. An important result by Genkin et al. (STOC ’14) shows how the classic protocols by Goldreich et al. (STOC ’87) and Ben-Or et al. (STOC ’88) naturally support this property, which allows to instantiate our compiler with two-party and multi-party protocols.
A key technical result we prove is that the passive protocol for distributed garbling due to Beaver et al. (STOC ’90) is in fact secure up to additive errors against malicious adversaries, thereby, yielding another powerful instantiation of our paradigm in the constant-round multi-party setting.
As another concrete example of instantiating our approach, we present a novel protocol for computing perfect matching that is secure in the 1-bit leakage model and whose communication complexity is less than the honest-but-curious implementations of textbook algorithms for perfect matching.
Anzeige
Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.
Where the security definition allows the adversary to submit an arbitrary leakage predicate such that the honest party learns its output condition on whether the predicate is true when applied on the parties’ inputs.
[HKE12] observed that their protocol need not achieve fully malicious security, but does satisfy a notion that is stronger than honest-but-curious security.
One could instead use commitments for the translation table, but this would require the check circuit to implement the cryptographic verification procedure of the decommitments. In some circumstances AES-based commitments (or other methods) might be concretely better than decoding the VSS.
While this notion is suggested heuristically in [HKE12], we achieve it formally. This notion is similar to the \(2^{-s}\)-CovIDA notion presented by Mohassel and Riva [MR13].