International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Amortized Complexity of Information-Theoretically Secure MPC Revisited

Authors:
Ignacio Cascudo
Ronald Cramer
Chaoping Xing
Chen Yuan
Download:
DOI: 10.1007/978-3-319-96878-0_14 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2018
Abstract: A fundamental and widely-applied paradigm due to Franklin and Yung (STOC 1992) on Shamir-secret-sharing based general n-player MPC shows how one may trade the adversary thresholdt against amortized communication complexity, by using a so-called packed version of Shamir’s scheme. For e.g. the BGW-protocol (with active security), this trade-off means that if $$t + 2k -2 < n/3$$ t+2k-20$$ ϵ>0 fraction below 1/3), this is improved to O(1) bits instead of O(n).
Video from CRYPTO 2018
BibTeX
@inproceedings{crypto-2018-28793,
  title={Amortized Complexity of Information-Theoretically Secure MPC Revisited},
  booktitle={Advances in Cryptology – CRYPTO 2018},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={10993},
  pages={395-426},
  doi={10.1007/978-3-319-96878-0_14},
  author={Ignacio Cascudo and Ronald Cramer and Chaoping Xing and Chen Yuan},
  year=2018
}