arXiv CSopen access

Onyx: Cost-Efficient Disk-Oblivious ANN Search

Onyx: Cost-Efficient Disk-Oblivious ANN Search Deevashwer Rathee∗

Jean-Luc Watson

Zirui Neil Zhao

UC Berkeley, NVIDIA

NVIDIA

UT Austin, NVIDIA

G. Edward Suh

Raluca Ada Popa

NVIDIA

UC Berkeley

arXiv:2604.20401v1 [cs.CR] 22 Apr 2026

Abstract

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 approaches, a practical alternative is to rely on hardware assumptions 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 principle, the solution is simple: run Compass [131], the state-ofthe-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 different ANN-ORAM co-design for the disk setting that significantly 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 challenge for efficient oblivious ANN search over SSDs is balancing 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 network, combines an access-count-efficient ANN (reducing network round-trips) with a bandwidth-efficient ORAM (reducing communication bandwidth), but each primitive aggressively trades off the other resource. The ANN layer fetches larger blocks to reduce accesses, wasting bandwidth due to

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 diskbased 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 bandwidthintensive accesses without hurting recall, and Onyx-ORAM proposes a locality-aware shallow tree design that reduces access count while remaining compatible with bandwidthefficient 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.

1

prunes the majority of bandwidth-intensive full-precision accesses without hurting recall. This reduces ANN bandwidth 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 combinations 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 latency with 90% top-10 recall, serving over 8M queries/dollar.

Oblivious ANN Search: Compass [OSDI’25] Client

Untrusted Server

Query

ANN Search

ORAM Network

ORAM Storage

>1 s latency, 100 queries/$ Compass-in-TEE Untrusted Server

Client TEE

Query

ORAM Storage

ANN Search

ORAM

SSD

Network CPU

CPU

CPU

CPU

SSD

160 ms latency, high CPU and SSD requirement Onyx: cost-efficient ANNS and ORAM co-design Untrusted Server

Client TEE

Query

Onyx-ANNS

Onyx-ORAM

ORAM Storage

SSD

Network CPU

~12 ms latency, ~70 QPS, low resource requirements

Figure 1. Prior designs for oblivious ANNS and Onyx. Compass [131] suffers from poor performance due to high network 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 resource utilization, yielding high performance and low cost.

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

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 fundamental 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 design. 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 savings. To address both, we propose two new co-designed primitives. Onyx-ANNS (§ 5) retains the low memory footprint and accesses required for disk-hosted indices, while introducing a compact intermediate representation that proactively

Motivation: Private Disk-hosted ANN Search

We discuss two deployment scenarios where cost and scalability necessitate private disk-hosted ANN indices. Scenario I: Enterprise Knowledge Bases. This scenario targets enterprise applications (e.g., RAG for internal semantic 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. Applications 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 II: 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., Microsoft Recall [73], Gemini Personal Intelligence [38]), where highly sensitive personal information such as browsing history, messages, and documents is consolidated into per-user indices. The combination of privacy, low latency, and scalability 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 network round trips. To achieve the interactive latencies required by real-time agents, confidential computing within clouds offers a natural solution. In this architecture, keeping 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

logic and data in TEE-protected memory, and for cost efficiency (§ 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 components running inside the TEE trust boundary: a bandwidthefficient ANN search engine (Onyx-ANNS) and an accesscount-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 external 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 OnyxORAM’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).

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 recovery 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 keyword search, recent work FiT [50] focuses on access pattern leakage during semantic search, showing that page-level accesses (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

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 index I, initialize both ORAMs over the index and load in-memory index state. • R ← Search(𝑥𝑞 , 𝑘): Given the query embedding vector 𝑥𝑞 , returns the keys R 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 memory and two on-disk ORAM-protected layouts. • Inside TEE (protected memory). (i) ANN metadata and the start node for graph traversal, (ii) following prior work [105, 131], highly compressed in-memory traversal hints Htrv for approximate distance computation during search, and (iii) ORAM client state for both ORAM instances (e.g., position maps, stashes, keys). • Outside TEE (external storage, untrusted). The full index is stored within two separate ORAM instances: (i) a

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 3

traversal ORAM holding per-node blocks consisting of adjacency lists N concatenated with compact pruning hints Hprn , and (ii) a refinement ORAM holding full-precision embedding vectors F .

These are the subject of an orthogonal line of work on improving enclave implementations and mitigations. For example, controlled-channel attacks can be mitigated by hardwareassisted 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 improved design—we therefore focus exclusively on disk access pattern leakage. We also assume that an orthogonal rollback protection mechanism (e.g., monotonic counters or distributed freshness protocols [3, 68, 103]) prevents the adversary from replaying stale state from the persistent storage. The query type is public and not hidden by our system.

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.2 3.1

Threat Model

Formalizing Security

We formalize the privacy guarantees of Onyx through an indistinguishability-based security game. We give a highlevel description here and defer the full specification to Figure 11 (Appendix F). Let ANNS denote a disk-resident ANN search system that executes within a TEE and accesses an untrusted storage interface through ORAM, with public parameters param. At a high level, the challenger C executes 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 adversary A plays the role of the malicious host and untrusted storage. Whenever the protocol issues an external storage access, the request is sent to A, 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 distinguish which of the two worlds the challenger is executing. If the challenger aborts at any point, the adversary loses.

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 inside 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 adversary 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 manipulate 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 storage 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 channels [75, 122], branch prediction attacks [32, 59], controlledchannel 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 leakage [33, 60], physical attacks [19, 27, 58, 70, 95], remoteattestation attacks [19, 27, 95], and denial-of-service attacks.

Definition 1. We say that a disk-resident ANN search system ANNS provides disk-access privacy if no non-uniform probabilistic polynomial-time adversary A can win the security game in Figure 11 (Appendix F) with probability nonnegligibly 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 mediated through ORAM, which guarantees data-oblivious accesses with confidentiality and integrity given authenticated encryption [10]. Onyx-ORAM builds on RingORAM [88], and the changes we introduce (§ 4.3) preserve all the protocol 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 indistinguishable. We provide the full proof in Appendix F. □ 4

4

Onyx-ORAM

Access count

Bandwidth

4.1

Background: RingORAM

RingORAM

≈ 52 · log(𝑁 )

≈ 3 · log(𝑁 )

PathORAM (ℓ = 2)

≈ log(𝑁 )

≈ 12 · log(𝑁 )

PathORAM (ℓ = 3)

≈ 23 · log(𝑁 ) ≈ 13 · log(𝑁 )

≈ 18.5 · log(𝑁 )

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) without 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 map PosMap to a random leaf and resides 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 ·𝐿 and Bandwidth ≈ 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

Onyx-ORAM

≈ 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 OnyxORAM, we propose reducing tree depth directly by using a 𝑑-ary tree, which cuts depth and access count by ℓ = log2 𝑑× while remaining compatible with large buckets. 𝑑-ary trees were introduced over a decade ago [34] but fell out of use: although 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 observation is that in a 𝑑-ary tree, although evictions are (𝑑−1)× more frequent, the number of dummy slots per bucket decreases 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 evictions 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). Additionally, the 𝑑-ary tree with fewer dummies reduces storage amplification by 4×, further improving cost-efficiency. Table 1 summarizes the I/O multipliers of Onyx-ORAM vs prior work: Onyx-ORAM improves PathORAM (ℓ = 3) access count by 2× while reducing its bandwidth by 4.6×.

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

4.3

Construction

Recall the access count multiplier for RingORAM from § 4.1
is AccessCount ≈ 2 + 𝑍𝐴+1 · 𝐿, where 𝑍 is the bucket capacity, 𝐴 is the eviction frequency, and 𝐿 = log2 𝑁 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 𝐿 = log2 𝑁 to ≈ 𝐿/3 by switching to a wider, shallower tree. Crucially, the depth reduction is only effective 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 perbucket 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 proportionally 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. RingORAM’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 to AccessCount ≈ (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 from log2 𝑁 to log𝑑 𝑁 and the access count by a factor of log2 𝑑. The trade-off is more frequent evictions: we generalize RingORAM to 𝑑-ary trees and found that evictions must be (𝑑−1)× more frequent to keep the stash bounded (§ 4.4). Since the tree has log2 𝑑 fewer levels, one would naïvely expect eviction bandwidth to increase by (𝑑−1)/log2 𝑑, or about 2.3× for 𝑑 = 8. For RingORAM’s large buckets, however, reducing 𝐴 has the benefit of proportionally reducing 𝑆 and the dummy padding, which added significant bandwidth pressure. This offsets the higher eviction frequency, 𝑑+1 reducing the net bandwidth increase to roughly 3 log 𝑑 ×,

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× access 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, evictions would still issue 𝑍 individual reads per bucket, and the 𝑑 −1 𝑍 /𝐴 access count term (which increased 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 bandwidth from (2𝑍 +𝑆)/𝐴 to (2𝑍 +2𝑆)/𝐴 per level, making bandwidth more sensitive to the dummy padding 𝑆. In a 𝑑-ary tree, 𝑆 shrinks proportionally with 𝐴, which reduces this pressure and actually ends up decreasing eviction bandwidth by ≈ 1.1× when we go from 𝑑 = 2 to 𝑑 = 8.

2

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 implementation). RingORAM and PathORAM are each limited by one of the two multipliers (RingORAM by access count, PathORAM by bandwidth) and both lie beyond the 6K QPS zone. Onyx-ORAM (𝑑 = 8) reduces both multipliers simultaneously, 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 reverselexicographic eviction order and all other protocol invariants. 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.

5.1

Background: DiskANN

DEEP

WIKI

Bandwidth (reduction)

Decoupling Onyx-ANNS

1.1× 2.7×

1.0× 5.0×

1.3× 2.0×

2.2× 3.8×

Access Count (increase)

Decoupling Onyx-ANNS

+91% +8%

+99% +5%

+72% +9%

+43% +15%

them to the beam. Since F is prefetched alongside N , the system 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 𝑁 )× (Table 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 undoing 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 approach 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 hints Htrv , 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 issue with naive decoupling is that it leverages in-memory hints for two tasks with very different precision requirements. Traversal can tolerate coarse hints because it only needs directional accuracy to move toward the query’s neighborhood. Graph connectivity corrects suboptimal local choices through convergent paths. Pruning, in contrast, is a sensitive filtering step where a mistakenly excluded true neighbor

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.

Onyx-ANNS

MARCO

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).

Theorem 3 (Stash overflow in 𝑑-ary RingORAM). Consider 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−𝑒 −𝑞 .

5

SIFT

Onyx-ANNS builds on DiskANN [105], a graph-based algorithm 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 list N (𝑝) and full-precision coordinates F (𝑝) packed together in a contiguous block on disk, so that both can be fetched efficiently with one I/O. Per-vector quantized hints Htrv (𝑝) [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 explored concurrently: for each candidate 𝑝, the system fetches the combined block N (𝑝) ∥F (𝑝) from disk, scores newly discovered neighbors using the in-memory hints Htrv , and adds 7

Index layout. Onyx-ANNS reorganizes DiskANN’s ondisk layout: N (𝑝) ∥Hprn (𝑝) are packed together (fetched during traversal), while F (𝑝) is stored separately (fetched only during refinement). Pruning hints Hprn are constructed using product quantization [48] at a higher fidelity than Htrv ; we choose |Hprn | per dataset to maximize bandwidth reduction. Only the traversal hints Htrv are stored in memory. Memory footprint. Since traversal and refinement blocks are now stored separately on disk, they require two independent 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 is Htrv ), 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 simplified Algorithm 1) are selected by approximate distance dist(𝑥𝑞 , Htrv (·)). For each, the system fetches N (𝑝) ∥Hprn (𝑝) from disk in a single I/O. Newly discovered neighbors are scored using Htrv and the beam is updated. Traversal continues until exactly 𝐿 nodes have been visited. This phase makes 𝐿 accesses, each of size |N | + |Hprn | bytes. Phase 2: Pruning (lines 7–8). The 𝐿 candidates are reranked using the prefetched pruning hints Hprn , 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 |.

is permanently lost, requiring higher precision. To address this mismatch, we introduce compact pruning hints Hprn , an intermediate representation that is substantially more precise than Htrv 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 list N whenever a node is visited during traversal, keeping the DRAM footprint unchanged. Three-step granular refinement. This yields a threestep granular refinement strategy (traverse → prune → refine) where traversal fetches much smaller blocks (N ∥Hprn rather than N ∥F ) and the majority of expensive full-precision fetches are avoided, all without increasing the memory footprint. 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 hints Htrv in memory, per-vector concatenation of pruning hints Hprn and neighbor indices N on external storage, and full precision coordinates F on external storage Output: Indices of the 𝐾-approximate nearest neighbors 1: L ← {𝑠}, V ← ∅

⊲ Candidate and visited lists // Phase 1: Traversal 2: while L \ V ≠ ∅ do 3: let 𝑝 ∗ ← arg min𝑝 ∈ L\V dist(𝑥𝑞 , Htrv (𝑝)) 4: fetch N (𝑝 ∗ ) ∥Hprn (𝑝 ∗ ) from external storage 5: update L ← L ∪ N (𝑝 ∗ ) and V ← V ∪ {𝑝 ∗ } 6: sort L by dist(𝑥𝑞 , Htrv (·)) and set L ← L [: 𝐿]

5.4

Analysis

The total access count is 𝐿 + 𝐿prn (vs. DiskANN’s 𝐿). The per| N |+| F | BWDiskANN access bandwidth ratio is: BW = 𝐿prn Onyx-ANNS ( | N |+| Hprn | )+

𝐿

·| F|

Two terms in the denominator determine the improvement: 𝐿 (|N | + |Hprn |), 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 | + |Hprn |) is large, since the numerator is dominated by |F | while the denominator remains small. Second, when |Htrv | 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 |/|Htrv | ≥ 64. MS-MARCO benefits 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.

// Phase 2: Pruning 7: sort L by dist(𝑥𝑞 , Hprn (·)) using pruning hints 8: set Lprn ← L [: 𝐿prn ] ⊲ Pruned candidate list

// Phase 3: Refinement 9: for each candidate 𝑝 ∈ Lprn do 10: fetch 𝑥 𝑝 ← F (𝑝) from external storage 11: sort Lprn by dist(𝑥𝑞 , F (·)) using full precision vectors 12: set R ← Lprn [: 𝐾] and return R

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 algorithm 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. 8

Dataset

#Vectors

Index Size

Vector Size

Hint Size

SIFT MARCO WIKI DEEP

1M 8.8M 20M 60M

0.6 GB 29 GB 64 GB 31 GB

512 B 3072 B 3072 B 384 B

8B 32 B 96 B 32 B

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 the 4-SSD configuration 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 committed 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.

Table 3. Datasets used in our evaluation. Index size corresponds to the plain graph index (full precision vectors + adjacency lists). Hint size refers to the in-memory hints, significantly compressed to minimize DRAM footprint.

6

Evaluation

ORAM Parameters. For large-bucket ORAMs (RingORAM and Onyx-ORAM), we set the early reshuffle rate to 0.1%. For RingORAM, we vary the bucket capacity 𝑍 between 32 and 128, after which point, the large 𝑍 capacity 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 𝑍 between 128 and 1024. For a given capacity 𝑁 , we pick the 𝑍 value that minimizes memory and storage overhead. Following 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.

We answer the following questions in this section: • Q1: Onyx-ORAM (§ 6.2). How does Onyx-ORAM perform against state-of-the-art tree-based ORAMs like RingORAM 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 benefit 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

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 refinement, we fix 𝐿 to match the coupled baseline and vary 𝐿prn until we achieve the same recall. We vary the beam width over {4, 8, 16} for 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) over {1, 2, . . . , 8} to measure the throughputvs-latency trade-off. For throughput-vs-recall plots, we limit the total number of visited nodes to ≤ 1500.

Experimental Setup

Datasets. We evaluate Onyx on both deployment scenarios 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 allocated 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 construction hyperparameters used in Appendix B.

6.2

Hardware Configuration. We run our experiments on a machine with an AMD EPYC 9554 Processor, with AMD SEVSNP [51] enabled, and Micron 7450 MAX SSDs [71] attached through vfio-pci. We partition our evaluation setup into resource units (RUs) using cgroups, 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,

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 baseline 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 accesscount-bound: even at small block sizes, its throughput plateaus 9

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 number of parallel requests, beamwidth configurations, and pruning hintsizes to measure the end-to-end performance (latency and throughput) of each ANN search system on a 1-SSD instance; better configurations are located towards the topleft 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 (a) Throughput vs. block size (b) Throughput vs. latency (512 B) substantial lead: 4.0–4.5× lower latency and 3.6–4.5× higher throughput than RingORAM + DiskANN, and 2.5–9.5× lower Figure 3. Onyx-ORAM vs prior work for 20M blocks latency and 2.5–9.5× higher throughput than PathORAM (1-SSD). LBM (local bucket metadata), FBR (full bucket + DiskANN. Under 4-SSD configuration, additional SSD rereads), ST (shallow tree) refer to steps in § 4.3; Onyx: sources help the baselines narrow the gap, particularly at the Ring+LBM+FBR+ST-8; Ring: RingORAM; Path: localityhigh end—shrinking to 7.4× against Compass-in-TEE, 6.0× optimized PathORAM. against PathORAM + DiskANN, and 3.9× against RingORAM + DiskANN—but a significant gap remains as the higher access counts and bandwidth of the baselines carry proportionaround 2K QPS because the high access count per logical opally higher compute overhead, and the workload becomes eration saturates the SSD’s IOPS. On the other hand, PathOcompute-bound (Appendix A.3). RAM is bandwidth-bound: its throughput degrades with inOnyx’s improvement is largest where its ANN search creasing block size, falling below RingORAM at 1 KB blocks. At very large block sizes, Onyx-ORAM also becomes bandwidth- achieves the greatest bandwidth reduction: in particular, searches over MS-MARCO benefit from a 5× reduction (§ 5.4) bound and matches the performance of RingORAM because given its highly compressed hints and large full-precision they have similar bandwidth overheads (Table 1). vectors. For MS-MARCO and WIKI, RingORAM + DiskANN Throughput vs. latency (Figure 3(b)). We evaluate the is the strongest baseline because these datasets use large throughput-latency tradeoff for Onyx and baselines with blocks (over 3 KB) from their large embedding vectors, where the addition of several intermediate design points activating bandwidth-efficient RingORAM excels. On DEEP, PathOthe techniques from § 4.3. At 512 B, the maximum traversal RAM + DiskANN performs best as its small 512 B blocks block size Onyx-ANN uses, Onyx-ORAM achieves up to 5.1× favor PathORAM’s lower access count. For SIFT, Compass-inhigher throughput and 2.7× lower latency than RingORAM, TEE is most competitive: it uses a larger number of neighbors and up to 3.4× higher throughput and 2.0× lower latency and higher beam width to reduce roundtrips, which is effecthan PathORAM. In sequence, enabling local bucket metative on small, localized graphs like 1M-vector SIFT, but bedata (LBM), full bucket reads (FBR), and shallow trees with comes wasteful on larger graphs. In all cases, Onyx achieves various 𝑑-arities yield better performance, following the an2.3–4.5× lower latency and 2.3–4.4× higher throughput over alytical results in Figure 2 (§ 4.4). Onyx-ORAM uses each of the best baseline for each dataset. these optimizations and a 𝑑 = 8-ary tree, which both analytThroughput vs. recall. Figure 4 shows throughput-vsically and experimentally yields the best tradeoff between recall across each dataset on a 1-SSD instance. Onyx’s imbandwidth and access count overheads. provement is consistent across all recall targets: against Compass-in-TEE, we demonstrate throughput improvements 6.3 End-to-End Oblivious ANN Search of 2.1–13.0× across datasets and recall targets; against RingOWe compare Onyx against Compass-in-TEE—the state-ofRAM + DiskANN, 2.7–5.2×; and against PathORAM + DiskANN, the-art oblivious ANN search system Compass [131] de2.3–10.2×. The per-dataset trends mirror the latency-throughput ployed inside a TEE to hide disk accesses. For each system, analysis above—the same factors that favor each baseline at we issue queries from the dataset’s query set with {1, 2, 4, 8} 90% recall carry over to other recall targets—and in all cases, parallel requests and measure throughput and latency at Onyx achieves 2.1–4.7× higher throughput than the best each concurrency level. Compass was designed for oblivibaseline for each dataset. ous access over a network and the Compass-ANN design Memory and storage. Table 4 summarizes memory and was not specifically optimized for disk; to provide stronger storage footprint for hosting each dataset. PathORAM with baselines, we consider two additional combinations with DiskANN exhibits the lowest footprint, as it does not store DiskANN: RingORAM + DiskANN, which replaces Compassany bucket metadata. Onyx uses only 10–30% more memory, ANN with DiskANN [105], and PathORAM + DiskANN, because its decoupled search architecture (§ 5.3) requires two which further replaces RingORAM with locality-optimized ORAM clients (one for traversal blocks, one for refinement 10

Throughput (QPS) Throughput (QPS)

Latency (ms)

Recall (a) SIFT

(b) MARCO

(c) WIKI

(d) DEEP

Queries/$

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).

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 footprint 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 because 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: OnyxORAM paired with DiskANN, and Onyx-ANN paired with either RingORAM or PathORAM. In every case, Onyx provides 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) Onyx Compass-in-TEE RingORAM+DiskANN PathORAM+DiskANN

0.17 0.16 0.21 0.13

0.76 0.99 0.73 0.61

2.39 2.93 2.39 2.16

2.99 3.84 2.57 2.31

Storage (GB) Onyx Compass-in-TEE RingORAM+DiskANN PathORAM+DiskANN

1.5 12.5 5.5 1.4

58.2 776.3 239.7 108.2

170.6 1361 515 208.5

76.9 706.4 271.4 70.7

lower throughput than Onyx because DiskANN’s large peraccess 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

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 advantage of Onyx, normalizing throughput by cost using public GCP pricing data (§ 6.1). For each scheme, we sweep over various resource allocations – vCPU counts in {1, 2, 3, 4} and SSD slices in {1, 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 observed 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.

Throughput (QPS)

Table 4. Memory and storage overhead of Onyx and baselines across our evaluation datasets.

(a) SIFT

(b) MS-MARCO

(c) WIKI

(d) DEEP

Cost Efficiency

Latency (ms)

7

Figure 6. Importance of ORAM-ANN co-design: pareto frontier of throughput vs. latency for Onyx and singlecomponent (Onyx-ORAM/ANN) constructions. Better configurations are towards the top-left; single markers indicate a scheme’s latency- and throughput-optimal configuration.

Related Work

Private nearest neighbor search. A number of cryptographic 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. Unlike 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 seminal 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

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, OnyxANN’s bandwidth reduction provides only a small additional benefit because DiskANN already uses small block sizes and Onyx-ORAM becomes access-count-bound. Path + OnyxANNS outperforms Ring + Onyx-ANNS because PathORAM is more access-optimized, and its higher bandwidth overhead is offset by Onyx-ANN’s bandwidth savings. On MSMARCO and WIKI which have large vectors, both components matter equally: Onyx-ORAM + Disk sees 2.8–4.5× 12

client-server model [23, 88, 89, 94, 101, 119, 131], hardware enclaves [14, 26, 31, 74, 91, 108, 128], and multi-server settings [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 private information retrieval. We focus on tree-based ORAM, but our access-optimized design is also compatible with hierarchical ORAMs [5, 83] since they also use bandwidthefficient large bucket designs like RingORAM. Disk-based ANN search. Disk-based ANN search includes both graph-based [105] and clustering-based [16, 29, 48] approaches. We focus on graph-based designs, in particular DiskANN [105], which is widely deployed in industry [25, 42, 46, 84, 107, 110, 113] and has been extended to filtered search [36], streaming updates [99, 120], low-memory operation [82], parallel indexing [67], and distributed indices [2]. These designs optimize for the plain-SSD regime where bandwidth is cheap and access count is the bottleneck; 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, motivated by ORAM’s 𝑂 (log 𝑁 )× bandwidth amplification (§ 5). Bandwidth efficiency has also been explored for in-memory ANN [126], which reduces memory bandwidth through incremental 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.

[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: Rollback 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. FutORAMa: 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 construction. [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. Shielding 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: Towards 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 Secure 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: Highlyefficient 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 Interposition. In 47th IEEE Symposium on Security and Privacy (IEEE S&P ’26).

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 security 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, Broadcom, 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. 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 Attacks 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 Accurate 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 Bottleneck 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 Computation. 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 Harsha Vardhan Simhadri. 2023. Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. In WWW. ACM, 3406–3416. [37] Michael T. Goodrich and Michael Mitzenmacher. 2011. PrivacyPreserving 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 Computation 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: Ramification, 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 Amsaleg. 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://www.amd.com/content/ dam/amd/en/documents/epyc-business-docs/white-papers/SEVSNP-strengthening-vm-isolation-with-integrity-protection-andmore.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 Science). 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 Memory 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) (Lecture 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://www.kernel.org/doc/html/latest/core-api/dmaapi.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 Symposium. 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 Approximate 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 Performance 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 Eisenbarth, Ingrid Verbauwhede, and Jo Van Bulck. 2025. BadRAM: Practical Memory Aliasing Attacks on Trusted Execution Environments. In SP. IEEE, 4117–4135. [71] Micron. 2023. Micron 7450 MAX NVMe SSD. https://www.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-stepswith-recall-aa03f8a0-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 Association. [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 Indexing. 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://www.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 Symposium. 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 Computer Society, 198–217. [90] Enes Sahin. 2024. Does ChatGPT Use RAG? A Developer’s Perspective on Retrieval in Real-World Systems. https://learningdaily.dev/does-chatgpt-use-rag-a-developersperspective-on-retrieval-in-real-world-systems-939c57d401f8. Accessed April 2026. [91] Sajin Sasy, Sergey Gorbunov, and Christopher W. Fletcher. 2018. ZeroTrace : 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

[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 Association, 1167–1186. [113] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai 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. InPlace 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. ControlledChannel Attacks: Deterministic Side Channels for Untrusted Operating 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

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 Jayaram Subramanya, and Jingdong Wang. 2022. Results of the NeurIPS’21 Challenge on Billion-Scale Approximate Nearest Neighbor 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: Efficient 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 Approach 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 SideChannel Attacks. CoRR abs/1712.08519 (2017). [105] Suhas Jayaram Subramanya, Devvrit, Harsha Vardhan Simhadri, Ravishankar 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 PostgreSQL. https://github.com/timescale/pgvectorscale. [108] Afonso Tinoco, Sixiang Gao, and Elaine Shi. 2023. EnigMap: ExternalMemory 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, Krishnan Sundaram, Samer Boshra, Balachandar Perumalswamy, Shivam Atri, Martin Chisholm, Revti Raman Singh, Greg Yang, Tamara Hass, Nitesh Dudhey, Subramanyam Pattipaka, Mark Hildebrand, Magdalen 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.

16

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 requiring 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.

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. OpenReview.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

A.3

Additional Evaluation Results

This appendix contains additional evaluation results, including the 4-SSD variants 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 PathORAM. The throughput gains are smaller than under 1-SSD (5.1× and 3.4×) because the baselines were I/O-bottlenecked and benefit from the extra SSD resources; the gap nevertheless persists because they become compute-bound (§ 6.3).

Throughput vs. recall. Figure 8 shows the throughputvs-recall results under 4-SSD. The trends are similarly consistent: 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 under 4-SSD as additional SSD resources reduce the I/O bottleneck. A.5

(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: localityoptimized PathORAM. A.2

End-to-End Oblivious ANN Search

Throughput vs. latency. Figure 8 complements Figure 4 under the 4-SSD configuration. Onyx achieves 2.2–7.4× lower latency and 2.2–7.3× higher throughput against Compass-inTEE; 3.2–4.6× lower latency and 3.2–3.9× higher throughput against RingORAM + DiskANN; and 2.4–6.0× lower latency and 2.3–6.0× higher throughput against PathORAM + DiskANN.

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 17

Onyx-ANNS Ablation

Figure 10 compares the throughput vs. latency of OnyxANNS with various pruning hint sizes, DiskANN (DA), and naive decoupling when each is combined with Onyx-ORAM. Naive decoupling, which uses small in-memory traversal 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 MSMARCO. The in-memory hints are too coarse to effectively prune candidates, barely reducing bandwidth (1.0–1.3×, Table 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 outperform 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 increases, 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

Throughput (QPS) Throughput (QPS)

Latency (ms)

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). DEEP 1.1×). Without increasing memory footprint beyond what naive decoupling or DiskANN requires, Onyx-ANNS consistently achieves the best throughput-latency tradeoff.

Throughput (QPS)

B

(a) SIFT

(b) MS-MARCO

(c) WIKI

(d) DEEP

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 and efConstruction = 80 for SIFT-1M and 𝑀 = 128 and efConstruction = 200 for MS-MARCO. For our benchmarks, we use efConstruction = 200 and 𝑀 = 64, which means the maximum graph degree is 2𝑀 = 128.

Latency (ms)

Figure 9. ORAM-ANN co-design ablation (4-SSD). Pareto frontier of throughput vs. latency for Onyx and singlecomponent (Onyx-ORAM and Onyx-ANN) constructions. Better configurations are towards the top-left.

C with large vectors (MS-MARCO 4.5×, WIKI 2.8×) where the bandwidth reduction is largest (3.8–5.0×, § 5.4), but OnyxANNS also improves on smaller-vector datasets (SIFT 1.2×,

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 dynamic updates are built from two primitives: GreedySearch and RobustPrune. At a high level, GreedySearch traverses the graph to find a candidate list of nearby nodes, while RobustPrune takes a target node together with such a candidate list and selects which candidates should be neighbors of the target. Concretely, RobustPrune processes candidates in increasing order of approximate distance (using in-memory traversal hints) to the target vector 𝑞. When it keeps a candidate 𝑝, it removes any later candidate 𝑝 ′ that is already well covered by 𝑝, i.e., whenever dist(𝑥 𝑝 , 𝑥 𝑝 ′ ) ≤ 𝛼 · dist(𝑥𝑞 , 𝑥 𝑝 ′ ). Here, 𝛼 > 1 is the usual slack parameter that improves graph connectivity and convergence [99]. Insertions. With these primitives, insertion is straightforward in Fresh-DiskANN. For a new point, we first run GreedySearch to find nearby nodes, and then run RobustPrune to choose its outgoing neighbors while maintaining the maximum 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 background, the system streams through the dataset, identifies points whose neighborhoods contain deleted nodes, uses the neighbors of the deleted nodes as repair candidates, and reruns RobustPrune to rebuild those neighborhoods. Batching amortizes the cost of this full streaming pass over many deletions.

with the full-precision vectors, so accessing only the graph metadata still requires fetching the entire larger block. Concretely, 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 ℓ. Stash is 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 eviction order.

Cost benefit of Onyx-ANNS layout. In both cases, the external-storage cost is heavily dominated by fetching neighbor information for the relevant candidates. With the OnyxANNS decoupled layout, this requires fetching only adjacency 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 19

Position map. The position map PosMap maps each block address 𝑎 to a triple (leaf, lvl, slot): PosMap[𝑎].leaf is the assigned leaf, PosMap[𝑎].lvl is the tree level of the bucket currently holding block 𝑎 (or ⊥ if the block is in the stash), and PosMap[𝑎].slot is 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, denoted disk[𝑏] [0..𝑍 +𝑆−1]. Each slot encrypts a pair (addrs, data): for real blocks, addrs is the block address; for dummies, addrs = ⊥. Decrypting a

Algorithm 2 Onyx-ORAM Protocol

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.

Parameters: Tree-arity 𝑑, bucket capacity 𝑍 , dummy slots 𝑆, eviction frequency 𝐴 Client state: Position map PosMap, stash Stash, perbucket metadata Meta, round counter 𝐺 Server state: Encrypted 𝑑-ary tree of depth 𝐿 with buckets of 𝑍 + 𝑆 slots

Per-bucket local metadata. Each bucket 𝑏 has metadata Meta[𝑏] stored locally at the ORAM client, consisting of: • A monotonic version counter ver. • A pseudorandom permutation ptrs[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 bits valid[0..𝑍 +𝑆−1], all set to 1 after a write. A bit is cleared when the corresponding slot is read. • A dummy counter dummy, initialized to 0 after each write. The next dummy slot is at physical offset ptrs[𝑍 +dummy]. • A total access counter count, initialized to 0 after each write. An early reshuffle is triggered when count reaches 𝑆 (i.e., this bucket has been accessed 𝑆 times).

′

1: function Access(𝑎, op, data ) 2: 3: 4: 5: 6: 7: 8: 9: 10:

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 write Enc(𝑏, 𝑘, 𝑥) and Dec(𝑏, 𝑘, ct) for AE encryption and decryption of physical slot 𝑘 ∈ [𝑍 +𝑆] in bucket 𝑏. The associated data for AEAD is aad = (𝑏 ∥ 𝑘 ∥ Meta[𝑏].ver), binding each ciphertext to its bucket index 𝑏, physical slot offset 𝑘, and the bucket’s current version ver. 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 adversary cannot cause selective failures that depend on the block’s identity. If any integrity check fails, the protocol aborts immediately.

E

11: 12:

(leaf𝑎 , lvl𝑎 , slot𝑎 ) ← PosMap[𝑎] leaf ′ ← UniformRandom(0, 𝑑 𝐿 − 1) PosMap[𝑎] ← (leaf ′, ⊥, ⊥) data ← ReadPath(leaf𝑎 , lvl𝑎 , slot𝑎 ) if data = ⊥ then data ← remove 𝑎 from Stash if op = write then data ← data′ Stash ← Stash ∪ {(𝑎, leaf ′, data)} 𝐺 ←𝐺 +1 if 𝐺 mod 𝐴 = 0 then EvictPath() EarlyReshuffle(leaf𝑎 ) 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: 18: 19: 20: 21:

else 𝑗 ← ⊥ offset ← GetOffset(𝑃 (leaf𝑎 , 𝑖), 𝑗) data′ ← ReadBlock(𝑃 (leaf𝑎 , 𝑖), offset) if data′ ≠ ⊥ then data ← data′ return data

22: function EvictPath 23: ℓ𝑒 ← ReverseDigits𝑑,𝐿 (𝐺/𝐴 mod 𝑑 𝐿 ) 24: for 𝑖 ← 0 to 𝐿 do 25: Stash ← Stash ∪ ReadBucket(𝑃 (ℓ𝑒 , 𝑖))

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, and ORAM𝐿∞,𝐴 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 RingORAM. The first step (Lemmas 1 and 2 of [88]) establishes that the stash overflow probability of ORAM𝑍,𝐴 𝐿 can be bounded by the probability that any rooted subtree in ORAM𝐿∞,𝐴 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

26: 27:

for 𝑖 ← 𝐿 to 0 do 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 (𝑆𝑍 ) > 𝑅] ≤ (𝑒𝑑)𝑛 max Pr[𝑋 (𝑇 ) > 𝑐 (𝑇 ) + 𝑅], 𝑛≥1

𝑇 :𝑛 (𝑇 )=𝑛

where 𝑇 ranges over rooted subtrees of ORAM𝐿∞,𝐴 , 𝑛(𝑇 ) 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

Algorithm 4 Onyx-ORAM Write Helpers

1: function GetOffset(𝑏, 𝑗) 2: 3: 4: 5: 6: 7: 8: 9:

1: function WriteBucket(𝑏, Stash)

if 𝑗 = ⊥ then 𝑗 ← 𝑍 + Meta[𝑏].dummy Meta[𝑏].dummy += 1 else Meta[𝑏].count += 1 𝑘 ← Meta[𝑏].ptrs[ 𝑗] Meta[𝑏].valid[ 𝑗] ← 0 return 𝑘

2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:

10: function ReadBlock(𝑏, offset) 11: read block disk[𝑏] [offset] from disk 12: (_, data) ← Dec(𝑏, offset, disk[𝑏] [offset]) 13: 14:

13: 14: 15: 16:

if decryption fails then abort 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: 21: 22: 23: 24: 25: 26: 27: 28:

17: 18:

select up to 𝑍 blocks from Stash assignable to 𝑏 ′ let (𝑎 𝑗 , leaf 𝑗 , data 𝑗 )𝑍𝑗=0−1 be the selected blocks remove selected blocks from Stash Meta[𝑏].ptrs ← RandomPerm(0, 𝑍 +𝑆−1) Meta[𝑏].ver += 1 for 𝑗 ← 0 to 𝑍 + 𝑆 − 1 do 𝑘 ← Meta[𝑏].ptrs[ 𝑗] if 𝑗 < 𝑍 ′ then disk[𝑏] [𝑘] ← Enc(𝑏, 𝑘, (𝑎 𝑗 , data 𝑗 )) else disk[𝑏] [𝑘] ← Enc(𝑏, 𝑘, (⊥, ⊥)) Meta[𝑏].valid ← {1}𝑍 +𝑆 Meta[𝑏].count ← 0 Meta[𝑏].dummy ← 0 for 𝑗 ← 0 to 𝑍 ′ − 1 do PosMap[𝑎 𝑗 ].(lvl, slot) ← (level(𝑏), 𝑗) write bucket disk[𝑏] to disk

19: function EarlyReshuffle(leaf) 20: for 𝑖 ← 0 to 𝐿 do

if decryption fails then abort blocks ← ∅ for 𝑗 ← 0 to 𝑍 − 1 do 𝑘 ← Meta[𝑏].ptrs[ 𝑗] if addrs[ 𝑗] ≠ ⊥ and Meta[𝑏].valid[ 𝑗] then 𝑎 ← addrs[ 𝑗] leaf𝑎 ← PosMap[𝑎].leaf blocks ← blocks ∪ {(𝑎, leaf𝑎 , data[ 𝑗])} return blocks

21: 22: 23:

if Meta[𝑃 (leaf, 𝑖)].count = 𝑆 then Stash ← Stash ∪ ReadBucket(𝑃 (leaf, 𝑖)) 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 children 𝑐 𝑗+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 created) 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 𝑏.

Lemma 1 (Expected bucket load in 𝑑-ary RingORAM). For any bucket 𝑏 ∈ ORAM𝐿∞,𝐴 with a 𝑑-ary tree, if 𝑁 ≤ 𝐴(𝑑2−1) ·𝑑 𝐿 , then 𝐸 [𝑌 (𝑏)] ≤ 𝐴(𝑑2−1) . 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 𝐸 [𝑌 (𝑏)] ≤ 𝑁 · 𝑑 −𝐿 ≤ 𝐴(𝑑2−1) . 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.

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

Interfaces. • Setup(I): initialize ANNS on index I using public parameters param. • Requests are drawn from the public API in § 3, namely Search(𝑥𝑞 , 𝑘), Insert(𝑝, 𝑥 𝑝 ), and Delete(𝑝). 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 parameters param. The challenger constructs the corresponding index I𝑏 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 𝑜𝑖,𝑏 on I𝑏 . 4. Adversary outputs a guess 𝑏 ′ and wins if 𝑏 ′ = 𝑏.

𝑑 −1 ∑︁

𝐴 𝑗 𝑑 𝑗=1

𝐴 (𝑑 − 1)𝑑 𝐴(𝑑 − 1) 𝐴(𝑑 − 1) = = = · 𝑑 2 2𝑑 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

Figure 11. Security game for disk-access privacy for a diskresident ANN search system ANNS.

Security Proof

Proof of Theorem 2. We prove indistinguishability via a sequence of hybrids. Let 𝜆 denote the security parameter.

Hybrid 𝐻 2 : replace ciphertexts with encryptions of zeros. 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 randomness, 𝐻 0 ≈𝑐 𝐻 1 by IND-CPA security of authenticated encryption [10].

Hybrid 𝐻 0 . The real security game (Figure 11) with secret bit 𝑏. The challenger runs Setup(I𝑏 ) and executes each operation 𝑜𝑖,𝑏 on I𝑏 . 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. Identical to 𝐻 0 except that the challenger aborts (and the adversary 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 authenticated 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 encryption, 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 information channel is the pattern of physical disk addresses.

Hybrid 𝐻 3 : switch to the other world. Identical to 𝐻 2 except the challenger runs Setup(I𝑏 ′ ) and executes 𝑜𝑖,𝑏 ′ (where 𝑏 ′ = 1 − 𝑏). This switch is well-defined because the security 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 number of ORAM accesses and the access granularity per operation depends only on param and the operation type: • Setup writes 2𝑁 logical blocks (𝑁 per ORAM instance), where 𝑁 = |𝐷 0 | = |𝐷 1 |. • Search makes exactly 𝐿 logical reads of block size |N | + |Hprn | from the traversal ORAM and 𝐿prn logical reads of block size |F | from the refinement ORAM (Algorithm 1). Insert and Delete also 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 leaf leaf𝑎 was drawn uniformly at random from [𝑑 𝐿 ] when the block was last written, independent of block identity. At each level, the physical slot offset is determined by the local pseudorandom permutation ptrs stored 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 independent of bucket contents. • EarlyReshuffle (Algorithm 4): triggers when count = 𝑆 for a bucket on the accessed path. The counter count is 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 𝑏 ′ . Identical 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[𝑏 ′ = 𝑏] ≤ 12 + negl(𝜆). □

23