Using correct design metrics and understanding the limitations of the underlying technology is critical to developing effective scheduling algorithms. Unfortunately, existing scheduling techniques used incorrect metrics and hadun-realisticassumptions for fair scheduling of multi-tenant FPGAs where each tenant is aimed to share approximately the same number of resources both spatially (in space) and temporally (in time).This paper proposes an improved fair scheduling algorithm that fixes earlier issues with metrics and assumptions for ‘fair’ multi-tenant FPGA use. Specifically, we claim three improvements. First, we consider both spatial and temporal aspects to provide spatiotemporal fairness—this improves a recent prior work that assumed all tasks would have the same latency. Second, we add the energy dimension to fairness: by calibrating the scheduling decision intervals and including their energy overhead, our algorithm offers trading off energy efficiency for fairness. Third, we consider previously ignored facts about FPGA multi-tenancy, such as the existence of heterogeneous regions and the inflexibility of run-time merging/splitting of partially reconfigurable regions.We develop and evaluate our improved fair scheduling algorithm with these three enhancements. Inspired by the Greek goddess of law and personification of justice, we name our fair scheduling solution THEMIS:Time,Heterogeneity, andEnergyMindedScheduling.We implemented our solution on Xilinx Zedboard XC7Z020 with real hardware workloads and used real measurements on the FPGA to quantify the savings of our approach. Compared to previous algorithms, our improved scheduling algorithm enhances fairness between 24.2–98.4% and allows a trade-off between 55.3× in energy vs. 69.3× in fairness. The paper thus informs cloud providers about future scheduling optimizations for fairness with related challenges and opportunities.

Machine learning (ML) and artificial intelligence (AI) applications have become crucial for current and future information systems. Meanwhile, hardware security threats are emerging for AI/ML applications, such as the possibility of private input/model leakage as a result of hardware side-channel leakage. Yet such vulnerabilities are only evaluated after deployment and as ad-hoc instances, which is too late and too costly. The development of a framework is necessary in order to evaluate attacks and defenses comprehensively, quickly, and accurately prior to their deployment.

FPGAs are newly added to the cloud to offer energy-efficient acceleration. Multi-tenancy is an emerging phenomenon in cloud FPGAs to enable resource efficiency. In a multi-tenant scenario, multiple users can share the same FPGA fabric either spatially (i.e., tenants share different resources at the same time) or temporally (tenants share the same resources in different time slots). Undesired access or manipulation of other tenant's data can cause security and safety issues. Although safety/security concepts in access control policies have been thoroughly studied in conventional cloud systems, they are relatively unknown for cloud FPGAs. Moreover, these concepts may not trivially extend to cloud FPGAs due to their different nature. This paper proposes an improved access control mechanism for multi-tenant cloud FPGAs. Compared to existing commercial tools, our solution allows dynamic configuration of access control privileges. Compared to earlier academic proposals with dynamic configuration, the results show that our proposal has three advantages: (i) enabling secure resource sharing of on-chip BRAMs to tenants, (ii) enabling safe sharing by resolving deadlocks and faulty access requests, and (iii) improvement in latency and throughput.

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.

Efficient lattice-based cryptosystems operate with polynomial rings with the Number Theoretic Transform (NTT) to reduce the computational complexity of polynomial multiplication. NTT has therefore become a major arithmetic component (thus computational bottleneck) in various cryptographic constructions like hash functions, key-encapsulation mechanisms, digital signatures, and homomorphic encryption. Although there exist several hardware designs in prior work for NTT, they all are isolated design instances fixed for specific NTT parameters or parallelization level. This article provides an extensive study of flexible design methods for NTT implementation. To that end, we evaluate three cases: (1) parametric hardware design, (2) high-level synthesis (HLS) design approach, and (3) design for software implementation compiled on soft-core processors, where all are targeted on reconfigurable hardware devices. We evaluate the designs that implement multiple NTT parameters and/or processing elements, demonstrate the design details for each case, and provide a fair comparison with each other and prior work. On a Xilinx Virtex-7 FPGA, compared to HLS and processor-based methods, the results show that the parametric hardware design is on average$4.4\times$and$73.9\times$smaller and$22.5\times$and$19.3\times$faster, respectively. Surprisingly, HLS tools can yield less efficient solutions than processor-based approaches in some cases.

This paper proposes the first side-channel attack on FALCON—a NIST Round-3 finalist for the post-quantum digital signature standard. We demonstrate a known-plaintext attack that uses the electromagnetic measurements of the device to extract the secret signing keys, which then can be used to forge signatures on arbitrary messages. The proposed attack targets the unique floating-point multiplications within FALCON’s Fast Fourier Transform through a novel extend-and-prune strategy that extracts the sign, mantissa, and exponent variables without false positives. The extracted floating-point values are then mapped back to the secret key’s coefficients. Our attack, notably, does not require pre-characterizing the power profile of the target device or crafting special inputs. Instead, the statistical differences on obtained traces are sufficient to successfully execute our proposed differential electromagnetic analysis. The results on an ARM-Cortex-M4 running the FALCON NIST’s reference software show that approximately 10k measurements are sufficient to extract the entire key.

Post-quantum digital signature is a critical primitive of computer security in the era of quantum hegemony. As a finalist of the post-quantum cryptography standardization process, the theoretical security of the CRYSTALS-Dilithium (Dilithium) signature scheme has been quantified to withstand classical and quantum cryptanalysis. However, there is an inherent power side-channel information leakage in its implementation instance due to the physical characteristics of hardware.This work proposes an efficient non-profiled Correlation Power Analysis (CPA) strategy on Dilithium to recover the secret key by targeting the underlying polynomial multiplication arithmetic. We first develop a conservative scheme with a reduced key guess space, which can extract a secret key coefficient with a 99.99% confidence using 157 power traces of the reference Dilithium implementation. However, this scheme suffers from the computational overhead caused by the large modulus in Dilithium signature. To further accelerate the CPA run-time, we propose a fast two-stage scheme that selects a smaller search space and then resolves false positives. We finally construct a hybrid scheme that combines the advantages of both schemes. Real-world experiment on the power measurement data shows that our hybrid scheme improves the attack’s execution time by 7.77×.

The Number Theoretic Transform (NTT) enables faster polynomial multiplication and is becoming a fundamental component of next-generation cryptographic systems. NTT hardware designs have two prevalent problems related to design-time flexibility. First, algorithms have different arithmetic structures causing the hardware designs to be manually tuned for each setting. Second, applications have diverse throughput/area needs but the hardware have been designed for a fixed, pre-defined number of processing elements. This paper proposes a parametric NTT hardware generator that takes arithmetic configurations and the number of processing elements as inputs to produce an efficient hardware with the desired parameters and throughput. We illustrate the employment of the proposed design in two applications with different needs: A homomorphically encrypted deep neural network inference (CryptoNets) and a post-quantum digital signature scheme (qTESLA). We propose the first NTT hardware acceleration for both applications on FPGAs. Compared to prior software and high-level synthesis solutions, the results show that our hardware can accelerate NTT up to 28× and 48×, respectively. Therefore, our work paves the way for high-level, automated, and modular design of next-generation cryptographic hardware solutions.

Lattice-based cryptography has been growing in demand due to their quantum attack resiliency. Polynomial multiplication is a major computational bottleneck of lattice cryptosystems. To address the challenge, lattice-based cryptosystems use the Number Theoretic Transform (NTT). Although NTT reduces complexity, it is still a well-known computational bottleneck. At the same time, NTT arithmetic needs vary for different algorithms, motivating flexible solutions. Although there are prior hardware and software NTT designs, they do not simultaneously offer flexibility and efficiency. This work provides an efficient and flexible NTT solution through domain-specific architectural support on RISC-V. Rather than using instruction-set extensions with compiler modifications or loosely coupling a RISC-V core with an NTT co-processor, our proposal uses application-specific dynamic instruction scheduling, memory dependence prediction, and datapath optimizations. This allows achieving a direct translation of C code to optimized NTT executions. We demonstrate the flexibility of our approach by implementing the NTT used in several lattice-based cryptography protocols: NewHope, qTESLA, CRYSTALS-Kyber, CRYSTALS-Dilithium, and Falcon. The results on the FPGA technology show that the proposed design is respectively 6x, 40x, and 3x more efficient than the baseline solution, Berkeley Out-of-Order Machine, and a prior HW/SW co-design, while providing the needed flexibility.