1 Introduction↩︎

Large language models (LLMs) are ubiquitous in everyday tools and services, powering interactive assistants, chatbots, and other conversational AI systems. As LLMs are often used to process highly sensitive inputs, including proprietary documents, personal communications, and security-critical prompts, naively entrusting LLM usage to a cloud service provider (CSP) creates various privacy concerns [1]–[5]. Ensuring that user prompts and AI-generated responses remain unobservable to CSP or other malicious users on CSP (thus, confidential) during cloud-based LLM inference is paramount for maintaining user trust and meeting legal and ethical data protection standards.

To address these concerns, LLM serving is rapidly adopting Trusted Execution Environments (TEEs) [6]–[8]. TEEs provide hardware-isolated environments that encrypt memory and restrict address access requests, ensuring that computations inside a confidential virtual machine (CVM) remain inaccessible even to the cloud provider. CVMs protect model weights, KV caches, and user prompts, and can be verified through remote attestation [7]–[9]. Building on CVMs, GPU vendors have also introduced GPU TEE support (also called confidential computing) tailored to large-scale confidential LLM inference [10], including NVIDIA Hopper H100/H200 [11] and Blackwell (e.g., B200 [12]). With this hardware foundation maturing, major technology companies are beginning to assemble complete confidential LLM inference stacks; Microsoft, Meta, and Google are integrating CPU and GPU TEEs into end-to-end frameworks that enforce privacy guarantees [10], [13], [14]. For example, Meta’s recently announced “Private Processing” framework  [13] uses confidential computing to deploy LLM-powered features (e.g., summarization of WhatsApp messages [15]) while ensuring that sensitive user data remains invisible to the underlying cloud provider and even Meta itself. Taken together, these efforts signal the emergence of a new baseline: an LLM serving pipeline in which confidentiality is guaranteed by hardware-enforced TEEs. Under this model, a malicious cloud LLM operator or hypervisor cannot recover the user prompt, intermediate states, or generated responses, achieving end-to-end privacy for practical large-scale deployments. ¹

However, even with CVMs, one component of the LLM serving pipeline remains a source of information leakage: tokenizer. A tokenizer splits the prompt into a sequence of short vocabulary terms (called tokens). Tokenizer’s memory access patterns, if observed by adversaries, can leak the prompts (more details about the adversaries in Section 3.1) [16]–[25]. CVMs only protect memory content and the computations on data but they do not protect against address pattern leakage. In this work, we target the byte-pair encoding (BPE)-style sub-word tokenizers, which are widely used in many modern decoder-only LLMs [26]–[29]. BPE tokenizers use a vocabulary and merge table, together with hash-based dictionary lookups, to map raw prompt text into a sequence of token identifiers (tokenIDs). The tokenizer relies on a hash map with a randomized seed chosen at initialization of the LLM serving process. Once constructed, the mapping from tokens to vocabulary table entries (hence the memory addresses) remains fixed for the lifetime of the inference engine. A malicious/compromised hypervisor can leverage page faults and cache side channels to correlate observed address traces with lookups under this fixed mapping for a given prompt (more details in Section 3.2). Without additional protection, the address patterns of tokenizer memory accesses can leak the prompt’s content, even though data remains encrypted in TEE memory. This attack is different from token-length based attacks [1], [30], where an adversary infers prompt characteristics from prompt length. In contrast, address pattern leakage enables deterministic prompt reconstruction.

LLM tokenizer is not a hypothetical attack vector. Recent work, TDXRay [31], demonstrates an end-to-end prompt-reconstruction attack on Intel TDX by tracking the tokenizer memory accesses, achieving over 90% reconstruction similarity across different model families. The tokenizer is therefore a high-fidelity prompt-reconstruction channel that survives the TEE protections deployed to prevent it. TDXRay discuss oblivous map as a mitigation ncadidate but finds the straightforward implementation prohibitive on the tokenizer path (53–369\(\times\) overhead), leaving an efficient oblivious tokenizer an open problem.

Prior works [32]–[34] demonstrated side-channel leakage in embedding layers on recommendation systems and LLMs, showing that memory access patterns in embedding table lookups can reveal sensitive inputs. Embedding layers, however, operate on tokenIDs generated by tokenization, whereas the tokenizer directly processes raw user prompts before any model computation occurs. Leakage at the tokenizer stage, therefore, exposes fine-grained user content at the earliest stage in the LLM pipeline. Protecting against tokenizer leakage constitutes a distinct systems problem with different architectural constraints from embedding protection.

1.1 OTRO: Efficient and Oblivious Tokenization Path↩︎

In this work, we propose OTRO, an efficient and secure Oblivious Tokenization Path tailored to confidential LLM serving. Building on Oblivious RAM (ORAM), which hides access patterns by making any two logical access sequences of the same length computationally indistinguishable [35]–[37], we investigate whether ORAM-based tokenizer protection can be made practical at the system scale. Existing tree-based ORAM, such as PathORAM [36], is a widely adopted baseline for general-purpose ORAM with strong security guarantees. But tree-based ORAMs incur significant overhead for randomizing tokenizer accesses, as we demonstrate later. Tree-based ORAMs organize \(N\) entries into a logarithmic-depth hierarchy causing only poly-logarithmic overhead in theory. However, when embedded into tokenizer lookups, each token access must traverse an entire ORAM path and perform complex eviction. In our measurements, this translates into up to 58% higher TTFT relative to a non-oblivious baseline, unacceptable for latency-critical inference.

Figure 1 quantifies the cost of naive protection. At the per-access level (Figure 1 (a)), Square-root ORAM (SqrtORAM)’s single-block lookup averages only 3.2 \(\mu s\), 10 \(\times\) faster than PathORAM. When integrated into HuggingFace’s Tokenizers (Figure 1 (b)), PathORAM and naive SqrtORAM incur 13\(\times\) and 323\(\times\) tokenizer slowdowns respectively; the former from full tree path traversals with small lookups per tree node, the latter from rebuild cost dominating the runtime. Even GPU offloading shows a 276 \(\times\) slowdown, as BPE’s greedy merge causes severe control-flow divergence that defeats SIMD parallelism. Among all these, SqrtORAM stands out for one reason. Isolating its per-access cost from rebuilds reveals only 2.4\(\times\) overhead over baseline without any protection, which shows that the rebuild, not the oblivious lookup itself, is what makes naive SqrtORAM 323\(\times\) slower. This motivates our key question, can rebuild cost be removed from the critical path entirely?

Our key observation is that the tokenizer tables are read-only structures during inference. Square-root ORAM (SqrtORAM) is an existing approach that offers near-unprotected-baseline per-access cost with one drawback: SqrtORAM suffers from expensive \(O(N \log^2 N)\) rebuilds every \(\sqrt{N}\) accesses. OTRO eliminates rebuild overhead by constructing a pool of replicated read-only SqrtORAM instances and decoupling accesses from rebuilds via an epoch-based rotation policy. Each instance, after serving \(\sqrt{N}\) accesses (an epoch), goes offline for oblivious rebuild, while subsequent tokenizer requests are routed to a fresh instance. OTRO leaves tokenizer access patterns provably independent of the prompt content under a DRAM-trace adversary, revealing nothing about which vocab or merge entries are touched. Additionally OTRO pads each epoch to its \(\sqrt{N}\) boundary with dummy accesses, reducing the observable transcript to input prompt length, which is unavoidable in any ORAM design.

To further reduce the number of instances in a pool and hide rebuilds from the critical path, OTRO introduces chunked tokenization which overlaps the prefill of prompt chunks with the rebuild phase via incremental prefill over a shared KV cache. Together, these techniques convert the bursty rebuild cost of SqrtORAM into amortized background work, keeping ORAM-induced stalls off the LLM pipeline’s critical path and yielding an oblivious tokenizer that closely tracks non-oblivious TTFT. Our key contributions are:

2 Background↩︎

2.1 Trusted Execution Environment↩︎

Trusted Execution Environment (TEE, a.k.a., confidential computing) is a hardware-protected enclave that executes code and processes data with confidentiality and integrity via memory encryption and isolation  [38]–[40], protecting against privileged software (e.g., a malicious hypervisor) and physical attack. CVMs extend TEE protection to an entire VM, securing both the guest OS and its applications within a hardware-protected boundary [40]–[42]. Unlike process-scoped enclaves (e.g., Intel SGX [43]), CVMs avoid enclave size limits and paging overheads, supporting multi-TB memory for data-intensive workloads in most server-class CPUs [9], [40], [42], [44]–[46].

NVIDIA’s Hopper (H100) and Blackwell (B200, RTX Pro 6000) GPUs extend TEE protection to the GPU, providing device-rooted attestation [47] and per-VM isolated memory [11], [12]. Together, CPU and GPU TEEs form an end-to-end confidential stack over PCIe, and major providers including Meta, Microsoft, and Google are assembling production confidential LLM inference pipelines on top of this foundation [14], [15], [48]–[52]. TEEs are the most practical candidate for confidential LLM inference, as alternatives such as homomorphic encryption or MPC are too slow, and differential privacy cannot provide complete confidentiality against a malicious hypervisor.

2.2 LLM Tokenization↩︎

Tokenization converts human-readable text into discrete token identifiers (tokenIDs) in the LLM inference pipeline. Widely deployed decoder-only LLMs use byte-pair encoding [53] over altenatives such as WordPiece [54], and SentencePiece [55], as it handles rare and out-of-vocabulary words through iterative merging of frequent byte pairs. Our work focuses on BPE tokenizers using HuggingFace’s Tokenizers library [56] with further details in Section 3.2.

2.3 Oblivious Random Access Memory↩︎

Oblivious random access memory (ORAM) [35] is a cryptographic mechanism that conceals memory access patterns from an adversary observing the memory interface. ORAM guarantees that any two logical access sequences of the same length result in computationally indistinguishable physical access traces. Most ORAM constructions assume a client-server setting (Figure 2), in which a small trusted client maintains the ORAM metadata, while an untrusted server stores the encrypted data blocks. In the following sections, we explain two fundamental ORAM structures, square-root ORAM (SqrtORAM) and tree-based ORAM (PathORAM), using the following notations. \(N\) denotes the number of data blocks in ORAM, and \(\mathsf{stash}\) is the stash of the ORAM. For PathORAM, \(L\) is the depth of the ORAM tree, and \(Z\) is the number of blocks per bucket, which includes both the real blocks and dummy blocks. Lastly, \(\mathcal{P}(l)\) denotes the path \(l\) .

SqrtORAM stores \(N\) data blocks and \(\sqrt{N}\) additional dummy blocks in an encrypted array on the untrusted server. The client holds the pseudo-random function, (\(\mathsf{PRF}\)) \(\pi\) with key \(K_s\) and a \(\mathsf{stash}\) of size \(\sqrt{N}\). To access a block \(Block_a\), (1) the client performs a linear scan of \(\mathsf{stash}\); (2) if not found, the client performs \(\mathsf{PRF}(K_s, Block_{a})\) locally and generates a real access request to the main array; if found, the client performs \(\mathsf{PRF}(K_s, Block_{dummy})\) locally and generates a dummy access (indistinguishable from the server’s view) to the main array; (3) securely computes/updates the requested data block; (4) (re)inserts it into the \(\mathsf{stash}\); (5) at every \(\sqrt{N}\) logical accesses, an oblivious rebuild/reshuffle phase is triggered, shuffling all \(N+\sqrt{N}\) blocks into a freshly permuted array using an oblivious sorting or permutation network. Each access in SqrtORAM requires a single block transfer to the server, minimizing latency and bandwidth overheads, but the rebuilding phase incurs \(O(N\log^2N)\) work.

PathORAM organizes \(N\) data blocks into a binary tree of height \(L=\log(N)\), where each tree node is a bucket that can hold up to \(Z\) ORAM blocks on its untrusted server. Each node is always padded with dummy blocks to maintain \(Z\) ORAM blocks. The client manages a position map that records the leaf (i.e., tree path) currently assigned to each logical data block, and a small buffer called the \(\mathsf{stash}\). PathORAM access proceeds as follows: (1) look up the leaf \(\mathcal{P}(l)\) derived from the position map; (2) read the entire path \(\mathcal{P}(l)\) into the client and move the retrieved blocks into the \(\mathsf{stash}\); (3) securely compute/update the requested data block; )4) assign the block a fresh random leaf and update the position map; (5) evict blocks from the \(\mathsf{stash}\) along \(\mathcal{P}(l)\) within the bucket capacity limit. Because each access transfers a full root-to-leaf path, PathORAM’s bandwidth and per-access eviction logic, which require write-back into the \(\mathcal{P}(l)\), can dominate when accesses are small and frequent (as in tokenizer-table lookups).

3 Leakage from Tokenizer Execution Path↩︎

In this section, we focus on how the tokenizer’s execution path becomes a concrete source of information leakage even when LLM inference is protected by TEEs. We begin by formalizing the threat model, then we present a motivating example that illustrates how input-dependent behaviors in the tokenizer expose structural access patterns. Finally, we evaluate naive defenses and show that the overhead is incompatible with latency-sensitive LLM serving.

3.1 Threat Model↩︎

Figure 3 illustrates the system topology for confidential LLM serving. The CPU TEE hosts the CVM protecting the guest OS, NVIDIA driver, software stacks including PyTorch, and tokenizer; the GPU TEE securely stores model weights and activations in on-package HBM. HBM is treated as part of the trusted computing base because of its tight physical integration within the GPU package [57], eliminating any observability into access patterns within the HBM and GPU L2 cache. This is consistent with existing TEE deployments which assume the integrity of the CPU and GPU SoC packages. Additionally, all traffic between CPU TEE, DRAM, and GPU TEE over PCIe is encrypted and authenticated.

Under this architecture, we adopt the standard threat model for CPU and GPU TEEs [6], [12], [14], assuming an adversary controlling the full software stack with physical access to the cloud server. With these capabilities, the adversary can mount software-based attacks (page fault-controlled channels and prime-and-probe cache attacks) to observe DRAM access patterns at cache line granularity [16], [25], [31] and can snoop the DRAM bus directly to obtain address-level access patterns [58], [59]. The adversary can perform a calibration phase of chosen queries to the tokenizer, correlating traces across many inputs to localize the memory regions and layouts of tokenizer tables, even under per-process hash randomization. This calibration is demonstrated as the one-time token-localization stage of TDXRay [31] where it recovers the table layout offline using crafted prompts. Therefore, we conservatively assume the tokenizer table layout is known to the adversary, and layout obscurity provides no meaningful protection against access-pattern leakage.

We distinguish two leakage channels. Fine-grained access-pattern leakage: a malicious hypervisor observing DRAM traces can reveal which specific vocabulary and merge-table entries were accessed, enabling exact prompt reconstruction (Section 3.2). Coarse length-based leakage: BPE table-lookup count, observable through ORAM access count, scales linearly with prompt byte length which is unavoidable in any practical ORAM deployment; hiding it would require padding every request to the maximum context length, incurring prohibitive overhead. OTRO targets the first channel as the more severe threat of exact reconstruction. The remaining input prompt length can be addressed independently through request length bucketing.

3.2 Case Study: Leakage in BPE Tokenizer↩︎

Compared to the largely branch-free, matrix-multiplication-dominated computation inside transformer blocks, the tokenizer is a branch-heavy, table-driven component that operates directly on the raw user prompt. Each input character or byte triggers conditional logic, hash lookups, and iterative merge decisions. This combination of rich control flow and prompt-dependent memory accesses makes the tokenizer an especially attractive target for side-channel attacks: leakage at this stage directly reveals the user’s original text, rather than intermediate embeddings or internal activations. We next explain the tokenizer process with a simple example and identify the source of leakage in it.

Figure 5 illustrates the workflow of the BPE tokenizer, consisting of the encoder step (Figure 5 (a)) and the BPE merge algorithm (Figure 5 (b)). The goal of the tokenizer in this example is to tokenize the input string "tiktoken is a fast BPE tokeniser." The BPE tokenizer in Figure 5 (a) takes the following steps. First, the pre-tokenization step takes our example input string and breaks it down into tokenizer-manageable pieces; in our example in Figure 5 (a), it is broken into per-word segments. The per-word segment is shown in the central tile of Figure 5 (a). Each word is preceded by an "_" to indicate the start of the word segment.

The next step is the encoder step (step 3). This step looks up the vocab table, which holds the learned vocabulary and its corresponding tokenIDs. For example, common words such as "fast" hit in the vocab table. But uncommon words such as "tiktoken" are not present in the vocab table. We illustrate which words hit and miss in the vocabulary table in the center tile of the figure under each word.

Upon failure to find a valid token in the vocab table for words, such as "tiktoken", BPE tokenizer builds a list of tokenIDs that together approximate the target word. This step is where the BPE algorithm has to access the vocabulary table repeatedly to merge short tokens into longer tokens using multiple merge passes. We illustrate that step next.

Figure 5 (b) shows the algorithm execution path for tokenizing the word "_BPE". The word is first split into individual characters where each character is treated as a token. The tokenizer algorithm finds a pair of adjacent tokens (characters) with the lowest rank, as illustrated by the numerical values in the merge table (greedy path selection), at each merge pass, and merges these two tokens into a single token. Importantly, each merge modifies the current token sequence, which in turn changes the set of adjacent candidate pairs considered in subsequent passes. As a result, the merge-table lookups are inherently dynamic; after each merge, newly formed adjacent pairs must be queried against the merge table, while previously valid pairs may become invalid. Consequently, the set of merge-table queries at pass \(k+1\) cannot be determined before completing pass \(k\), making the merge procedure inherently sequential. The word "_BPE" is decomposed into the base symbols of "_", "B", "P", and "E". Then, the algorithm consecutively chooses the adjacent pairs "_+B" and "P+E", as they have the lowest ranks in the merge table (426 and 1687, respectively). BPE merges stop when there are no mergeable pairs, which is denoted by \(2^{32}-1\).

Consider the series of access requests shown in Figure 4 that is derived from the examples in Figure 5 (b), for the input word "_BPE." Given that the model’s vocabulary and merge tables are fixed, each observed lookup address can be mapped back to a concrete entry (a vocab token or a merge-pair with a specific rank) using an offline address-to-entry map. The vocabulary accesses reveal that the initial base symbols were materialized during the execution (e.g., "_", "B", "P", and "E"). Also, the merge-table accesses reveal the candidate adjacent pairs examined at each step (e.g., "_+B", "B+P", and "P+E"); the selected merge can be inferred from the subsequent update-dependent accesses (e.g., "_B+P" is the next pass’s changed set of candidate pairs that were probed).

With these observations, an adversary can reconstruct the word by replaying the deterministic BPE procedure. In the first merge pass, the tokenizer probes the merge-table entries, namely "_+B", "B+P", and "P+E", which let an observer recover the ranks of these candidates. Although the trace does not explicitly label which candidate was chosen, the chosen merge can be inferred from the subsequent access behavior: the tokenizer materializes the merged token, "_B" via a vocabulary lookup and updates the local neighborhood of the merged position, which changes the set of adjacent pairs that will be queried in the next pass. Observing that the next pass probes pairs consistent with "_B" (rather than "BP" or "PE") identifies "_+B" as selected merge. Repeating this reasoning across such replays produces the same intermediate token sequence and thus the same final tokenization outcome. Because BPE tokenization is deterministic given the vocabulary and merge rules, the replay procedure described above uniquely determines the resulting token sequence. Thus, address-level vocabulary and merge table access traces are sufficient to reconstruct tokenizer outputs without observing plaintext memory contents.

4 Prompt Reconstruction on Intel TDX↩︎

The leakage of user prompt through tokenizer access pattern in Section 3.2 is realized end-to-end on Intel TDX by TDXRay [31]. TDXRay performs prompt-reconstruction attack against unmodified confidential VM performing LLM inference, recovering user prompts from the tokenizer’s memory accesses while all guest memory remains encrypted.

The attack proceeds in two steps. In the one-time setup, the adversary builds a host-side tracer from the TDX interface, which combines the page-management APIs (e.g.TDX.MEM.RANGE.BLOCK/UNBLOCK with a cache side-channel, pinning each access to the 64-byte cacheline it touches. Using custom prompts, it then localizes the tokenizer’s table entries in the guest’s physical memory, exploiting the fact that the tokenizer’s table layout is fixed after initialization. Because this layout is static until the victim process restarts, the cost is amortized over the lifetime of the inference.

Once the table is localized, each victim prompt leaks its entire plaintext. The adversary records the cache-line granularity access trace of the tokenizer tables and replays the deterministic lookup procedure. This is the same reconstruction argued in Section 3.2 to recover the prompt. TDXRay reports over 90% reconstruction similarity across model families. This result proves that the tokenizer is a demonstrated, highly-vulnerable prompt-reconstruction channel under a realistic host adversary that even survives the TEE protections. Thus, defending against it requires making the tokenizer’s table-access pattern independent of the input, which we develop in Section [sec:idea].

5 OTRO: Oblivious Tokenization Path with Square-Root ORAM↩︎

In this section, we introduce OTRO, an efficient and oblivious tokenization pathway built on top of SqrtORAM and tailored to BPE tokenizers in LLM inference serving.

5.1 OTRO Overview↩︎

Directly embedding SqrtORAM into the LLM tokenization pipeline presents two challenges: (i) each instance serves only \(\sqrt{N}\) accesses before requiring a rebuild, and (ii) the rebuild costs \(O(N \log^{2} N)\), which is prohibitive on the critical path. OTRO overcomes these obstacles by exploiting the read-only nature of tokenizer tables and by decoupling accesses from costly rebuilds via three ideas.

OTRO replicates the static vocabulary and merge tables across a pool of read-only SqrtORAM instances, effectively increasing the \(\sqrt{N}\)-access limit. Epoch-Based Rotation and Background Rebuild: an epoch-based rotation policy routes accesses to instances with remaining \(\sqrt{N}\)-access budget, while depleted instances rebuild asynchronously in the background, so that rebuilds never block foreground tokenization. Dummy accesses pad each epoch to its \(\sqrt{N}\) boundary, reducing the observable transcript to a coarse epoch count. Chunked Tokenization with KV-Shared Prefill: long prompts are split into chunks whose tokenization can be interleaved with GPU prefill using a shared KV cache, reducing the active SqrtORAM instance count and providing slack to hide rebuild latency.

Figure 6 illustrates the overall OTRO system deployed under a CVM. The tokenizer executes in the CPU TEE, while the embedding and Transformer layers (including both prefill and decoding) execute in the GPU TEE. Each client session receives an independent SqrtORAM pool keyed by identifier \(cid\), ensuring full isolation among clients; no client’s accesses influence another’s epoch counters or rebuild schedule. The pool manager selects instances via the epoch-based rotation policy and triggers asynchronous rebuilds for exhausted instances, keeping rebuild work off the critical path. Since per-client pools are independent, multi-client throughput scales with GPU scheduling, so the single-client evaluation in Section 7 captures the full OTRO-specific performance.

5.2 SqrtORAM Pool Access↩︎

The key observation in the LLM tokenizer during inference is that tokenization and detokenization issues only read operations to the vocab/merge tables. The read-only access pattern indicates the rebuild never needs to reconcile updated blocks allowing OTRO to decouple the strict rebuild-after-\(\sqrt{N}\)-access requirement of SqrtORAM. OTRO maintains a pool of independently permuted SqrtORAM instances that hold the same vocab/merge data, so while one instance rebuilds asynchronously, other continues serving requests uninterrupted.

The LLM tokenizer’s vocab and merge tables are publicly available, but we seek to obfuscate subsequent access patterns by constructing multiple independently permuted SqrtORAM instances. When a new client session begins, OTRO assigns the client a unique \(cid\) and uploads the plaintext tokenizer data into TEE-protected DRAM. OTRO concatenates the vocab and merge table into a single flat array, then generates \(P\) independent permutations using per-instance keys (\(k_i, 0\leq i < P\)), instantiating \(P\) SqrtORAM structures each with a distinct random layout. Because the tokenizer data is public, the obliviousness of future accesses relies solely on access-pattern indistinguishability provided by each SqrtORAM instance rather than on the layout obscurity. OTRO retains all ORAM metadata, including \(\mathsf{PRF}\), random key (\(k_i\)), \(\mathsf{stash}\), and access counters for each ORAM instance in its TEE-protected memory. Furthermore, with per-client pools, access patterns from distinct clients are fully isolated.

During LLM inference, the tokenizer’s memory request is submitted to the OTRO pool manager, which selects a SqrtORAM instance from the client’s dedicated pool. We deploy an epoch-based instance rotation policy, Algorithm 7, where each SqrtORAM instance is fully utilized, serving \(\sqrt{N}\) accesses before being scheduled for rebuild. The manager maintains a pool of SqrtORAM instances and a pointer to the currently active instance. Each instance serves up to \(\sqrt{N}\) accesses in an epoch, during which all incoming requests are mapped to that instance, independent of the address being accessed. Once an instance reaches its per-epoch access limit, the manager launches an asynchronous rebuild (LaunchRebuildAsync) for that instance in a detached thread and advances the active pointer to the next instance in the pool. The choice of the instance is a deterministic function of the global access count; an adversary can see when OTRO switches instances, but the switching of instances is a function of "global access count", which is already leaked in any practical ORAM designs. Thus, the decision is independent of the logical sequence and does not encode any information about the data being accessed.

The exact ORAM access count within an epoch is observable to the hypervisor and leaks fine-grained length information beyond what byte length already reveals. Since each epoch naturally spans exactly \(\sqrt{N}\) accesses, OTRO pads dummy accesses to the next \(\sqrt{N}\) boundary at epoch completion, causing at most \(\sqrt{N}-1\) additional dummy accesses. This replaces the exact access count with the coarser epoch number, dramatically reducing the residual access-count leakage, which is analyzed in Sec 7.5.

5.3 Chunked Tokenization↩︎

As shown in Figure 8, we introduce chunked tokenization to effectively hide rebuild latency in variable-length prompt input scenarios while minimizing the number of SqrtORAM instances. Supporting tokenization for variable-length input prompts would ideally require a pool sized to the model’s maximum context length, which can expand to the order of hundreds of instances for long-context models like Llama-3.1 (128K tokens). Chunked tokenization effectively reduces the number of replicas by interleaving tokenization and GPU prefill: the pool need only be large enough to cover one chunk at a time rather than the full prompt.

The number of instances can be determined either by the model’s maximum context length or by the ratio between rebuild and \(\sqrt{N}\)-access latency. Each LLM has a maximum context length of \(L_{\mathsf{max\_ctx}}\) tokens. We can set the pool size, \(n_{\mathsf{pool}} = \min( \lceil \frac{L_{\mathsf{max\_ctx}} * \lambda_{\mathsf{att}}}{A_{\max}^{\mathsf{oram}}} \rceil, \lceil \frac{T_{\mathsf{reshuffle}}}{T_{\mathsf{access}}*A_{\max}^{\mathsf{oram}}} \rceil)\) where \(\lambda_{\mathsf{att}}\) is the ORAM access rate per token, \(T_{reshuffle}\) is the per-instance rebuild time, and \(T_{access}\) is the per-lookup latency excluding rebuild.

OTRO partitions the input prompt into multiple smaller chunks that are tokenized and fed into the LLM pipeline. The chunking is strictly an internal scheduling mechanism occurring at pre-tokenization boundaries (i.e., whitespace-delimited words) and does not change the logical behavior of the tokenizer or the model; BPE merges never cross the chunk boundaries, producing a token sequence bit-for-bit identical to tokenizing the full input at once. Additionally, for correctness, special tokens, such as beginning-of-sequence and end-of-sequence, are not inserted at the chunk boundaries. With incremental prefill over a shared KV cache, the model sees a single contiguous token sequence of tokenIDs identical to the non-ORAM baseline; OTRO’s chunking affects only performance and memory behavior, not semantics.

Chunk size \(\mathsf{chunk}_{\mathsf{tok}}\) is chosen with explicit awareness of GPU utilization and ORAM rebuild time so that the prefill duration of the chunk overlaps with the rebuild phase of the next chunk: \(T_{\mathsf{gpu},\mathsf{prefill}}(\mathsf{chunk}_{\mathsf{tok}}) > T_{\mathsf{reshuffle}}\). This ensures that once the tokenization of the chunk ends and the rebuild phase is launched, the entire rebuild phase completes while the GPU is executing the prefill stage. We select the chunk size so that each chunk’s GPU prefill interval serves as a "coverage window" that amortizes the SqrtORAM rebuild cost, allowing the system to maintain high GPU utilization while keeping SqrtORAM-induced stalls off the critical path of the LLM pipeline.

5.4 Detokenization↩︎

The de-tokenization process converts the tokenIDs generated by LLM decoding into human-readable text using a reversed vocab table. Obfuscating access patterns to this structure, therefore, plays an important part in guarding output prompts from leakage. We apply our ORAM-based obfuscation, OTRO to detokenizer accesses. The main difference lies in ORAM block organization; each ORAM block needs to be padded to the maximum vocabulary length in the reversed vocab table. Without padding, the word length could leak from the returned message length of ORAM access. Thus, compared to OTRO in the tokenization path, we will have a fewer blocks (\(N\)), but a bigger data size per block.

Similarly to overlapping tokenization and LLM prefill, we overlap detokenization and the LLM decode stage. In contrast to the prefill stage, which requires the entire tokenized result of the input prompt, the decode stage emits output tokens every few tens of milliseconds. Thus, the number of instances required by OTRO can be dramatically reduced, as the \(\sqrt{N}\) accesses occur over hundreds of milliseconds to seconds, in which the other instance can finish its rebuild.

6 Security Analysis↩︎

We consider a probabilistic polynomial-time adversary \(\mathcal{A}\) that controls the untrusted software stack and can observe all physical DRAM accesses generated by the CVM. Due to TEE memory protection and encryption, the adversary cannot observe plaintext DRAM contents, cryptographic keys, or internal CVM state, and it cannot tamper with execution inside the CVM.

The security goal of OTRO is to protect the table-dependent memory behavior of tokenization and detokenization. Concretely, even if an adversary can observe the CVM’s physical DRAM trace, they should learn nothing about which logical entries in the vocabulary table or merge table are accessed. In other words, OTRO provides an access-pattern confidentiality guarantee for tokenizer-table lookups, which is the primary channel that links DRAM addresses to specific tokens or merges. This guarantee is intentionally scoped to the ORAM-protected table interface, rather than the entire tokenizer implementation. Consistent with prior ORAM-based systems [36], [37], [60], we do not attempt to eliminate side channels that stem from computation-level effects (e.g., timing variability or microarchitectural vulnerability) that may arise from specific code patterns or implementation details; analyzing and hardening such channels requires a different methodology and is orthogonal to OTRO’s design. Likewise, OTRO does not protect against input-structural leakage that is either unavoidable or application-dependent, including the processing time, the length of the input sequence, and the total number of tokenizer table lookups by default; with padding enabled, only the coarser epoch count is revealed.

The observable transcript consists of the sequence of physical DRAM accesses arising from i) tokenizer and detokenizer table lookups and ii) background rebuild operations. Public configuration parameters, including vocabulary size, table layout, pool size, chunk size, and the maximum context length of the model, are explicitly revealed. Without access count padding, the observable transcript includes the total number of accesses and the number of processing epochs. With access-count padding enabled, only the epoch count \(\lceil \text{access\_count} / \sqrt{N} \rceil\) is revealed, since dummy accesses fill each epoch to the \(\sqrt{N}\) boundary before rotation. For example, OTRO may reveal that a given input triggered 3014 table accesses processed across two chunks, but it should not reveal which logical entries of the tokenizer tables were accessed or the frequency of such accesses.

Let \(j(i) = \left\lfloor \frac{i-1}{\sqrt{N}} \right\rfloor \bmod n_{\text{pool}} + 1\) denote the SqrtORAM instance selected for the \(i\)-th logical access. By Algorithm 7, \(j(i)\) is a deterministic function of \(i\) and public parameters \(\sqrt{N}\) and \(n_{pool}\); it does not depend on the logical address being accessed. Since rebuild operations are triggered solely when the per-instance access counter reaches \(\sqrt(N)\), their timing is likewise determined by the aggregate access count. Thus, instance rotation and rebuild scheduling introduce no additional input-dependent leakage beyond what is already captured in the observable transcript.

7 Evaluation↩︎

7.1 Experimental Setup and Implementation↩︎

We evaluate on an Intel Xeon Gold 6548Y\(+\) and an NVIDIA H100 GPU (Driver 550.163.01). Host runs Ubuntu 25.04, and the guest CVM (Intel TDX) runs Ubuntu 24.04 with 64 vCPUs and 256 GB memory. Because we implement ORAM logic inside unmodified TDX, we inherit the deterministic AES-XTS behavior of TME; integrating Obelix-like probabilistic memory encryption would remove ciphertext determinism and is considered orthogonal to our work.

We prototype OTRO in HuggingFace Tokenizers (v0.22), redirecting each memory request to OTRO. Chunked tokenization works as a scheduling module that interleaves tokenization and prefill above nano-vLLM’s [61] existing KV-cache mechanisms. We disable the tokenizer’s software merge cache in all configurations as its data-dependent hit/miss pattern leaks additional prompt information outside of the ORAM-protected path. We compare OTRO with Baseline (no obfuscation), PathORAM [36], and naive SqrtORAM [35] (np=1), and evaluate two OTRO variants: 1) GPU overlap (GO), which overlaps rebuilds with GPU computation but stalls if all instances are exhausted, and 2) OTRO (GO+CT) which additionally applies chunked tokenization to eliminate the stalls. To probe the no-stall regime, we also provision a large upper-bound pool (np=300); we derive the minimum pool size using \(n_{pool} \geq \lceil T_{rebuild} / T_{epoch} \rceil\), which yields approximately 201, 59, 146, and 419 for Llama-3.1, Qwen3, Gemma-3, and Phi-3, respectively. For Phi-3, whose epoch consumption time is particularly short, a large pool (\(\approx419\)) would be required to strictly avoid stalls; however, due to its shorter rebuild latency, observed stall durations remain small in practice.

We measure time-to-first-token (TTFT), tokenizer memory, and initialization cost for Llama-3.1-8B [27], Qwen3-8B [29], Gemma3-4B [26], and Phi-3-mini [28] under PyTorch-2.6. These models cover a range of vocabulary sizes and merge-table configurations (Table 1); since ORAM overhead depends primarily on tokenizer vocabulary size rather than model depth, they are representative without requiring larger variants. Input prompt length is swept from 1500 to 6500 words, where each word yielding 3–5 tokens. Lastly, we note that OTRO’s per-client design (Sec 5.1) ensures that concurrent multi-client behavior is architecturally independent across clients; the only shared resource is the GPU, which affects baseline and OTRO equally. Therefore, the single-client prompt-length sweep presented here captures the full OTRO-specific performance behavior, and multi-client throughput scales with GPU scheduling rather than ORAM design choices.

OTRO requires no changes to model weights, CUDA kernels, or transformer architecture. Chunked tokenization adds a thin scheduling layer above the serving framework’s existing prefill and KV-cache mechanisms, with no retraining or model reconfiguration required, and thus, OTRO can be modularly deployed, agnostic to the underlying serving framework.

7.2 Offline Tuning for CPU-GPU Overlap↩︎

Before running our main experiments, we perform an offline profiling phase to determine how to best overlap the rebuild phase of OTRO’s SqrtORAM instances with the model’s prefill phase. For each model, we sweep the chunk size for tokenization and the number of SqrtORAM instances in the pool and profile them together with the GPU prefill kernels. The goal is to select a configuration that maximizes overlap between CPU-side work (chunked tokenization and SqrtORAM rebuilds) and GPU prefill.

During the offline tuning, we monitor GPU utilization in the prefill phase to avoid configurations where aggressive chunking results in GPU SM starvation. Very fine-grained chunk sizes can reduce the amount of work (tokens) fed per prefill kernel launch and lower GPU occupancy, offsetting the benefits of overlap. We discard the configurations that noticeably degrade prefill utilization and choose the best-performing setting that both preserves high GPU utilization and provides strong overlap CPU-GPU overlap. Our profiling shows that for Llama-3.1, using a prompt chunk of approximately 3000 words (\(\approx\)​9000 tokens after tokenization) provides enough CPU slack to complete the rebuild from the current epoch and tokenize the next chunk, and overlap with the GPU prefill. Offline profiling selects chunk sizes of \(\sim3000\), \(\sim1700\), \(\sim5000\), and \(\sim1500\) words for Llama-3.1, Qwen3, Gemma-3, and Phi-3, respectively, maintaining GPU utilization within 83–100%.

During the decode stage, our profiling shows an average GPU utilization of 51–65% and memory utilization of 41-49% across all models, with approximately 20–30 ms of compute per generated token. Given this headroom, we find that a pool of just two SqrtORAM instances is sufficient: their rebuild work can be entirely overlapped with the decode kernels, so the cost is effectively hidden in the decoder phase.

7.3 Time-To-First-Token Latency↩︎

Figure [fig:ttft] presents the normalized TTFT over the baseline of no ORAM obfuscation in Llama-3.1, Qwen-3, Gemma-3 and Phi-3. Figure 10 (a) shows the percentage of tokenization latency in TTFT. We first evaluate the end-to-end effect of ORAM-based tokenization on TTFT for Llama-3.1. Across input prompt length, the normalized TTFT reflects the latency overhead of the tokenizer-only implementation depicted in Figure 1 (b). PathORAM implementation consistently degrades TTFT by an average of 1.48\(\times\), as tokenizer latency occupies nearly 35.73% within the entire TTFT. The result reflects the high per-access cost of 5.16\(\times\) in the tokenizer-only experiment. For naive SqrtORAM (np=1) implementation, TTFT increases by an average of 11.12\(\times\), in which the tokenization time dominates TTFT with 92.42%; the rebuild cost for naive SqrtORAM implementation occupies 99% of the tokenization time.

SqrtORAM (np=300), which provisions the number of SqrtORAM instances to an upper-bound, depicts an ideal scenario where SqrtORAM does not pay any rebuild penalties during the tokenization. Compared to baseline, the results show a 6.90% increase in TTFT; the average access latency increases by 1.26\(\times\) in Figure 1 (b). The tokenization time is only 10.86% of the total TTFT. GO (np=48) performs near-optimal from 2000 to 3000 input prompt length, but spikes after 3500. The main reason for this spike is that once the access limit is reached for all instances in the pool, the next tokenization must wait until at least one instance is free. While the rebuilds are overlapped and the system does not pay the full price as in naive SqrtORAM (np=1), GO (np=48) pays an average of 57% increase in TTFT. OTRO, which is depicted as GO+CT (np=48) in the figures, performs similarly to the ideal case of SqrtORAM (np=300) in smaller input settings. However, once input length exceeds 4000, OTRO reduces TTFT by 5% compared to the ideal. As chunk tokenization encodes the first 3000 words and overlaps the rest with GPU computation, we do not pay the extra tokenization cost induced by SqrtORAM. Across our evaluation, OTRO increases TTFT by only 4.59% on average compared to the baseline. This small overhead leaves TTFT dominated by the model execution (91.41%) rather than tokenization (5.58%), so the cost of oblivious tokenization is modest in practice.

Across Qwen3, Gemma-3 and Phi-3, the qualitative trends mirror Llama-3.1: naive SqrtORAM (np=1) incurs the worst overhead, GO spikes at long prompts once all instances exhaust their \(\sqrt{N}\) budget, and OTRO (GO+CT) stays near the ideal SqrtORAM curve. The key difference is that tokenization accounts for under 3% of baseline TTFT for all three models, yet the naive PathORAM and SqrtORAM (np=1) inflates this significantly. Qwen3 generates more tokens per word (4.89 on average) due to its smaller merge table, lengthening GPU prefill and further diluting tokenizer overhead; OTRO limits TTFT increase to just 0.5% (tokenizer accounts for 3.2% of TTFT). Gemma-3 has 2x larger vocab and merge tables than Llama-3.1 but allocates more budgets to non-English scripts and its smaller model size (4B) keeps GPU prefill time comparable to Llama-3.1; GO’s long-prompt TTFT spike is avoided by OTRO’s chunked tokenization overlap. Phi-3 has the smallest absolute TTFT due to its compact tokenizer and model, but its normalized TTFT trends and ORAM configuration ordering are consistent with other models.

Access-count padding adds at most \(\sqrt{N}\)-1 dummy accesses per epoch. Given our measured per-access latency of \(\sim 3.2\mu s\) and \(\sqrt{N}\leq881\) across all evaluated models, the worst-case padding overhead is \(881 * 3.2\mu s \approx2.8ms\) per epoch; this is less than 0.4% of the Phi-3 rebuild latency (116 ms) and negligible relative to TTFT. Thus, we omit padding overhead from TTFT figures.

The ORAM that protects the detokenization vocab table stores longer data blocks, since each token’s textual form is padded to the maximum vocabulary string length (e.g., Llama-3.1’s longest vocab entry is 256 B). This detokenization ORAM touches its table only once during TTFT and once per decoding step to map generated token IDs back to text, so its cost is amortized over the entire decoding phase. We do not observe any systematic impact on TTFT or decoding throughput attributable to detokenization ORAM. The baseline detokenization throughputs are 21.23, 29.61, 33.08, 23.85 ms/token for Llama-3.1, Qwen3, Gemma-3, and Phi-3, respectively. Detokenizer with PathORAM and SqrtORAM shows 21.53 and 21.34 ms/token for Llama-3.1, 29.61 and 30.14 ms/token for Qwen3, 34.28 and 33.56 ms/token for Gemma-3, and 23.52 and 22.97 ms/token for Phi-3. Lastly, OTRO for detokenizer performs 23.10, 29.56, 33.55, and 21.38 ms/token for Llama-3.1, Qwen3, Gemma-3, and Phi3, respectively. All of these differences are within the normal variance of the end-to-end decoding latency, which is on the order of 20–40 ms per step. Thus, we conclude that detokenization ORAM latency is negligible in the overall LLM pipeline.

7.4 System Level Cost↩︎

We measure end-to-end memory impact using process resident set size (RSS), recorded after (1) loading the model and baseline tokenizer, and (2)constructing the ORAM structures; then, we report the difference, as shown in Table 2. The baseline, non-oblivious tokenizer uses 60.1 MB, 92.0 MB, 137.0 MB, and 16.0 MB of memory for Llama-3.1, Qwen3, Gemma-3, and Phi-3, respectively, to store both the tokenizer and detokenizer tables inside the TEE. PathORAM increases the tokenizer footprint due to its tree layouts and dummy blocks, whereas SqrtORAM with a single instance remains within \(\approx\)​12 MB of the baseline. Our proposed design, OTRO, requires an extra 285.9 MB for Llama-3.1 (48 instances), 46.0 MB for Qwen3 (17 instances), 333.0 MB for Gemma-3 (28 instances), and 30.5 MB for Phi-3 (26 instances). Since OTRO instantiates an independent pool per client, the memory overhead scales linearly with the number of concurrent clients; at under 0.5 GB per client, a 256 GB CVM can support tens of concurrent clients without memory pressure. For detokenizer, OTRO keeps only two SqrtORAM instances, resulting in 7.68 MB, 8.34 MB, 22.9 MB, and 4.0 MB for Llama-3.1, Qwen3, Gemma-3, and Phi-3, respectively, and we observe no systematic impact on decoding throughput across all models.

Figure 10 (b) depicts the one-time initialization cost of installing ORAM metadata and the tokenizer tables at model load time. For Llama-3.1, the baseline initialization is \(\approx0.46\,s\), and OTRO increases this to \(\approx0.64\,s\) (39.7% increase). The initialization cost grows by 46.9% (from \(\approx0.40\,s\) to \(\approx0.59\,s\)), 86.3% (\(\approx1.25\,s\) to \(\approx2.34\,s\)), and 351.9% (\(\approx0.04\,s\) to \(\approx0.15\,s\)) for Qwen3, Gemma-3, and Phi-3. Since initialization happens once per model load, we do not treat the initialization cost as a major system bottleneck.

7.5 Residual Leakage Quantification↩︎

We quantify the information available to an adversary observing OTRO’s metadata under a closed-world model: we sample 20K prompts from the ShareGPT corpus, tokenize with Llama-3.1’s BPE tokenizer, and model prompt selection as uniform over the corpus (\(H(\text{prompt}) = \log_2(20{,}000) = 14.29\) bits) of prior uncertainty. This closed-world assumption overstates what the adversary can infer, as real prompt spaces are vastly large; our analysis is a conservative upper bound on adversary advantage, not a lower bound on security.

After ORAM obfuscation, the adversary’s non-trivial observables reduce to two scalar quantities: prompt byte length and total ORAM access count, both inferable from the DRAM trace. Since BPE table lookups scale linearly with input length (\(R^2=0.9915\), \(\text{access\_count} = 3.20 \times \text{byte\_length} + 11.26\)), the adversary can directly invert the access count to recover prompt length. Epoch count is a deterministic function of total access count and the public parameter \(\sqrt{N}\), and chunk count is a deterministic function of total access count and public chunk size; neither contributes independent information beyond access count. Furthermore, OTRO fuses the vocabulary and merge tables into a single ORAM structure, making individual vocab and merge table accesses physically indistinguishable. The adversary therefore cannot observe per-word merge pass counts or distinguish vocab lookups from merge lookups; only the aggregate access count is visible.

We model prompt selection as uniform over the corpus, giving the adversary an initial uncertainty of \(H(\text{prompt})=14.29\) bits, equivalent to 20,000 equally-likely candidates. Observing byte length alone resolves 8.75 bits, leaving \(H(\text{prompt | byte\_length}) = 5.53\) bits of remaining uncertainty. Observing the access count in addition resolves a further 3.94 bits (\(I(\text{access\_count}; \text{prompt} | \text{byte\_length}) = 3.94\) bits), leaving \(H(\text{prompt | byte\_length, access\_count}) = 1.60\) bits, approximately 3 candidates on average. Critically, 8.75 bits of the 12.69 bits the adversary resolves come from byte length alone, a channel that is independent of OTRO and unavoidable in any practical ORAM deployment since the total access count is a deterministic function of input length. OTRO’s access count contributes only 3.94 additional bits beyond what byte length already reveals, and the near-perfect linear relationship between byte length and access count (\(R^2=0.9915\)) confirms that these two observables are largely redundant.

Table 3 reports the adversary’s residual uncertainty stratified by prompt length. Short prompts are most private: for prompts under 100 bytes, 2.49 bits of uncertainty remain because many distinct short prompts share similar byte lengths and access counts, limiting the adversary’s ability to distinguish among them. As prompt length increases, byte length becomes increasingly identifying on its own. For prompts exceeding 500 bytes, \(H(\text{prompt | byte\_length})\) drops to 1.10 bits or below, meaning the adversary retains almost no uncertainty even before access count is considered. The near-zero residual uncertainty for long prompts is therefore driven primarily by byte length observability, not by OTRO’s access count.

The 3.94 bits contributed by the raw access count beyond byte length can be further reduced through a natural extension of OTRO’s epoch structure. Since each SqrtORAM epoch already spans exactly \(\sqrt{N}\) accesses before instance rotation, OTRO can optionally pad dummy accesses (Section 5.2), revealing only the epoch number \(\lceil \text{access\_count} / \sqrt{N} \rceil\) rather than the exact access count. This coarsening is consistent with OTRO’s existing design: the adversary already observes instance switches at epoch boundaries, so the epoch number is an already-observable quantity that carries no additional information.

Table 3 shows the effect of padding. The additional leakage beyond byte length drops from 3.94 bits to just \(0.04\) bits — within 0.04 bits of the theoretical minimum achievable by any system that leaks byte length (0.00 bits). Residual uncertainty \(H(\text{prompt} | \text{observable})\) rises from 1.60 bits to 5.49 bits, recovering 38.4% of the original prompt entropy compared to 11.2% without padding. The per-bucket improvement is particularly striking for short prompts, where additional leakage from access count drops from 4.48 bits to 0.00 bits, and for medium prompts (100–500 bytes), where it drops from 4.07 bits to 0.11 bits. For long prompts (\(>\)​500 bytes), byte length already dominates and padding contributes negligible additional benefit, consistent with \(H(\text{prompt} \mid \text{byte\_length})\) being near zero in that regime regardless.

Without ORAM protection, the adversary observes the complete sequence of vocabulary and merge-table indices, enabling full prompt reconstruction as demonstrated in Section 3.2, leaving \(H(\text{prompt | full trace}) \approx 0\) bits of residual uncertainty; the adversary identifies the prompt exactly regardless of its length. Table 3 summarizes the leakage under each configuration. OTRO without padding raises this residual uncertainty from 0 to 1.60 bits overall; OTRO with access-count padding raises it further to 5.49 bits. In both configurations, OTRO replaces the fine-grained, per-token access pattern (which enables exact reconstruction) with coarse, length-correlated metadata. The residual identification risk for long prompts exists in any system that leaks input length, which every practical ORAM does, and is not a weakness introduced by OTRO.

8 Related Work↩︎

Side-channel attacks against TEEs in cloud environments are more powerful than non-TEE-based attacks. The attackers can access privileged interfaces (e.g., performance counters [62] and power consumption analyzers [63]) and intentionally control global resources [64]–[68] to gather more fine-grained information on the TEE. In particular, ciphertext side-channel attacks against AMD SEV allow the attackers to monitor ciphertexts to infer secrets [16], [25]. Current research demonstrates that side-channel attacks are serious threats to TEE environments. Thus, countermeasures to protect data and code running inside TEEs are necessary.

[32], [33] apply ORAM to mitigate access-pattern leakage in embedding tables in ML workloads and [34] uses deep hash embedding as an alternative. These techniques operate after tokenization, on tokenIDs, whereas OTRO targets the tokenizer.

PIR [69], [70] provides protocol-level index hiding that allows a client to retrieve a database item without revealing the queried index to the server. PIR protects the logical query at the protocol layer, but does not inherently guarantee memory-oblivious execution under a low-level side-channel adversary observing page faults or DRAM traces. Oblivious maps [71], [72] provide a key-value abstraction built on top of ORAM that hides which key is accessed during lookup or update. While oblivious maps present a higher-level interface, their security ultimately relies on the underlying ORAM’s access-pattern indistinguishability. In contrast to PIR’s protocol-level query privacy and oblivious maps’ key–value abstraction, our work operates at the memory-access abstraction within a CVM.

Many ORAM works like [60], [73]–[82] target the traditional client-server model without TEEs. Our system assumes ORAM inside TEEs; thus, these works are orthogonal to ours.

ZeroTrace [83], Obliviate [84], Oblix [71] and [32], [85], [86] are based on an earlier generation of TEEs, Intel SGX [87]. With memory constraints of SGX, neither SqrtORAM or PathORAM cannot be placed inside the TEE-protected memory. Thus, operate in a different regime from VM-based TEEs. PRO-ORAM [88] builds on SqrtORAM and overlaps accesses with rebuilds to support read-only workloads but targets SGX-enabled cloud storage servers and optimizes constant-latency access to large files in a network setting. In contrast, OTRO uses a pool of SqrtORAM instances as a fine-grained protection layer for tokenizer-table lookups inside a CVM, with the objective to minimize TTFT for real-time inference. As a result, while both systems exploit read-only data and pipelined rebuild, they address different deployment models, threat surfaces, and latency objectives.

A recent work, Menhir [89], is, to our knowledge, the first system to leverage VM-based TEE in implementing ORAM logic, with Intel TME protecting the ORAM structure in TEE-protected DRAM. Obelix [90] identifies the deterministic behavior in AES-XTS-based Intel TME as a limitation and resolves it by attaching a 64-bit counter that adds probabilistic variation to AES-XTS, effectively randomizing the ciphertext for repeated accesses to the same physical location. These works are complementary to our design, hardening the security guarantees in ORAM logic.

9 Conclusion↩︎

Tokenizers inside TEEs remain a real, exploitable source of side-channel leakage. Greedy BPE tokenization yields deterministic, data-dependent table accesses, producing DRAM address traces that a privileged adversary can observe. Recent work has turned this into an end-to-end attack that reconstructs user prompts on production Intel TDX. In this paper, we mitigate this channel and provide efficient tokenizer-tailored solution with OTRO. Our central observation is that the tokenizer’s vocabulary and merge tables are read-only during inference, which lets us circumvent the periodic rebuild overhead inherent to in SqrtORAM. OTRO removes this from the critical path in three steps. First, OTRO replicates the tables across a pool of independent SqrtORAM instances. Second, an epoch-based rotation runs the rebuild of depleted instances asynchronously in the background, while continuously serving incoming tokenizer requests from an available instance. Third, chunked tokenization interleaves the tokenization of prompt chunks with GPU prefill, overlapping CPU rebuild work with GPU computation to further reduce the number of instances the pool holds. Together, these techniques turn the bursty rebuild cost of SqrtORAM into background work that does not stall the serving pipeline. Our prototype on Llama-3.1, Qwen3, Gemma-3, and Phi-3 keeps TTFT overhead within 4.5% of the unprotected baseline while reducing the observable trace to prompt length alone, demonstrating that workload-aware ORAM integration is a viable path to end-to-end confidentiality in production LLM-serving stacks.

References↩︎

---

1. Denial-of-service attacks fall outside the scope of confidential LLM serving, as they degrade availability rather than confidentiality and can be readily observed by end users.↩︎