Commitments to Quantum States

Published on ● Video Link: https://www.youtube.com/watch?v=3iAiX1dO1Gk



Duration: 48:16
274 views
4


Fermi Ma (Princeton University)
https://simons.berkeley.edu/talks/fermi-ma-princeton-university-2023-05-05
Minimal Complexity Assumptions for Cryptography

What does it mean to commit to a quantum state? In this talk, I will present a simple, but perhaps counterintuitive answer: a quantum state commitment (QSC) is binding if sending the commitment erases the committed message from the sender’s view. Using this new definition, I will show how to construct the first succinct QSCs, which can be seen as an analog of collision-resistant hashing for quantum messages.

Commitments to quantum states open the door to many new cryptographic possibilities. Our flagship application is a quantum-communication version of Kilian's succinct arguments for any language that has quantum PCPs with constant error and polylogarithmic locality. Plugging in the PCP theorem, this yields succinct arguments for NP under significantly weaker assumptions than required classically; moreover, if the quantum PCP conjecture holds, this extends to QMA. At the heart of our security proof is a new rewinding technique for extracting quantum information.

Joint work with Sam Gunn, Nathan Ju, and Mark Zhandry.
https://eprint.iacr.org/2022/1358.pdf




Other Videos By Simons Institute for the Theory of Computing


2023-05-23Generalization bounds for Neural Network Based Decoders
2023-05-23Optimal Neural Network Compressors and the Manifold Hypothesis
2023-05-23Fairness without Imputation: A Decision Tree Approach for Fair Prediction with Missing Values
2023-05-23Secure Distributed Matrix Multiplication
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



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