Clients may be offline at different times and face censorship, rate limits, shutdowns, or intermittent links; replicated bulletin-board servers provide temporary application-layer storage until connectivity returns.

1. assumption

   Identity knowledge and public setup

   assumed

   Senders and receivers know pseudonyms for one another and possess a client with public IBE/HIBE parameters, but they need no pairwise pre-shared key or prior synchronous exchange.

   System, network, adversary, anonymous-channel, and leakage model
2. assumption

   Anonymous client-server channels

   assumed external service

   Uploads and queries are assumed to travel through an anonymity network such as Tor; PIB³ does not itself hide the client's network address from a server observing an ordinary identified transport.

   System, network, adversary, anonymous-channel, and leakage model
3. threat model

   Network and bulletin-board adversary

   defined

   A polynomial-time adversary may observe and disrupt links, corrupt a server, control malicious uploaders, adaptively insert records, and participate in retrieval as that server, but cannot violate the stated cryptographic assumptions.

   System, network, adversary, anonymous-channel, and leakage model
4. definition

   Explicit leakage

   explicitly modeled

   Privacy exposes the public epoch, database size, and number of PIR retrievals. Padding to a fixed bound can hide retrieval count only if the application also specifies dummy retrievals and behavior when real matches exceed that bound.

   System, network, adversary, anonymous-channel, and leakage model · Main bulletin-board privacy theorem and hybrid proof sketch

HIBESC extends two-level HIBE with CipherGen, Token, and Check. Anyone can create a searchable ciphertext for identity vector (id, epoch), but only the first-level identity-key holder can form the matching epoch token.

1. security definition

   Correctness, soundness, and fixed-epoch anonymity

   defined

   Correct matching tokens and ciphertexts must accept; mismatched identity or epoch should reject; and ciphertexts for different identities in the same public epoch should be computationally indistinguishable under the specified games.

   Searchable-HIBE syntax, correctness, soundness, and fixed-epoch anonymity
2. proof

   Searchable-HIBE reduction chain

   reduction provided

   The appendices establish an intermediate ciphertext-identity-indifferentiability property and reduce fixed-epoch anonymity to decisional bilinear Diffie-Hellman, with explicit random-oracle programming and abort probability accounting.

   Searchable-HIBE reductions and fixed-epoch anonymity proof

The receiver splits a search token between two replicated, non-colluding servers. Each partially evaluates Check for every record; the receiver combines replies into a matching index set and uses two-server PIR to fetch the corresponding IBE ciphertexts.

1. attack

   Why one server is insufficient

   demonstrated analytically

   A single server sees which records share a query token and can upload a probe ciphertext for a chosen identity and epoch, then test future tokens against it. Token sharing removes that direct Check oracle from any one allowed corrupted server.

   Single-server access-profile leakage and chosen-identity attack

The manuscript claims correctness and privacy for the concrete scheme under the component assumptions and leakage model, conditional coalition privacy for the extension, and practical feasibility for the measured prototype configurations.

1. claim

   Two-server bulletin-board privacy

   theorem with reduction

   Theorem 1 bounds a bulletin-board adversary by two PIR-privacy terms, two searchable-HIBE anonymity terms, two IBE-anonymity terms, and an IBE IND-CPA term, with active probing captured up to retrieval-count leakage.

   Main bulletin-board privacy theorem and hybrid proof sketch · Full PIB privacy hybrid argument
2. claim

   Conditional coalition privacy

   conditional theorem

   Theorem 2 extends privacy to a strict server coalition only when token shares are simulatable for that coalition and the chosen N-server PIR is private against the same coalition, with retrieval count available to its simulator.

   N-server protocol and conditional coalition-privacy theorem
3. claim

   Optimized retrieval communication

   asymptotically analyzed

   Hash-compressed partial Check values and batched PIR yield four rounds and reported communication O((n + λ) log n + C + G), where n is record count, λ the security parameter, C record size, and G group-element size.

   Collision analysis, optimized communication, and round count

Support includes formal syntax and games, reductions for component and composed privacy, an explicit attack on the tempting one-server design, asymptotic analysis, and a prototype benchmark of the heavy server-side search and PIR operations.

1. evidence

   Prototype benchmark setup

   reported experiment

   The 128-bit-security prototype ran on an AWS c6a.8xlarge instance with 32 vCPUs. Most configurations were repeated ten times; the largest final PIR row was repeated twice, and reported variance was negligible but omitted.

   Prototype setup, search and PIR measurements, latency, and omitted client benchmark
2. evidence

   Linear full-database search

   reported measurement

   Server-side pairing search scaled from roughly 0.47-0.48 seconds at 1,000 ciphertexts to about 45 seconds at 100,000 ciphertexts on the test machine.

   Prototype setup, search and PIR measurements, latency, and omitted client benchmark
3. evidence

   PIR and end-to-end server computation

   reported measurement

   For 100-kilobit payloads and 100,000 records, reported DPF evaluation is 35.597 seconds and total server computation is just over 80 seconds; smaller records or databases take seconds or fractions of seconds.

   Prototype setup, search and PIR measurements, latency, and omitted client benchmark

Privacy is conditional on cryptographic assumptions, anonymous transport, synchronized replicated databases, the allowed non-colluding coalition, and explicit leakage. The prototype is not a deployed censorship-resistance study or independent reproduction.

1. limitation

   Non-collusion and PIR boundary

   theorem boundary

   Two-server privacy excludes both servers colluding. The N-server claim covers only coalitions for which both token-share simulation and the underlying PIR privacy property hold.

   Main bulletin-board privacy theorem and hybrid proof sketch · N-server protocol and conditional coalition-privacy theorem
2. limitation

   Epoch, size, and access-count leakage

   explicit leakage

   The scheme does not hide public epoch, database size, or unpadded retrieval count. Padding shifts rather than eliminates costs and requires an overflow rule when a user has more than the fixed number of matches.

   System, network, adversary, anonymous-channel, and leakage model · Main bulletin-board privacy theorem and hybrid proof sketch
3. limitation

   Partial prototype evaluation

   experimental boundary

   The benchmark covers computationally heavy server components, not the complete client path, WAN anonymity-network delay, censorship behavior, database synchronization, availability attacks, or a real multi-user deployment.

   Prototype setup, search and PIR measurements, latency, and omitted client benchmark