Paper deep dive
Onyx: Cost-Efficient Disk-Oblivious ANN Search
Deevashwer Rathee, Jean-Luc Watson, Zirui Neil Zhao, G. Edward Suh, Raluca Ada Popa
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 99%
Last extracted: 4/26/2026, 5:45:42 PM
Summary
Onyx is a cost-efficient, disk-oblivious Approximate Nearest Neighbor (ANN) search system designed for Trusted Execution Environments (TEEs). It addresses the high latency and cost of traditional ORAM-based ANN search by inverting the standard design: instead of minimizing access count at the ANN level and bandwidth at the ORAM level, Onyx minimizes bandwidth in the ANN layer (via Onyx-ANNS) and access count in the ORAM layer (via Onyx-ORAM). Onyx-ANNS uses a compact intermediate representation to prune bandwidth-intensive accesses, while Onyx-ORAM utilizes a locality-aware shallow tree design. The system achieves significantly better performance and cost-efficiency compared to state-of-the-art solutions like Compass-in-TEE.
Entities (7)
Relation Signals (4)
Onyx-ORAM → buildson → RingORAM
confidence 100% · Onyx-ORAM builds on RingORAM [88]
Onyx → contains → Onyx-ANNS
confidence 100% · Onyx, with two new co-designed components: Onyx-ANNS... and Onyx-ORAM
Onyx → contains → Onyx-ORAM
confidence 100% · Onyx, with two new co-designed components: Onyx-ANNS... and Onyx-ORAM
Onyx → improvesperformanceof → Compass
confidence 90% · Compared to the state-of-the-art oblivious ANN search system, Onyx achieves 1.7–9.9× lower cost and 2.3–12.3× lower latency.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Approximate nearest neighbor (ANN) search in AI systems increasingly handles sensitive data on third-party infrastructure. Trusted execution environments (TEEs) offer protection, but cost-efficient deployments must rely on external SSDs, which leaks user queries through disk access patterns to the host. Oblivious RAM (ORAM) can hide these access patterns but at a high cost; when paired with existing disk-based ANN search techniques, it makes poor use of SSD resources, yielding high latency and poor cost-efficiency. The core challenge for efficient oblivious ANN search over SSDs is balancing both bandwidth and access count. The state-of-the-art ORAM-ANN design minimizes access count at the ANN level and bandwidth at the ORAM level, each trading-off the other, leaving the combined system with both resources overutilized. We propose inverting this design, minimizing bandwidth consumption in the ANN layer and access count in the ORAM layer, since each component is better suited for its new role: ANN's inherent approximation allows for more bandwidth efficiency, while ORAM has no fundamental lower bounds on access count (as opposed to bandwidth). To this end, we propose a cost-efficient approach, Onyx, with two new co-designed components: Onyx-ANNS introduces a compact intermediate representation that proactively prunes the majority of bandwidth-intensive accesses without hurting recall, and Onyx-ORAM proposes a locality-aware shallow tree design that reduces access count while remaining compatible with bandwidth-efficient ORAM techniques. Compared to the state-of-the-art oblivious ANN search system, Onyx achieves $1.7-9.9\times$ lower cost and $2.3-12.3\times$ lower latency.
Tags
Links
- Source: https://arxiv.org/abs/2604.20401v1
- Canonical: https://arxiv.org/abs/2604.20401v1
Trouble viewing inline? Open PDF directly →
Full Text
114,744 characters extracted from source content.
Expand or collapse full text
Onyx: Cost-Efficient Disk-Oblivious ANN Search Deevashwer Rathee ∗ UC Berkeley, NVIDIA Jean-Luc Watson NVIDIA Zirui Neil Zhao UT Austin, NVIDIA G. Edward Suh NVIDIA Raluca Ada Popa UC Berkeley Abstract Approximate nearest neighbor (ANN) search in AI systems increasingly handles sensitive data on third-party infrastruc- ture. Trusted execution environments (TEEs) offer protec- tion, but cost-efficient deployments must rely on external SSDs, which leaks user queries through disk access patterns to the host. Oblivious RAM (ORAM) can hide these access patterns but at a high cost; when paired with existing disk- based ANN search techniques, it makes poor use of SSD resources, yielding high latency and poor cost-efficiency. The core challenge for efficient oblivious ANN search over SSDs is balancing both bandwidth and access count. The state-of-the-art ORAM-ANN design minimizes access count at the ANN level and bandwidth at the ORAM level, each trading-off the other, leaving the combined system with both resources overutilized. We propose inverting this de- sign, minimizing bandwidth consumption in the ANN layer and access count in the ORAM layer, since each component is better suited for its new role: ANN’s inherent approxi- mation allows for more bandwidth efficiency, while ORAM has no fundamental lower bounds on access count (as op- posed to bandwidth). To this end, we propose a cost-efficient approach, Onyx, with two new co-designed components: Onyx-ANNS introduces a compact intermediate represen- tation that proactively prunes the majority of bandwidth- intensive accesses without hurting recall, and Onyx-ORAM proposes a locality-aware shallow tree design that reduces access count while remaining compatible with bandwidth- efficient ORAM techniques. Compared to the state-of-the-art oblivious ANN search system, Onyx achieves 1.7–9.9×lower cost and 2.3–12.3× lower latency. 1 Introduction Approximate nearest neighbor (ANN) search powers many AI systems, including retrieval-augmented generation (RAG) [44,61], search [52,79], and recommendation [92,123]. As these systems increasingly run on third-party infrastructure and operate over sensitive data, privacy has become a critical requirement. For example, systems such as ChatGPT serve hundreds of millions of users and perform RAG queries over their highly sensitive chat messages [90]. A natural first step to protect the search index and query contents is to encrypt them. However, it is well-known from over a decade of leakage-abuse attacks [11,13,41,47,50, ∗ This work was done during an internship at NVIDIA. 78,81,127] that encryption alone is not enough: a service provider observing the sequence of accesses during query processing can infer information about the query and the dataset, and sometimes, recover the dataset entirely [56]. Cryptographic approaches such as oblivious RAM (ORAM) [35] hide this leakage, but remain too expensive for ANN search. Given a 10M-vector index at 90% recall, the state-of-the-art solution Compass [131] serves 100 queries/$ and incurs over 1 s of latency, far from the under-20 ms latencies expected in production deployments [110]. To avoid the high overhead of purely cryptographic ap- proaches, a practical alternative is to rely on hardware as- sumptions and run ANN search inside a trusted execution environment (TEE) [18,51], where the index is stored in the protected TEE memory. However, keeping the entire index in enclave memory quickly becomes expensive at scale (§ 2.1). In practice, cost-efficient ANN systems store the index on SSDs [16,99,105,106,111,114], but this storage typically lies outside the TEE trust boundary, introducing access pattern leakage through disk I/O (§ 3.1). ORAM-in-TEE for disk-oblivious accesses. In princi- ple, the solution is simple: run Compass [131], the state-of- the-art ORAM-ANN system, inside a TEE to hide disk access patterns. However, this approach is unsuitable for the disk setting as it places heavy demands on SSD I/O, ultimately requiring more compute and SSD resources and driving up cost. For instance, sustaining≈50 QPS on a 20M 3 KB vector index at 90% recall requires at least 4 vCPUs and 8 SSD units, and still incurs≈ 160 ms latency (§ 6.3). To address this, we propose Onyx, a fundamentally differ- ent ANN-ORAM co-design for the disk setting that signifi- cantly reduces this overhead through efficient utilization of SSD resources (see Figure 1 for an overview). Onyx achieves up to 10×better cost-efficiency than the Compass-in-TEE approach; with a single vCPU and a single SSD unit on the same index, it sustains≈ 70 QPS at 12 ms latency. Inverting the ORAM-ANN co-design. The core chal- lenge for efficient oblivious ANN search over SSDs is balanc- ing SSD bandwidth and SSD access count, since both directly determine performance and resource cost. Prior ORAM-ANN co-design [131], optimizing for oblivious search over a net- work, combines an access-count-efficient ANN (reducing net- work round-trips) with a bandwidth-efficient ORAM (reduc- ing communication bandwidth), but each primitive aggres- sively trades off the other resource. The ANN layer fetches larger blocks to reduce accesses, wasting bandwidth due to 1 arXiv:2604.20401v1 [cs.CR] 22 Apr 2026 Oblivious ANN Search: Compass [OSDI’25] Compass-in-TEE Onyx: cost-efficient ANNS and ORAM co-design ORAM Storage Client Query ANN Search ORAM Network Untrusted Server TEE 160 ms latency, high CPU and SSD requirement Client Query ANN Search ORAM Network Untrusted Server ORAM Storage >1 s latency, 100 queries/$ ORAM Storage Client Onyx-ANNS Onyx-ORAM Untrusted Server SSD ~12 ms latency, ~70 QPS, low resource requirements CPUCPUCPU CPU CPU SSD SSD Query Network TEE Figure 1. Prior designs for oblivious ANNS and Onyx. Com- pass [131] suffers from poor performance due to high net- work overhead, and mirroring its design into a TEE yields a system that needs significant CPU and SSD resources to sustain reasonable performance. Onyx proposes co-designed primitives for ANNS and ORAM that jointly improve re- source utilization, yielding high performance and low cost. the inherently low spatial locality of ANN search [77,114], while the ORAM layer makes many fine-grained accesses to reduce data movement but is ultimately limited by funda- mental lower bounds to ORAM bandwidth [55, 57]. In this work, we invert this design, arguing that both ORAM and ANN are better-suited for their new role. ANN search is naturally approximate, so it can maintain high recall with smaller, lower-precision representations, supporting aggressive bandwidth reduction. ORAM has no fundamental lower bounds on access count, allowing it to significantly reduce the number of I/O operations required per access. New primitives for our co-design. Existing primitives fall short of realizing the optimization objectives of our de- sign. ANN search algorithms for disk-hosted indices are designed assuming bandwidth is plentiful, which is true for plain SSDs but not for ORAM over SSDs. On the ORAM side, access-efficient designs such as EnigMap [108] introduce high bandwidth amplification, negating the ANN-side sav- ings. To address both, we propose two new co-designed prim- itives. Onyx-ANNS (§ 5) retains the low memory footprint and accesses required for disk-hosted indices, while introduc- ing a compact intermediate representation that proactively prunes the majority of bandwidth-intensive full-precision accesses without hurting recall. This reduces ANN band- width by up to 5×while increasing access count by at most 15% compared to the state-of-the-art [105] disk-based ANN search (§ 5.2). Onyx-ORAM (§ 4) proposes a locality-aware shallow tree design that significantly reduces access count while remaining compatible with bandwidth-efficient ORAM techniques. Compared to EnigMap-style access-optimized PathORAM [108], our design achieves 2×lower access count and 4.6×lower bandwidth simultaneously (§ 4.2) Together, the two primitives achieve a much better balance of SSD bandwidth and access count than any prior combination. Evaluation summary. We implement and evaluate Onyx in § 6. Overall, Onyx is consistently the most cost-efficient and lowest-latency approach for TEE-based oblivious ANN search at scale. Compared to Compass-in-TEE, it achieves 1.7–9.9×lower cost and 2.3–12.3×lower latency across all datasets (§ 6.3). We also evaluate Onyx against other com- binations of state-of-the-art ORAM and ANN techniques. Compared to the best of these baselines, Onyx achieves 2.6– 4.2×lower cost and 2.5–4.5×lower latency. Given a resource partition with just 1 vCPU, 4 GB RAM, and 187.5 GB SSD, Onyx can host a 64 GB index and sustain 70 QPS at 12 ms la- tency with 90% top-10 recall, serving over 8M queries/dollar. 2 Background We provide background on our setting below. Details on the specific ORAM and ANN primitives we build on are deferred to the sections where we discuss our designs (§ 4 and § 5). 2.1 Motivation: Private Disk-hosted ANN Search We discuss two deployment scenarios where cost and scala- bility necessitate private disk-hosted ANN indices. Scenario I: Enterprise Knowledge Bases. This scenario targets enterprise applications (e.g., RAG for internal seman- tic search) hosted on third-party clouds [84,110,113,117]. To protect proprietary data while leveraging cloud scalability, organizations use Confidential VMs [39,72]. The primary motivation for disk-based indexing is cost-efficiency. Applica- tions that do not require very high throughput (e.g. 100 QPS) often cannot justify the expense of keeping the entire index in memory. For example, a single 20M-vector partition with 3 KB vectors [20] requires 64 GB DRAM to host in memory, but only≈ 2 GB memory with a disk-hosted index (§ 6.1). Scenario I: Personalized Data Stores. This scenario targets multi-tenant services where each user maintains a private, isolated index. A key use case is private memory for the next generation of personalized AI agents (e.g., Mi- crosoft Recall [73], Gemini Personal Intelligence [38]), where highly sensitive personal information such as browsing his- tory, messages, and documents is consolidated into per-user indices. The combination of privacy, low latency, and scala- bility makes disk-hosted indices inside a TEE a natural fit. 2 Existing privacy-preserving solutions such as Compass [131] rely on client-side processing, incurring high-latency net- work round trips. To achieve the interactive latencies re- quired by real-time agents, confidential computing within clouds offers a natural solution. In this architecture, keep- ing the full indices of millions of users constantly in cloud DRAM is economically infeasible. A disk-hosted index only needs a small in-memory cache per user to serve low-latency requests: for example, a 1M-vector index [49] requires only 8 MB of in-memory hints instead of the 640 MB index (§ 6.1). 2.2 Disk Access Pattern Leakage We focus on the direct leakage from disk I/O during ANN search on disk-hosted indices. The SSD typically lies outside the TEE trust boundary, and the host software stack can directly observe the sequence of disk accesses issued during query execution. Even if the index and query contents are encrypted, the access pattern alone can reveal both. Over a decade of research on leakage-abuse attacks [11, 13,24,41,47,50,56,78,81,127] has shown that such access patterns enable highly effective query recovery, and from that, reconstruction of the dataset itself. Even in a passive setting, where the attacker only observes access patterns, the Refined Score attack [24] recovers≈85% of queries starting from just≈10 known queries, and optimization-based attacks such as IHOP [81] and Jigsaw [78] achieve near-perfect re- covery using only an auxiliary dataset (e.g., a public corpus approximating the target data). Active attacks amplify the threat: because indices ingest data from many sources (e.g., emails, shared documents), an adversary can inject carefully crafted entries that encode identifiers into the access pattern so that each future query produces a uniquely decodable response. File-injection attacks [11,127] show that tracking 푛 identifiers requires only 푂(log푛) injected entries. While majority of these attacks were developed for key- word search, recent work FiT [50] focuses on access pattern leakage during semantic search, showing that page-level ac- cesses (exactly the granularity leaked in our setting) suffice to infer the specific vectors fetched within each page for graph-based ANN indices like HNSW. Since ANN search is typically followed by a retrieval of the corresponding data for the퐾nearest vectors, the adversary can learn both the query’s neighborhood in embedding space and the returned documents. Encrypting the index is insufficient; a secure disk-based ANN search must make query-oblivious accesses to the untrusted storage, which is the goal of our work. 3 System Overview Onyx is a privacy-preserving semantic search system that allows querying a database while keeping the queries and the dataset private. To protect privacy, it executes within a trusted execution environment (TEE), keeping the core logic and data in TEE-protected memory, and for cost ef- ficiency (§ 2.1), it stores the index outside the TEE trust boundary on untrusted external storage (e.g., NVMe SSDs). Design overview. Onyx consists of two co-designed com- ponents running inside the TEE trust boundary: a bandwidth- efficient ANN search engine (Onyx-ANNS) and an access- count-efficient ORAM client (Onyx-ORAM). Onyx-ANNS introduces compact pruning hints and a three-step granular refinement strategy (§ 5.2) that ensures the majority of ex- ternal storage accesses fetch only small blocks (adjacency lists and pruning hints, 256–512 bytes each), with only a few accesses fetching the larger full-precision embedding vectors. These accesses are mediated through two separate Onyx-ORAM instances: one for the small traversal blocks and one for the larger refinement blocks. Onyx-ORAM uses a locality-aware shallow tree design (§ 4.2) that balances both access count and bandwidth to achieve high throughput at the traversal block sizes. The two components reinforce each other: since ORAM performance is sensitive to block size, Onyx-ANNS’s smaller blocks directly reduce the Onyx- ORAM’s per-access overhead, and Onyx-ORAM achieves its greatest throughput advantage precisely at the 256–512 byte block sizes that dominate Onyx-ANNS accesses (Figure 2). Operations. Within the broader semantic search pipeline, which consists of both an embedding model to map data items to vectors and a vector database to do a similarity search over them, Onyx specifically focuses on the vector database component. It supports the following operations over the embedding vectors: • Setup(I): Given an ANN indexI, initialize both ORAMs over the index and load in-memory index state. • R ← Search(푥 푞 ,푘): Given the query embedding vector 푥 푞 , returns the keysR of the 푘 nearest neighbors. • Insert(푝,푥 푝 ): Add vector 푥 푝 to index with key 푝. • Delete(푝): Remove the entry corresponding to key 푝. To avoid expensive per-block initialization, one can use prior work on bulk-loading the initial ORAM contents such as BULKOR [63] and EnigMap [108]. In the rest of the paper, we primarily focus on search performance. At the same time, the same design choices we make to improve search can also improve insertion and deletion performance (Appendix C). Data layout. Onyx splits state across TEE-protected mem- ory and two on-disk ORAM-protected layouts. •Inside TEE (protected memory). (i) ANN metadata and the start node for graph traversal, (i) following prior work [105,131], highly compressed in-memory traversal hintsH trv for approximate distance computation during search, and (i) ORAM client state for both ORAM in- stances (e.g., position maps, stashes, keys). •Outside TEE (external storage, untrusted). The full index is stored within two separate ORAM instances: (i) a 3 traversal ORAM holding per-node blocks consisting of ad- jacency listsNconcatenated with compact pruning hints H prn , and (i) a refinement ORAM holding full-precision embedding vectorsF . Paper organization. We present Onyx-ORAM in § 4 and Onyx-ANNS in § 5, starting with ORAM because ANNS builds on top of it. Both sections present: background on their base primitive (§ 4.1, § 5.1), design overview (§ 4.2, § 5.2), construction (§ 4.3, § 5.3), and I/O analysis (§ 4.4, § 5.4). We evaluate Onyx in § 6 and discuss related work in § 7. 3.1 Threat Model Trusted computing base. Following a common TEE threat model [18,51], we assume that the CPU package is trusted and functions correctly. The application code running in- side the TEE is also assumed to be correctly implemented and free of software vulnerabilities. All data residing within the TEE’s private memory is protected by hardware-level encryption and isolation; DRAM access patterns are out of scope (see scope and exclusions below). Adversary capabilities. Like prior TEE systems [4,9,21, 45,80,86,87,93,96,100,104,129], we assume that the ad- versary does not compromise the TEE but can observe and manipulate its interactions with untrusted interfaces like storage. Our security guarantees hold even if the adversary knows the stored vector index and the distribution of user queries. Since the TEE communicates with an untrusted disk via shared memory (e.g., bounce buffers [64]) visible to the hypervisor, the adversary can directly observe the disk access pattern generated during query execution. It can also manip- ulate the responses returned from disk unless prevented by integrity checks. Its goal is to infer information about the query/dataset from the observed disk access pattern. We focus on disk access patterns because disk-based stor- age is essential for cost efficiency and scalability (§ 2.1), and even a perfect TEE cannot prevent this leakage: an untrusted disk inherently lies outside the trust boundary, and a cloud provider can trivially inspect the I/O trace. As discussed in § 2.2, the observed access pattern can reveal the exact top-퐾 results for a given query, making disk access obliviousness a first-order privacy requirement for deploying cost-efficient ANN search on third-party cloud providers. Scope and exclusions. A compromised TEE is out of scope for our work. This includes cache-based side chan- nels [75,122], branch prediction attacks [32,59], controlled- channel attacks via page faults and interrupts [12,118,121], transient execution attacks [54,65], software-based fault injection [53,76,125], timing and performance counter leak- age [33,60], physical attacks [19,27,58,70,95], remote- attestation attacks [19,27,95], and denial-of-service attacks. These are the subject of an orthogonal line of work on im- proving enclave implementations and mitigations. For exam- ple, controlled-channel attacks can be mitigated by hardware- assisted interrupt protection [21,104,112], and cache-based leakage by partitioning and core isolation [80,109]. Unlike these enclave implementation issues, disk access patterns arise outside the enclave and cannot be mitigated by im- proved design—we therefore focus exclusively on disk ac- cess pattern leakage. We also assume that an orthogonal rollback protection mechanism (e.g., monotonic counters or distributed freshness protocols [3,68,103]) prevents the ad- versary from replaying stale state from the persistent storage. The query type is public and not hidden by our system. 3.2 Formalizing Security We formalize the privacy guarantees of Onyx through an indistinguishability-based security game. We give a high- level description here and defer the full specification to Fig- ure 11 (Appendix F). LetANNSdenote a disk-resident ANN search system that executes within a TEE and accesses an untrusted storage interface through ORAM, with public pa- rametersparam. At a high level, the challengerCexecutes the protocol and maintains the private state of the system, which remains hidden from the adversary since TEE side channels are out of scope, while the adversaryAplays the role of the malicious host and untrusted storage. Whenever the protocol issues an external storage access, the request is sent toA, which observes the access trace and can return an arbitrary response. The adversary adaptively chooses two equal-size indices and a sequence of paired operations (constrained to have matching types), and wins if it can dis- tinguish which of the two worlds the challenger is executing. If the challenger aborts at any point, the adversary loses. Definition 1. We say that a disk-resident ANN search sys- temANNSprovides disk-access privacy if no non-uniform probabilistic polynomial-time adversaryAcan win the se- curity game in Figure 11 (Appendix F) with probability non- negligibly higher than random guessing. Theorem 2. Onyx is disk-access private when instantiated with a secure authenticated encryption scheme [10]. Proof sketch.The ORAM and ANN search parameters are configured statically and are public. The ANN operation type is public, and the number and granularity of (logical) disk accesses made by each ANN operation depends only on these public parameters (§ 5.3). Each (logical) disk access is medi- ated through ORAM, which guarantees data-oblivious ac- cesses with confidentiality and integrity given authenticated encryption [10]. Onyx-ORAM builds on RingORAM [88], and the changes we introduce (§ 4.3) preserve all the pro- tocol invariants and the security guarantees. Thus, either the adversary deviates from the protocol and the challenger aborts, or the two traces seen by the adversary are indistin- guishable. We provide the full proof in Appendix F.□ 4 4 Onyx-ORAM 4.1 Background: RingORAM Onyx-ORAM builds on RingORAM [88], a tree-based ORAM that hides access patterns to untrusted storage. We use the non-recursive variant (the TEE holds the position map) with- out the XOR trick (the SSD has no compute capability). For푁blocks, RingORAM organizes storage as a binary tree over buckets with depth퐿=Θ(log푁). Each block is mapped by a position mapPosMapto a random leaf and re- sides either on that root-to-leaf path or in a client-local stash. Every퐴accesses, a background eviction process flushes stash blocks along a deterministic path that cycles through the tree, while ensuring each block remains on its assigned path. Each bucket holds at most푍real blocks, and is padded to 푍+푆blocks with dummies. A bucket can be accessed at most 푆times before it must be fetched, reshuffled, and rewritten (early reshuffle);푆is configured so that eviction reshuffles the bucket with high probability before this limit is reached. Access. To read a block, the client first checks the stash, then fetches a root-to-leaf path (the block’s assigned path, or a random path if the block was in the stash). For each bucket on the path, it reads a small metadata header to determine which block to read (the real block if present, otherwise an unread dummy). The accessed block is then added to the stash, remapped to a fresh random path, and returned. Eviction. Every퐴accesses, eviction reads푍random blocks per bucket on the eviction path (since buckets have at most푍real blocks), assigns stash blocks to eviction buckets, adds dummies, shuffles and encrypts the buckets, and then writes back the full 푍 + 푆 buckets to the tree. I/O multipliers. The dominant cost for ORAM over SSD is SSD I/O, which comes from two sources: the access count multiplier (I/O requests per logical access) and the bandwidth multiplier (bytes transferred per logical access). Ignoring the rare early reshuffles, RingORAM’s I/O multipliers are: AccessCount≈ 2+ 푍+1 퐴 ·퐿 andBandwidth≈ 1+ 2푍+푆 퐴 ·퐿 . The leading 2 in the access count comes from the per-level metadata fetch. The(푍 +1)/퐴term reflects eviction access count amortized over 퐴 accesses. 4.2 Design Overview Goal: access-efficient ORAM. Recall that our co-design requires an access-count-efficient ORAM. This, however, should not sacrifice bandwidth efficiency. For the block sizes typical of our bandwidth-efficient ANN search (256–512 Bytes), both multipliers contribute significantly (§ 4.4), and our ORAM must balance both. Tension between access count and bandwidth. To hide access patterns over푁blocks, state-of-the-art tree-based ORAMs [88,102] make random accesses to푂(log푁)tree levels per logical access. This is the core bottleneck for access count, since the remaining ORAM operations (e.g., evictions) can be made deterministic and sequential (§ 4.3, step 2). To Access countBandwidth RingORAM≈ 5 2 · log(푁)≈ 3· log(푁) PathORAM(ℓ= 2)≈ log(푁)≈ 12· log(푁) PathORAM(ℓ= 3) ≈ 2 3 · log(푁) ≈ 18.5· log(푁) Onyx-ORAM≈ 1 3 · log(푁)≈ 4· log(푁) Table 1. I/O multipliers for Onyx-ORAM vs prior work. PathORAMℓ: levels packed per page. RingORAM bandwidth shown is the best case, achieved in the large-bucket limit. reduce this, EnigMap [108] proposed packingℓtree levels into a single SSD page for PathORAM [102], thereby reducing tree depth and access count byℓ×. This, however, leads to high bandwidth: packing increases bandwidth by 2 ℓ −1 ℓ ×, and the design is incompatible with the large buckets used by bandwidth-efficient ORAMs like RingORAM. Our approach: locality-aware shallow trees. In Onyx- ORAM, we propose reducing tree depth directly by using a 푑-ary tree, which cuts depth and access count byℓ= log 2 푑× while remaining compatible with large buckets. 푑 -ary trees were introduced over a decade ago [34] but fell out of use: al- though they reduce tree depth, they increase the frequency of bandwidth-heavy evictions by(푑−1)×, growing bandwidth by roughly푑/log푑×and incurring a similar kind of trade-off as EnigMap’s level packing. For oblivious accesses to SSDs, however, we observe that this design point becomes attractive for large-bucket ORAMs like RingORAM. RingORAM uses large buckets with many dummy slots to allow fetching individual blocks rather than entire buckets, saving significant bandwidth. The key obser- vation is that in a푑-ary tree, although evictions are(푑−1)× more frequent, the number of dummy slots per bucket de- creases proportionally (since fewer accesses occur between evictions), and the two effects balance each other out. This is especially prominent with our locality-aware optimizations, which require fetching even more dummies to keep the evic- tions sequential. For푑=8, this effect is so prominent that the푑-ary tree ends up not increasing eviction bandwidth at all while reducing access count by 3×(§ 4.3, step 3). Addi- tionally, the푑-ary tree with fewer dummies reduces storage amplification by 4×, further improving cost-efficiency. Ta- ble 1 summarizes the I/O multipliers of Onyx-ORAM vs prior work: Onyx-ORAM improves PathORAM(ℓ=3)ac- cess count by 2× while reducing its bandwidth by 4.6×. 4.3 Construction Recall the access count multiplier for RingORAM from § 4.1 isAccessCount≈ 2+ 푍+1 퐴 ·퐿 , where푍is the bucket capac- ity,퐴is the eviction frequency, and퐿= log 2 푁is the tree depth. We reduce this multiplier to≈ 퐿/3 in Onyx-ORAM, and we do so in two stages. First, we apply locality-aware optimizations that eliminate the multiplicative factor before 5 퐿, reducing the per-level cost from 2+(푍 +1)/퐴down to 1, i.e., a single block read per level. Second, we reduce the tree depth itself from퐿= log 2 푁to≈ 퐿/3 by switching to a wider, shallower tree. Crucially, the depth reduction is only effec- tive once the locality-aware optimizations are in place and it is particular well-suited for bandwidth-efficient ORAMs with large buckets. We describe these changes as a sequence of steps, each stacking on the previous one, and then discuss how the three steps reinforce each other to yield a much better trade-off than any one in isolation. Algorithm 2 in Appendix D gives the full protocol. Step 1: Store bucket metadata locally and increase bucket size. In RingORAM, each access fetches small per- bucket metadata at every level of the path to determine which block within the bucket to read (§ 4.1). This adds one I/O per level, accounting for the leading 2 (instead of 1) in the access count expression, and also limits bucket size to small values (e.g.,푍=32, 128) for smaller blocks because metadata storage grows with푍. Onyx-ORAM stores this metadata locally to avoid a per-level metadata fetch. This requires at least 10 bytes of memory per block, which can more than double the ORAM memory footprint (Appendix A.2); as we will see, our later design choices substantially minimize this overhead. With the metadata cost removed, we are free to use much larger buckets, which in turn allows a proportion- ally larger eviction period퐴. The larger퐴better amortizes eviction cost, and together these changes reduce the access count multiplier to AccessCount≈ (1+(푍 + 1)/퐴)· 퐿. Step 2: Fetch entire buckets during evictions. RingO- RAM’s eviction reads only푍blocks from each bucket on the eviction path (as opposed to푍+푆), as there could be at most 푍real blocks in a bucket. Since푆is typically≈2푍, this saves significant bandwidth, but it means the eviction must issue 푍separate reads per bucket, which increases access count. Onyx-ORAM instead reads each bucket in full (푍 + 푆slots) as a single sequential I/O. This trades additional bandwidth for far fewer accesses, reducing the access count multiplier toAccessCount ≈ (1+2/퐴) · 퐿 ≈1· 퐿since퐴can be set large enough to make the eviction term negligible. Step 3: Use a shallower tree. Onyx-ORAM replaces the binary tree with a푑-ary tree (푑>2), reducing depth fromlog 2 푁tolog 푑 푁and the access count by a factor of log 2 푑. The trade-off is more frequent evictions: we general- ize RingORAM to푑-ary trees and found that evictions must be(푑−1)×more frequent to keep the stash bounded (§ 4.4). Since the tree haslog 2 푑fewer levels, one would naïvely expect eviction bandwidth to increase by(푑−1)/log 2 푑, or about 2.3×for푑=8. For RingORAM’s large buckets, how- ever, reducing퐴has the benefit of proportionally reducing 푆and the dummy padding, which added significant band- width pressure. This offsets the higher eviction frequency, reducing the net bandwidth increase to roughly 푑+1 3 log 2 푑 × , Figure 2. I/O overhead design space for ORAM schemes at퐵=512 Bytes. Gray iso-throughput contours show the maximum I/O multipliers that our evaluation SSD (§ 6.1) can theoretically sustain at a given throughput. Arrows trace Onyx-ORAM’s step-by-step improvements from RingORAM, annotated with the factor change in each multiplier. which for푑=8 is≈1. As a result, this step yields a 3×ac- cess count reduction with essentially no bandwidth penalty: AccessCount≈ 퐿 3 . The three steps above are not independent; they reinforce each other and together yield a much better trade-off than any one in isolation: Step 1 enables Step 3. A푑-ary tree requires large푍to properly amortize the more frequent evictions; for instance, with푑=8, the ratio푍/퐴is 6.4 for푍=32 but drops to 4.13 for푍=256. Large buckets are efficient because Step 1 eliminates the per-access metadata overhead that previously scaled with 푍 . Step 2 enables Step 3. Without full-bucket reads, evic- tions would still issue푍individual reads per bucket, and the 푍/퐴access count term (which increased 푑−1 log푑 × ) would make the access count worse not better. Step 3 benefits Step 1. The reduced padding and fewer buckets in a푑-ary tree shrink the otherwise high per-block metadata memory footprint: the overhead of storing bucket metadata locally drops from 10 bytes/block (푑=2) to just 2.5 bytes/block (푑=8). For the same reasons, ORAM storage amplification is also reduced by 4× (Appendix A.2). Step 3 benefits Step 2. Step 2 increased eviction band- width from(2푍+푆)/퐴to(2푍+2푆)/퐴per level, making band- width more sensitive to the dummy padding푆. In a푑-ary tree, 푆shrinks proportionally with퐴, which reduces this pres- sure and actually ends up decreasing eviction bandwidth by ≈ 1.1× when we go from 푑= 2 to 푑= 8. 6 4.4 Analysis Performance analysis. Figure 2 shows the maximum analytical throughput each ORAM design can sustain on our evaluation SSD with 512-byte blocks, computed from the I/O multipliers and the SSD’s bandwidth and IOPS ceilings (see § 6.2 for throughput results with actual implementa- tion). RingORAM and PathORAM are each limited by one of the two multipliers (RingORAM by access count, PathO- RAM by bandwidth) and both lie beyond the 6K QPS zone. Onyx-ORAM (푑=8) reduces both multipliers simultane- ously, reaching the 15K QPS zone. This plot also shows that maintaining bandwidth is important:푑=16 achieves a lower access count than푑=8 but at higher bandwidth, and lands in the 12–15K QPS zone. This highlights the importance of balancing both multipliers, and푑=8 strikes a favorable trade-off for our setting. Eviction analysis. Onyx-ORAM generalizes RingORAM’s binary tree to a푑-ary tree while preserving the reverse- lexicographic eviction order and all other protocol invari- ants. We state the main result here and defer the full proof, which closely follows the structure of RingORAM’s stash analysis [88], to Appendix E. Theorem 3 (Stash overflow in푑-ary RingORAM). Con- sider a푑-ary Onyx-ORAM with푁blocks, bucket capacity 푍, eviction period퐴, and tree depth퐿= ⌈log 푑 2푁 퐴(푑−1) ⌉. Let 푎= 퐴(푑−1)/2. If푞= 푍 ln(푍/푎)+푎− 푍 −1− ln푑>0, then Pr[stash> 푅] ≤ (푎/푍) 푅 1−푒 −푞 . Setting푑=2 recovers the original RingORAM result [88]. The key consequence is that the maximum eviction period scales as퐴 ≤2푍/(푑−1), compared to퐴 ≤2푍for binary RingORAM: evictions must be(푑−1)× more frequent. 5 Onyx-ANNS 5.1 Background: DiskANN Onyx-ANNS builds on DiskANN [105], a graph-based algo- rithm that is the state-of-the-art for disk-based ANN search, and is widely deployed in industry [42, 84, 110, 113, 117]. Index layout. The dataset is organized as a proximity graph on external storage. For each vector푝with embedding 푥 푝 , the index stores its neighbor listN(푝)and full-precision coordinatesF(푝)packed together in a contiguous block on disk, so that both can be fetched efficiently with one I/O. Per-vector quantized hintsH trv (푝)[48] are stored in memory to approximate distances during traversal, which would otherwise require fetching full-precision vectors for each visited node. Greedy search. A greedy beam search navigates the graph to find the top-퐾vectors closest to a query푥 푞 . Beam width푊controls how many unvisited candidates are ex- plored concurrently: for each candidate푝, the system fetches the combined blockN(푝)∥F(푝)from disk, scores newly dis- covered neighbors using the in-memory hintsH trv , and adds SIFT MARCO DEEP WIKI Bandwidth (reduction) Decoupling1.1×1.0×1.3×2.2× Onyx-ANNS 2.7×5.0×2.0×3.8× Access Count (increase) Decoupling +91% +99% +72% +43% Onyx-ANNS +8% +5% +9% +15% Table 2. Bandwidth reduction and access count increase of naive decoupling and Onyx-ANNS over DiskANN at top-10 90% recall on our evaluation datasets (§ 6). them to the beam. SinceFis prefetched alongsideN, the sys- tem maintains an exact top-퐾ranking throughout the search using the full-precision coordinates. The search continues until퐿nodes have been fetched; increasing퐿improves recall at the cost of more disk accesses. 5.2 Design Overview Goal: bandwidth-efficient ANN search. Recall that our co-design requires a bandwidth-efficient disk-based ANN search. Existing designs [16,105,114] target plain SSDs, where random reads up to 4 KB cost nearly the same. ANN accesses are typically smaller, making access count the core bottleneck and fetching extra bytes effectively free. With ORAM, however, bandwidth is amplified by푂(log푁)×(Ta- ble 1), and every byte the ANN layer transfers directly affects performance, calling for a new disk-based ANN design that minimizes bandwidth. Decoupling traversal and refinement. We start by un- doing an access-efficiency optimization that disk-based ANN designs make: fusing traversal and refinement operations. To achieve high recall, graph traversal must touch many nodes, and this coupling would force our ANN search to fetch large, full precision vectors (384–3072 bytes), consuming excessive bandwidth. With decoupling, we can follow the standard ap- proach from clustering-based ANNs [29]: use low-precision vectors as hints to prune the traversal candidate list, and fetch full-precision vectors only for the pruned subset. Naively pruning using the in-memory traversal hintsH trv , however, is not effective (Appendix A.5): these hints are often too coarse to filter candidates effectively and require re-ranking nearly the entire candidate list, roughly doubling the access count while barely reducing bandwidth (Table 2). Increasing traversal hint size to improve pruning precision is also not a viable solution, as it increases the DRAM footprint and thus the deployment cost (§ 2.1). Decoupling traversal and pruning hints. The core is- sue with naive decoupling is that it leverages in-memory hints for two tasks with very different precision require- ments. Traversal can tolerate coarse hints because it only needs directional accuracy to move toward the query’s neigh- borhood. Graph connectivity corrects suboptimal local choices through convergent paths. Pruning, in contrast, is a sensitive filtering step where a mistakenly excluded true neighbor 7 is permanently lost, requiring higher precision. To address this mismatch, we introduce compact pruning hintsH prn , an intermediate representation that is substantially more precise thanH trv but an order of magnitude smaller than F. Crucially, these pruning hints are not stored in memory; instead, they are fetched from disk alongside the neighbor listNwhenever a node is visited during traversal, keeping the DRAM footprint unchanged. Three-step granular refinement. This yields a three- step granular refinement strategy (traverse→prune→re- fine) where traversal fetches much smaller blocks (N∥H prn rather thanN∥F) and the majority of expensive full-precision fetches are avoided, all without increasing the memory foot- print. Table 2 shows that for the same recall, our approach reduces bandwidth by 2–5×across datasets compared to DiskANN, while increasing access count by only 5–15%. 5.3 Construction Algorithm 1 Onyx-ANNS GreedySearch Algorithm Input: Query vector 푥 푞 Parameters: Result size퐾, candidate list size퐿, and pruned list size 퐿 prn s.t. 퐾 ≤ 퐿 prn ≤ 퐿 Index Layout: Start node푠and traversal hintsH trv in memory, per-vector concatenation of pruning hintsH prn and neighbor indicesNon external storage, and full precision coordinatesF on external storage Output: Indices of the 퐾 -approximate nearest neighbors 1: L ←푠,V ←∅⊲ Candidate and visited lists // Phase 1: Traversal 2: whileL ≠∅ do 3:let 푝 ∗ ← arg min 푝∈L dist(푥 푞 ,H trv (푝)) 4:fetchN(푝 ∗ )∥H prn (푝 ∗ ) from external storage 5:updateL ←L∪N(푝 ∗ ) andV ←V∪푝 ∗ 6:sortL by dist(푥 푞 ,H trv (·)) and setL ←L[: 퐿] // Phase 2: Pruning 7: sortL by dist(푥 푞 ,H prn (·)) using pruning hints 8: setL prn ←L[: 퐿 prn ]⊲ Pruned candidate list // Phase 3: Refinement 9: for each candidate 푝 ∈ L prn do 10:fetch 푥 푝 ←F(푝) from external storage 11: sortL prn by dist(푥 푞 ,F(·)) using full precision vectors 12: setR ←L prn [: 퐾] and returnR Algorithm 1 gives the search procedure for Onyx-ANNS, simplified to beam width푊=1 (i.e., one candidate explored per step) for clarity. In addition to beam width푊, the algo- rithm takes three parameters: the result size퐾, the candidate list size퐿, and the pruned list size퐿 prn , where퐾 ≤ 퐿 prn ≤ 퐿. To ensure obliviousness, both퐿and퐿 prn are fixed parameters independent of the query. Index layout. Onyx-ANNS reorganizes DiskANN’s on- disk layout:N(푝)∥H prn (푝)are packed together (fetched dur- ing traversal), whileF(푝)is stored separately (fetched only during refinement). Pruning hintsH prn are constructed using product quantization [48] at a higher fidelity thanH trv ; we choose|H prn |per dataset to maximize bandwidth reduction. Only the traversal hintsH trv are stored in memory. Memory footprint. Since traversal and refinement blocks are now stored separately on disk, they require two indepen- dent ORAM clients, which nearly doubles the ORAM-side memory footprint. Nevertheless, the ORAM client state is typically a small fraction of total memory (the bulk isH trv ), and we show in § 6.3 that this leads to only a 10–30% increase. We walk through the three phases below. Phase 1: Traversal (lines 2–6). A greedy beam search explores the graph starting from node푠. At each step, the top푊unvisited candidates (rather than one, as in the sim- plified Algorithm 1) are selected by approximate distance dist(푥 푞 ,H trv (·)). For each, the system fetchesN(푝)∥H prn (푝) from disk in a single I/O. Newly discovered neighbors are scored usingH trv and the beam is updated. Traversal con- tinues until exactly퐿nodes have been visited. This phase makes 퐿 accesses, each of size|N|+|H prn | bytes. Phase 2: Pruning (lines 7–8). The퐿candidates are re- ranked using the prefetched pruning hintsH prn , and only the top 퐿 prn are retained. No disk accesses are needed since all pruning hints were prefetched during traversal. Phase 3: Refinement (lines 9–11). For each of the 퐿 prn surviving candidates,F(푝)is fetched from disk, candidates are re-ranked by exact distance, and the top-퐾are returned. This phase makes exactly 퐿 prn accesses, each of size|F|. 5.4 Analysis The total access count is퐿+퐿 prn (vs. DiskANN’s퐿). The per- access bandwidth ratio is: BW DiskANN BW Onyx-ANNS = |N|+|F| (|N|+|H prn |)+ 퐿 prn 퐿 ·|F| Two terms in the denominator determine the improvement: (|N| + |H prn |), the smaller traversal block, and 퐿 prn 퐿 · |F|, the amortized refinement cost. These depend on two dataset characteristics. First, when|F|is large, the block size ratio (|N|+|F|)/(|N|+|H prn |)is large, since the numerator is dominated by|F|while the denominator remains small. Sec- ond, when|H trv |is highly compressed to minimize memory footprint (e.g., for personal databases),퐿must be large to achieve high recall with coarse guidance, and pruning hints can filter aggressively, yielding a small 퐿 prn /퐿. Our datasets illustrate both effects nicely (Table 2). WIKI and MS-MARCO have large embedding vectors (|F|=3072 B), and MS-MARCO and SIFT are personal databases that have highly compressed hints|F|/|H trv | ≥64. MS-MARCO bene- fits from both factors and achieves the largest improvement (5×), followed by WIKI (3.8×) with its large vectors, then SIFT (2.7×) with its better pruning ratio, and finally DEEP, where neither factor applies but we still see 1.8× improvement. 8 Dataset #Vectors Index Size Vector Size Hint Size SIFT1M0.6 GB512 B8 B MARCO8.8M29 GB3072 B32 B WIKI20M64 GB3072 B96 B DEEP60M31 GB384 B32 B Table 3. Datasets used in our evaluation. Index size cor- responds to the plain graph index (full precision vectors + adjacency lists). Hint size refers to the in-memory hints, sig- nificantly compressed to minimize DRAM footprint. 6 Evaluation We answer the following questions in this section: •Q1: Onyx-ORAM (§ 6.2). How does Onyx-ORAM per- form against state-of-the-art tree-based ORAMs like RingO- RAM and locality-optimized PathORAM on SSDs? •Q2: End-to-End Oblivious ANN Search (§ 6.3). How does Onyx compare against state-of-the-art oblivious ANN search and other ORAM-ANN combinations? •Q3: Onyx Co-design (§ 6.4). What is the combined bene- fit of the Onyx’s co-designed primitives, compared to their individual performance? •Q4: Cost Efficiency (§ 6.5). What is the cost benefit (throughput per $) of Onyx compared to state-of-the-art oblivious ANN search systems, across a wide range of hardware configurations? 6.1 Experimental Setup Datasets. We evaluate Onyx on both deployment sce- narios from § 2.1, adopting two datasets from Compass – SIFT [49] (1M vectors) and MS-MARCO [22] (8.8M vectors) – for personal databases and WIKI [20] (20M vectors) and DEEP [8] (60M vectors) for enterprize databases where large indices are sharded into disk-served partitions. Following partitioned disk-based ANN systems [114], we use a DRAM budget of approximately 4 GB per partition, with 2 GB allo- cated for hints. Together, these four datasets cover a wide range of index sizes (0.6–64 GB), vector dimensionalities (384 B–3 KB), and hint compression ratios (12×–96×), as summarized in Table 3. We summarize the index construc- tion hyperparameters used in Appendix B. Hardware Configuration. We run our experiments on a machine with an AMD EPYC 9554 Processor, with AMD SEV- SNP [51] enabled, and Micron 7450 MAX SSDs [71] attached throughvfio-pci. We partition our evaluation setup into resource units (RUs) usingcgroups, and all experiments are performed on a single RU unless otherwise mentioned. Since Onyx and each baseline have different SSD requirements (the latter require substantially more SSD resources), we analyze performance on two RU configurations: a cheaper configuration –1-SSD– with 1 vCPU, 4 GB of RAM, and 1 SSD unit, providing 85K IOPS, 330 MB/s read bandwidth, 175 MB/s write bandwidth, and 187.5 GB of storage, and a more expensive configuration –4-SSD– with the same vCPU and DRAM, but 4×the SSD resources. Due to space constraints, we summarize results for the4-SSDconfigura- tion throughout this section, but defer plots to Appendix A. Unless otherwise mentioned, we target퐾=10 and 90% recall, which is standard for benchmarking ANN search [6,97,98]. We estimate dollar cost using GCP’s N2D-standard pricing with AMD SEV-SNP enabled and 3-year resource-based com- mitted use discounts (as of March 2026) [40]. Under this pricing, vCPUs are $12.2/month, memory is $1.2/GB/month, and each local SSD unit is $6.75/month. ORAM Parameters. For large-bucket ORAMs (RingO- RAM and Onyx-ORAM), we set the early reshuffle rate to 0.1%. For RingORAM, we vary the bucket capacity푍be- tween 32 and 128, after which point, the large푍capac- ity increases the overhead for per-bucket metadata fetches such that overall performance is degraded. For Onyx-ORAM, which is optimized for larger bucket sizes, we vary푍be- tween 128 and 1024. For a given capacity푁, we pick the푍 value that minimizes memory and storage overhead. Follow- ing EnigMap [108], we set푍=4 for PathORAM and for each block size, vary the level-packing parameterℓbased on how many tree levels fit within a 4 KB SSD page and select the best-performing configuration. ANN Search Parameters. We vary recall by varying the candidate list size퐿during the search until the target recall is reached. For approaches that decouple traversal and re- finement, we fix퐿to match the coupled baseline and vary 퐿 prn until we achieve the same recall. We vary the beam width over4,8,16for DiskANN-based indices (including Onyx-ANN), and the speculation set size and direction filter size∈ [2,8]and[4,24], respectively, for Compass indices. We target at most 9 round trips (to match Compass), but if the recall target cannot be met within this budget, we increment the round-trip count until the target is reached. For all approaches, we vary the number of parallel requests (queue depth) over1,2, . . .,8to measure the throughput- vs-latency trade-off. For throughput-vs-recall plots, we limit the total number of visited nodes to≤ 1500. 6.2 Onyx-ORAM We evaluate Onyx-ORAM in isolation against RingORAM [88] and locality-optimized PathORAM [102,108] on 20M block storage, matching the WIKI-20M dataset. Figure 3 provides a detailed comparison between Onyx and each baseline across two performance metrics. Throughput vs. block size (Figure 3(a)). Onyx-ORAM maintains substantially higher throughput than both base- line ORAM protocols at small (256–512 B) block sizes which are used in ANN search, achieving over 10K logical accesses per second in that range. In contrast, RingORAM is access- count-bound: even at small block sizes, its throughput plateaus 9 (a) Throughput vs. block size(b) Throughput vs. latency (512 B) Figure 3. Onyx-ORAM vs prior work for 20M blocks (1-SSD). LBM (local bucket metadata), FBR (full bucket reads), ST (shallow tree) refer to steps in § 4.3; Onyx: Ring+LBM+FBR+ST-8; Ring: RingORAM; Path: locality- optimized PathORAM. around 2K QPS because the high access count per logical op- eration saturates the SSD’s IOPS. On the other hand, PathO- RAM is bandwidth-bound: its throughput degrades with in- creasing block size, falling below RingORAM at 1 KB blocks. At very large block sizes, Onyx-ORAM also becomes bandwidth- bound and matches the performance of RingORAM because they have similar bandwidth overheads (Table 1). Throughput vs. latency (Figure 3(b)). We evaluate the throughput-latency tradeoff for Onyx and baselines with the addition of several intermediate design points activating the techniques from § 4.3. At 512 B, the maximum traversal block size Onyx-ANN uses, Onyx-ORAM achieves up to 5.1× higher throughput and 2.7×lower latency than RingORAM, and up to 3.4×higher throughput and 2.0×lower latency than PathORAM. In sequence, enabling local bucket meta- data (LBM), full bucket reads (FBR), and shallow trees with various푑-arities yield better performance, following the an- alytical results in Figure 2 (§ 4.4). Onyx-ORAM uses each of these optimizations and a푑=8-ary tree, which both analyt- ically and experimentally yields the best tradeoff between bandwidth and access count overheads. 6.3 End-to-End Oblivious ANN Search We compare Onyx against Compass-in-TEE—the state-of- the-art oblivious ANN search system Compass [131] de- ployed inside a TEE to hide disk accesses. For each system, we issue queries from the dataset’s query set with1,2,4,8 parallel requests and measure throughput and latency at each concurrency level. Compass was designed for oblivi- ous access over a network and the Compass-ANN design was not specifically optimized for disk; to provide stronger baselines, we consider two additional combinations with DiskANN: RingORAM + DiskANN, which replaces Compass- ANN with DiskANN [105], and PathORAM + DiskANN, which further replaces RingORAM with locality-optimized PathORAM [102,108]. For a fair comparison on SIFT and MS-MARCO, we match Compass’s ANN hint sizes. Throughput vs. latency. In Figure 4, we sweep over num- ber of parallel requests, beamwidth configurations, and prun- ing hintsizes to measure the end-to-end performance (latency and throughput) of each ANN search system on a1-SSD instance; better configurations are located towards the top- left of the figures. Against Compass-in-TEE, Onyx achieves 2.3–12.3×lower latency and 2.3–12.2×higher throughput. Even against the disk-optimized baselines, Onyx maintains a substantial lead: 4.0–4.5×lower latency and 3.6–4.5×higher throughput than RingORAM + DiskANN, and 2.5–9.5×lower latency and 2.5–9.5×higher throughput than PathORAM + DiskANN. Under4-SSDconfiguration, additional SSD re- sources help the baselines narrow the gap, particularly at the high end—shrinking to 7.4×against Compass-in-TEE, 6.0× against PathORAM + DiskANN, and 3.9×against RingORAM + DiskANN—but a significant gap remains as the higher ac- cess counts and bandwidth of the baselines carry proportion- ally higher compute overhead, and the workload becomes compute-bound (Appendix A.3). Onyx’s improvement is largest where its ANN search achieves the greatest bandwidth reduction: in particular, searches over MS-MARCO benefit from a 5×reduction (§ 5.4) given its highly compressed hints and large full-precision vectors. For MS-MARCO and WIKI, RingORAM + DiskANN is the strongest baseline because these datasets use large blocks (over 3 KB) from their large embedding vectors, where bandwidth-efficient RingORAM excels. On DEEP, PathO- RAM + DiskANN performs best as its small 512 B blocks favor PathORAM’s lower access count. For SIFT, Compass-in- TEE is most competitive: it uses a larger number of neighbors and higher beam width to reduce roundtrips, which is effec- tive on small, localized graphs like 1M-vector SIFT, but be- comes wasteful on larger graphs. In all cases, Onyx achieves 2.3–4.5×lower latency and 2.3–4.4×higher throughput over the best baseline for each dataset. Throughput vs. recall. Figure 4 shows throughput-vs- recall across each dataset on a1-SSDinstance. Onyx’s im- provement is consistent across all recall targets: against Compass-in-TEE, we demonstrate throughput improvements of 2.1–13.0×across datasets and recall targets; against RingO- RAM + DiskANN, 2.7–5.2×; and against PathORAM + DiskANN, 2.3–10.2×. The per-dataset trends mirror the latency-throughput analysis above—the same factors that favor each baseline at 90% recall carry over to other recall targets—and in all cases, Onyx achieves 2.1–4.7×higher throughput than the best baseline for each dataset. Memory and storage. Table 4 summarizes memory and storage footprint for hosting each dataset. PathORAM with DiskANN exhibits the lowest footprint, as it does not store any bucket metadata. Onyx uses only 10–30% more memory, because its decoupled search architecture (§ 5.3) requires two ORAM clients (one for traversal blocks, one for refinement 10 Throughput (QPS) Latency (ms) Throughput (QPS) Recall (a) SIFT(b) MARCO(c) WIKI(d) DEEP Figure 4. (Top) Pareto frontier of throughput vs. latency of Onyx and baselines (1-SSD; top-left is better). Dots below the curves represent sub-optimal parameterizations; single markers are the configuration for a scheme that maximizes both latency and throughput. (Bottom) Throughput vs. recall of Onyx and baselines (1-SSD). Queries/$ Latency (ms) (a) SIFT(b) MS-MARCO(c) WIKI(d) DEEP Figure 5. Pareto frontier of cost-normalized throughput (Queries/$) vs. latency for Onyx and baselines, highlighting the most cost-effective configurations (vCPU and SSD resources allocated). Better configurations are towards the top-left. blocks). This overhead is more noticeable on datasets with smaller hints (e.g., DEEP), where ORAM client state is a larger fraction of total memory usage. Compass-in-TEE has the highest memory usage across most datasets because it uses RingORAM with a binary tree and stores bucket metadata locally, inflating per-block overhead without the Onyx’s푑- ary tree-based mitigation (§ 4.3, Appendix A.2). On SIFT, the index is small enough that fixed-size buffers and other constants dominate memory usage rather than metadata. Onyx has one of the smallest storage footprints across all datasets (2.0–2.7×amplification over the plaintext index), with PathORAM + DiskANN achieving a comparable foot- print when its binary tree capacity tightly fits푁(e.g., 2.3× on DEEP). RingORAM + DiskANN requires 3.0–4.1×more storage than Onyx due to the many dummy blocks in its tree (§ 4.3), and Compass-in-TEE requires 8–13×more be- cause its ORAM parameters have larger amplification and it uses larger blocks to accommodate CompassANN. A single SSD unit (187.5 GB) suffices to host any of our benchmarks under Onyx. 6.4 Onyx Co-design Figure 6 isolates the contribution of each Onyx component by comparing against three partial combinations: Onyx- ORAM paired with DiskANN, and Onyx-ANN paired with either RingORAM or PathORAM. In every case, Onyx pro- vides the best throughput at the lowest latency. On the SIFT and DEEP datasets with small vectors, the ORAM is the 11 SIFT MARCO WIKI DEEP Memory (GB) Onyx0.170.762.392.99 Compass-in-TEE0.160.992.933.84 RingORAM+DiskANN0.210.732.392.57 PathORAM+DiskANN0.130.612.162.31 Storage (GB) Onyx1.558.2170.676.9 Compass-in-TEE12.5776.31361706.4 RingORAM+DiskANN5.5239.7515271.4 PathORAM+DiskANN1.4108.2208.570.7 Table 4. Memory and storage overhead of Onyx and base- lines across our evaluation datasets. Throughput (QPS) (a) SIFT(b) MS-MARCO (c) WIKI(d) DEEP Latency (ms) Figure 6. Importance of ORAM-ANN co-design: pareto frontier of throughput vs. latency for Onyx and single- component (Onyx-ORAM/ANN) constructions. Better con- figurations are towards the top-left; single markers indicate a scheme’s latency- and throughput-optimal configuration. primary bottleneck: Onyx-ORAM + Disk approaches Onyx (10–20% lower performance), while replacing Onyx-ORAM with RingORAM or PathORAM degrades performance by 4.9–5.0×and 2.3–2.4×, respectively. In these datasets, Onyx- ANN’s bandwidth reduction provides only a small additional benefit because DiskANN already uses small block sizes and Onyx-ORAM becomes access-count-bound. Path + Onyx- ANNS outperforms Ring + Onyx-ANNS because PathORAM is more access-optimized, and its higher bandwidth over- head is offset by Onyx-ANN’s bandwidth savings. On MS- MARCO and WIKI which have large vectors, both compo- nents matter equally: Onyx-ORAM + Disk sees 2.8–4.5× lower throughput than Onyx because DiskANN’s large per- access bandwidth saturates the SSD, and Ring + Onyx-ANNS or Path + Onyx-ANNS show 3.2–4.1×and 3.0–3.1×lower throughput, respectively, because Onyx-ORAM significantly outperforms the baselines for the small 256–512 byte block accesses made by Onyx-ANNS (§ 6.2). Thus, co-design is essential: neither component alone is sufficient to achieve Onyx’s performance across the full workload range. 6.5 Cost Efficiency Given enough CPU and disk resources, even the inefficient baselines we compare against can achieve high throughput and low latency. Figure 5 demonstrates the cost-efficiency ad- vantage of Onyx, normalizing throughput by cost using pub- lic GCP pricing data (§ 6.1). For each scheme, we sweep over various resource allocations – vCPU counts in1,2,3,4and SSD slices in1,2,3,4,8,12,16– and plot the Pareto-optimal queries/$ vs latency tradeoff across all configurations. Onyx achieves 1.7–9.9×higher QPS/$ than Compass-in-TEE, 3.1– 4.2×higher than Ring + Disk, and 2.6–7.3×higher than Path + Disk. These improvements are proportional to what we ob- served in § 6.3: to match Onyx’s performance, baselines must increase both SSD and compute resources. Their poor SSD utilization—driven by higher access counts and bandwidth overheads—demands more SSD slices, and more compute to drive that I/O, so scaling resources does not meaningfully improve cost-efficiency. Onyx’s best cost-efficiency point is always at 1 SSD slice, because its compact index fits within a single slice and its throughput is not bottlenecked by the SSD. Additionally, storage amplification locks baselines into larger configurations: Compass-in-TEE requires 4–8 SSD slices on the enterprise datasets (e.g., 8 slices on WIKI to fit the 1.4 TB index), while Ring + Disk and Path + Disk require 2–3 slices. 7 Related Work Private nearest neighbor search. A number of crypto- graphic approaches target private nearest neighbor search with strong security guarantees, using techniques based on ORAM [131], MPC [15], homomorphic encryption [30,62], and PIR [43,130]. These approaches incur high overhead due to the strong cryptographic security model they target; among them, Compass [131] is the state-of-the-art, but still requires>1 s latency and roughly 100 queries per dollar. Un- like these works, Onyx relies on hardware trust assumptions (TEEs) to offer a practical solution with low latency and high cost-efficiency, achieving 12 ms latency and over 8 million queries per dollar (§ 6.3). Oblivious RAM. ORAM was first introduced by the sem- inal work of Goldreich and Ostrovsky [35] in 1996. Since then, a long line of work has proposed ORAM constructions, including hierarchical schemes [5,35,37,83,85] and the more popular tree-based designs [88,102,115]. ORAMs have been applied to various settings, including the traditional 12 client-server model [23,88,89,94,101,119,131], hardware enclaves [14,26,31,74,91,108,128], and multi-server set- tings [1,17,28,66,116,124]. Onyx operates in the enclave or TEE setting and is the first to optimize ORAM for hiding ANN search disk access patterns. The closest ORAM work to ours is EnigMap [108], which focuses on doubly oblivious access to an external storage from a TEE, where the ORAM client itself is data-oblivious to hide memory access patterns within the TEE. Onyx-ORAM achieves better performance than EnigMap in our (singly-oblivious) setting by leveraging 푑-ary trees, which were first introduced by Gentry et al. [34]. 푑-ary trees are also used in multi-server settings [1,124] where their high bandwidth overhead is offset through pri- vate information retrieval. We focus on tree-based ORAM, but our access-optimized design is also compatible with hi- erarchical ORAMs [5,83] since they also use bandwidth- efficient large bucket designs like RingORAM. Disk-based ANN search. Disk-based ANN search in- cludes both graph-based [105] and clustering-based [16,29, 48] approaches. We focus on graph-based designs, in par- ticular DiskANN [105], which is widely deployed in indus- try [25,42,46,84,107,110,113] and has been extended to fil- tered search [36], streaming updates [99,120], low-memory operation [82], parallel indexing [67], and distributed in- dices [2]. These designs optimize for the plain-SSD regime where bandwidth is cheap and access count is the bottle- neck; for instance, Starling [114] reduces access count by 2×while increasing bandwidth by up to 16×. Onyx-ANNS targets bandwidth-efficient disk-based ANN search, moti- vated by ORAM’s푂(log푁)×bandwidth amplification (§ 5). Bandwidth efficiency has also been explored for in-memory ANN [126], which reduces memory bandwidth through in- cremental reads and early rejection of candidates. These techniques are incompatible with our setting because they require fine-grained, data-dependent accesses per candidate. We focus on graph-based ANN search in this work but our refinement strategy can also be used in clustering-based indices [16, 29] to minimize bandwidth. Acknowledgments We thank Benjamin Karsin and Vikram Sharma Mailthody for their helpful discussions and insightful comments that helped shape this work. We are also grateful to the Sky Lab se- curity group members for their valuable feedback. This work was supported in part by NSF CAREER Award 1943347, and by generous gifts from Accenture, AMD, Anyscale, Broad- com, Cisco, IBM, Intel, Intesa Sanpaolo, Lambda, Lightspeed, Mibura, Microsoft, NVIDIA, Samsung SDS, and SAP. References [1] Ittai Abraham, Christopher W. Fletcher, Kartik Nayak, Benny Pinkas, and Ling Ren. 2017. Asymptotically Tight Bounds for Composing ORAM with PIR. In Public Key Cryptography (1) (Lecture Notes in Computer Science). Springer, 91–120. [2] Philip Adams, Menghao Li, Shi Zhang, Li Tan, Qi Chen, Mingqin Li, Zengzhong Li, Knut Magne Risvik, and Harsha Vardhan Simhadri. 2025. DISTRIBUTEDANN: Efficient Scaling of a Single DISKANN Graph Across Thousands of Computers. CoRR abs/2509.06046 (2025). [3]Sebastian Angel, Aditya Basu, Weidong Cui, Trent Jaeger, Stella Lau, Srinath T. V. Setty, and Sudheesh Singanamalla. 2023. Nimble: Roll- back Protection for Confidential Cloud Services. In OSDI. USENIX Association, 193–208. [4]Sergei Arnautov, Bohdan Trach, Franz Gregor, Thomas Knauth, André Martin, Christian Priebe, Joshua Lind, Divya Muthukumaran, Dan O’Keeffe, Mark Stillwell, David Goltzsche, David M. Eyers, Rüdiger Kapitza, Peter R. Pietzuch, and Christof Fetzer. 2016. SCONE: Secure Linux Containers with Intel SGX. In OSDI. USENIX Association, 689– 703. [5] Gilad Asharov, Ilan Komargodski, and Yehuda Michelson. 2023. Fu- tORAMa: A Concretely Efficient Hierarchical Oblivious RAM. In CCS. ACM, 3313–3327. [6]Martin Aumüller, Erik Bernhardsson, and Alexander John Faithfull. 2017. ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms. In SISAP (Lecture Notes in Computer Science). Springer, 34–49. [7]Compass Authors. 2024. Compass Faiss Fork. https://github.com/ Clive2312/faiss. Custom Faiss fork used for Compass index construc- tion. [8] Artem Babenko and Victor S. Lempitsky. 2016. Efficient Indexing of Billion-Scale Datasets of Deep Descriptors. In CVPR. IEEE Computer Society, 2055–2063. [9]Andrew Baumann, Marcus Peinado, and Galen C. Hunt. 2014. Shield- ing Applications from an Untrusted Cloud with Haven. In OSDI. USENIX Association, 267–283. [10] Mihir Bellare and Chanathip Namprempre. 2000. Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm. In ASIACRYPT (Lecture Notes in Computer Science). Springer, 531–545. [11]Laura Blackstone, Seny Kamara, and Tarik Moataz. 2020. Revisiting Leakage Abuse Attacks. In NDSS. The Internet Society. [12]Jo Van Bulck, Frank Piessens, and Raoul Strackx. 2017. SGX-Step: A Practical Attack Framework for Precise Enclave Execution Control. In SysTEX@SOSP. ACM, 4:1–4:6. [13] David Cash, Paul Grubbs, Jason Perry, and Thomas Ristenpart. 2015. Leakage-Abuse Attacks Against Searchable Encryption. In CCS. ACM, 668–679. [14]Javad Ghareh Chamani, Ioannis Demertzis, Dimitrios Papadopoulos, Charalampos Papamanthou, and Rasool Jalili. 2024. GraphOS: To- wards Oblivious Graph Processing. IACR Cryptol. ePrint Arch. 2024 (2024), 642. https://eprint.iacr.org/2024/642 [15]Hao Chen, Ilaria Chillotti, Yihe Dong, Oxana Poburinnaya, Ilya P. Razenshteyn, and M. Sadegh Riazi. 2020. SANNS: Scaling Up Se- cure Approximate k-Nearest Neighbors Search. In USENIX Security Symposium. USENIX Association, 2111–2128. [16]Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. SPANN: Highly- efficient Billion-scale Approximate Nearest Neighborhood Search. In NeurIPS. 5199–5212. [17]Weikeng Chen and Raluca Ada Popa. 2020. Metal: A Metadata-Hiding File-Sharing System. In NDSS. The Internet Society. [18] Pau-Chen Cheng, Wojciech Ozga, Enriquillo Valdez, Salman Ahmed, Zhongshu Gu, Hani Jamjoom, Hubertus Franke, and James Bottomley. 2024. Intel TDX Demystified: A Top-Down Approach. Comput. Surveys 56, 9 (2024). doi:10.1145/3652597 [19] Jalen Chuang, Alex Seto, Nicolas Berrios, Stephan van Schaik, Christina Garman, and Daniel Genkin. 2026. TEE.fail: Breaking Trusted Execution Environments via DDR5 Memory Bus Interpo- sition. In 47th IEEE Symposium on Security and Privacy (IEEE S&P ’26). 13 IEEE Computer Society. https://tee.fail [20]Cohere. 2023. Wikipedia Embeddings (English, 768-dimensional). https://cohere.com/blog/embedding-archives-wikipedia. [21]Scott Constable, Jo Van Bulck, Xiang Cheng, Yuan Xiao, Cedric Xing, Ilya Alexandrovich, Taesoo Kim, Frank Piessens, Mona Vij, and Mark Silberstein. 2023. AEX-Notify: Thwarting Precise Single-Stepping At- tacks through Interrupt Awareness for Intel SGX Enclaves. In USENIX Security Symposium. USENIX Association, 4051–4068. [22]Nick Craswell, Bhaskar Mitra, Emine Yilmaz, Daniel Campos, and Jimmy Lin. 2021. MS MARCO: Benchmarking Ranking Models in the Large-Data Regime. In SIGIR. ACM, 1566–1576. [23]Natacha Crooks, Matthew Burke, Ethan Cecchetti, Sitar Harel, Rachit Agarwal, and Lorenzo Alvisi. 2018. Obladi: Oblivious Serializable Transactions in the Cloud. In OSDI. USENIX Association, 727–743. [24] Marc Damie, Florian Hahn, and Andreas Peter. 2021. A Highly Ac- curate Query-Recovery Attack against Searchable Encryption using Non-Indexed Documents. In USENIX Security. USENIX Association, 143–160. [25]DataStax. 2024. JVector: Graph-based vector search for Java. https: //github.com/datastax/jvector. [26] Emma Dauterman, Vivian Fang, Ioannis Demertzis, Natacha Crooks, and Raluca Ada Popa. 2021. Snoopy: Surpassing the Scalability Bot- tleneck of Oblivious Storage. In SOSP. ACM, 655–671. [27]Jesse De Meulemeester, David Oswald, Ingrid Verbauwhede, and Jo Van Bulck. 2026. Battering RAM: Low-Cost Interposer Attacks on Confidential Computing via Dynamic Memory Aliasing. In 47th IEEE Symposium on Security and Privacy (S&P). [28]Jack Doerner and Abhi Shelat. 2017. Scaling ORAM for Secure Com- putation. In CCS. ACM, 523–535. [29] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2024.The Faiss library.(2024). arXiv:2401.08281 [cs.LG] [30]Joshua J. Engelsma, Anil K. Jain, and Vishnu Naresh Boddeti. 2022. HERS: Homomorphically Encrypted Representation Search. IEEE Trans. Biom. Behav. Identity Sci. 4, 3 (2022), 349–360. [31]Saba Eskandarian and Matei Zaharia. 2019. ObliDB: Oblivious Query Processing for Secure Databases. Proc. VLDB Endow. 13, 2 (2019), 169–183. [32] Dmitry Evtyushkin, Ryan Riley, Nael B. Abu-Ghazaleh, and Dmitry Ponomarev. 2018. BranchScope: A New Side-Channel Attack on Directional Branch Predictor. In ASPLOS. ACM, 693–707. [33]Stefan Gast, Hannes Weissteiner, Robin Leander Schröder, and Daniel Gruss. 2025. CounterSEVeillance: Performance-Counter Attacks on AMD SEV-SNP. In NDSS. The Internet Society. [34]Craig Gentry, Kenny A. Goldman, Shai Halevi, Charanjit S. Jutla, Mariana Raykova, and Daniel Wichs. 2013. Optimizing ORAM and Using It Efficiently for Secure Computation. In Privacy Enhancing Technologies (Lecture Notes in Computer Science). Springer, 1–18. [35]Oded Goldreich and Rafail Ostrovsky. 1996. Software Protection and Simulation on Oblivious RAMs. J. ACM 43, 3 (1996), 431–473. [36]Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan, Amit Singh, and Har- sha Vardhan Simhadri. 2023. Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. In W. ACM, 3406–3416. [37]Michael T. Goodrich and Michael Mitzenmacher. 2011. Privacy- Preserving Access of Outsourced Data via Oblivious RAM Simulation. In ICALP (2) (Lecture Notes in Computer Science). Springer, 576–587. [38]Google. 2025. Gemini Personal Intelligence. https://gemini.google/ overview/personal-intelligence/. [39]Google Cloud. 2024. Confidential Computing. https://cloud.google. com/confidential-computing. Accessed March 2026. [40] Google Cloud. 2026. Compute Engine Pricing. https://cloud.google. com/compute/vm-instance-pricing. [41] Paul Grubbs, Thomas Ristenpart, and Vitaly Shmatikov. 2017. Why Your Encrypted Database Is Not Secure. In HotOS. ACM, 162–168. [42]Harsha Simhadri. 2026.Overview of the DiskANN Project (2018–present). https://harsha-simhadri.org/diskann-overview.html. [43]Alexandra Henzinger, Emma Dauterman, Henry Corrigan-Gibbs, and Nickolai Zeldovich. 2023. Private Web Search with Tiptoe. In SOSP. ACM, 396–416. [44]Yizheng Huang and Jimmy Xiangji Huang. 2026. A Survey on Retrieval-Augmented Text Generation for Large Language Models. Comput. Surveys (2026). doi:10.1145/3805774 [45]Tyler Hunt, Zhiting Zhu, Yuanzhong Xu, Simon Peter, and Emmett Witchel. 2016. Ryoan: A Distributed Sandbox for Untrusted Compu- tation on Secret Data. In OSDI. USENIX Association, 533–549. [46]Intel. 2024. Scalable Vector Search (SVS). https://github.com/intel/ ScalableVectorSearch. [47]Mohammad Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. 2012. Access Pattern disclosure on Searchable Encryption: Ramifica- tion, Attack and Mitigation. In NDSS. The Internet Society. [48] Hervé Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Trans. Pattern Anal. Mach. Intell. 33, 1 (2011), 117–128. [49]Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Am- saleg. 2011. Searching in one billion vectors: Re-rank with source coding. In ICASSP. IEEE, 861–864. [50]Grace Jia, Alex Wong, and Anurag Khandelwal. 2025. Found in Translation: A Generative Language Modeling Approach to Memory Access Pattern Attacks. In USENIX Security Symposium. USENIX Association, 7957–7975. [51] David Kaplan. 2020. SEV-SNP: Strengthening VM Isolation with Integrity Protection and More.https://w.amd.com/content/ dam/amd/en/documents/epyc-business-docs/white-papers/SEV- SNP-strengthening-vm-isolation-with-integrity-protection-and- more.pdf. [52] Omar Khattab and Matei Zaharia. 2020. ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT. In SIGIR. ACM, 39–48. [53]Yoongu Kim, Ross Daly, Jeremie S. Kim, Chris Fallin, Ji-Hye Lee, Donghyuk Lee, Chris Wilkerson, Konrad Lai, and Onur Mutlu. 2014. Flipping bits in memory without accessing them: An experimental study of DRAM disturbance errors. In ISCA. IEEE Computer Society, 361–372. [54]Paul Kocher, Jann Horn, Anders Fogh, Daniel Genkin, Daniel Gruss, Werner Haas, Mike Hamburg, Moritz Lipp, Stefan Mangard, Thomas Prescher, Michael Schwarz, and Yuval Yarom. 2019. Spectre Attacks: Exploiting Speculative Execution. In IEEE Symposium on Security and Privacy. IEEE, 1–19. [55] Ilan Komargodski and Wei-Kai Lin. 2021. A Logarithmic Lower Bound for Oblivious RAM (for All Parameters). In CRYPTO (4) (Lecture Notes in Computer Science). Springer, 579–609. [56]Steven Lambregts, Huanhuan Chen, Jianting Ning, and Kaitai Liang. 2022. VAL: Volume and Access Pattern Leakage-Abuse Attack with Leaked Documents. In ESORICS (1) (Lecture Notes in Computer Sci- ence). Springer, 653–676. [57]Kasper Green Larsen and Jesper Buus Nielsen. 2018. Yes, There is an Oblivious RAM Lower Bound!. In CRYPTO (2) (Lecture Notes in Computer Science). Springer, 523–542. [58]Dayeol Lee, Dongha Jung, Ian T. Fang, Chia-Che Tsai, and Raluca Ada Popa. 2020. An Off-Chip Attack on Hardware Enclaves via the Mem- ory Bus. In USENIX Security Symposium. USENIX Association, 487– 504. [59]Sangho Lee, Ming-Wei Shih, Prasun Gera, Taesoo Kim, Hyesoon Kim, and Marcus Peinado. 2017. Inferring Fine-grained Control Flow 14 Inside SGX Enclaves with Branch Shadowing. In USENIX Security Symposium. USENIX Association, 557–574. [60] Woomin Lee, Taehun Kim, Seunghee Shin, Junbeom Hur, and Youngjoo Shin. 2025.T-Time: A Fine-Grained Timing-Based Controlled-Channel Attack Against Intel TDX. In ESORICS (3) (Lec- ture Notes in Computer Science). Springer, 323–341. [61] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. 2020. Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks. In NeurIPS. [62]Jingyu Li, Zhicong Huang, Min Zhang, Cheng Hong, Jian Liu, Tao Wei, and Wenguang Chen. 2025. Panther: Private Approximate Nearest Neighbor Search in the Single Server Setting. In CCS. ACM, 365–379. [63]Xiang Li, Yunqian Luo, and Mingyu Gao. 2024. Bulkor: Enabling Bulk Loading for Path ORAM. In SP. IEEE, 4258–4276. [64]Linux Kernel Documentation. 2024. Bounce Buffers for Confidential Computing. https://w.kernel.org/doc/html/latest/core-api/dma- api.html. [65] Moritz Lipp, Michael Schwarz, Daniel Gruss, Thomas Prescher, Werner Haas, Anders Fogh, Jann Horn, Stefan Mangard, Paul Kocher, Daniel Genkin, Yuval Yarom, and Mike Hamburg. 2018. Meltdown: Reading Kernel Memory from User Space. In USENIX Security Sym- posium. USENIX Association, 973–990. [66] Steve Lu and Rafail Ostrovsky. 2013. Distributed Oblivious RAM for Secure Two-Party Computation. In TCC (Lecture Notes in Computer Science). Springer, 377–396. [67]Magdalen Dobson Manohar, Zheqi Shen, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2024. ParlayANN: Scalable and Deterministic Parallel Graph-Based Approx- imate Nearest Neighbor Search Algorithms. In PPoPP. ACM, 270–285. [68]Sinisa Matetic, Mansoor Ahmed, Kari Kostiainen, Aritra Dhar, David M. Sommer, Arthur Gervais, Ari Juels, and Srdjan Capkun. 2017. ROTE: Rollback Protection for Trusted Execution. In USENIX Security Symposium. USENIX Association, 1289–1306. [69] David A. McGrew and John Viega. 2004. The Security and Perfor- mance of the Galois/Counter Mode (GCM) of Operation. In Progress in Cryptology - INDOCRYPT 2004 (Lecture Notes in Computer Science). Springer, 343–355. doi:10.1007/978-3-540-30556-9_27 [70] Jesse De Meulemeester, Luca Wilke, David F. Oswald, Thomas Eisen- barth, Ingrid Verbauwhede, and Jo Van Bulck. 2025. BadRAM: Practi- cal Memory Aliasing Attacks on Trusted Execution Environments. In SP. IEEE, 4117–4135. [71]Micron. 2023. Micron 7450 MAX NVMe SSD. https://w.micron. com/products/storage/ssd/data-center-ssd/7450-ssd. [72]Microsoft. 2024.Azure Confidential Computing.https://learn. microsoft.com/en-us/azure/confidential-computing/.Accessed March 2026. [73] Microsoft. 2024.Retrace your steps with Recall.https: //support.microsoft.com/en-us/windows/retrace-your-steps- with-recall-a03f8a0-a78b-4b3e-b0a1-2eb8ac48701c. [74]Pratyush Mishra, Rishabh Poddar, Jerry Chen, Alessandro Chiesa, and Raluca Ada Popa. 2018. Oblix: An Efficient Oblivious Search Index. In IEEE Symposium on Security and Privacy. IEEE Computer Society, 279–296. [75]Ahmad Moghimi, Gorka Irazoqui, and Thomas Eisenbarth. 2017. CacheZoom: How SGX Amplifies the Power of Cache Attacks. In CHES (Lecture Notes in Computer Science). Springer, 69–90. [76]Kit Murdock, David F. Oswald, Flavio D. Garcia, Jo Van Bulck, Daniel Gruss, and Frank Piessens. 2020. Plundervolt: Software-based Fault Injection Attacks against Intel SGX. In SP. IEEE, 1466–1482. [77]Jiongkang Ni, Xiaoliang Xu, Yuxiang Wang, Can Li, Jiajie Yao, Shihai Xiao, and Xuecang Zhang. 2023. DiskANN++: Efficient Page-based Search over Isomorphic Mapped Graph Index using Query-sensitivity Entry Vertex. CoRR abs/2310.00402 (2023). [78]Hao Nie, Wei Wang, Peng Xu, Xianglong Zhang, Laurence T. Yang, and Kaitai Liang. 2024. Query Recovery from Easy to Hard: Jigsaw Attack against SSE. In USENIX Security Symposium. USENIX Associa- tion. [79]Rodrigo Nogueira and Kyunghyun Cho. 2019. Passage Re-ranking with BERT. CoRR abs/1901.04085 (2019). [80]Oleksii Oleksenko, Bohdan Trach, Robert Krahn, Mark Silberstein, and Christof Fetzer. 2018. Varys: Protecting SGX Enclaves from Practical Side-Channel Attacks. In USENIX ATC. USENIX Association, 227–240. [81]Simon Oya and Florian Kerschbaum. 2022. IHOP: Improved Statistical Query Recovery against Searchable Symmetric Encryption through Quadratic Optimization. In USENIX Security Symposium. USENIX Association, 2407–2424. [82]Yu Pan, Jianxin Sun, and Hongfeng Yu. 2023. LM-DiskANN: Low Memory Footprint in Disk-Native Dynamic Graph-Based ANN In- dexing. In IEEE Big Data. IEEE, 5987–5996. [83]Sarvar Patel, Giuseppe Persiano, Mariana Raykova, and Kevin Yeo. 2018. PanORAMa: Oblivious RAM with Logarithmic Overhead. In FOCS. IEEE Computer Society, 871–882. [84]Pinecone. 2024. Pinecone: Vector Database for Machine Learning. https://w.pinecone.io. [85]Benny Pinkas and Tzachy Reinman. 2010. Oblivious RAM Revisited. In CRYPTO (Lecture Notes in Computer Science). Springer, 502–519. [86]Rishabh Poddar, Chang Lan, Raluca Ada Popa, and Sylvia Ratnasamy. 2018. SafeBricks: Shielding Network Functions in the Cloud. In NSDI. USENIX Association, 201–216. [87] Christian Priebe, Kapil Vaswani, and Manuel Costa. 2018. EnclaveDB: A Secure Database Using SGX. In IEEE Symposium on Security and Privacy. IEEE Computer Society, 264–278. [88]Ling Ren, Christopher W. Fletcher, Albert Kwon, Emil Stefanov, Elaine Shi, Marten van Dijk, and Srinivas Devadas. 2015. Constants Count: Practical Improvements to Oblivious RAM. In USENIX Security Sym- posium. USENIX Association, 415–430. [89] Cetin Sahin, Victor Zakhary, Amr El Abbadi, Huijia Lin, and Stefano Tessaro. 2016. TaoStore: Overcoming Asynchronicity in Oblivious Data Storage. In IEEE Symposium on Security and Privacy. IEEE Com- puter Society, 198–217. [90] Enes Sahin. 2024.Does ChatGPT Use RAG? A Devel- oper’sPerspectiveonRetrievalinReal-WorldSystems. https://learningdaily.dev/does-chatgpt-use-rag-a-developers- perspective-on-retrieval-in-real-world-systems-939c57d401f8. Accessed April 2026. [91]Sajin Sasy, Sergey Gorbunov, and Christopher W. Fletcher. 2018. Ze- roTrace : Oblivious Memory Primitives from Intel SGX. In NDSS. The Internet Society. [92]J. Ben Schafer, Dan Frankowski, Jonathan L. Herlocker, and Shilad Sen. 2007. Collaborative Filtering Recommender Systems. In The Adaptive Web (Lecture Notes in Computer Science). Springer, 291–324. [93]Felix Schuster, Manuel Costa, Cédric Fournet, Christos Gkantsidis, Marcus Peinado, Gloria Mainar-Ruiz, and Mark Russinovich. 2015. VC3: Trustworthy Data Analytics in the Cloud Using SGX. In IEEE Symposium on Security and Privacy. IEEE Computer Society, 38–54. [94]Amin Setayesh, Cheran Mahalingam, Emily Chen, and Sujaya Maiyya. 2025. Treebeard: A Scalable and Fault Tolerant ORAM Datastore. In USENIX Security Symposium. USENIX Association, 7583–7602. [95]Alexander Seto, Oytun Kuday Duran, Samy Amer, Jalen Chuang, Stephan van Schaik, Daniel Genkin, and Christina Garman. 2025. WireTap: Breaking Server SGX via DRAM Bus Interposition. In CCS. ACM, 708–722. [96]Youren Shen, Hongliang Tian, Yu Chen, Kang Chen, Runji Wang, Yi Xu, Yubin Xia, and Shoumeng Yan. 2020. Occlum: Secure and Efficient Multitasking Inside a Single Enclave of Intel SGX. In ASPLOS. ACM, 15 955–970. [97]Harsha Vardhan Simhadri, Martin Aumüller, Amir Ingber, Matthijs Douze, George Williams, Magdalen Dobson Manohar, Dmitry Baranchuk, Edo Liberty, Frank Liu, Benjamin Landrum, Mazin Karjikar, and Laxman Dhulipala. 2024. Results of the Big ANN: NeurIPS’23 Competition. CoRR abs/2409.17424 (2024).https: //arxiv.org/abs/2409.17424 [98]Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamy, Gopal Srinivasa, Suhas Ja- yaram Subramanya, and Jingdong Wang. 2022.Results of the NeurIPS’21 Challenge on Billion-Scale Approximate Nearest Neigh- bor Search. In NeurIPS 2021 Competitions and Demonstrations Track (Proceedings of Machine Learning Research, Vol. 176). PMLR, 177–189. https://proceedings.mlr.press/v176/simhadri22a.html [99]Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2021. FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search. CoRR abs/2105.09613 (2021). [100] Mahdi Soleimani, Grace Jia, and Anurag Khandelwal. 2025. Weave: Ef- ficient and Expressive Oblivious Analytics at Scale. In OSDI. USENIX Association, 939–955. [101]Emil Stefanov and Elaine Shi. 2013. ObliviStore: High Performance Oblivious Cloud Storage. In IEEE Symposium on Security and Privacy. IEEE Computer Society, 253–267. [102]Emil Stefanov, Marten van Dijk, Elaine Shi, Christopher W. Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. 2013. Path ORAM: an extremely simple oblivious RAM protocol. In CCS. ACM, 299–310. [103] Raoul Strackx and Frank Piessens. 2016. Ariadne: A Minimal Ap- proach to State Continuity. In USENIX Security Symposium. USENIX Association, 875–892. [104]Raoul Strackx and Frank Piessens. 2017. The Heisenberg Defense: Proactively Defending SGX Enclaves against Page-Table-Based Side- Channel Attacks. CoRR abs/1712.08519 (2017). [105]Suhas Jayaram Subramanya, Devvrit, Harsha Vardhan Simhadri, Rav- ishankar Krishnaswamy, and Rohan Kadekodi. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In NeurIPS. 13748–13758. [106]Bing Tian, Haikun Liu, Yuhang Tang, Shihai Xiao, Zhuohui Duan, Xiaofei Liao, Hai Jin, Xuecang Zhang, Junhua Zhu, and Yu Zhang. 2025. Towards High-throughput and Low-latency Billion-scale Vector Search via CPU/GPU Collaborative Filtering and Re-ranking. In FAST. USENIX Association, 171–185. [107]Timescale. 2024. pgvectorscale: DiskANN-based indexing for Post- greSQL. https://github.com/timescale/pgvectorscale. [108]Afonso Tinoco, Sixiang Gao, and Elaine Shi. 2023. EnigMap: External- Memory Oblivious Map for Secure Enclaves. In USENIX Security Symposium. USENIX Association, 4033–4050. [109] Daniel Townley, Kerem Arikan, Yu David Liu, Dmitry Ponomarev, and Oguz Ergin. 2022. Composable Cachelets: Protecting Enclaves from Cache Side-Channel Attacks. In USENIX Security Symposium. USENIX Association, 2839–2856. [110] Nitish Upreti, Harsha Vardhan Simhadri, Hari Sudan Sundar, Krish- nan Sundaram, Samer Boshra, Balachandar Perumalswamy, Shivam Atri, Martin Chisholm, Revti Raman Singh, Greg Yang, Tamara Hass, Nitesh Dudhey, Subramanyam Pattipaka, Mark Hildebrand, Mag- dalen Dobson, Jack Moffitt, Haiyang Xu, Naren Datha, Suryansh Gupta, Ravishankar Krishnaswamy, Prashant Gupta, Abhishek Sahu, Hemeswari Varada, Sudhanshu Barthwal, Ritika Mor, James Codella, Shaun Cooper, Kevin Pilch, Simon Moreno, Aayush Kataria, Santosh Kulkarni, Neil Deshpande, Amar Sagare, Dinesh Billa, Zishan Fu, and Vipul Vishal. 2025. Cost-Effective, Low Latency Vector Search with Azure Cosmos DB. Proc. VLDB Endow. 18, 12 (2025), 5166–5183. [111]Karthik V., Saim Khan, Somesh Singh, Harsha Vardhan Simhadri, and Jyothi Vedurada. 2024. BANG: Billion-Scale Approximate Nearest Neighbor Search using a Single GPU. CoRR abs/2401.11324 (2024). [112]Daan Vanoverloop, Andrés Sánchez, Flavio Toffalini, Frank Piessens, Mathias Payer, and Jo Van Bulck. 2025. TLBlur: Compiler-Assisted Automated Hardening against Controlled Channels on Off-the-Shelf Intel SGX Platforms. In USENIX Security Symposium. USENIX Associ- ation, 1167–1186. [113]Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xi- aohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021. Milvus: A Purpose-Built Vector Data Management System. In SIGMOD Conference. ACM, 2614–2627. [114] Mengzhao Wang, Weizhi Xu, Xiaomeng Yi, Songlin Wu, Zhangyang Peng, Xiangyu Ke, Yunjun Gao, Xiaoliang Xu, Rentong Guo, and Charles Xie. 2024. Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment. Proc. ACM Manag. Data 2, 1 (2024), V2mod014:1– V2mod014:27. [115] Xiao Wang, T.-H. Hubert Chan, and Elaine Shi. 2015. Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound. In CCS. ACM, 850–861. [116]Xiao Shaun Wang, Yan Huang, T.-H. Hubert Chan, Abhi Shelat, and Elaine Shi. 2014. SCORAM: Oblivious RAM for Secure Computation. In CCS. ACM, 191–202. [117]Weaviate. 2024. Weaviate: Open-Source Vector Database. https: //weaviate.io. Accessed March 2026. [118] Luca Wilke, Florian Sieck, and Thomas Eisenbarth. 2024. TDXdown: Single-Stepping and Instruction Counting Attacks against Intel TDX. In CCS. ACM, 79–93. [119]Peter Williams, Radu Sion, and Alin Tomescu. 2012. PrivateFS: a parallel oblivious file system. In CCS. ACM, 977–988. [120]Haike Xu, Magdalen Dobson Manohar, Philip A. Bernstein, Badrish Chandramouli, Richard Wen, and Harsha Vardhan Simhadri. 2025. In- Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search. CoRR abs/2502.13826 (2025). [121]Yuanzhong Xu, Weidong Cui, and Marcus Peinado. 2015. Controlled- Channel Attacks: Deterministic Side Channels for Untrusted Op- erating Systems. In IEEE Symposium on Security and Privacy. IEEE Computer Society, 640–656. [122] Yuval Yarom and Katrina Falkner. 2014. FLUSH+RELOAD: A High Resolution, Low Noise, L3 Cache Side-Channel Attack. In USENIX Security Symposium. USENIX Association, 719–732. [123]Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. 2018. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. In KDD. ACM, 974– 983. [124] Jinsheng Zhang, Qiumao Ma, Wensheng Zhang, and Daji Qiao. 2016. MSKT-ORAM: A Constant Bandwidth ORAM without Homomorphic Encryption. IACR Cryptol. ePrint Arch. 2016 (2016), 882. [125]Ruiyi Zhang, Lukas Gerlach, Daniel Weber, Lorenz Hetterich, Youheng Lü, Andreas Kogler, and Michael Schwarz. 2024. CacheWarp: Software-based Fault Injection using Selective State Reset. In USENIX Security Symposium. USENIX Association. [126]Teresa Zhang. 2025. Optimizing Memory Bandwidth for Efficient Approximate Nearest Neighbor Search. In KDD 2025. https://kdd2025. kdd.org/wp-content/uploads/2025/07/CameraReady-06.pdf [127]Yupeng Zhang, Jonathan Katz, and Charalampos Papamanthou. 2016. All Your Queries Are Belong to Us: The Power of File-Injection Attacks on Searchable Encryption. In USENIX Security Symposium. USENIX Association, 707–720. [128]Leqian Zheng, Zheng Zhang, Wentao Dong, Yao Zhang, Ye Wu, and Cong Wang. 2025. H2O2RAM: A High-Performance Hierarchical 16 Doubly Oblivious RAM. In USENIX Security Symposium. USENIX Association, 8501–8520. [129] Wenting Zheng, Ankur Dave, Jethro G. Beekman, Raluca Ada Popa, Joseph E. Gonzalez, and Ion Stoica. 2017. Opaque: An Oblivious and Encrypted Distributed Analytics Platform. In NSDI. USENIX Association, 283–298. [130] Mingxun Zhou, Elaine Shi, and Giulia Fanti. 2025. Pacmann: Efficient Private Approximate Nearest Neighbor Search. In ICLR. OpenRe- view.net. [131]Jinhao Zhu, Liana Patel, Matei Zaharia, and Raluca Ada Popa. 2025. Compass: Encrypted Semantic Search with High Accuracy. In OSDI. USENIX Association, 915–938. A Additional Evaluation Results This appendix contains additional evaluation results, includ- ing the4-SSDvariants of the main-body figures and the ablation studies. A.1 Onyx-ORAM (4-SSD) Figure 7 complements Figure 3. The trends are consistent: Onyx-ORAM’s improvements carry over with additional SSD resources. At 512 B, Onyx-ORAM achieves 3.9×higher throughput and 2.7×lower latency than RingORAM, and 2.9×higher throughput and 2.0×lower latency than PathO- RAM. The throughput gains are smaller than under1-SSD (5.1×and 3.4×) because the baselines were I/O-bottlenecked and benefit from the extra SSD resources; the gap neverthe- less persists because they become compute-bound (§ 6.3). (a) Throughput vs. block size(b) Throughput vs. latency (퐵=512 B) Figure 7. Onyx-ORAM vs prior work for 20M blocks (4-SSD). LBM (local bucket metadata), FBR (full bucket reads), ST (shallow tree) refer to steps in § 4.3; Onyx: Ring+LBM+FBR+ST-8; Ring: RingORAM; Path: locality- optimized PathORAM. A.2 ORAM Memory and Storage We measure the per-block memory footprint of Onyx-ORAM, PathORAM, RingORAM, and RingORAM with local bucket metadata (LBM) in our implementation. Onyx-ORAM (푑= 8) requires∼8.7 bytes/block, comparable to RingORAM at ∼8.6 bytes/block and only slightly above PathORAM at∼7 bytes/block. Adding LBM to RingORAM, however, raises the cost to∼17.6 bytes/block, demonstrating that the푑-ary tree is essential to keep local metadata overhead low (§ 4.3). Onyx-ORAM also achieves better storage amplification than both baselines across all evaluated datasets, only re- quiring 1.7–1.8× the disk footprint of the original plaintext dataset, compared to 2.1–3.8×for PathORAM and 7.5–7.7× for RingORAM. Storage amplification costs can vary across datasets, as푁may not tightly fit the ORAM tree capacity, requiring an additional level that is largely underutilized. A.3 End-to-End Oblivious ANN Search Throughput vs. latency. Figure 8 complements Figure 4 under the4-SSDconfiguration. Onyx achieves 2.2–7.4×lower latency and 2.2–7.3×higher throughput against Compass-in- TEE; 3.2–4.6×lower latency and 3.2–3.9×higher through- put against RingORAM + DiskANN; and 2.4–6.0×lower latency and 2.3–6.0×higher throughput against PathORAM + DiskANN. Throughput vs. recall. Figure 8 shows the throughput- vs-recall results under4-SSD. The trends are similarly con- sistent: 2.1–7.3×against Compass-in-TEE, 2.6–4.0×against RingORAM + DiskANN, and 2.2–6.0×against PathORAM + DiskANN across all datasets and recall targets. A.4 Co-design Ablation (4-SSD) Figure 9 complements Figure 6. The same co-design insights from § 6.4 apply: on small-vector datasets (SIFT, DEEP), the ORAM optimization remains the primary driver, while on large-vector datasets (MS-MARCO, WIKI) both components contribute. The gaps are modestly smaller under4-SSDas additional SSD resources reduce the I/O bottleneck. A.5 Onyx-ANNS Ablation Figure 10 compares the throughput vs. latency of Onyx- ANNS with various pruning hint sizes, DiskANN (DA), and naive decoupling when each is combined with Onyx-ORAM. Naive decoupling, which uses small in-memory traver- sal hints to prune the candidates list, fails to improve over DiskANN on three of four datasets: it is 25–27% slower on SIFT and DEEP, and roughly matches DiskANN on MS- MARCO. The in-memory hints are too coarse to effectively prune candidates, barely reducing bandwidth (1.0–1.3×, Ta- ble 2) while nearly doubling the access count (+72–99%). Only on WIKI, where vectors are large enough to yield a 2.2×bandwidth reduction, does naive decoupling outper- form DiskANN (1.7×). Onyx-ANNS resolves this by introducing pruning hints that progressively reduce bandwidth without significantly increasing access count (+5–15%). As pruning hint size in- creases, bandwidth savings grow and throughput improves: for instance, on MS-MARCO, increasing hints from 64 B to 256 B improves throughput from 4.8 to 14.9 QPS (4.5× over DiskANN). The effect is most pronounced on datasets 17 Throughput (QPS) Latency (ms) Throughput (QPS) Recall (a) SIFT(b) MARCO(c) WIKI(d) DEEP Figure 8. (Top) Pareto frontier of throughput vs. latency of Onyx and baselines (4-SSD; top-left is better). Dots below the curves represent sub-optimal parameterizations; single markers are the configuration for a scheme that maximizes both latency and throughput. (Bottom) Throughput vs. recall of Onyx and baselines (4-SSD). Throughput (QPS) (a) SIFT(b) MS-MARCO (c) WIKI(d) DEEP Latency (ms) Figure 9. ORAM-ANN co-design ablation (4-SSD). Pareto frontier of throughput vs. latency for Onyx and single- component (Onyx-ORAM and Onyx-ANN) constructions. Better configurations are towards the top-left. with large vectors (MS-MARCO 4.5×, WIKI 2.8×) where the bandwidth reduction is largest (3.8–5.0×, § 5.4), but Onyx- ANNS also improves on smaller-vector datasets (SIFT 1.2×, DEEP 1.1×). Without increasing memory footprint beyond what naive decoupling or DiskANN requires, Onyx-ANNS consistently achieves the best throughput-latency tradeoff. B Index Construction Hyperparameters Onyx Index (DiskANN). Onyx builds on DiskANN [105], which constructs a Vamana proximity graph on disk. All indices use a build search list size of퐿=128, L2 distance, and 32-bit floating-point vectors. The max graph degree is푅=32 for all datasets except MS-MARCO, which uses 푅=64. For pruning hints, we sweep over multiple hint sizes per dataset and select the best configuration: SIFT uses 16, 32, 64 B; MS-MARCO uses 64, 128, 256 B; WIKI uses 192, 256, 384 B; and DEEP uses 48, 64, 96 B. Compass Index (HNSW + PQ). Compass indices were built using the authors’ Faiss fork [7], which constructs an HNSW graph for traversal and uses the same PQ codes [48] as DiskANN for in-memory traversal hints. For Compass datasets, we used the same parameters as the paper [131]: 푀=64 andefConstruction=80 for SIFT-1M and푀= 128 andefConstruction=200 for MS-MARCO. For our benchmarks, we useefConstruction=200 and푀=64, which means the maximum graph degree is 2푀= 128. C Dynamic ANN Index In this section, we discuss how Onyx-ANNS’s decoupled index layout can be applied to FreshDiskANN [99] to support dynamic indices with insertions and deletions. 18 Throughput (QPS) Latency (ms) (a) SIFT(b) MS-MARCO(c) WIKI(d) DEEP Figure 10. Onyx-ANNS ablation (1-SSD). Each curve varies the search queue depth (smallest QD value); other labeled values are pruning hint sizes. Pareto frontiers highlight the best-performing configurations for each approach. FreshDiskANN Update Primitives. FreshDiskANN’s dy- namic updates are built from two primitives:GreedySearch andRobustPrune. At a high level,GreedySearchtraverses the graph to find a candidate list of nearby nodes, while RobustPrunetakes a target node together with such a candi- date list and selects which candidates should be neighbors of the target. Concretely,RobustPruneprocesses candidates in increasing order of approximate distance (using in-memory traversal hints) to the target vector푞. When it keeps a candi- date푝, it removes any later candidate푝 ′ that is already well covered by푝, i.e., wheneverdist(푥 푝 ,푥 푝 ′ ) ≤ 훼 · dist(푥 푞 ,푥 푝 ′ ) . Here,훼>1 is the usual slack parameter that improves graph connectivity and convergence [99]. Insertions. With these primitives, insertion is straight- forward in Fresh-DiskANN. For a new point, we first run GreedySearchto find nearby nodes, and then runRobustPrune to choose its outgoing neighbors while maintaining the max- imum out-degree. We then try to add reverse edges from those selected neighbors back to the new point by rerunning RobustPrune on each affected neighborhood. Deletions. Deletions are trickier because every node that points to the deleted point must be updated, and there may be many such nodes. As in prior dynamic graph indices, this repair is handled lazily and in batches. In the back- ground, the system streams through the dataset, identifies points whose neighborhoods contain deleted nodes, uses the neighbors of the deleted nodes as repair candidates, and rerunsRobustPruneto rebuild those neighborhoods. Batch- ing amortizes the cost of this full streaming pass over many deletions. Cost benefit of Onyx-ANNS layout. In both cases, the external-storage cost is heavily dominated by fetching neigh- bor information for the relevant candidates. With the Onyx- ANNS decoupled layout, this requires fetching only adja- cency lists together with pruning hints, which fit in much smaller blocks. In contrast, in coupled designs such as DiskANN and Compass, the neighbor information is stored together with the full-precision vectors, so accessing only the graph metadata still requires fetching the entire larger block. Con- cretely, for WIKI-20M, this translates to performing an equal number of accesses but with 384-byte blocks as opposed to 3.2 KB blocks with the coupled baseline. Writeback via eviction. The updated neighborhoods also need to be written back to external storage. This can naturally be piggybacked on the ORAM eviction procedure, as ORAM necessitates that every block that is accessed must be written back. D Onyx-ORAM Protocol The Onyx-ORAM protocol is summarized in Algorithm 2. It relies on read helpers in Algorithm 3 and write helpers in Algorithm 4. Notation. The ORAM tree has arity푑, depth퐿, bucket capacity푍, dummy slots푆, and eviction frequency퐴(one eviction per퐴accesses).푃(ℓ,푖)denotes the bucket at level푖 on the root-to-leaf path to leafℓ.Stashis the client-local stash of blocks not yet written back, and퐺is the global access counter.ReverseDigits 푑,퐿 (푥)reverses the퐿-digit base-푑 representation of푥, yielding the reverse-lexicographic evic- tion order. Position map. The position mapPosMapmaps each block address푎to a triple(leaf, lvl, slot):PosMap[푎].leafis the as- signed leaf,PosMap[푎].lvlis the tree level of the bucket cur- rently holding block푎(or⊥if the block is in the stash), and PosMap[푎].slotis the logical slot index within that bucket (or⊥if in the stash). The cached(lvl, slot)allow ReadPath to locate the target block directly: at the matching level it reads the known slot, and at all other levels it reads the next unread dummy. Bucket layout on disk. Each bucket푏on disk consists of 푍+푆individually encrypted slots, denoteddisk[푏][0..푍+푆−1]. Each slot encrypts a pair(addrs, data): for real blocks,addrs is the block address; for dummies,addrs=⊥. Decrypting a 19 slot yields both the address and the data. During eviction, the entire bucket is read or written as a single I/O; during a regular access, ReadBlock fetches a single block. Per-bucket local metadata. Each bucket푏has metadata Meta[푏] stored locally at the ORAM client, consisting of: • A monotonic version counter ver. •A pseudorandom permutationptrs[0..푍+푆−1]mapping logical slot indices to physical slot offsets on disk. Logical slots 0..푍−1 correspond to real block slots and푍..푍+푆−1 to dummy slots. • Per-slot validity bitsvalid[0..푍+푆−1], all set to 1 after a write. A bit is cleared when the corresponding slot is read. •A dummy counterdummy, initialized to 0 after each write. The next dummy slot is at physical offsetptrs[푍+dummy]. •A total access countercount, initialized to 0 after each write. An early reshuffle is triggered whencountreaches 푆 (i.e., this bucket has been accessed 푆 times). Authenticated encryption. All slots are protected by an authenticated encryption (AE) scheme with associated data (instantiated with AES-GCM [69]) using a global secret key sk. We writeEnc(푏,푘,푥)andDec(푏,푘, ct)for AE encryption and decryption of physical slot푘 ∈ [푍+푆]in bucket푏. The associated data for AEAD isaad= (푏∥푘∥ Meta[푏].ver), binding each ciphertext to its bucket index푏, physical slot offset푘, and the bucket’s current versionver. This prevents the adversary from replaying, reordering, or substituting ciphertexts across slots, buckets, or versions. Every slot read from disk—whether it contains a real block or a dummy—is integrity-verified via the AEAD tag; this ensures the ad- versary cannot cause selective failures that depend on the block’s identity. If any integrity check fails, the protocol aborts immediately. E Eviction Analysis for 푑-ary RingORAM This section proves Theorem 3. The analysis builds directly on the stash analysis of RingORAM [88] (Section 4 of that work). We adopt the same notation:ORAM 푍,퐴 퐿 denotes a non-recursive Ring ORAM with퐿+1 levels, bucket size푍, and one eviction per퐴accesses, andORAM ∞,퐴 퐿 denotes the corresponding∞-ORAM with infinite bucket capacity. The only structural difference is that the tree is푑-ary instead of binary: each internal node has푑children, and the tree has푑 퐿 leaves. Eviction paths cycle through all푑 퐿 leaves in reverse-lexicographic order. The proof follows the same two-step structure as RingO- RAM. The first step (Lemmas 1 and 2 of [88]) establishes that the stash overflow probability ofORAM 푍,퐴 퐿 can be bounded by the probability that any rooted subtree inORAM ∞,퐴 퐿 is overloaded. These lemmas depend only on the tree structure and the greedy eviction algorithm, and hold unchanged for 푑-ary trees. The only difference is in the combinatorial bound on the number of rooted subtrees with푛nodes. In a푑-ary Algorithm 2 Onyx-ORAM Protocol Parameters: Tree-arity푑, bucket capacity푍, dummy slots 푆 , eviction frequency 퐴 Client state: Position mapPosMap, stashStash, per- bucket metadata Meta, round counter 퐺 Server state: Encrypted푑-ary tree of depth퐿with buckets of 푍 + 푆 slots 1: function Access(푎, op, data ′ ) 2: (leaf 푎 , lvl 푎 , slot 푎 ) ← PosMap[푎] 3:leaf ′ ← UniformRandom(0,푑 퐿 − 1) 4:PosMap[푎] ← (leaf ′ , ⊥, ⊥) 5:data← ReadPath(leaf 푎 , lvl 푎 , slot 푎 ) 6: if data=⊥ then data← remove 푎 from Stash 7: if op= write then data← data ′ 8:Stash← Stash∪(푎, leaf ′ , data) 9: 퐺 ← 퐺 + 1 10: if 퐺 mod 퐴= 0 then EvictPath() 11:EarlyReshuffle(leaf 푎 ) 12: if op= read then return data 13: function ReadPath(leaf 푎 , lvl 푎 , slot 푎 ) 14:data←⊥ 15: for 푖 ← 0 to 퐿 do 16:if 푖= lvl 푎 then 푗 ← slot 푎 17:else 푗 ←⊥ 18:offset← GetOffset(푃(leaf 푎 ,푖), 푗) 19:data ′ ← ReadBlock(푃(leaf 푎 ,푖), offset) 20:if data ′ ≠⊥ then data← data ′ 21: return data 22: function EvictPath 23: ℓ 푒 ← ReverseDigits 푑,퐿 (퐺/퐴 mod 푑 퐿 ) 24: for 푖 ← 0 to 퐿 do 25:Stash← Stash∪ ReadBucket(푃(ℓ 푒 ,푖)) 26: for 푖 ← 퐿 to 0 do 27:WriteBucket(푃(ℓ 푒 ,푖), Stash) tree, this count equals the푑-ary Catalan number 1 푛 푑푛 푛−1 . Us- ing 푑푛 푛−1 ≤ 푑푛 푛 ≤ (푒푑) 푛 (the last step via 푚 푘 ≤ (푒푚/푘) 푘 ), the subtree count is at most(푒푑) 푛 . This reduces to(2푒) 푛 for 푑=2, which is a slightly looser but simpler bound than the 4 푛 used in [88]. Concretely: Pr[st(푆 푍 )> 푅] ≤ ∑︁ 푛≥1 (푒푑) 푛 max 푇 :푛(푇)=푛 Pr[푋(푇)> 푐(푇)+ 푅], where푇ranges over rooted subtrees ofORAM ∞,퐴 퐿 ,푛(푇)is the number of nodes,푐(푇)= 푛(푇) · 푍is the capacity, and 푋(푇) is the number of blocks in푇 before post-processing. The second step is where the generalization to푑-ary trees matters: we must bound the expected bucket load퐸[푌(푏)] for each bucket 푏 in ORAM ∞,퐴 퐿 before post-processing. 20 Algorithm 3 Onyx-ORAM Read Helpers 1: function GetOffset(푏, 푗 ) 2: if 푗=⊥ then 3:푗 ← 푍 + Meta[푏].dummy 4:Meta[푏].dummy+= 1 5: else 6:Meta[푏].count+= 1 7: 푘 ← Meta[푏].ptrs[푗] 8:Meta[푏].valid[푗] ← 0 9: return 푘 10: function ReadBlock(푏, offset) 11: read block disk[푏][offset] from disk 12: (_, data) ← Dec(푏, offset, disk[푏][offset]) 13: if decryption fails then abort 14: return data 15: function ReadBucket(푏) 16: read bucket disk[푏] from disk 17: for 푗 ← 0 to 푍 + 푆− 1 do 18:푘 ← Meta[푏].ptrs[푗] 19: (addrs[푗], data[푗]) ← Dec(푏,푘, disk[푏][푗]) 20:if decryption fails then abort 21:blocks←∅ 22: for 푗 ← 0 to 푍 − 1 do 23:푘 ← Meta[푏].ptrs[푗] 24:if addrs[푗]≠⊥ and Meta[푏].valid[푗] then 25:푎 ← addrs[푗] 26:leaf 푎 ← PosMap[푎].leaf 27:blocks← blocks∪(푎, leaf 푎 , data[푗]) 28: return blocks Lemma 1 (Expected bucket load in푑-ary RingORAM). For any bucket푏 ∈ ORAM ∞,퐴 퐿 with a푑-ary tree, if푁 ≤ 퐴(푑−1) 2 ·푑 퐿 , then 퐸[푌(푏)] ≤ 퐴(푑−1) 2 . Proof. Leaf buckets. A leaf bucket푏contains blocks placed there by the last EvictPath through that leaf. There are at most푁distinct blocks, each mapped to푏independently with probability 푑 −퐿 . Thus 퐸[푌(푏)] ≤ 푁 ·푑 −퐿 ≤ 퐴(푑−1) 2 . Non-leaf buckets. Let푏be a bucket at level푖(0≤ 푖< 퐿) with푑children푐 1 , . . .,푐 푑 . Let푚 1 < 푚 2 < ·< 푚 푑 be the times of the last EvictPath operation through each child. Due to the deterministic reverse-lexicographic eviction order, a bucket at level푖is evicted every푑 푖 eviction operations, and consecutive children of푏are evicted푑 푖 eviction operations apart. Therefore푚 푑 −푚 1 =(푑− 1)·푑 푖 . We now count which blocks can reside in푏after the last eviction through푏(at time푚 푑 ). When a block is accessed and remapped, it gets time stamp푚 ∗ , which is the current eviction counter. Algorithm 4 Onyx-ORAM Write Helpers 1: function WriteBucket(푏, Stash) 2:select up to 푍 blocks from Stash assignable to 푏 3:let(푎 푗 , leaf 푗 , data 푗 ) 푍 ′ −1 푗=0 be the selected blocks 4:remove selected blocks from Stash 5:Meta[푏].ptrs← RandomPerm(0,푍+푆−1) 6:Meta[푏].ver+= 1 7: for 푗 ← 0 to 푍 + 푆− 1 do 8:푘 ← Meta[푏].ptrs[푗] 9:if 푗< 푍 ′ then 10:disk[푏][푘] ← Enc(푏,푘,(푎 푗 , data 푗 )) 11:else 12:disk[푏][푘] ← Enc(푏,푘,(⊥,⊥)) 13:Meta[푏].valid←1 푍+푆 14:Meta[푏].count← 0 15:Meta[푏].dummy← 0 16: for 푗 ← 0 to 푍 ′ − 1 do 17:PosMap[푎 푗 ].(lvl, slot) ← (level(푏), 푗) 18: write bucket disk[푏] to disk 19: function EarlyReshuffle(leaf) 20: for 푖 ← 0 to 퐿 do 21:if Meta[푃(leaf,푖)].count= 푆 then 22:Stash← Stash∪ ReadBucket(푃(leaf,푖)) 23:WriteBucket(푃(leaf,푖), Stash) •Blocks with timestamp푚 ∗ ≤ 푚 1 : all푑children have been evicted after these blocks were created, so these blocks have been pushed to a child or deeper. They are not in 푏. •Blocks with timestamp푚 ∗ > 푚 푑 : these were created after the last eviction through푏and have not yet been processed. They are not in 푏. • Blocks with timestamp푚 푗 < 푚 ∗ ≤ 푚 푗+1 for some 1≤ 푗 ≤ 푑 −1: during the eviction at time푚 푑 , EvictPath reads푏and writes it back, pushing blocks as deep as possible along the eviction path. Blocks mapped to chil- dren푐 푗+1 , . . .,푐 푑 (whose evictions at푚 푗+1 , . . .,푚 푑 occur after the block was created) are pushed to those children. However, blocks mapped to children푐 1 , . . .,푐 푗 (whose last evictions at푚 1 , . . .,푚 푗 occurred before the block was cre- ated) cannot be pushed further, because EvictPath only pushes blocks along the current eviction path, and children 푐 1 , . . .,푐 푗 are not on the eviction paths at times푚 푗+1 , . . .,푚 푑 . These blocks remain in 푏. For blocks in the third case with푚 푗 < 푚 ∗ ≤ 푚 푗+1 : the number of accesses in this window is퐴·(푚 푗+1 −푚 푗 )= 퐴·푑 푖 , and each block is mapped to one of푐 1 , . . .,푐 푗 ’s subtrees with 21 probability 푗 ·푑 −(푖+1) . Summing over all 푗 from 1 to 푑− 1: 퐸[푌(푏)]= 푑−1 ∑︁ 푗=1 퐴·푑 푖 · 푗 ·푑 −(푖+1) = 퐴 푑 푑−1 ∑︁ 푗=1 푗 = 퐴 푑 · (푑− 1)푑 2 = 퐴(푑− 1) 2푑 = 퐴(푑− 1) 2 □ With Lemma 1 in hand, the remainder of the proof follows RingORAM [88] exactly, with푎= 퐴(푑−1)/2 replacing푎= 퐴/2 and(푒푑) 푛 replacing 4 푛 . For any rooted subtree푇with 푛= 푛(푇)nodes,퐸[푋(푇)] ≤ 푛· 푎. Since the block indicators 푋 푖 (푇)are independent (each determined by a fresh random leaf assignment), the Chernoff bound gives: Pr[푋(푇)> 푐(푇)+ 푅] ≤ 푎 푍 푅 · 푒 −푛 푍 ln(푍/푎)+푎−푍 . Let푞= 푍 ln(푍/푎)+ 푎− 푍 −1− ln푑. Substituting into the union bound with the(푒푑) 푛 subtree count and summing the geometric series: Pr[st(푆 푍 )> 푅] ≤ ∑︁ 푛≥1 푎 푍 푅 · 푒 −푞푛 = (푎/푍) 푅 1−푒 −푞 . The stash overflow probability decreases exponentially in푅 whenever푞>0, which completes the proof of Theorem 3. □ F Security Proof Proof of Theorem 2. We prove indistinguishability via a se- quence of hybrids. Let 휆 denote the security parameter. Hybrid퐻 0 . The real security game (Figure 11) with se- cret bit푏. The challenger runsSetup(I 푏 )and executes each operation표 푖,푏 onI 푏 . The adversary observes physical disk addresses and ciphertexts for each storage access, and can respond arbitrarily to any access request. Hybrid퐻 1 : challenger aborts on any tampering. Iden- tical to퐻 0 except that the challenger aborts (and the adver- sary loses) whenever the adversary returns a ciphertext for slot(푏,푘, ver)that the challenger did not produce for that slot.퐻 0 ≈ 푐 퐻 1 because each slot is encrypted with authen- ticated encryption using associated data(푏∥푘∥ ver)that uniquely identifies the bucket, physical offset, and version (a monotonic counter incremented on every bucket write). The challenger validates every response against this associated data and aborts if verification fails. Thus, the challenger not aborting even on seeing a tampered ciphertext would imply breaking the INT-CTXT property [10] of authenticated en- cryption, which happens with negligible probability. This means that in퐻 1 , the adversary can only win by following the protocol faithfully, returning exactly the ciphertexts the challenger wrote for each slot. Its only remaining informa- tion channel is the pattern of physical disk addresses. Interfaces. • Setup(I): initializeANNSon indexIusing public parameters param. •Requests are drawn from the public API in § 3, namely Search(푥 푞 ,푘),Insert(푝,푥 푝 ), andDelete(푝). During any such operation, whenever the protocol issues an external storage read or write, the request is sent to A, which observes the access trace and may return an arbitrary response. If any operations outputs abort due to integrity checks, the challenger aborts and the adversary loses. Game. 1. Challenger samples a uniformly random bit푏 ∈ 0,1. 2.The adversary chooses two equally sized datasets퐷 0 and퐷 1 and one set of public parametersparam. The challenger constructs the corresponding indexI 푏 and runs ANNS.Setup(I 푏 ). 3. The adversary iterates adaptively. At step푖, it chooses a pair of operations(표 푖,0 ,표 푖,1 ), potentially based on all prior observations, subject to the constraint that표 푖,0 and표 푖,1 have the same operation type. The challenger then executes the corresponding operation표 푖,푏 onI 푏 . 4. Adversary outputs a guess 푏 ′ and wins if 푏 ′ =푏. Figure 11. Security game for disk-access privacy for a disk- resident ANN search system ANNS. Hybrid퐻 2 : replace ciphertexts with encryptions of ze- ros. Identical to퐻 1 except that every ciphertext written to disk encrypts a fixed string 0 퐵 (where퐵is the slot size) instead of the real payload(addrs, data). The challenger now maintains the entire ORAM tree on disk internally, so that it can follow the same access patterns as in퐻 1 ; only the plaintext inside each ciphertext visible to the adversary changes. Since each slot is encrypted with a fresh random- ness,퐻 0 ≈ 푐 퐻 1 by IND-CPA security of authenticated en- cryption [10]. Hybrid퐻 3 : switch to the other world. Identical to퐻 2 ex- cept the challenger runsSetup(I 푏 ′ )and executes표 푖,푏 ′ (where 푏 ′ =1− 푏). This switch is well-defined because the secu- rity game requires표 푖,0 and표 푖,1 to have the same operation type and|퐷 0 |= |퐷 1 |, so the challenger can execute the푏 ′ - world operations using the same public parameters. Since all ciphertexts encrypt 0 퐵 and the adversary must follow the protocol faithfully (from퐻 2 ), the only observable difference between퐻 2 and퐻 3 is the pattern of physical disk addresses. We show this pattern is identically distributed by arguing that neither the ANN layer nor the ORAM layer introduces data-dependent disk accesses. 22 ANN layer: logical access pattern is data-oblivious. The num- ber of ORAM accesses and the access granularity per opera- tion depends only on param and the operation type: • Setup writes 2푁logical blocks (푁per ORAM instance), where 푁=|퐷 0 |=|퐷 1 |. • Searchmakes exactly퐿logical reads of block size|N|+ |H prn | from the traversal ORAM and퐿 prn logical reads of block size|F|from the refinement ORAM (Algorithm 1). InsertandDeletealso make similar logical accesses based on static public parameters (Appendix C). Since표 푖,0 and표 푖,1 have the same operation type (by the game’s constraint), the logical access sequences in퐻 2 and 퐻 3 have the same length. ORAM layer: physical access pattern is data-oblivious. We walk through each subroutine that issues disk I/O and show that the physical addresses depend only on the ORAM’s random coins and public state, not on which logical blocks are accessed: •ReadPath (Algorithm 2): reads one slot per level on path 푃(leaf 푎 ,0), . . .,푃(leaf 푎 ,퐿). The leafleaf 푎 was drawn uni- formly at random from[푑 퐿 ]when the block was last writ- ten, independent of block identity. At each level, the phys- ical slot offset is determined by the local pseudorandom permutationptrsstored inside the TEE, invisible to the adversary. Whether the target block or a dummy is read, the adversary sees a single slot read at a random offset. •EvictPath (Algorithm 2): the eviction leaf is computed deterministically from the public access counter퐺via ReverseDigits 푑,퐿 . At each level, the entire bucket is read and then written back—the I/O pattern is fixed and inde- pendent of bucket contents. • EarlyReshuffle (Algorithm 4): triggers whencount= 푆 for a bucket on the accessed path. The countercountis public (it equals the number of times the bucket has been accessed since its last reshuffle, which the adversary can track). The reshuffle reads and writes the full bucket, a fixed I/O pattern. The two ORAM instances (traversal and refinement) use independent keys, position maps, and random coins, so the argument applies to each instance separately, and their joint access trace is identically distributed in 퐻 2 and 퐻 3 . 퐻 2 ≡ 퐻 3 : the physical access pattern and all ciphertexts are identically distributed. Hybrid퐻 4 : restore real ciphertexts for world푏 ′ . Identi- cal to퐻 3 except ciphertexts now encrypt the real payloads for world푏 ′ . By the same IND-CCA2 argument as퐻 0 ≈ 푐 퐻 1 , we have퐻 3 ≈ 푐 퐻 4 . Note that퐻 4 is exactly the security game with secret bit 푏 ′ . Conclusion. 퐻 0 ≈ 푐 퐻 1 ≈ 푐 퐻 2 ≡ 퐻 3 ≈ 푐 퐻 4 , where퐻 0 is the game with bit푏and퐻 4 is the game with bit 1−푏. Therefore Pr[푏 ′ =푏] ≤ 1 2 + negl(휆).□ 23