Powerful Primitives in the Bounded Quantum Storage Model

In this paper, we delve deeper into the BQSM. We first adapt conventional definitions, such as those pertaining to encryption and one-time programs, to the BQSM. We then proceed to construct a variety of cryptographic primitives as elaborated on below.

We first build information-theoretic secure one-time programs ²²2A one-time program (as introduced in [15]) $(1)$ can be used to obtain a single evaluation of the program on any input chosen by the user, and at the same time, $(2)$ (black-box obfuscation) cannot be used to obtain any other information about the program (see Definition 11). through utilizing the BQS-OT scheme. We then leverage one-time programs to construct information-theoretic secure CCA1-symmetric encryption. All these schemes are secure against any computationally unbounded adversary with s qmemory where s can be any fixed polynomial (in the security parameter) whereas honest users do not need any qmemory.

Next, we address the challenges associated with information-theoretic asymmetric key cryptography, particularly the task of hiding the secret key from the public key without relying on computational assumptions. We propose the novel primitive termed program broadcast as a natural solution.

Roughly speaking, a $k$-time program broadcast of a function $P$ allows arbitrarily many users to each $(1)$ obtain a single evaluation of the program, and, at the same time, $(2)$ cannot be used by any user to learn more than $k$ evaluations of the program. We proceed to construct an information-theoretically secure program broadcast and employ it to build CCA1-secure asymmetric key encryption. In the full paper, we also use program broadcast to build information-theoretically secure signatures, signature tokens, and encryption tokens. A signature token, as first defined in [5], can be used to sign a single message (without the signing key) and then self-destructs. We similarly define decryption tokens – each such token allows its holder to decrypt a single ciphertext and then self-destructs.

The schemes built from program broadcast are secure against any computationally unbounded adversary with s qmemory where s can be any fixed polynomial in the security parameter but require ${\lg }^k(\lambda )$ qmemory for the receiver where $k\in ℝ$ can take any value larger than $2$. This implies that the gap between the qmemory required of the honest user and the needed qmemory to break security approaches ${\lg }^2(\lambda )\text{vs.}\mathrm{𝗉𝗈𝗅𝗒}\left(\lambda \right)$ which translates to a gap of $m\text{vs.}{e}^{\sqrt{m}}$ by setting $m={\lg }^2(\lambda )$. While we cannot assert that the required qmemory for the honest receiver in the asymmetric setting is optimal, we show in the full paper that it is not possible to achieve asymmetric key cryptography without requiring any qmemory for the honest user. Given that our qmemory requirements are already quite minimal, there is little room for improvement. For simplicity, in the rest of the paper we work with $k=3$, however, our results easily apply to any value $k>2$.

Prior to this work, none of the aforementioned primitives have been achieved in the BQSM and all are impossible information-theoretically in the plain model.

Our constructions additionally satisfy disappearing security which shall be formally defined in Sec. 5 but we provide a brief overview here. A transmission, say a ciphertext or signature, is deemed disappearing if it can no longer be used after a certain point [21]. In the encryption setting, an adversary cannot decrypt a ciphertext even if the private key is revealed afterward. While in the authentication setting, an adversary cannot forge a signature of a message $\mu$ even if it has received a signature of $\mu$ earlier! Such disappearing properties are impossible in the plain model for obvious reasons, but in the BQSM an adversary cannot necessarily store a ciphertext or signature for later use.

The qmemory requirements for the receiver in our program broadcast, asymmetric key encryption, and signature schemes make these constructions difficult to actualize with current technology given the difficulty of storing quantum states. It is worth noting, however, that the users only need a small amount of qmemory and only need it at the start in order to process the public keys. Therefore, we hope that these schemes will become feasible with further advancements.

Meanwhile, our one-time programs, symmetric key encryption, and message authentication codes can be realized with current technology as they only require the ability to prepare, send, and measure a single qubit in the BB84 basis. Specifically, these constructions can be implemented on hardware designed to run quantum key distribution (QKD), albeit with a caveat. Indeed, popular weak coherent pulse sources require interaction as the receiver needs to tell the sender which pulses were received. However, other technologies can enable non-interactive quantum transmissions to allow for non-interactive primitives such as one-time programs, encryption, and signature schemes. For instance, heralded photon sources can, in principle, remove the need for interaction.

Note also that our constructions can be modified to allow for users with imperfect apparatus to perform non-interactive error correction without compromising the security of the scheme as we briefly discuss in Sec. 9. With all that being said, in this work, we focus on building the theory and leave it as an open research direction to properly prepare the theoretical constructions for real-world applications.

We compare our results with similar contributions in alternative models.

We now present a quantum algorithm $𝒪$ that converts any polynomial classical circuit to a one-time program in the BQSM (Theorem 17). Fortunately, the BQSM dodges all the impossibility proofs of one-time programs. The work showing the impossibility of quantum one-time programs [7] does not apply to our setting since our programs cannot be stored by the adversary to be reused. Moreover, the proof of the impossibility of quantum obfuscation [7] does not apply since it requires the adversary to run the quantum circuit homomorphically. Adversaries in our setting are forced to continuously perform measurements on quantum states (due to the memory bound) which interrupts a quantum homomorphic evaluation.

Before describing the construction, we discuss its intuition. A natural first attempt is to apply previous one-time program constructions [15, 18] based on one-time memory devices but replace the devices with BQS-OT transmissions. The problem is that simulating an adversary requires determining which 1-out-of-2 strings are received from the oblivious transfer transmissions. This information allows the simulator to deduce which evaluation the adversary has learned from the program. In earlier constructions, this is not a problem since the adversary must explicitly ask which string it wishes to receive from the one-time memory devices. Note that Kilian [23] builds a similar notion known as oblivious circuit evaluation from OT but the simulator is also assumed to be given this information. In these works, the simulator can simply run the adversary and “know” which strings are requested. However, in our case, it is not clear this extraction is always possible – a complex adversary might not know itself which 1-out-of-2 strings it has received! To make matters worse, our adversary is a quantum and computationally unbounded algorithm. Note that the proof of security for BQS-OT does not provide a method to extract the receiver’s chosen bit but rather just shows that such a bit must exist.

To solve this issue, we construct a simulator that (inefficiently) analyzes the circuit of the adversary gate-by-gate to extract the chosen bit. In particular, the simulator takes the circuit of the adversary and runs it an exponential number of times on all possible BQS-OT transmissions. This allows the simulator to approximately determine the distribution of the measurement results obtained by the adversary given the transmission provided to the adversary. This then allows the simulator to determine the distribution of the BQS-OT transmission from the perspective of the adversary given the measurement results obtained. In other words, the simulator can infer which part of the transmission the adversary is uncertain about which can be used to determine which string the adversary is oblivious to.

The rest of the construction involves adapting Kilian’s approach [23] for building one-time programs from oblivious transfer to the quantum realm. Readers are referred to Sec. 6 for the formal statement of our result. However, the construction and proof are given in the full paper as they are quite long and detailed.

We use one-time programs to build a symmetric key encryption scheme that satisfies indistinguishability under (lunchtime) chosen ciphertext attack (IND-CCA1) [8] and with disappearing ciphertexts. IND-CCA1 tests security against an adversary that can query the encryption oracle at any point in the experiment and can query the decryption oracle at any point before the challenge ciphertext is received. To satisfy disappearing security under CCA1, we require that such an adversary cannot win the IND-CCA1 experiment even if the private key is revealed after the challenge ciphertext is given.

To achieve IND-CPA (where the adversary is not given access to a decryption oracle), the ciphertext can simply consist of a one-time program that evaluates to $⟂$ on every input except on the private key, where it outputs the message. By the security of one-time programs, an adversary has a negligible chance of guessing the key and learning the message. Upgrading to CCA1-security turns out to be far more involved as we now discuss.

First of all, it is trivial to show that we must rely on quantum ciphertexts for unconditional security in the BQSM. Now, traditionally, a CPA-secure scheme can be upgraded to a CCA-secure one by simply authenticating ciphertexts using message-authentication codes or a signature scheme. However, it seems difficult to authenticate a quantum ciphertext in a way that allows verification without any qmemory. Alternatively, we could authenticate the output of the one-time programs in the CPA construction. Specifically, instead of sending programs that map the secret key to the message, we send programs that map the key to the message along with a tag or signature of the message.

This solution fails due to the following attack: an adversary queries the encryption oracle on an arbitrary message $\mu$, receives a one-time program, modifies the one-time program so that it outputs $⟂$ on any input starting with 0, and forwards the modified one-time program to the decryption oracle. Depending on the response received from the oracle, the adversary can successfully determine the first bit of the secret key. This attack can be repeated a polynomial number of times to deduce the entire secret key. It turns out an adversary can perform a variety of attacks of this sort due to a fundamental problem with the BQSM: this model provides security by ensuring that users only receive partial information from a transmission. Hence, it is difficult to detect whether an adversary has tampered with a transmission.

To thwart such attacks, we rely on a construction where a ciphertext consists of two interdependent one-time programs. The first program initiates some randomness and this randomness is used to ensure that the second one-time program is evaluated on a seemingly random input during decryption. To prevent the adversary from choosing the first one-time program, we authenticate the output of the first program in the second program using the secret key. We show that it is difficult to modify both programs simultaneously in a meaningful way without being detected. Proving this rigorously is somewhat technical as the adversary can still perform various modifications successfully – the reader is referred to Theorem 22 for the formal proof.

Asymmetric cryptography utilizes a pair of related keys, a secret and a public key, to enable versatile cryptographic applications. Specifically, our goal is to build information-theoretic secure asymmetric key encryption and digital signatures in the BQSM. However, the task of concealing the secret key from the public key without relying on computational assumptions poses a significant challenge. Such assumptions should be avoided in the BQSM given the goal of this model is to base security purely on the memory limitations of the players.

This implies we need to impose the memory bound in some way during the public key transmission in order to hide the secret key. In the classical bounded storage model, this can be done by announcing a large classical public key [12]. However, in our scenario, imposing the memory bound necessitates the use of quantum public keys. Unfortunately, due to no-cloning, we need to create and distribute multiple copies of the quantum key – this is the general approach taken in the computational setting as well [17, 13, 22]. Here we face a critical problem: if a computationally unbounded adversary gains access to multiple copies of the key, it can repeatedly reuse its quantum memory to process multiple keys. Such an adversary could gradually extract classical information from each key copy until it has learned the entire quantum public key.

To prevent this attack, it is imperative that every public key copy needs additional qmemory to process, preventing an adversary from processing an unlimited number of keys. In other words, we need to distribute keys in a way so that all users must process the keys simultaneously or in parallel. More abstractly, we want to distribute quantum information in a way that allows every user to learn some information while preventing a computationally unbounded adversary from learning too much information. This goal is a recurring theme in various settings, hence, we introduce a new notion which we term program broadcast that formalizes and captures this objective. We build this primitive unconditionally in the BQSM and employ it to build asymmetric cryptography.

All in all, this is the first work to achieve information-theoretic asymmetric key encryption in any of the bounded (classical or quantum) storage models. This is the main focus and contribution of this paper. In the following, we first discuss program broadcast, which may be of independent interest, and then how this can be used to realize asymmetric cryptography.

In many situations, we would like to send multiple one-time programs to multiple users while ensuring that no adversary can take advantage of all the information to learn the program. This is the goal of program broadcast. Recall that a $k$-time program broadcast of a function $P$ allows an unbounded polynomial number of users to each $(1)$ obtain at least a single evaluation of the program, and, at the same time, $(2)$ cannot be used by any user to learn more than $k$ evaluations of the program. Essentially, an adversary with access to the broadcast can be simulated with access to $k$ queries to an oracle for $P$.

In Sec. 7, we present a scheme for an information-theoretically secure program broadcast in the BQSM. The idea is to distribute a polynomial number of augmented one-time programs of $P$ in a fixed time period. Unlike the one-time programs discussed in the previous section, these augmented versions require a small amount of qmemory to process.

More rigorously, there is a set time where the sender distributes one-time programs of the form $𝒪(P\oplus c_i)$ where $𝒪$ is our one-time compiler. In each one-time program, the output of $P$ is padded with a different value $c_i$. A quantum ciphertext is generated which encrypts the value $c_i$ and is sent with the corresponding one-time program. Users can evaluate the one-time program but need to store the ciphertext states until the encryption key is revealed to make use of their evaluation. The key is revealed at a set time after all users have received a one-time program copy. By revealing this classical key at the end, we are essentially forcing users to process the programs in a parallel fashion, limiting the number of evaluations that can be learned. In other words, an adversary with bounded qmemory can store the ciphertext states for a limited number of one-time programs and thus can only learn a limited number of evaluations of $P$.

To prove this rigorously, we need a new min-entropy lower bound (Lemma 7) which roughly states that if $H_{\mathrm{\infty }}(X_0{X}_1\mathrm{\dots }{X}_{p-1}|Q)\ge \alpha$, where $X_i\in {\{0,1\}}^n$ and $Q$ is some quantum information, then there exists $i\in [p]$ and negligible $ϵ$ such that roughly $H_{\mathrm{\infty }}^{ϵ}(X_i)\ge \alpha /p$. Konig and Renner [24] established such a bound but only in the case when $n$ is sufficiently large with respect to $p$. Unfortunately, in our applications, $n$ is very small with respect to $p$. Informally, we resolve this issue by using their bound when $p$ is small and then use this as a base case to an inductive argument for larger values of $p$ achieving the required result. This result is of independent interest in the field of information theory.

Note that while one-time programs can be built from one-time memory devices in the plain model, this is insufficient to build program broadcast in the plain model. Specifically, we need to use the qmemory bound outside the one-time programs as well in order to construct this primitive. Hence, program broadcast acts as a more pronounced advantage of the BQSM.

We now discuss how we upgrade our symmetric key encryption scheme to a CCA1-secure asymmetric key scheme using program broadcast. We let the private key be a large program $P$ while the public key is a quantum program broadcast of $P$. A user can use the broadcast to learn a single evaluation of $P$ which can be used to encrypt messages in the same way as in the private key setting. However, an adversary can only learn a limited number of evaluations by the security of the program broadcast. If $P$ is large enough then this knowledge is not sufficient to predict the output of $P$ on a random input. In other words, the adversary cannot predict the encryption key of another user, so security is reduced to the symmetric key setting.

It is not difficult to show that the public keys need to be mixed-state for information-theoretic security in the BQSM. This might seem unfortunate, but we believe that it is not very relevant whether keys are pure or mixed-state. Some works, such as [4], require that the quantum public keys be pure since this would provide some level of certification by allowing users to compare keys with a SWAP test. However, this test is not always feasible to perform in the BQSM given that keys cannot necessarily be stored. Instead, we provide a more secure way to certify mixed-state quantum keys without establishing authenticated quantum channels in a companion work [2]. That being said, in this work, we do not certify public keys and it is always assumed that honest users receive authentic quantum public keys. This is a common assumption for the quantum public key schemes, such as those in [17, 13, 22], as a quantum state cannot be signed [3].

We briefly discuss two interesting impossibility results that we present in the full paper. First, we show that it is impossible to implement asymmetric schemes (with unbounded public key copies) in the BQSM without requiring qmemory from the honest user. The fundamental idea is that if the public keys require no qmemory to process then an adversary can request and process an unbounded number of key copies which would reveal information about the secret key. The technical argument is more involved since the public keys may be mixed-state which could aid in hiding information.

The second impossibility result is concerned with the disappearing property of our constructions. The ciphertexts and one-time programs satisfy disappearing security providing interesting applications as we discussed earlier. However, this disappearing property can also be disadvantageous in some scenarios. For instance, sometimes, it is more beneficial to have an obfuscation that can be stored and reused multiple times instead of a disappearing one-time program. The final contribution of this paper is to provide a negative result showing that non-disappearing obfuscation and one-time programs are impossible in the BQSM.

The proof relies on a new approach since our simulator is computationally unbounded, which nullifies adversarial attacks used in standard impossibility proofs [1, 14, 6, 7]. Essentially, we show that if a computationally unbounded adversary can perform a single evaluation after the qmemory bound applies then it can rewind the program and perform another evaluation. By the gentle measurement lemma [32], this rewinding introduces only a negligible error each time which allows the adversary to learn a super-polynomial number of evaluations with non-negligible probability. These evaluations can be used to learn more information regarding the hidden program than any simulator can learn using only a polynomial number of oracle queries. We refer the reader to the full paper for more details.

In the following, we denote Hilbert spaces by calligraphic letters: $\mathscr{H}$, $𝒱$, etc… The set of positive semi-definite operators in Hilbert space $\mathscr{H}$ are denoted $\mathrm{Pos}(\mathscr{H})$. When Hilbert space $𝒳$ holds a classical value, we denote the random variable for this value by $X$.

We denote the density matrix of a quantum state in a register $E$ as ${\rho }_E$. If a quantum state depends on a classical variable $X$, then we denote ${\rho }_E^x$ as the density matrix of the state given $X=x$. Meanwhile, to an observer who does not know the value of $X$, the state is given by ${\rho }_E≔{\sum }_{x}P(X=x){\rho }_E^x$ and the joint state by ${\rho }_{XE}≔{\sum }_{x}P(X=x)|x⟩⟨x|\otimes {\rho }_E^x$. Such states having a quantum part depending on a classical value are called cq-states. The random variable $X$ then corresponds to the classical state ${\rho }_X≔{\sum }_{x}P(X=x)|x⟩⟨x|$.

We denote the trace distance between two density matrices as $\delta (\rho ,\sigma )$ and the trace norm as ${\Vert \rho \Vert }_1$.

Notice that ${\rho }_{XE}={\rho }_X\otimes {\rho }_E$ if and only if ${\rho }_E$ is independent of $X$ (i.e. ${\rho }_E^x={\rho }_E$) which means that no information can be learned regarding ${\rho }_E$ from $X$ and vice versa. More generally, if ${\rho }_{XE}$ is $ϵ$-close to ${\rho }_E\otimes {\rho }_X$ in terms of trace distance denoted as $\delta ({\rho }_{XE},{\rho }_X\otimes {\rho }_E)\le ϵ$ or equivalently ${\rho }_{XE}{\approx }_{ϵ}{\rho }_X\otimes {\rho }_E$, then no observer can distinguish between the two systems with advantage greater than $ϵ$. We write $⟨{\rho }_A,{\rho }_B⟩$ to denote a sequential transmission where register $A$ is sent and then register $B$.

The rectilinear or $+$ basis for the complex space ${ℂ}^2$ is the pair $\{|0⟩,|1⟩\}$ while the diagonal or $\times$ basis is the pair $\{{|0⟩}_{\times },{|1⟩}_{\times }\}$ where ${|0⟩}_{\times }≔\frac{|0⟩+|1⟩}{\sqrt{2}}$ and ${|1⟩}_{\times }≔\frac{|0⟩-|1⟩}{\sqrt{2}}$. To choose between the $+$ and $\times$ basis depending on a bit $b\in \{0,1\}$, we write ${\{+,\times \}}_b$.

We say $x{\in }_{R}X$ if $x$ is chosen uniformly at random from the values in $X$. We let ${\mathrm{𝟙}}_k$ denote the density matrix of a uniformly distributed variable on $k$ elements. Also, let $[n]≔[0,1,\mathrm{\dots },n-1]$ and let $\mathrm{𝗇𝖾𝗀𝗅}\left(n\right)$ be denoting any function that is smaller than the inverse of any polynomial for large enough $n$.

We say an algorithm $A$ is QPT if it is a quantum polynomial-time algorithm. We let $A^P$ denote an algorithm with access to a polynomial number of classical oracle queries to the program $P$ and let $A^{qP}$ denote access to $q$ classical oracle queries.

Recall a Pauli pad [27] information-theoretically hides a $n$-qubit state using a $2n$-bit key $k$. We denote ${\text{PP}}_k(\rho )$ to be the Pauli pad of the state with density matrix $\rho$ using key $k$.

By abuse of notation, if $x$ is a binary string and $M$ is a matrix then, for simplification, we let $M\cdot x$ denote the string representation of the vector $M\cdot \overrightarrow{x}$.

We remind the reader of the notion of quantum Rényi Entropy and its variants. See [25] for more detailed definitions.

This section discusses lower bounds on the average min-entropy and presents a new generalized min-entropy splitting lemma conditioned on quantum states. This will be fundamental in our program broadcast construction.

The min-entropy satisfies the following chain rule.

If $X=X_0{X}_1$ has high entropy, then it was shown in [10] that, in a randomized sense, one of $X_0$ or $X_1$ has high entropy.

More generally, min-entropy sampling gives lower bounds on the min-entropy of a subset of a string given the min-entropy of the entire string. In [24], it was shown how to sample min-entropy relative to quantum knowledge which allows us to give a lower bound on min-entropy conditioned on a quantum state.

For the rest of this work, we let ${\text{H}}_{m,\mathrm{\ell }}$ denote a two-universal class of hash functions from ${\{0,1\}}^m$ to ${\{0,1\}}^{\mathrm{\ell }}$. Remember that a class of hash functions is two-universal if for every distinct $x,x^{\prime }\in {\{0,1\}}^m$ and for $F{\in }_R{\text{H}}_{m,\mathrm{\ell }}$, we have $Pr[F(x)=F(x^{\prime })]\le \frac{1}{2^{\mathrm{\ell }}}$.

The following result shows that it is difficult to learn a large matrix using a small number of samples and is proven in the full paper.

We present the following experiment to define disappearing security for one-time programs. Intuitively, the experiment checks whether an adversary that receives a one-time program can retrieve the evaluation on a random input $x$ that is only revealed after the program. The experiment focuses on matrix branching programs but the same experiment can be applied to any circuit class where sampling can be done efficiently.

Experiment ${\text{1TP}}_{𝚷\mathbf{,}𝓐}^{\text{Dis}}\mathbf{(}𝒎\mathbf{,}𝒏\mathbf{,}\mathbf{\ell }\mathbf{)}$: Let $\mathrm{\Pi }(m,P)$ be the one-time program protocol with security parameter $m$ on the matrix branching program $P:{\{0,1\}}^n\to {\{0,1\}}^{\mathrm{\ell }}$. 1. Sample $x{\in }_R{\{0,1\}}^n$ and a matrix branching program $P:{\{0,1\}}^n\to {\{0,1\}}^{\mathrm{\ell }}$ uniformly at random. 2. Protocol $\mathrm{\Pi }(m,P)$ is executed between the experiment and adversary $𝒜$. 3. After the execution ends, send $x$ to $𝒜$. 4. $𝒜$ outputs a guess $p$ for $P(x)$. 5. The output of the experiment is 1 if $p=P(x)$ and 0 otherwise.

We first recall the definition of a quantum asymmetric (public) key encryption scheme on classical messages. Note that the public key in this setting is quantum so multiple copies must be created and distributed due to the no-cloning theorem. Hence, we add an algorithm KeySend that outputs a copy of the quantum public key when queried. In our security experiment, the adversary is allowed to receive a polynomial number of public key copies. We also introduce an algorithm KeyReceive which describes how to extract a reusable classical key from a public key copy to use for encryption.

We now present an experiment to test disappearing security under lunchtime chosen ciphertext attack (qDCCA1) in the BQSM. Recall, IND-CCA1 [8] tests security against an adversary that can query the encryption oracle at any point in the experiment and can query the decryption oracles at any point before the challenge ciphertext is received. To satisfy disappearing security under CCA1, we require that an adversary cannot win the IND-CCA1 experiment even if the private key is revealed after the challenge ciphertext is given.

Experiment ${\text{AsyK}}_{𝚷\mathbf{,}𝓐}^{\text{qDCCA1}}\mathbf{(}𝝀\mathbf{)}$: 1. Sample a private key $sk\leftarrow \text{Gen}(1^{\lambda })$ and bit $b{\in }_R\{0,1\}$. 2. Generate a public key ${\rho }_{pk}\leftarrow \text{KeySend}(sk)$. 3. Extract key $k\leftarrow \text{KeyReceive}({\rho }_{pk})$. 4. Adversary outputs two messages $m_0,m_1\leftarrow {𝒜}^{\text{KeySend}(sk),\text{Enc}(k,\cdot ),\text{Dec}(sk,\cdot )}$. 5. Send ${𝒜}^{\text{KeySend}(sk),\text{Enc}(k,\cdot )}$ the ciphertext ${\rho }_{ct}\leftarrow \text{Enc}(k,m_b)$. 6. Give ${𝒜}^{\text{KeySend}(sk),\text{Enc}(k,\cdot )}$ the private key $sk$. 7. ${𝒜}^{\text{KeySend}(sk),\text{Enc}(k,\cdot )}$ outputs a guess $b^{\prime }$. 8. The output of the experiment is $1$ if $b^{\prime }=b$ and 0 otherwise.

We can similarly construct disappearing experiment in the symmetric key case, denoted ${\text{SymK}}_{\mathrm{\Pi },𝒜}^{\text{qDCCA1}}(\lambda )$ by deleting steps 2 & 3 and replacing $k$ with $sk$ in the asymmetric experiment.

In this section, we present a private key encryption scheme that satisfies disappearing indistinguishability under chosen ciphertext attacks (qDCCA1).

We now look into the asymmetric key setting and construct an asymmetric key encryption scheme with information-theoretic disappearing security under chosen-ciphertext attacks in the BQSM. The private key is a large matrix and the public key is a program broadcast of the matrix. Since different users will likely learn different evaluations, an evaluation can be used as a secret key to encrypt messages in the same way as in Construction 21. Note that honest users need a small qmemory to process the broadcast as described in Construction 18. This is in contrast to the private key setting where no qmemory is required.