On the computational overhead of MPC with dishonest majority

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Standard

On the computational overhead of MPC with dishonest majority. / Nielsen, Jesper Buus; Ranellucci, Samuel.

Public-Key Cryptography – PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. ed. / Serge Fehr . Vol. 10175 Berlin Heidelberg : Springer VS, 2017. p. 369-395 (Lecture Notes in Computer Science, Vol. 10175).

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Harvard

Nielsen, JB & Ranellucci, S 2017, On the computational overhead of MPC with dishonest majority. in S Fehr (ed.), Public-Key Cryptography – PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. vol. 10175, Springer VS, Berlin Heidelberg, Lecture Notes in Computer Science, vol. 10175, pp. 369-395, 20th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2017, Amsterdam, Netherlands, 28/03/2017. https://doi.org/10.1007/978-3-662-54388-7_13

APA

Nielsen, J. B., & Ranellucci, S. (2017). On the computational overhead of MPC with dishonest majority. In S. Fehr (Ed.), Public-Key Cryptography – PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings (Vol. 10175, pp. 369-395). Springer VS. Lecture Notes in Computer Science, Vol.. 10175 https://doi.org/10.1007/978-3-662-54388-7_13

CBE

Nielsen JB, Ranellucci S. 2017. On the computational overhead of MPC with dishonest majority. Fehr S, editor. In Public-Key Cryptography – PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. Berlin Heidelberg: Springer VS. pp. 369-395. (Lecture Notes in Computer Science, Vol. 10175). https://doi.org/10.1007/978-3-662-54388-7_13

MLA

Nielsen, Jesper Buus and Samuel Ranellucci "On the computational overhead of MPC with dishonest majority". Fehr , Serge (ed.). Public-Key Cryptography – PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. Berlin Heidelberg: Springer VS. (Lecture Notes in Computer Science, Vol. 10175). 2017, 369-395. https://doi.org/10.1007/978-3-662-54388-7_13

Vancouver

Nielsen JB, Ranellucci S. On the computational overhead of MPC with dishonest majority. In Fehr S, editor, Public-Key Cryptography – PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. Vol. 10175. Berlin Heidelberg: Springer VS. 2017. p. 369-395. (Lecture Notes in Computer Science, Vol. 10175). https://doi.org/10.1007/978-3-662-54388-7_13

Author

Nielsen, Jesper Buus ; Ranellucci, Samuel. / On the computational overhead of MPC with dishonest majority. Public-Key Cryptography – PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. editor / Serge Fehr . Vol. 10175 Berlin Heidelberg : Springer VS, 2017. pp. 369-395 (Lecture Notes in Computer Science, Vol. 10175).

Bibtex

@inproceedings{775d0e2ed3fa491fa5d9a7988642a38c,
title = "On the computational overhead of MPC with dishonest majority",
abstract = "We consider the situation where a large number n of players want to securely compute a large function f with security against an adaptive, malicious adversary which might corrupt t < cn of the parties for some given c ∈ [0, 1). In other words, only some arbitrarily small constant fraction of the parties are assumed to be honest. For any fixed c, we consider the asymptotic complexity as n and the size of f grows. We are in particular interested in the computational overhead, defined as the total computational complexity of all parties divided by the size of f. We show that it is possible to achieve poly-logarithmic computational overhead for all c < 1. Prior to our result it was only known how to get poly-logarithmic overhead for c < 1/2. We therefore significantly extend the area where we can do secure multiparty computation with polylogarithmic overhead. Since we allow that more than half the parties are corrupted, we can only get security with abort, i.e., the adversary might make the protocol abort before all parties learn their outputs. We can, however, for all c make a protocol for which there exists d > 0 such that if at most dn parties are actually corrupted in a given execution, then the protocol will not abort. Our result is solely of theoretical interest. In its current form, it has not practical implications whatsoever.",
author = "Nielsen, {Jesper Buus} and Samuel Ranellucci",
year = "2017",
doi = "10.1007/978-3-662-54388-7_13",
language = "English",
isbn = "9783662543870",
volume = "10175",
series = "Lecture Notes in Computer Science",
publisher = "Springer VS",
pages = "369--395",
editor = "{Fehr }, Serge",
booktitle = "Public-Key Cryptography – PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings",
note = "20th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2017 ; Conference date: 28-03-2017 Through 31-03-2017",

}

RIS

TY - GEN

T1 - On the computational overhead of MPC with dishonest majority

AU - Nielsen, Jesper Buus

AU - Ranellucci, Samuel

PY - 2017

Y1 - 2017

N2 - We consider the situation where a large number n of players want to securely compute a large function f with security against an adaptive, malicious adversary which might corrupt t < cn of the parties for some given c ∈ [0, 1). In other words, only some arbitrarily small constant fraction of the parties are assumed to be honest. For any fixed c, we consider the asymptotic complexity as n and the size of f grows. We are in particular interested in the computational overhead, defined as the total computational complexity of all parties divided by the size of f. We show that it is possible to achieve poly-logarithmic computational overhead for all c < 1. Prior to our result it was only known how to get poly-logarithmic overhead for c < 1/2. We therefore significantly extend the area where we can do secure multiparty computation with polylogarithmic overhead. Since we allow that more than half the parties are corrupted, we can only get security with abort, i.e., the adversary might make the protocol abort before all parties learn their outputs. We can, however, for all c make a protocol for which there exists d > 0 such that if at most dn parties are actually corrupted in a given execution, then the protocol will not abort. Our result is solely of theoretical interest. In its current form, it has not practical implications whatsoever.

AB - We consider the situation where a large number n of players want to securely compute a large function f with security against an adaptive, malicious adversary which might corrupt t < cn of the parties for some given c ∈ [0, 1). In other words, only some arbitrarily small constant fraction of the parties are assumed to be honest. For any fixed c, we consider the asymptotic complexity as n and the size of f grows. We are in particular interested in the computational overhead, defined as the total computational complexity of all parties divided by the size of f. We show that it is possible to achieve poly-logarithmic computational overhead for all c < 1. Prior to our result it was only known how to get poly-logarithmic overhead for c < 1/2. We therefore significantly extend the area where we can do secure multiparty computation with polylogarithmic overhead. Since we allow that more than half the parties are corrupted, we can only get security with abort, i.e., the adversary might make the protocol abort before all parties learn their outputs. We can, however, for all c make a protocol for which there exists d > 0 such that if at most dn parties are actually corrupted in a given execution, then the protocol will not abort. Our result is solely of theoretical interest. In its current form, it has not practical implications whatsoever.

UR - http://www.scopus.com/inward/record.url?scp=85014438192&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-54388-7_13

DO - 10.1007/978-3-662-54388-7_13

M3 - Article in proceedings

AN - SCOPUS:85014438192

SN - 9783662543870

VL - 10175

T3 - Lecture Notes in Computer Science

SP - 369

EP - 395

BT - Public-Key Cryptography – PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings

A2 - Fehr , Serge

PB - Springer VS

CY - Berlin Heidelberg

T2 - 20th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2017

Y2 - 28 March 2017 through 31 March 2017

ER -