On the Limitations of Pseudorandom Unitaries

This chapter delves into the limitations of pseudorandom unitaries (PRUs) in the context of quantum cryptography. It explores the implications of PRUs for quantum bit commitments and key agreements, highlighting the challenges and potential of these primitives in enhancing cryptographic security. The study introduces the concept of pseudorandom unitaries and their role in quantum cryptography, particularly in weakening the assumptions needed for traditional cryptographic tasks. It discusses the relationship between PRUs and various quantum cryptographic primitives, such as quantum bit commitments, secret-key encryption, digital signatures, and message authentication codes. The chapter also examines the concept of quantum cryptography with classical communication (QCCC) and the limitations of QCCC primitives. It presents a general framework to show separations between PRUs and QCCC primitives, focusing on QCCC bit commitments and key agreements. The study introduces the notion of strong pseudorandom unitaries (strong PRUs) and explores their relationship with QCCC primitives. Central to the results is the establishment of LOCC indistinguishability frameworks for unitaries, which are crucial for proving the separations. The chapter concludes with a discussion on the implications of these findings for the future of quantum cryptography.