It is well known that Shor's quantum algorithm for integer factorization can break down the RSA public-key cryptosystem, which is widely used in many cryptographic applications. Thus, public-key cryptosystems in the quantum computational setting are longed for cryptology. In order to define the security notions of public-key cryptosystems, we have to model the power of the sender, receiver, adversary and channel. While we may consider a setting where quantum computers are available only to adversaries, we generally discuss what are the right security notions for (quantum) public-key cryptosystems in the quantum computational setting. Moreover, we consider the security of quantum public-key cryptosystems known so far.
The bounded quantum storage model aims to achieve security against computationally unbounded adversaries that are restricted only with respect to their quantum memories. In this work, we provide information-theoretic secure constructions in this model for the following powerful primitives: (1) CCA1-secure symmetric key encryption, message authentication codes, and one-time programs. These schemes require no quantum memory for the honest user, while they can be made secure against adversaries with arbitrarily large memories by increasing the transmission length sufficiently. (2) CCA1-secure asymmetric key encryption, encryption tokens, signatures, signature tokens, and program broadcast. These schemes are secure against adversaries with roughly em quantum memory where m is the quantum memory required for the honest user. All of the constructions additionally satisfy disappearing security, essentially preventing an adversary from storing and using a transmission later on.