1970 Primitives Assumptions PKE 1980 Signatures ZK OT Factoring Discrete Log 1990 Secure computation 2000 Minimize communication? Minimize interaction? 2010 Minimize local computation?1970 1980 1990 2000 2010 PKE Secure Computation ZK Primitives Signatures Assumptions OT • Minimize communication? • Minimize interaction? • Minimize local computation? Factoring Discrete Log