This paper demonstrates the first side-channel attack on homomorphic encryption (HE), which allows computing on encrypted data. We reveal a power-based side-channel leakage of Microsoft SEAL prior to v3.6 that implements the Brakerski/Fan-Vercauteren (BFV) protocol. Our proposed attack targets the Gaussian sampling in the SEAL's encryption phase and can extract the entire message with a single power measurement. Our attack works by (1) identifying each coefficient index being sampled, (2) extracting the sign value of the coefficients from control-flow variations, (3) recovering the coefficients with a high probability from data-flow variations, and (4) using a Blockwise Korkine-Zolotarev (BKZ) algorithm to efficiently explore and estimate the remaining search space. Using real power measurements, the results on a RISC-V FPGA implementation of the SEAL (v3.2) show that the proposed attack can reduce the plaintext encryption security level from 2128to 24.4. Therefore, as HE gears toward real-world applications, such attacks and related defenses should be considered.

This paper proposes a discrete Gaussian sampling hardware design that can flexibly support different sampling parameters,that is more efficient (in area-delay product) compared to the majority of earlier proposals,and that has constant execution time. The proposed design implements a Cumulative Distribution Table (CDT) approach,reduces the table size with Gaussian convolutions,and adopts an innovative fusion tree search algorithm to achieve a compact and fast sampling technique---to our best knowledge,this is the first hardware implementation of fusion tree search algorithm. The proposed hardware can support all the discrete Gaussian distributions used in post-quantum algorithms (FALCON,qTESLA,and FrodoKEM),the homomorphic encryption library of SEAL,and other algorithms such BLISS digital signature and LP public-key encryption. Our proposed hardware can be configured at design-time to optimize a single configuration or at run-time to support multiple Gaussian distribution parameters. Our design,furthermore,has constant-time behavior by design,eliminating timing side-channel attacks---this is achieved by reading all table contents at the same time to also reduce the latency. The results on a Xilinx Virtex-7 FPGA show that our solution can outperform all prior proposals in area-delay product by 1.67--235.88X,only falling short of those designed for the LP encryption scheme.