Quantum computing is receiving increasing attention as it promises to revolutionize the current computational landscape. The advent of quantum computers will be particularly disruptive in the field of cryptography, where characteristically quantum properties like entanglement and the ``no-cloning theorem'' open up a plethora of novel opportunities. In this talk, I will describe two broad, and connected, research questions. The first is: if a quantum device is meant to perform tasks that are beyond the reach of classical computers, how can a classical user trust that her quantum device is behaving as intended? I will focus particularly on the connections of this question with foundational questions in quantum information. The second is: once we trust our quantum devices, what kinds of cryptographic tasks can we realize that are beyond the reach of classical computers? I will describe some concrete examples.