Researchers at Carnegie Mellon University Break Long-Standing Efficiency Barrier in Cryptographic Data Protection

PITTSBURGH — In a major development for the fields of cryptography and data privacy, researchers Andrew Krapivin and Elaine Shi from Carnegie Mellon University have published a new scientific paper that shatters a long-standing efficiency barrier in the design of secure data structures. Their research successfully overcomes what the academic community has termed the "log-squared curse," presenting optimal solutions for both statistically secure Oblivious RAM (ORAM) and oblivious search trees within the external-memory model.

The findings, detailed in a research paper titled "Optimal Statistical Oblivious RAM and Search Tree in the External-Memory Model" (Paper 2026/2419) and released on the Cryptology ePrint Archive, address a fundamental challenge in computer science: how to allow a trusted client to query and interact with encrypted data stored on untrusted servers without leaking any information about the data itself or the nature of the queries being performed.

The Privacy Dilemma of Untrusted Memory

In modern computing architectures, outsourcing data storage and processing to untrusted environments—such as commercial cloud providers or third-party data centers—has become standard practice. However, this convenience introduces severe security risks. Even when data is fully encrypted at rest, an adversary monitoring the system can observe the memory access patterns, including which memory addresses are read or written, the timing of the requests, and the frequency of access. These metadata leakage channels can be exploited to reconstruct sensitive user data, perform inference attacks, and compromise confidential applications.

To combat this vulnerability, researchers developed Oblivious RAM, a conceptual framework designed to mask access patterns entirely. An ORAM scheme transforms a sequence of logical memory requests into an indistinguishable sequence of physical block accesses, ensuring that an observer watching the memory bus gains zero information about the underlying operations.

Yet, achieving this ironclad security has historically come with a steep performance penalty. It is a well-established theoretical principle in cryptography that any ORAM scheme must suffer from a logarithmic overhead. More specifically, each logical request must incur a minimum average cost of $Omega(log_B N)$ block transfers, where $N$ represents the total size of the logical memory and $B$ denotes the block size utilized by the oblivious implementation. This logarithmic boundary applies universally to both general ORAM frameworks and specialized data structures like oblivious Search Trees (ST).

Confronting the Log-Squared Curse

Despite knowing the theoretical lower bounds, computer scientists have struggled for years to design practical schemes that achieve this optimal performance threshold. For a long time, the academic community has remained trapped by what is widely known as the "log-squared curse," a performance bottleneck manifesting across two distinct frontiers.

The first frontier involves statistically secure ORAMs. While optimality has previously been achieved for computationally secure ORAM schemes under specific parameter conditions—such as when the block size $B$ equals a constant $Theta(1)$ or when $B$ is greater than or equal to $log^1+epsilon N$ for an arbitrarily small constant $epsilon > 0$—progress regarding statistical security has remained stagnant. Statistical security offers a stronger theoretical guarantee than computational security, as it protects against adversaries with unbounded computational power, relying instead on probability theory rather than unproven mathematical assumptions.

The second frontier concerns oblivious search trees. Until now, researchers have been entirely unable to bypass the log-squared curse for search trees, even when relaxing their security requirements and relying on standard computational assumptions. As a result, systems utilizing oblivious search trees have had to accept suboptimal performance overheads that scaled quadratically with the logarithmic terms, introducing significant latency into database queries and data retrieval operations.

Breaking Barriers in Broad Parameter Regimes

In their new paper, Krapivin and Shi demonstrate that these long-standing barriers are not fundamental limitations of mathematics or physics, but rather artifacts of previous algorithmic approaches. By introducing novel design techniques tailored to the external-memory model, the Carnegie Mellon researchers successfully break the log-squared curse for both oblivious search trees and statistically secure ORAM across broad parameter regimes.

The paper outlines two primary results that redefine the state of the art in memory obliviousness.

The first major result introduces an optimal, statistically secure ORAM scheme that achieves the theoretical lower bound of $O(log_B N)$ cost. This efficiency is guaranteed as long as the block size satisfies the condition $B geq log^1+epsilon N$. By matching the optimal asymptotic cost for statistical security, this advancement bridges a crucial gap that has persisted in cryptographic literature for years.

The second major result delivers an optimal, statistically secure oblivious search tree that also operates at the optimal $O(log_B N)$ cost. This milestone is achieved when the block size satisfies $B geq log^2+epsilon N$. Crucially, this performance matches the efficiency of the best known non-oblivious search trees within this parameter region. In practical terms, this breakthrough implies that developers can achieve complete data and query obliviousness for search trees effectively for free, removing the traditional performance penalty associated with secure data structures.

Real-World Implications and Hardware Alignment

A notable strength of the new research lies in the practicality of its requirements. The assumptions regarding the block size $B$ that are necessary to achieve these optimal bounds are described by the authors as standard and mild.

These parameter requirements do not rely on exotic or unrealistic hardware configurations. Instead, they seamlessly coincide with the standard wide cache-line assumption that has long been prevalent in the classical algorithms literature. Furthermore, they align exceptionally well with modern hardware-enclave architectures—such as Intel SGX, AMD SEV, or ARM TrustZone—which are increasingly deployed to execute oblivious algorithms in real-world systems. Prominent technology platforms, including privacy-focused communication tools like Signal and major industry applications maintained by Meta, already utilize hardware enclaves and secure memory access patterns to safeguard user privacy. The theoretical improvements introduced by Krapivin and Shi provide a mathematically rigorous foundation that could enhance the efficiency and scalability of these deployed systems.

The research paper concludes with formal definitions, proofs, and analytical models within the cryptographic ePrint repository, providing the academic and engineering communities with the detailed framework required to analyze and implement these optimal oblivious data structures.