Geometry of Secure Computation

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=QOVTNLb--iA


Duration: 47:30
694 views
17

Hemanta Maji (Purdue University)
https://simons.berkeley.edu/talks/hemanta-maji-purdue-university-2023-05-04
Minimal Complexity Assumptions for Cryptography

Reducing the overhead of security solutions increases their adoption. Motivated by such efficiency considerations, characterizing secure computation's round and communication complexity is natural.

The seminal results of Chor-Kushilevitz-Beaver (STOC-1989, FOCS-1989, DIMACS-1989) determine these complexities for deterministic computations. Determining randomized-output functions' round and communication complexity remained open for over three decades. This talk will present how we settled this long-standing open problem.

Our technical innovation is a geometric framework for this research -- opening a wormhole connecting it to geometry research. This framework encodes all candidate secure protocols as points. Studying mathematical properties of novel generalizations of their convex hull implies round and communication complexity results.



Other Videos By Simons Institute for the Theory of Computing


2023-05-23On the Robustness to Misspecification of α-Posteriors and Their Variational Approximations
2023-05-23Majorizing Measures, Codes, and Information
2023-05-22KEYNOTE: A (Con)Sequential View of Information for Statistical Learning and Optimization
2023-05-06Black-Box Separations in Quantum Cryptography *Presented Virtually
2023-05-06Quantum pseudorandomness in Algorithmica, and its implications to cryptography and complexity
2023-05-06On the Computational Hardness Needed for Quantum Cryptography
2023-05-06Commitments to Quantum States
2023-05-06Quantum Minimalism
2023-05-05Cryptography with Certified Deletion *Presented Virtually
2023-05-05Black-Hole Radiation Decoding as a Cryptographic Assumption
2023-05-05Geometry of Secure Computation
2023-05-05Collision-Resistance from Multi-Collision-Resistance
2023-05-05New Ways to Garble Arithmetic Circuits
2023-05-05Unclonable Polymers and Their Cryptographic Applications
2023-05-05Batch Proofs are Statistically Hiding
2023-05-05Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography
2023-05-04Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
2023-05-04Assumptions in cryptography and complexity theory
2023-05-04Mutual Empowerment Between Circuit Obfuscation and Circuit Minimization
2023-05-04Tales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential Privacy
2023-05-04Tutorial on obfuscation


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Minimal Complexity Assumptions for Cryptography
Hemanta Maji