How Would Oblivious Memory Boost Graph Analytics on Trusted Processors?

Jiping Yu 1 2 3, Xiaowei Zhu 2, Kun Chen 2, Guanyu Feng 1, Yunyi Chen 1 2 3, Xiaoyu Fan 1 2 3, Wenguang Chen 1 2 · 2025

Read How Would Oblivious Memory Boost Graph Analytics on Trusted Processors? by Jiping Yu 1 2 3, Xiaowei Zhu 2, Kun Chen 2, Guanyu Feng 1, Yunyi Chen 1 2 3, Xiaoyu Fan 1 2 3, Wenguang Chen 1 2 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-24255.txt.

Introduction

Jiping Yu and six colleagues ask how oblivious memory would help trusted processors. Trusted hardware lets parties compute jointly while keeping data private. Privacy comes at a cost. Data-oblivious algorithms hide access patterns, but they run slowly. Graph analytics are important and especially exposed to access-pattern attacks.

Oblivious memory built into the processor hides accesses from adversaries. The authors co-design storage layouts and algorithms around it. Their prototype runs a hundred times faster than baselines. The memory needed is only about per-core cache size. Existing processors could add it with negligible overhead. The insight is architectural. A small, well-placed hardware feature can remove a large software penalty. Private graph analytics on untrusted infrastructure is the target use.

Catalog record

CREATORJiping Yu 1 2 3, Xiaowei Zhu 2, Kun Chen 2, Guanyu Feng 1, Yunyi Chen 1 2 3, Xiaoyu Fan 1 2 3, Wenguang Chen 1 2
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-24255

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

How Would Oblivious Memory Boost Graph Analytics on Trusted Processors? Jiping Yu 1 2 3, Xiaowei Zhu 2, Kun Chen 2, Guanyu Feng 1, Yunyi Chen 1 2 3, Xiaoyu Fan 1 2 3, Wenguang Chen 1 2 Abstract Trusted processors provide a way to perform joint computations while preserving data privacy. To overcome the performance degradation caused by data-oblivious algorithms to prevent information leakage, we explore the benefits of oblivious memory (OM) integrated in processors, to which the accesses are unobservable by adversaries. We focus on graph analytics, an important application vulnerable to access-pattern attacks. With a co-design between storage structure and algorithms, our prototype system is 100 × \times faster than baselines given an OM sized around the per-core cache which can be implemented on existing processors with negligible overhead. This gives insights into equipping trusted processors with OM. I Introduction In many scenarios, multiple parties can benefit from participating in joint computations on their aggregate data. For example, multiple banks may share their blocklists to identify frauds that can hardly be detected using their own data; different hospitals can share patient data to train a better machine learning model that helps in medical diagnosis. A basic requirement is to ensure the data privacy while allowing the parties to compute the results. Recently, there is a trend to perform multi-party data processing with trusted execution environments (TEE) [ 7 ] , which may largely reduce the computation overhead, compared with cryptographic tools such as Homomorphic Encryption (HE) [ 9 ] and Secure Multi-Party Computation (MPC) protocols [ 26 , 32 , 16 ] . Under this setting, multiple parties first agree on a joint data processing task whose implementation is open to all participants for review, and then outsource the actual computation to a third-party (e.g. cloud service provider) with trusted processors. Although many TEE implementations support transparent encryption of in-memory data, accessed memory addresses are not protected at the hardware level, which leaves the opportunity for curious eavesdroppers on the memory controller to infer a surprisingly large amount of information [ 31 , 17 , 21 , 5 , 10 , 14 ] . To this end, we need to make the program running in the TEE to be data-oblivious [ 22 , 33 , 8 ] , so that only insensitive information such as the dataset size can be inferred from the observed memory trace. Thus, the algorithms need to be redesigned and become slower than plaintext versions, which reduces the performance benefits of using TEEs for multi-party data processing. To mitigate such performance loss, many oblivious algorithms [ 21 , 33 , 8 , 28 ] assume there exists an oblivious memory (OM), to which the access patterns are assumed to be invisible to the attackers. Based on OM, the algorithms can achieve much better performance than the versions not relying on OM. In this paper, we extend the above idea and study multi-party graph analytics on TEEs equipped with OMs. The reasons to pay special attention to algorithms on graphs are as follows. (1) Graph analytics can attain better effects if utilizing multi-source data. For example, in financial fraud detection [ 24 ] , direct information sharing among financial institutions is prohibited, but with multi-party graph analytics, they can rely on the collaborative transaction graph to detect hidden fraud transactions which are untraceable with each own data. (2) Graph analytics is vulnerable to access-pattern attacks. For example, the operation that “for each edge from u to v , update w_{1}(v)\leftarrow w_{1}(v)+w_{2}(u) ” is a common routine of graph algorithms such as PageRank [ 23 ] . If directly implemented in TEE, even though the vertex data w_{1}(v) and w_{2}(u) are protected as ciphertext, u and v could be inferred from the addresses of memory access operations (or at least in cacheline-level granularities), which leaks sensitive information about the graph structure. (3) Graph analytics is costly, and it is hard to achieve data-obliviousness. To prevent information leakage, existing solutions [ 20 ] use expensive operations like sorting, which brings a lot of performance overhead, thus calls for a specially designed method that can make full use of OM. Actually, as many graph algorithms are iterative, it is beneficial to reorganize the graph structure so that each subsequent iteration is performed more efficiently, which leaves quite a lot of design opportunities. We design a prototype system named ObliGE ( Obli vious G raph E ngine). Based on TEE with OM, we adopt a grid structure, which makes possible a highly-efficient oblivious graph scanning method, completely eliminating sorting passes from computation iterations. We also propose pre- and post-processing methods to make the whole processing pipeline oblivious. Our evaluation shows ObliGE outperforms oblivious sort-based baselines by up to two orders of magnitude, and largely closes the performance gap compared with non-oblivious methods, making it practical for processing large-scale graphs. We are delighted to see that OM can have much larger effects on boosting graph analytics, than on other applications such as sorting. We also discuss the OM size requirements and the feasibility to implement such OM on trusted processors. We hope the results inspire hardware designers to equip trusted processors with OM. II Preliminaries II-A Multi-Party Graph Analytics on Trusted Processors Graph analytics generally refers to iterative computation on graphs. The edges are immutable, while the vertex data may change across iterations. For example, PR (PageRank [ 23 ] ), BFS (breadth-first search) and WCC (weak-connected components) are classic graph analytics applications. For multi-party scenarios, each party holds parts of vertices and edges, wishing to compute the results on the merged graph. We formulate the task of multi-party graph analytics on trusted processors as follows. II-A 1 Roles We identify the roles of p clients, which provides input graph data and receives the results, and a central server equipped with trusted processors, which solely helps the computation and is typically provided by a cloud service. II-A 2 Input Each client i inputs a private graph (V_{i},E_{i}) . V_{i} denotes its set of vertices, while each element of E_{i} is a pair (u,v) such that u,v\in V_{i} , denoting an edge from u to v . The parties agree with t , the number of iterations, as a public information. II-A 3 Output After the computation, each client i receives the resulting weight w^{t}(v) for each vertex v\in V_{i} . The method of weight calculation depends on the graph analytics application. For example, for the PageRank algorithm [ 23 ] , we have \textstyle w^{t}(v)=(1-f)+f\cdot\sum_{(u,v)\in E}\frac{w^{t-1}(u)}{d(u)};w^{0}(v)=1 where f is a constant damping factor (typically 0.85 ), d(u) denotes the out-degree of u and E is the set of all edges ( E=\cup_{i=0}^{p-1}E_{i} ). Typically, an application starts with the vertex weights of the previous iteration, denoted by w^{t-1}(\cdot) , examines all edges E , and computes the weights for the subsequent iteration, w^{t}(\cdot) . After completion of all T iterations, these weights form the final result. II-A 4 Threat Model and Security Assumptions We consider clients to be semi-honest, implying that every client is expected to adhere precisely to the protocol (e.g., provide correct input data) while being keen on examining the private information (i.e. V_{i} , E_{i} )

Read the complete text