Explore communication lower bounds for information-theoretic secure multiparty computation in this conference talk from the ITC Conference. Delve into two classes of lower bounds: one for perfect passive secure multiparty computation with n=2t+1 parties, and another for perfect maliciously secure setting with n=3t+1 parties. Examine the proof of a lower bound applicable to secure evaluation of any function, assuming parties can choose to learn or not learn the output. Investigate the existence of a reactive functionality requiring Ω(nS) bits of communication for perfect malicious security implementation. Learn how these results extend to suboptimal thresholds and their implications for Boolean circuits and finite fields. Gain insights into functional entropy, examples, and statistical security through a comprehensive exploration of secure multiparty computation challenges and advancements.
Overview
Syllabus
Intro
Secure multiparty computation
Communication lower bounds
Our questions
Our results
Functional entropy
Lower bound, max threshold n=2+1
Examples
A reactive functionality
Lower bound, four parties
Lower bound, 3+1 parties
An upper bound for 14
Statistical security
Conclusion
Taught by
Paul G. Allen School
