Towards Closing the Performance Gap for Cryptographic Kernels Between CPUs and Specialized Hardware

---

Review Form

Reviewer: The Guardian (Adversarial Skeptic)

Summary

The authors present an effort to improve the performance of cryptographic kernels (NTT, BLAS) on x86 CPUs to better compete with specialized hardware like ASICs. The work consists of two main parts: first, a hand-optimized AVX-512 implementation of 128-bit integer arithmetic for these kernels; and second, a proposal for a small ISA extension, MQX, containing three new instructions for multi-word arithmetic. The performance of this hypothetical MQX extension is then evaluated using a novel modeling technique called "Performance Projection using Proxy ISA" (PISA), and its potential is further extrapolated to a full multi-core system using a "speed-of-light" roofline model.

Strengths

The primary strength of this paper is the development and benchmarking of a high-performance AVX-512 implementation for 128-bit cryptographic kernels. The results presented in Section 5.3 and 5.4 for the AVX-512 baseline are based on real-world measurements on contemporary hardware. These results (e.g., a 38x speedup for NTTs over OpenFHE on a single core) are significant and provide a valuable, updated baseline for the community against which future ASIC, GPU, and CPU solutions should be compared. This part of the work is a solid engineering contribution.

Weaknesses

The paper's conclusions regarding the potential of CPUs to "close the gap" hinge entirely on the proposed MQX extension, and the evaluation of MQX is predicated on a chain of questionable assumptions and a flawed modeling methodology.

1. The PISA Methodology Is Fundamentally Unsound: The core of the MQX evaluation rests on the PISA model (Section 4.2), which projects the performance of hypothetical MQX instructions by mapping them to existing AVX-512 instructions. This mapping is not technically justified.

   • _mm512_mul_epi64 -> _mm512_mullo_epi64: A widening 64x64 multiply produces a 128-bit result. The proxy, mullo, produces only the lower 64 bits. It is microarchitecturally naive to assume that an execution unit producing twice the amount of data would have identical latency, throughput, and execution port requirements as one producing half the data. This assumption is unsubstantiated.
   • _mm512_adc_epi64 -> _mm512_mask_add_epi64: An add-with-carry operation requires a dedicated data path for propagating carry bits between lanes or from a flag register. A masked add operation uses the mask for predication (to write-enable lanes), not as an arithmetic input. These are fundamentally different operations. The authors' justification—that scalar ADD and ADC have similar performance—is irrelevant and does not scale to a 512-bit wide SIMD unit with 8 independent carry operations.

2. The "Validation" of PISA Is a Circular Argument: In Section 5.2, the authors attempt to validate PISA by using it to predict the performance of an existing AVX2 instruction (_mm256_mul_epu32) with another existing instruction as a proxy. While the error is low, this only proves that PISA works when the target and proxy instructions are structurally and functionally very similar. It provides zero evidence that the model is accurate when mapping a hypothetical, functionally distinct instruction (like a widening multiply or a true vector ADC) to a proxy with different semantics and hardware requirements.

3. The Speed-of-Light (SOL) Analysis Is Overly Optimistic and Misleading: The roofline analysis in Section 6 extrapolates single-core performance to a 192-core system using a model that assumes perfect, linear scaling (Equation 13). This is an unrealistic best-case scenario that ignores critical system-level bottlenecks that would dominate at that scale, such as memory bandwidth limitations, cache coherency overhead, and NUMA effects. The authors even observe their kernel becoming memory-bound on a single core at NTT size 2¹⁶ (Section 5.4), which contradicts the assumption that performance would continue to scale linearly with more cores. Presenting these highly idealized "MQX-SOL" numbers on the same plots (Figure 1, Figure 7) as measured hardware creates a misleading visual comparison.

4. Hardware Implementation Claims Are Unsubstantiated: The paper repeatedly claims that MQX requires "minimal proposed hardware modifications" (Abstract) and "minimize[s] the required engineering effort" (Section 4.1). These are strong claims made without any supporting evidence from hardware design, such as proposed circuit diagrams, area estimates, or timing analysis. The fact that similar instructions existed in a past, in-order architecture (Larrabee) does not mean they are trivial to integrate into a modern, complex out-of-order server core.

Questions to Address In Rebuttal

1. Please provide a detailed microarchitectural justification for the specific proxy instruction choices in PISA. How can a widening multiply that produces a 128-bit result be reasonably expected to have the same performance characteristics as a multiply-low that produces a 64-bit result?

2. Beyond the weak analogy to scalar instructions, what evidence supports the assumption that a vector add-with-carry (adc_epi64) instruction would map to the same execution ports and have the same performance as a masked add (mask_add_epi64)?

3. The validation of PISA in Section 5.2 uses existing instructions. How does this experiment validate the model's predictive power for the proposed MQX instructions, which are functionally different from their chosen proxies in ways that the validation experiment does not capture?

4. Please defend the use of a perfect linear scaling model for the SOL analysis in Section 6. Given that your own results show the NTT kernel can become memory-bound on a single core, why should we believe that performance would continue to scale linearly up to 192 cores without being throttled by shared resources like the memory controller?

Review Form:

Reviewer: The Synthesizer (Contextual Analyst)

Summary

This paper addresses the significant performance gap between general-purpose CPUs and specialized hardware (ASICs/GPUs) for cryptographic kernels, particularly the Number Theoretic Transform (NTT) and BLAS operations central to Fully Homomorphic Encryption (FHE). The authors present a multi-pronged approach to narrowing this gap. First, they develop highly-optimized implementations using existing SIMD instruction sets (AVX-512), demonstrating substantial speedups over state-of-the-art libraries. Finding this insufficient to close the gap entirely, they propose a minimal and targeted ISA extension called Multi-word Extension (MQX), consisting of just three new instructions for multi-word arithmetic (widening multiply, add-with-carry, subtract-with-borrow).

The core of the paper lies not just in this proposal, but in its pragmatic evaluation. The authors introduce a clever performance modeling methodology, "Performance Projection using Proxy ISA (PISA)," which estimates the performance of the proposed MQX instructions by mapping them to existing, structurally similar AVX-512 instructions on real hardware. This avoids the inaccuracies of cycle-level simulation for modern proprietary microarchitectures. Finally, using a speed-of-light projection, they argue that a top-tier server CPU equipped with MQX could achieve performance comparable to state-of-the-art ASICs, potentially making CPUs a viable platform for demanding cryptographic workloads and eliminating the data-transfer bottlenecks associated with accelerators.

Strengths

The primary strength of this work is its compelling and well-constructed argument for reconsidering the role of CPUs in the era of specialized cryptographic accelerators. It successfully connects a high-level system challenge to low-level microarchitectural solutions.

1. A Pragmatic and Feasible ISA Extension: The MQX proposal is compelling precisely because it is so minimal. Rather than designing a complex co-processor, the authors identify the three most critical missing primitives for large integer arithmetic. Crucially, as noted in Section 4.1 (page 6), they ground their proposal in historical precedent by drawing direct parallels to scalar x86 instructions (ADC/SBB) and prior vector ISAs like Intel's Larrabee New Instructions (LRBni). This is a masterstroke of contextualization, transforming a hypothetical proposal into a plausible and de-risked engineering path for hardware vendors.

2. Innovative and Credible Performance Modeling (PISA): The PISA methodology (Section 4.2, page 7) is a significant contribution in its own right. The authors rightly identify the challenge of evaluating new ISA extensions without access to proprietary design details. PISA offers an elegant middle-ground between high-level analytical models and full simulation. By grounding projections in the measured performance of existing proxy instructions and validating the methodology with known instructions (Section 5.2, page 9), the authors build a strong foundation of credibility for their subsequent MQX performance claims. This is a technique that could be adopted by other researchers in the architecture community.

3. Holistic, Multi-Layered Approach: The paper tells a complete and convincing story. It begins with state-of-the-art software optimization (the AVX-512 implementation), demonstrates its limits, proposes a targeted hardware fix (MQX), and then projects the system-level impact (the speed-of-light analysis in Section 6, page 11). This layered approach makes the final conclusion—that CPUs can approach ASIC performance—feel earned and well-supported, rather than speculative.

4. Significant Contextual Placement: This work fits beautifully within the broader landscape of computer architecture. It directly engages with the long-standing debate on general-purpose vs. specialized computing. By targeting FHE, a workload often considered the exclusive domain of accelerators, the paper makes a powerful case for the continued relevance and adaptability of the modern CPU. The potential to eliminate the host-accelerator data transfer bottleneck is a critical system-level advantage that is correctly highlighted.

Weaknesses

The paper's weaknesses are minor and largely related to the inherent limitations of its forward-looking proposal, rather than flaws in its execution or reasoning.

1. Optimism of the Speed-of-Light Model: The speed-of-light (SOL) analysis in Section 6 is a powerful tool for illustrating potential, but it is, by the authors' own admission, an optimistic upper bound. Achieving near-linear scaling across 192 cores for a memory-intensive kernel like NTT is a formidable software and system challenge, involving NUMA effects, cache coherence, and thread synchronization overheads that are not captured in the simple scaling model of Equation 13. While the authors wisely temper their claims in the "Towards realizing SOL performance" paragraph (page 12), the headline results in Figure 7 might be interpreted as more achievable than they are in practice.

2. Limited Exploration of Power and Area: The design philosophy of MQX is to minimize engineering effort, which implicitly addresses area and design cost. However, the paper does not include any quantitative estimates of the silicon area or power impact of adding the proposed MQX execution units (e.g., 8 parallel 64x64->128-bit multipliers). While a detailed analysis is beyond the scope of this work, some high-level discussion or citation of related work on the cost of such units would strengthen the argument for hardware feasibility.

Questions to Address In Rebuttal

1. The SOL projection in Section 6 assumes that the single-core implementation can be scaled across a multi-core chip. However, the performance of the single-core MQX implementation itself begins to degrade for larger NTT sizes (e.g., N=2^16 on Intel Xeon, Figure 5a), which you hypothesize is due to L2 cache capacity. On a large multi-core processor where L3 cache is a shared resource, could contention for shared caches and memory bandwidth become a dominant bottleneck well before linear scaling is achieved, thus making the SOL projections even more optimistic for larger problem sizes?

2. The PISA methodology relies on mapping a proposed instruction to a single "most structurally similar" existing instruction. In the case of _mm512_mul_epi64, the proxy is _mm512_mullo_epi64. Could the authors elaborate on why this is a reasonable proxy? A full 64x64->128 widening multiplier is more complex than a 64x64->64 multiply-low unit. Is the assumption that the critical path latency and port usage would be similar, or that a modern SIMD multiplier already computes the full result internally and simply discards the high part for mullo? Some justification here would further bolster confidence in PISA.

3. Your work compellingly argues for bringing multi-word arithmetic support to CPU vector units. Beyond FHE, what other application domains do you see as major beneficiaries of the MQX extension? Could this be a general-purpose feature that also accelerates other forms of cryptography, high-precision scientific computing, or even large number factorization?

---

Review Form

Reviewer: The Innovator (Novelty Specialist)

Summary

The paper presents an investigation into closing the performance gap between general-purpose CPUs and specialized hardware for cryptographic kernels, specifically NTT and BLAS operations on large integers. The authors' contribution can be deconstructed into three parts: (1) an optimized software implementation using existing scalar and SIMD instructions (AVX-512), (2) a proposed ISA extension named Multi-word Extension (MQX) to further accelerate these kernels, and (3) a performance modeling methodology termed Performance Projection using Proxy ISA (PISA) to estimate the gains from MQX.

My analysis concludes that while the engineering effort is sound and the performance results are compelling, the core ideas presented as novel are, in fact, derivative of prior, well-established architectural concepts. The central proposal, MQX, is a direct adaptation of SIMD instructions proposed and documented over a decade ago for Intel's Larrabee and Knights Corner architectures. The PISA methodology is a pragmatic formalization of a common-sense modeling technique (proxy-based estimation) rather than a fundamentally new evaluation framework. The paper's primary contribution is therefore not one of invention, but of demonstrating the significant value of re-introducing and adapting old ideas to a new data type (64-bit) and a modern problem domain (cryptography).

Strengths

1. Excellent Problem-to-Solution Mapping: The paper correctly identifies the specific arithmetic operations (multiplication with wide results, addition/subtraction with carry propagation) that are bottlenecks for large integer arithmetic in existing SIMD instruction sets.
2. High-Impact, Low-Complexity Proposal: The proposed MQX instructions, despite their lack of novelty, are shown to yield substantial performance improvements (a further 2.1x-3.7x over AVX-512 on page 10, Figure 5). The authors correctly argue that the hardware implementation cost would be minimal, as the scalar analogues are fundamental to the x86 ISA. This represents a very favorable complexity-vs-benefit trade-off.
3. Commendable Transparency: The authors are transparent in citing the prior art that their work is based on. In Section 4.1 (page 6), they explicitly draw parallels between MQX and the SIMD instructions found in Intel's Larrabee New Instructions (LRBni) [38] and Knights Corner (KNC) intrinsics [23]. This transparency is laudable, but it also serves to undermine the claim of novelty.

Weaknesses

1. Fundamental Lack of Novelty in the MQX ISA Extension: The core proposal of this paper is the MQX instruction set. However, these instructions are conceptually identical to prior art.

   • Vector Add-with-Carry and Subtract-with-Borrow: The proposed _mm512_adc_epi64 and _mm512_sbb_epi64 are vector versions of the x86 ADC/SBB instructions. As the authors themselves note, vector versions of these operations (vadcpi, vsbbpi) were key features of the Larrabee ISA (LRBni) [38] from 2008 and were later documented as intrinsics for the Knights Corner (MIC) architecture [23]. The only "delta" here is the extension from 32-bit elements to 64-bit elements and the use of AVX-512 mask registers for carry/borrow flags instead of a dedicated flag register. This is an evolutionary, data-width-extension change, not a novel conceptual contribution.
   • Widening Multiplication: The proposed _mm512_mul_epi64 to produce a 128-bit result from two 64-bit inputs is an extension of the fundamental MUL instruction in x86. Again, vector widening multiplies for smaller data types (e.g., 32-bit) existed in KNC. The concept is not new.

2. Limited Novelty of the "PISA" Methodology: The authors introduce PISA as their method for performance modeling (Section 4.2, page 7). While giving it an acronym lends it an air of novelty, the underlying technique is simply proxy-based performance estimation. The practice of using an existing, structurally similar instruction to model the performance characteristics (latency, port usage) of a hypothetical instruction is a standard and long-standing technique in both industry and academic architecture exploration, especially when cycle-accurate simulators are unavailable or lack support for new ISAs. The novelty is in the application, not the method itself.

3. Framing of the Contribution: The paper is framed as a proposal for a new ISA extension. A more accurate framing would be an argument for the reinstatement and adaptation of previously abandoned, but highly effective, SIMD concepts for modern cryptographic workloads. The current framing overstates the inventive aspect of the work.

Questions to Address In Rebuttal

1. Beyond the change in operand width from 32-bit to 64-bit and the use of mask registers for carry propagation, what are the fundamental conceptual differences between the proposed MQX instructions (adc_epi64, sbb_epi64) and the vadcpi/vsbbpi instructions from Larrabee New Instructions [38]? Please justify why this adaptation constitutes a novel architectural proposal rather than an extension of prior art.

2. The PISA methodology (Section 4.2, page 7) is presented as a novel contribution. Can the authors provide citations to prior work in performance modeling and differentiate PISA from the general, well-established practice of proxy-based estimation, where an existing instruction is used to model a proposed one that maps to similar hardware resources?

3. The sensitivity analysis in Section 5.5 (page 11) suggests that replacing a full widening multiply with a multiply-high instruction (+Mh,C) results in only a minor performance degradation. Given that a multiply-high instruction is likely cheaper to implement than a full widening multiply that must write back two full vectors, why did the authors choose to propose the more complex instruction in the main MQX design? Does this choice represent the optimal trade-off between implementation cost and performance benefit?