Paper 2026/2816

SoK: Understanding Virtual Machines over Fully Homomorphic Encryption

Abstract

We survey the current literature on fully homomorphic encryption (FHE) from a virtual machine (VM) perspective. We observe that programs behave in an intrinsically different way over FHE than on plaintext, forming a new paradigm of computation that is fundamentally constrained by the obliviousness of data. To better understand the computational properties, we compile more than 125 works to formulate a cross-layer systematic view of FHE VMs, with a special focus on understanding the concrete programming models over encrypted data. In particular, we identify three distinct forms of VMs over FHE, namely, the SISD VM, the SIMD VM, and the hybrid VM. To aid the cross-layer systematization, we also discuss how current FHE compilers and hardware accelerators can be applied to enhance the usability and performance of the respective VMs. In the experiment, we test eight VM instructions with varying precision as well as two end-to-end application programs to quantitatively assess the concrete design trade-offs for each of the VM paradigms. We conclude that FHE VMs of different types exhibit distinct utility and performance characteristics, necessitating new design methodologies to be developed in a cross-layer manner.