Delay Tolerant Network (DTN) is a widely used network in computer network and wireless network, there are no permanent end-to-end connections between source and destination nodes (vertices). Betweenness centrality (BC) is used to find the key nodes (vertices) of DTNs, and there are kinds of implementations of the BC algorithm for DTNs. However, most recent algorithms in BC computation suffer from the problem of high auxiliary memory consumption. To reduce BC computing’s memory consumption, we propose a path-merging-based algorithm called Galliot to calculate the BC values using GPU, which aims to minimize the on-board memory consumption and enable the BC computation of large-scale graphs on GPU. The proposed algorithm requires$\mathcal {O}(n)$space and runs in$\mathcal {O}(mn)$time on unweighted graphs. We present the theoretical principle for the proposed path merging method. Moreover, we propose a locality-oriented policy to maintain and update the worklist to improve GPU data locality. In addition, we conducted extensive experiments on NVIDIA GPUs to show the performance of Galliot. The results show that Galliot can process the larger graphs, which have$11.32\times $more vertices and$5.67\times $more edges than the graphs that recent works can process. Moreover, Galliot can achieve up to$38.77\times $speedup over the existing methods.

Recently, deep learning as a service (DLaaS) has emerged as a promising way to facilitate the employment of deep neural networks (DNNs) for various purposes. However, using DLaaS also causes potential privacy leakage from both clients and cloud servers. This privacy issue has fueled the research interests on the privacy-preserving inference of DNN models in the cloud service. In this paper, we present a practical solution named BAYHENN for secure DNN inference. It can protect both the client's privacy and server's privacy at the same time. The key strategy of our solution is to combine homomorphic encryption and Bayesian neural networks. Specifically, we use homomorphic encryption to protect a client's raw data and use Bayesian neural networks to protect the DNN weights in a cloud server. To verify the effectiveness of our solution, we conduct experiments on MNIST and a real-life clinical dataset. Our solution achieves consistent latency decreases on both tasks. In particular, our method can outperform the best existing method (GAZELLE) by about 5x, in terms of end-to-end latency.

Oblivious RAM (ORAM) is a cryptographic primitive designed to hide memory access patterns. To achieve this objective, the intended data block is loaded and evicted back together with other data blocks and dummy blocks in each ORAM access. To further protect the timing pattern, extra dummy ORAM accesses are triggered periodically. Such designs lead to huge memory access overheads. Many techniques have been proposed to mitigate this problem by reducing the total number of ORAM accesses and the number of blocks per access. However, the impact of the access order of intended data block in an ORAM access is not addressed yet. In this work, we argue that higher performance can be achieved by advancing the access to the intended data block in ORAM accesses. However, changing the access order of blocks directly compromises the ORAM security. To solve this problem, we propose a duplication method to advance the access to the intended data blocks without compromising the ORAM security. The method leverages dummy blocks to store extra copies of data blocks, to facilitate early access of intended data blocks. These dummy blocks with valid data duplications are called Shadow blocks in this work. We further introduce two data duplication techniques, called RD-Dup and HD-Dup, to reorder the data block access for different purposes. In addition, we propose ORAM space partitioning to make RD-Dup and HD-Dup cooperate with each other efficiently. Compared with state-of-the-art ORAMs, our design can achieve a 32% reduction in system execution time on average, with negligible hardware overheads.