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 cryptographic security model in which a large public random source is available for a limited phase, while an adversarial party can retain only a bounded amount of information from it. The adversary may compute without a complexity limit during access. A particular protocol and security goal must still be specified and proved; the storage assumption alone does not deliver secrecy.[ref-30e8e1a80f62][ref-63b9a39dc9e7]
Hyper-encryption, the frozen selected member, is an encryption use of BSM, not another name for the model. BSM also supports a distinct oblivious-transfer use.[ref-30e8e1a80f62][ref-63b9a39dc9e7]
Scope of Application¶
The identity has four necessary roles: (1) a public random source and its access window; (2) a stated cap on what the adversary can retain about that source, rather than a cap on temporary computation; (3) an honest protocol that uses the source; and (4) a declared cryptographic function, adversarial capabilities, timing and security parameters. The bounded actor may be an outside observer or a dishonest participant. Initial shared keys, sampling rules and honest storage amounts vary by construction.[ref-30e8e1a80f62][ref-63b9a39dc9e7][^ref-306991aa3eed]
This is a classical formal model. The cited papers do not establish a deployed system able to distribute and erase enough public randomness. Aumann–Ding–Rabin's author-institution abstract supports only a high-level description of its two communication schemes, including scheme-specific later-key-disclosure secrecy; its full protocol and proof conditions were not inspected here. Ding's complete original gives a concrete OT construction. Dziembowski–Maurer's lower bound concerns bare key agreement, not all BSM tasks.[ref-30e8e1a80f62][ref-63b9a39dc9e7][^ref-306991aa3eed]
Clarity¶
“Bounded” means that only a limited record of the public source remains available to the adversary after the access window. Unlimited computation while seeing the source does not let it keep every bit for later. What information suffices for an attack, however, depends on the stated protocol and goal.[ref-30e8e1a80f62][ref-63b9a39dc9e7]
Ding's general setup uses a receiver budget \(B=\gamma n\) with \(\gamma<1\). Its displayed Protocol A analysis uses \(B=n/6\) and two independent public \(n\)-bit strings \(\alpha_0\) and \(\alpha_1\) broadcast successively. Neither the two-string schedule nor the fraction \(1/6\) defines every BSM protocol.[^ref-63b9a39dc9e7]
Manages Complexity¶
To read a BSM claim, identify the public source and when it is accessible, the party whose retained information is capped, how the honest parties use the source, and the exact security game. This checklist keeps a model premise separate from a proved result. It also prevents importing Ding's OT budget into Aumann–Ding–Rabin's communication claim, or a bare-key-agreement lower bound into either protocol.[ref-30e8e1a80f62][ref-63b9a39dc9e7][^ref-306991aa3eed]
Abstract Reasoning¶
If an otherwise identical experiment lets the adversary retain all relevant source information, the distinctive BSM premise disappears. A theorem requiring the cap cannot simply be carried over. If the cap remains but the function changes from communication secrecy to OT privacy, the model can remain while the actors, messages and proof obligations change. Neither use is a kind of Constraint: each contains a strict Constraint constituent, namely the hard retained-information budget. The reviewed typed edge is child-to-parent composition / part_of / parent_in_child to live Prime Constraint.[ref-30e8e1a80f62][ref-63b9a39dc9e7]
Knowledge Transfer¶
The portable pattern across these cases is temporary public randomness plus a bound on adversarial retained information. In communication, the bounded actor is an external observer and the goal is message secrecy. In OT, it is a possibly dishonest receiver and the goal is asymmetric transfer. These are unlike security experiments even though they share the same resource model. A device with little RAM or a large public data feed does not qualify without all four BSM roles.[ref-30e8e1a80f62][ref-63b9a39dc9e7]
Example¶
Communication schemes¶
Aumann–Ding–Rabin report two two-party schemes. Four-role map: publicly available random bits used during message transmission supply the source and window, though the abstract does not establish every access detail; an outside observer has bounded retained information despite unrestricted computation; the parties' schemes combine public bits with an initially shared secret as honest protocol use; and message confidentiality, with later key disclosure covered for their specified schemes, is the security goal. This is a map from the inspected abstract, not a reconstruction of its full proof.[^ref-30e8e1a80f62]
Oblivious transfer¶
Ding's Protocol A supplies an unlike use. Four-role map: successive independent \(n\)-bit broadcasts \(\alpha_0\) and \(\alpha_1\) supply the source and window; a dishonest receiver is subject to the retention cap, with generic \(B=\gamma n\) and the displayed \(B=n/6\) analysis kept distinct; Alice and Bob sample selected positions, with Alice holding \(M_0,M_1\) and Bob choosing \(\delta\), as honest protocol use; and the security goal is that Bob obtains \(M_\delta\) without learning both bits while Alice does not learn \(\delta\), under the stated construction and parameters. Its honest storage and cheating bounds are construction-specific.[^ref-63b9a39dc9e7]
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.
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: an encryption member using BSM, not the model's genus.[^ref-30e8e1a80f62]
- Computational hardness or generic small-memory computing: BSM restricts adversarial retained source information within a specified cryptographic experiment, not its momentary computation.[ref-30e8e1a80f62][ref-63b9a39dc9e7]
- Automatic security: a storage cap is a hypothesis; every claimed goal needs a protocol-specific argument.[ref-30e8e1a80f62][ref-63b9a39dc9e7]
- Bare BSM as all BSM: removing an initial shared key defines a variant; the 2008 lower bound addresses bare key agreement only.[^ref-306991aa3eed]
- Quantum or noisy storage: a different storage carrier requires a separate equivalence argument.
References¶
[^ref-30e8e1a80f62]: 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.
[^ref-63b9a39dc9e7]: 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.
[^ref-306991aa3eed]: 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.