3
$\begingroup$

In the bounded storage model, it assumes the storage of the adversary is bounded or limited, and thus it is possible that we can achieve a kind of cryptography without relying on hardness assumption. But what does it mean by "bounded storage"? Should it assume the length of the message is always too long for any computer on the earth to store? So can I conclude that the cryptographic scheme that replies on bounded storage model is not so efficient(if it is not very inefficient)? Since it should always send a very long message. And I think it is not compatible with blockchain(hard to imagine a very long message is stored on the blockchain). Am I right?

Reference: Simple Schemes in the Bounded Storage Model, Disappearing Cryptography in the Bounded Storage Model, Secure Multiparty Computation in the Bounded Storage Model, Speak Much, Remember Little: Cryptography in the Bounded Storage Model, Revisited

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ [edited] My very limited understanding of the bounded storage model is that it assumes adversaries have limited storage for their intermediary calculations, but lets normal users use feasibly little storage, and aims (if not necessarily succeeds) to work with as normal/small size of messages as possible. $\endgroup$
    – fgrieu ♦
    Nov 9, 2021 at 9:37
  • 1
    $\begingroup$ Can you add sources/link where this expression appear to help us to understand the context? $\endgroup$
    – Ievgeni
    Nov 9, 2021 at 13:55
  • 1
    $\begingroup$ @levgeni: about the only paper on the BSM that I attempted to read is Jiaxin Guan, Mark Zhandary: Simple Schemes in the Bounded Storage Model, in proceedings of Eurocrypt 2019. $\endgroup$
    – fgrieu ♦
    Nov 9, 2021 at 15:17

1 Answer 1

Reset to default
1
$\begingroup$

But what does it mean by "bounded storage"?

Typically, the bounded storage means that an adversary cannot store all of the bits that were exchanged in the protocol. For example, in key exchange, the eavesdropper cannot store the whole exchange of the honest parties. In section 1.1 of the first paper you cite, it mentions that the bounds are usually as follows. For a security parameter $n$, the honest participants exchange $O(n^2)$ bits and need $O(n)$ bits of storage to perform the protocol while the adversary needs $\Omega(n^2)$ bits of storage to break the scheme.

Should it assume the length of the message is always too long for any computer on the earth to store?

The bounded storage assumption should hold against anyone who has access to the transmission in the scheme. So if you're communicating over local area networks for example, the memory bound would need to apply to every machine within range. On the other hand, if you're performing key exchange over the internet, the memory bound would need to be quite large.

So can I conclude that the cryptographic scheme that replies on bounded storage model is not so efficient(if it is not very inefficient)?

It depends on the metric of efficiency and in which context you apply the schemes. They are memory efficient, but do require a large transmission.

Since it should always send a very long message. And I think it is not compatible with blockchain(hard to imagine a very long message is stored on the blockchain). Am I right?

If the message is stored on a public blockchain, then by definition you are not in the bounded storage model since many computers all over the world have a copy of the bits exchange, so they can all break the scheme.

I should also mention that there is a quantum variant of the bounded storage model, where it is assumed that the adversary has limited quantum storage. This model is better justified than the classical model since storing quantum information is actually very hard and one of the main challenges in building a scalable quantum computer. Moreover, sending and measuring qubits is actually quite easier technologically. You can buy commercial boxes that achieve this. And the schemes are conceived so that honest participants need no quantum memory whatsoever. The main downside is that these boxes need to be linked by a quantum channel and sending quantum signals over long distances is also difficult. If you're interested to learn more, I suggest starting with Christian Schaffner's thesis.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.