Bounded Storage Model¶
A cryptographic security model that uses temporary public randomness and a bound on adversarial retained information, rather than computational limits, to evaluate specified protocol goals.
Core Idea¶
The bounded storage model (BSM) is a classical cryptographic security model. A large public random source is accessible during a specified phase, but an adversarial party can retain only a bounded amount of information from it. The adversary may compute without a complexity limit while that source is available. Security is then evaluated for a particular protocol and goal under the assumed retention limit; the assumption alone proves no secrecy theorem.[1][2][3]
The frozen selected member, hyper-encryption, is an encryption use of the model, not another name for the model. Unlike protocol uses include Aumann, Ding and Rabin's two-party communication schemes and Ding's one-out-of-two oblivious transfer (OT). The former constrains an outside observer and seeks message secrecy; the latter constrains a possibly dishonest receiver and seeks an asymmetric transfer. Their different goals and adversarial roles make the shared resource model visible.[1][2]
Structural Signature¶
Sig role-phrases:
- Public random source and window. A long random string or stream \(R\) is publicly accessible for a specified phase. Access and later availability are part of the experiment; a bare statement that some bits are random does not define BSM.[2][3]
- Adversarial retention constraint. A declared bound limits what the adversarial party can keep about \(R\), not what it can compute while seeing \(R\). The adversary can be an eavesdropper or a protocol participant, and the relevant capacity is construction-relative.[1][2]
- Honest protocol use. Honest parties sample, retain or interact using the public source according to a stated protocol. An initial short shared secret, particular sampling rule and amount of honest storage are design choices, not universal model roles.[1][2][3]
- Security goal and parameters. The experiment declares a functionality, adversarial capability, error/security parameters and timing. Message confidentiality, OT privacy and bare key agreement are different goals. Whether a construction achieves one is a theorem question, not an automatic consequence of naming the model.[1][2][3]
Remove the retained-information cap while leaving a public random source and an encryption routine: the distinctive BSM premise is gone. Remove an initial shared secret while retaining the source, cap and specified goal: a bare BSM variant can still be posed. Replace message confidentiality by OT choice privacy: the model can persist while the protocol and security experiment change.[3][2]
What It Is Not¶
BSM is not a computational-hardness assumption. It permits an adversary unlimited computation while restricting retained source information under the specified schedule. Nor is it a generic low-memory algorithm: the limited retention is an adversarial capability in a cryptographic experiment involving public randomness and a security goal.[1][2]
It is not equivalent to encryption or to OT. Those are protocol functions that can use this model, and neither function follows from a storage bound alone. Likewise, later disclosure of a secret key is covered by Aumann–Ding–Rabin's specified schemes as reported in their abstract, not by every BSM construction. A bounded-quantum-storage or noisy-storage protocol changes the stored carrier and needs its own equivalence argument before it can be merged into this classical identity.[1][2]
Scope of Application¶
The admitted scope is classical information-theoretic cryptography using a large public random source and a limit on adversarial retained information. The source can be publicly broadcast or otherwise made available under a defined protocol schedule. The model is used in two-party communication and OT, with key-agreement variants illustrating that an initial shared secret is not constitutive. The cited works support these formal settings; they do not demonstrate a deployed source that can reliably distribute and erase enough randomness.[1][2][3]
Aumann–Ding–Rabin's author-institution abstract reports two secure communication protocols and scheme-specific secrecy even after later key disclosure. The complete original protocol and proof hypotheses were not inspected here, so this entry does not infer a universal key-revelation guarantee or exact access schedule from the abstract. Ding's full original gives a concrete OT protocol and capacity analysis. Dziembowski–Maurer's full paper studies bare key agreement; its honest-access lower bound is confined to that task and variant.[1][2][3]
Clarity¶
“Bounded storage” describes retained output, not a prohibition on temporary computation. A computationally powerful adversary can process the public source while it passes, but the game constrains what remains available later. This distinction explains why simply increasing later computing power need not recover bits or information that the adversary did not keep in a protocol proven secure under the assumption. It does not establish secrecy for an arbitrary protocol.[1][3]
The unit and timing must be read from the particular source. Ding's general setup writes a receiver bound \(B=\gamma n\) with \(\gamma<1\). In the displayed analysis of his Protocol A, \(B=n/6\); Protocol A broadcasts two independent public \(n\)-bit strings \(\alpha_0\) and \(\alpha_1\) successively. The one-string exposition of the generic model is not the two-string schedule of this worked construction. These statements should not be collapsed into a claim that every BSM scheme uses two strings or one universal storage fraction.[2]
Manages Complexity¶
A BSM claim can be audited in four steps: name the public random source and its window; name which party is storage-bounded and exactly what it may retain; describe the honest protocol's use of the source; and state the security game and parameters. This sequence separates model membership from a protocol's claimed achievement. It also prevents transfer of one paper's bound or key schedule into another paper's theorem.[2][3]
For instance, Ding's dishonest receiver and Aumann–Ding–Rabin's external eavesdropper occupy the same adversarial-retention role, but not the same social position or security game. Dziembowski–Maurer's bare model removes an initial secret and asks a key-agreement question. One can compare these by roles without treating their security results as interchangeable.[1][2][3]
Abstract Reasoning¶
Suppose an otherwise identical security experiment allows the adversary to retain all relevant information about \(R\). The BSM separation between transient public access and limited retained state vanishes; any prior theorem whose hypothesis requires that bound cannot simply be carried over. Conversely, reducing the amount an adversary may retain does not by itself prove a given encryption or OT construction secure. The formal security argument must connect the protocol's sampling and messages to its stated goal.[1][2]
Now change only the goal. The public source and storage cap could support either a communication-secrecy experiment or a transfer-privacy experiment, but the honest and dishonest participant roles change. Ding's sender has bits \(M_0,M_1\), the receiver has choice \(\delta\), and the intended output is \(M_\delta\) without both bits being learned by the receiver or \(\delta\) by the sender. Those are not consequences one may infer from the communication protocol's confidentiality result.[2]
Knowledge Transfer¶
The transfer across these cryptographic settings is the timed public-source plus retained-information structure. Aumann–Ding–Rabin use it to analyze message communication in the presence of a bounded outside observer. Ding uses it for OT against a bounded dishonest receiver. The change of protocol function does not remove the structural roles; it changes the security game and which actor bears the bound.[1][2]
The structure should not be exported by verbal resemblance alone. A fast public data feed plus a device with small RAM is not BSM unless the experiment states adversarial retained information, honest use and a cryptographic goal. The generally portable resource-limitation component is already represented by live Prime Constraint; the named BSM additionally requires its classical public-random-source and cryptographic setting.
Examples¶
Canonical: bounded-storage secure communication¶
Aumann–Ding–Rabin report two secure two-party communication protocols in BSM. Mapped back: the public random source and window are publicly available random bits used during message transmission, though their abstract does not give every access schedule; the adversarial retention constraint limits an outside observer's stored output while allowing unlimited computation; honest protocol use combines public bits with an initially shared secret, with a short-key/many-public-bits design and a longer-key/fewer-public-bits design; the security goal and parameters concern message confidentiality and, for their proved schemes, secrecy after later key revelation. The abstract supplies the high-level mapping, not full theorem conditions or a license to call every BSM protocol “everlasting.”[1]
Applied: Ding's one-out-of-two oblivious transfer¶
Ding's Protocol A gives a different formal use. Mapped back: the public random source and window consist of independently drawn \(n\)-bit \(\alpha_0\) and \(\alpha_1\) broadcast in successive protocol steps with a short pause; the adversarial retention constraint is on a dishonest receiver's state, with general \(B=\gamma n\), \(\gamma<1\), and displayed Protocol A analysis at \(B=n/6\); honest protocol use has Alice holding \(M_0,M_1\), Bob holding private choice \(\delta\), and both sampling selected positions of the two strings; the security goal and parameters require Bob to obtain \(M_\delta\) without learning both bits and Alice not to learn \(\delta\), under Ding's construction and game. His stated honest storage and cheating bounds are construction-specific, not a universal property of the model.[2]
The two cases are unlike in functionality and adversarial placement. A selected encryption protocol called hyper-encryption maps to the first use; it is not a synonym for the model.[1][2]
Structural Tensions¶
T1: Adversarial retention gap versus honest resource cost. Limiting what an adversary can keep is the model's leverage, but honest parties must obtain enough of the public source, possibly retain samples or share a secret, for a particular construction to work. Aumann–Ding–Rabin contrast their short-key/many-public-bits and longer-key/fewer-public-bits communication designs. Ding reports honest storage for his OT construction. Dziembowski–Maurer prove an honest-access requirement in bare key agreement. These are separate protocol-specific observations, not a common numeric tradeoff law for all BSM tasks. Diagnostic: for this stated security goal and adversarial retention budget, what public-source volume and honest storage or key budget does the chosen protocol actually require?[1][2][3]
Structural–Framed Character¶
BSM sits between a structural formal model and a framed cryptographic practice. Evaluative weight: whether a capacity bound holds is a formal predicate, but whether it is physically plausible and whether the specified security error is acceptable depend on an application. Human-practice dependence: designers choose a source schedule, which actor is adversarial, a protocol and a goal; the abstract model does not make those choices. Institutional origin: the named literature supplies definitions and proofs, while no one paper's institution or implementation constitutes the identity. Vocabulary travel: “bounded storage” can be said of any device, but it travels literally as BSM only when the public-random-source security roles recur. Import versus recognition: recognizing BSM in a new classical protocol requires the four roles; it does not require importing Ding's two broadcasts, Aumann–Ding–Rabin's key choice, or Dziembowski–Maurer's bare-key-agreement lower bound.[1][2][3]
Its character: a formal, source-timed cryptographic security model with a precise adversarial resource assumption and protocol-dependent conclusions. Its mathematical constraint is crisp, while the chosen source, actor, goal and operational feasibility keep the named abstraction in its domain.
Structural Core vs. Domain Accent¶
The core is the public random source and limited access window, an adversary with bounded retained information but unrestricted computation during access, honest protocol use, and a declared functionality and security experiment. The live Prime Constraint supplies the broad constituent skeleton: a domain of possible retained states, a hard capacity condition, a feasible adversary class, and binding or slack relative to a stated limit. The strict composition / part_of / parent_in_child edge points from BSM to that necessary constituent; Constraint need not involve cryptography, and BSM is not itself a kind of Constraint.
The domain accent is inseparable from the subject: \(R\) is public randomness in a classical cryptographic game, the retention cap is an adversary assumption, and an honest protocol pursues a stated secrecy or transfer goal. ADR communication and Ding OT vary within that domain. A free-standing Prime for “security from less retained information” would need an independently defined cross-domain full signature and unlike noncryptographic positives; these sources establish no such node. They instead support a specialist model containing an already live Prime constituent. The proof status of each protocol remains outside the model definition.[1][2]
Instantiates / Related Primes¶
This entry is part of Constraint.
Strict parent: Constraint (Composition, part_of, parent_in_child, child to parent). The parent domain is the set of possible adversarial retained records or functions of \(R\); the explicit predicate is a maximum retained-information budget; it divides feasible and excluded strategies. Saturation and slack are meaningful even if no actual attacker is observed. The bound is hard in the stated experiment and arises from its resource assumption. Both ADR's eavesdropper and Ding's dishonest receiver fill these roles. Removing the bound erases BSM's distinguishing premise; the broader Constraint Prime applies to other domains without any public random source.[1][2]
Rejected strict alternatives: live Threat Model is a revisable decision artifact with scoped assets, attack paths, impacts and response priorities, none necessary to this formal experiment. Information Asymmetry may arise as a successful protocol outcome, but a capacity assumption alone does not ensure its full signature. Randomness is an input assumption here, not a proof that the full live Randomness node's source and quality roles are present. Encryption is a protocol function using BSM in one case, whereas OT supplies another; neither is a kind-of parent for the model.[1][2]
Relationships to Other Abstractions¶
Current abstraction Bounded Storage Model Domain-specific
Parents (1) — more general patterns this builds on
-
Bounded Storage Model is part of Constraint Prime
A hard cap on adversarial retained source information is constitutive of every admitted bounded-storage experiment.Possible retained records or functions of the public random source form the domain; the declared maximum retained-information budget separates feasible from excluded adversarial strategies. The bound may be saturated or slack, is hard for the security experiment, and originates in its stated resource assumption. Remove it and the distinctive model disappears. Both the external observer in Aumann–Ding–Rabin and the dishonest receiver in Ding instantiate the same constituent without making the model itself a Constraint.
Hierarchy path (1) — routes to 1 parentless root
- Bounded Storage Model → Constraint
Neighborhood in Abstraction Space¶
Bounded Storage Model sits in a sparse region of the domain-specific corpus (73rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Adversarial AI & Security Attacks (14 abstractions)
Nearest neighbors
- Data Extraction Through Prompting — 0.86
- Computational hardness assumption — 0.84
- Small Subgroup Confinement Attack — 0.84
- Noisy Channel Model — 0.83
- Input Manipulation Attack — 0.82
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
- Hyper-encryption: the frozen selected encryption member using BSM, not its model genus.[1]
- A generic memory-limited program: BSM bounds an adversarial party's retained information about a public source in a security experiment, not arbitrary algorithm workspace.[1][2]
- Unconditionally secure protocol by name alone: model assumptions need a protocol-specific proof and security parameters.[1][2]
- Bare BSM as all of BSM: no initial shared key is one variant, and the 2008 honest-access lower bound concerns bare key agreement.[3]
- Quantum or noisy storage models: a bound on a different carrier is a neighboring model until full-role equivalence is shown.
References¶
[1] Yonatan Aumann, Yan Zong Ding, and Michael O. Rabin (2002), Everlasting Security in the Bounded Storage Model, IEEE Transactions on Information Theory 48(6):1668–1680. https://doi.org/10.1109/TIT.2002.1003845. Author-institution publication record, Abstract lines 38–42 and metadata lines 20–24, 44–53; the full journal protocol and proof text was not directly inspected for this entry. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w
[2] Yan Zong Ding (2001), Oblivious Transfer in the Bounded Storage Model, Advances in Cryptology — CRYPTO 2001, LNCS 2139, printed pp. 155–170. https://doi.org/10.1007/3-540-44647-8_9. Full original proceedings PDF: Abstract and §1 printed pp. 155–156; §2 p. 157; §3.2 Protocol A pp. 162–163. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z
[3] Stefan Dziembowski and Ueli Maurer (2008), The Bare Bounded-storage Model, The Tight Bound on the Storage Requirement for Key Agreement, IEEE Transactions on Information Theory 54(6):2790–2792. The original title page uses a colon after “Model.” Full author-hosted original PDF, Abstract and §§I–II. Its lower bound addresses bare key agreement, not every bounded-storage protocol. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m