Cryptography from Pseudorandom Quantum States
Abstract: Pseudorandom states, introduced by Ji, Liu and Song (Crypto'18), are efficiently-computable quantum states that are computationally indistinguishable from Haar-random states. One-way functions imply the existence of pseudorandom states, but Kretschmer (TQC'20) recently constructed an oracle relative to which there are no one-way functions but pseudorandom states still exist. Motivated by this, we study the intriguing possibility of basing interesting cryptographic tasks on pseudorandom states.
We construct, assuming the existence of pseudorandom state generators, (a) statistically binding and computationally hiding commitments and (b) pseudo one-time encryption schemes. A consequence of (a) is that pseudorandom states are sufficient to construct maliciously secure multiparty computation protocols in the dishonest majority setting. We believe that our results point to an intriguing new landscape of cryptographic protocols and hardness assumptions in the quantum world.
Speaker bio: Dr. Henry Yuen is an Assistant Professor of Computer Science at Columbia University. His research focuses on the interplay between quantum computing, complexity theory, cryptography, and information theory. Yuen received a BA in mathematics from the University of Southern California in 2010, and received his PhD in computer science at MIT in 2016. He was an assistant professor in the Computer Science and Mathematics departments at the University of Toronto between 2018 - 2020, and joined the faculty of Columbia in 2021.
To watch online go to the IQUIST youtube channel: https://www.youtube.com/channel/UCCzAySwQXF8J4kRolUzg2ww
For Zoom link you may check the IQUIST calendar weekly email or contact Kelly Foster (email@example.com), or Hannah Stites (firstname.lastname@example.org). To subscribe to our weekly email for event announcements, please go to https://lists.illinois.edu/lists/subscribe/iquist-announcements.