Privacy-Preserving Machine Learning (PPML) is one of the most relevant use cases for Secure Multiparty Computation (MPC). While private training of large neural networks such as VGG-16 or ResNet-50 on state-of-the-art datasets such as ImageNet is still out of reach, given the performance overhead of MPC, GPU-based MPC frameworks are starting to achieve practical runtimes for private inference. However, we show that, unlike plaintext machine learning, using GPU acceleration for both linear (e.g., convolutions) and non-linear neural network layers (e.g., ReLU) is actually counterproductive in PPML. While GPUs effectively accelerate linear layers compared to CPU-based MPC implementations, the MPC circuits required to evaluate non-linear layers introduce memory overhead and frequent data movement between the GPU and the CPU to handle network communication. This results in slow ReLU performance and high GPU memory requirements in state-of-the-art GPU-based PPML frameworks, hindering them from scaling to multiple images per second inference throughput and more than eight images per batch on ImageNet. To overcome these limitations, we propose PIGEON, an open-source framework for Private Inference of Neural Networks. PIGEON employs a novel ABG programming model that switches between Arithmetic Vectorization and Bitslicing on the CPU for non-linear layers depending on the MPC-specific computation required while offloading linear layers to the GPU. Compared to the state-of-the-art PPML framework Piranha, PIGEON improves ReLU throughput by two orders of magnitude, reduces peak GPU memory utilization by one order of magnitude, and scales better with large batch sizes. This translates to one to two orders of magnitude improvements in throughput for large ImageNet batch sizes (e.g., 192) and more than 70% saturation of a 25 Gbit/s network.

Multi-party computing (MPC) has been gaining popularity as a secure computing model over the past few years. However, prior works have demonstrated that MPC protocols still pay substantial performance penalties compared to plaintext, particularly when applied to ML algorithms. The overhead is due to added computation and communication costs. Prior studies, as well as our own analysis, found that most MPC protocols today sequentially perform communication and computation. The participating parties must compute on their shares first and then perform data communication to allow the distribution of new secret shares before proceeding to the next computation step. In this work, we show that serialization is unnecessary, particularly in the context of ML computations (both in Convolutional neural networks and in Transformer-based models). We demonstrate that it is possible to carefully orchestrate the computation and communication steps to overlap.

Memory access patterns have been demonstrated to leak critical information such as security keys and a program's spatial and temporal information. This information leak poses a significant privacy challenge in machine learning models with embedding tables. Embedding tables are used to learn categorical features from training data. The address of an embedding table entry carries privacy sensitive information since the address of an entry discloses features associated with a user. Oblivious RAM (ORAM), and its enhanced variants, such as PathORAM, have emerged as viable solutions to hide leakage from memory access streams. PathORAM fetches an entire path of memory blocks for every memory fetch request, thereby leading to substantial bandwidth and performance overheads.

Leaking memory access addresses can significantly empower an adversary in several computing usage scenarios – from key extraction to disclosing private information. Oblivious RAM has been proposed as a solution to this problem. Oblivious RAM involves reading multiple blocks instead of a single block for each memory access and changing the address of the data block being read after each access. State-of-the-art ORAMs (PathORAM and RingORAM) consider a tree-based structure for storing the data. However, ORAM designs pay a performance penalty. One reason is the strict requirement to evict stash blocks on a particular path that was previously read from. In treebased ORAMs, each memory block is assigned a random path number, and when accessing a single block, one must fetch all the blocks in that path. Once the path is fetched into a client, the computation on the block is performed and that block is assigned a new random path number. All the blocks that were fetched into the client should be evicted to the memory. However, the eviction process must place the unmodified blocks on the same path that the prior read has fetched data from. This eviction requirement may cause a block not to be placed back in the ORAM tree due to limited space on a given tree node. As a result, the client must temporarily hold the block in its stash, which is a secure storage. Every fetch request for a block must search the stash before issuing a request to the ORAM. As the stash size grows, the stash search process becomes a substantial latency hurdle. On the other hand, if the stash is small then the client has to issue dummy reads which are useless reads in the tree for the sole purpose of creating more opportunities to place the stash data back in the tree. An alternate approach used in prior works is to embed dummy data blocks to create large bucket sizes at each tree level to enable better stash eviction probability. Neither of the above two solutions is palatable in practice. Dummy reads increase memory access latency, while dummy blocks increase the fetch bandwidth to bring large buckets from each level into the stash. Furthermore, dummy blocks also decrease the effective memory size available.To solve this problem we propose PageORAM, a novel block eviction and placement strategy. PageORAM makes the critical observation that DRAM is accessed at the granularity of a page (also referred to as row buffer), which is at least an order magnitude larger than the tree node size. Thus, a page may hold data blocks from multiple sub-trees. Hence, when fetching a path, PageORAM fetches a few additional sub-paths from the tree that are already present in an open DRAM page. These additional fetches vastly increase stash eviction options by opening up exponentially more data block placement choices. Thus, PageORAM enables a dramatic reduction in stash size without increasing page access counts in DRAM. While this observation may be counter-intuitive, we note that PageORAM reduces the overall bandwidth even after accounting for the increased fetches along the sub-paths. The reason is that by vastly improving stash block placement possibilities, PageORAM can significantly reduce the bucket size of the tree. Our implementation of PageORAM demonstrates an order of magnitude slower stash growth, increased bucket occupancy with useful data, and correspondingly improved memory access latency and reduced memory bandwidth. In our experiments, we find that PageORAM can either reduce the memory space requirement of the tree-based ORAMs by up to 40% compared to baseline tree-based ORAM or give a performance improvement of up to 7.8x for the same structured tree-based ORAM.

Q-Table based Reinforcement Learning (QRL) is a class of widely used algorithms in AI that work by successively improving the estimates of Q values -- quality of state-action pairs, stored in a table. They significantly outperform Neural Network based techniques when the state space is tractable. Fast learning for AI applications in several domains (e.g. robotics), with tractable 'mid-sized' Q-tables, still necessitates performing substantial rapid updates. State-of-the-art FPGA implementations of QRL do not scale with the increasing Q-Table state space, thus are not efficient for such applications. In this work, we develop a novel FPGA implementation of QRL, scalable to large state spaces and facilitating a large class of AI applications. Our pipelined architecture provides higher throughput while using significantly fewer on-chip resources and thereby supports a variety of action selection policies that covers Q-Learning and variations of bandit algorithms. Possible dependencies caused by consecutive Q value updates are handled, allowing the design to process one Q-sample every clock cycle. Additionally, we provide the first known FPGA implementation of the SARSA (State-Action-Reward-State-Action) algorithm. We evaluate our architecture for Q-Learning and SARSA algorithms and show that our designs achieve a high throughput of up to 180 million Q samples per second.

CNNs have proven to be extremely powerful in various computer vision applications. To alleviate the computation burden and improve hardware efficiency, low-complexity convolution algorithms (e.g., spectral convolution) and data quantization schemes have been implemented on FPGAs. However, to translate the reduced algorithm complexity into improved hardware performance, we need significant manual tuning of mapping parameters specific to the CNN model and the target FPGA device. We propose a flexible tool to automate the process of generating high throughput accelerators for quantized, spectral CNNs. The tool takes as input high level specification of the CNN model, the data quantization scheme and the target hardware architecture. It outputs synthesizable Verilog after fast exploration of the complete design space. Our tool is flexible in three dimensions: 1) data representation, 2) FPGA architecture, and 3) CNN models. To support arbitrary quantization bit width, we propose a resource-efficient multiplier design, which uses the fixed, high bit-width DSPs to implement various low bit-width complex multiplications needed in spectral CNNs. To support FPGAs with limited on-chip memory, we propose a systolic array-based architecture for spectral convolution, which exploits high computation parallelism in DSPs without stressing BRAM resources. To support CNNs with various layer parameters, we tile and permute data blocks to saturate the communication and computation capacity. Finally, we propose a fast design space exploration algorithm to complete the end-to-end Verilog generation. The whole design space exploration and verilog generation takes less than 1 second on an Intel Core i5 laptop. We perform evaluation on Stratix-10 and Stratix-V FPGAs, using AlexNet and VGG16. The generated accelerators achieve 2× to 4× higher throughput than state-of-the-art, for 8-bit and 16-bit data quantization.