Why is MPC considered 'universal' despite being computationally expensive?
Think about your answer, then reveal below.
Model answer: MPC is universal in the theoretical sense: for any function f that can be computed by a Turing machine, there exists an MPC protocol enabling n parties to compute f on secret inputs without revealing the inputs. This does not mean MPC is practical (it is exponentially slower than plaintext computation), but it proves no function is inherently uncomputable in the MPC setting. Universality is the fundamental theorem of MPC; practicality is engineering.
Universality is a theoretical guarantee; achieving practical efficiency requires domain-specific optimizations and careful protocol design.
Question 2 Multiple Choice
In secret-sharing-based MPC (e.g., Shamir secret sharing), how does computation on shared secrets work?
AShared secrets cannot be operated on; the scheme is only for storage
BAddition and multiplication of secret shares can be performed locally without revealing the underlying secret; addition is linear, multiplication requires interaction (communication)
COnly addition is possible; multiplication of secrets is impossible
DComputation on secrets requires reconstructing them, revealing secrets to all parties
Secret sharing enables computation on shared values without reconstruction. Addition of secrets is linear: if a is shared as (a_1, ..., a_n) and b as (b_1, ..., b_n), then a+b is shared as (a_1+b_1, ..., a_n+b_n), computed locally by each party. Multiplication is nonlinear: computing a*b from shares requires interaction (typically one round). This property enables designing MPC protocols where most computation is local, with minimal interaction for multiplications.