The noisy-storage model[1] refers to a cryptographic model employed in quantum cryptography. It assumes that the quantum memory device of an attacker (adversary) trying to break the protocol is imperfect (noisy). The main goal of this model is to enable the secure implementation of two-party cryptographic primitives, such as bit commitment, oblivious transfer and secure identification.
Quantum communication has proven to be extremely useful when it comes to distributing encryption keys. It allows two distant parties Alice and Bob to expand a small initial secret key into an arbitrarily long secret key by sending qubits (quantum bits) to each other. Most importantly, it can be shown that any eavesdropper trying to listen into their communication cannot intercept any information about the long key. This is known as quantum key distribution (QKD).
Yet, it has been shown that even quantum communication does not allow the secure implementation of many other two-party cryptographic tasks.[2] [3] [4] [5] These all form instances of secure function evaluation. An example is oblivious transfer. What sets these tasks apart from key distribution is that they aim to solve problems between two parties, Alice and Bob, who do not trust each other. That is, there is no outside party like an eavesdropper, only Alice and Bob. Intuitively, it is this lack of trust that makes the problem hard. Unlike in quantum key distribution, Alice and Bob cannot collaborate to try and detect any eavesdropping activity. Instead, each party has to fend for himself.
Since tasks like secure identification are of practical interest, one is willing to make assumptions on how powerful the adversary can be. Security then holds as long as these assumptions are satisfied. In classical cryptography, i.e., without the use of quantum tools, most of these are computational assumptions. Such assumptions consists of two parts. First, one assumes that a particular problem is difficult to solve. For example, one might assume that it is hard to factor a large integer into its prime factors (e.g. 15=5x3). Second, one assumes that the adversary has a limited amount of computing power, namely less than what is (thought to be) required to solve the chosen problem.
In information theoretic cryptography physical assumptions appear, which do not rely on any hardness assumptions, but merely assume a limit on some other resource. In classical cryptography, the bounded-storage model introduced by Ueli Maurer assumes that the adversary can only store a certain number of classical bits.[6] [7] Protocols are known that do (in principle) allow the secure implementation of any cryptographic task as long as the adversary's storage is small. Very intuitively, security becomes possible under this assumption since the adversary has to make a choice which information to keep. That is, the protocol effectively overflows his memory device leading to an inevitable lack on information for the adversary. It was later discovered that any classical protocol which requires the honest parties to store
n
O(n2)
This gap changes dramatically when using quantum communication[9] . That is, Alice and Bob can send qubits to each other as part of the protocol. Likewise, one now assumes that the adversary's quantum storage is limited to a certain number of qubits. There is no restriction on how many classical bits the adversary can store. This is known as the bounded-quantum-storage model.[9] [10] It was shown that there exist quantum protocols in which the honest parties need no quantum storage at all to execute them, but are nevertheless secure as long as Alice transmits more than twice the number of qubits than the adversary can store.
More generally, security is possible as long as the amount of information that the adversary can store in his memory device is limited. This intuition is captured by the noisy-storage model,[1] which includes the bounded-quantum-storage model as a special case.[11] Such a limitation can, for example, come about if the memory device is extremely large, but very imperfect. In information theory such an imperfect memory device is also called a noisy channel. The motivation for this more general model is threefold. First, it allows one to make statements about much more general memory devices that the adversary may have available. Second, security statements could be made when the signals transmitted, or the storage device itself, uses continuous variables whose dimension is infinite and thus cannot be captured by a bounded storage assumption without additional constraints. Third, even if the dimension of the signals itself is small, the noisy-storage analysis allows security beyond the regime where bounded-storage itself can make any security statement. For example, if the storage channel is entanglement breaking, security is possible even if the storage device is arbitrarily large (i.e., not bounded in any way).
The assumption of the noisy-storage model is that during waiting times
\Deltat
l{F}:l{S}(l{H}\rm) → l{S}(l{H}\rm)
\rho\rm\inl{S}(l{H}\rm)
\rho\rm\inl{S}(l{H}\rm)
The latter assumption also implies that he can perform any form of error correcting encoding before and after using the noisy memory device, even if it is computationally very difficult to do (i.e., it requires a long time). In this context, this is generally referred to as an encoding attack
l{E}
l{D}
l{E}
l{F}
l{D}
In practise, one often considers storage devices that consist of
N
l{F}=l{N} ⊗
l{N}:S(\Complexd) → S(\Complexd)
d
N
l{F}=l{N} ⊗
l{N}(\rho)=λ\rho+(1-λ)id/2
N
l{F}=id ⊗
id
Most protocols proceed in two steps. First, Alice and Bob exchange
n
The second step is to perform classical post-processing of the measurement data obtained in step one. Techniques used depend on the protocol in question and include privacy amplification, error-correcting codes, min-entropy sampling, and interactive hashing.
To demonstrate that all two-party cryptographic tasks can be implemented securely, a common approach is to show that a simple cryptographic primitive can be implemented that is known to be universal for secure function evaluation. That is, once one manages to build a protocol for such a cryptographic primitive all other tasks can be implemented by using this primitive as a basic building block. One such primitive is oblivious transfer. In turn, oblivious transfer can be constructed from an even simpler building block known as weak string erasure in combination with cryptographic techniques such as privacy amplification.
All protocols proposed to date allow one of the parties (Alice) to have even an unlimited amount of noise-free quantum memory. I.e., the noisy-storage assumption is applied to only one of the parties (Bob). For storage devices of the form
l{F}=l{N} ⊗
l{N}=id
n>2N
N<n/2
n
n\gtrapproxN
n=N
l{F}=l{N} ⊗
n
n>2 ⋅ N ⋅ C(l{N})
C(l{N})
l{N}
l{N}
n>2 ⋅ N ⋅ EC(l{N})
EC(l{N})
l{N}
EC(l{N})
l{F}=l{N} ⊗
n
n>Q(l{N})N
Q
l{N}
l{N}
The three mutually unbiased bases are the same encodings as in the six-state protocol of quantum key distribution. The last condition does form the best known condition for most channels, yet the quantum capacity as well as the strong converse parameter are generally not easy to determine.
Using such basic primitives as building blocks is not always the most efficient way to solve a cryptographic task. Specialized protocols targeted to solve specific problems are generally more efficient. Examples of known protocols are
The assumption of bounded-quantum-storage has also been applied outside the realm of secure function evaluation. In particular, it has been shown that if the eavesdropper in quantum key distribution is memory bounded, higher bit error rates can be tolerated in an experimental implementation.[10]