A Lightweight Fault-Detection Scheme for Barrett Modular Multiplication Using Multiple Conditional Reduction Paths

This paper proposes a lightweight fault-detection scheme for Barrett Modular Multiplication (BMM) using a Statistical Reduction Monitoring (SRM) method. The work addresses security concerns in lattice-based Post-Quantum Cryptography (PQC) and Fully Homomorphic Encryption (FHE) schemes, where BMM is a critical component of Number Theoretic Transform (NTT) operations.

Polynomial multiplication is the most resource-, time-, and energy-critical operation in lattice-based PQC and FHE schemes. Lattice-based PQC schemes such as Kyber and Dilithium have been standardized, while lattice-based FHE schemes including BGV, BFV, and CKKS are leading candidates in the FHE area. BMM is widely adopted in PQC and FHE hardware accelerators due to its hardware-friendly nature and efficient modular reduction capabilities. However, Side-Channel Attacks (SCAs) and Hardware Trojans may introduce intentional faults, while aging and other factors can cause unintentional faults. These faults may target the BMM unit, potentially leading to information leakage and compromising system security.

The paper discusses two primary attack vectors:

1. Loop-abort attacks (Espitau et al.): Attackers abort the sampling process before completion to obtain lower-degree polynomials, breaking intended masking and leaking linear equations that reveal information about secrets.

2. Zeroizing attacks (Ravi et al.): Attackers target the modular multiplication operation of NTT and make the twiddle factor (root of unity) zero, producing lower-degree polynomials at the NTT output, thereby reducing the entropy of secret and error polynomials.

The proposed word-wise BMM takes two l-bit operands (a and b) as inputs along with an l-bit modulus q. In each iteration, the algorithm extracts w-bit words from the inputs. The algorithm uses:

• Variable c: stores the shifted partial multiplication result

• Variable κ: stores the truncated lower bits of the product between c and the precomputed constant μ (where μ = ⌊2(2l)/q⌋)

• Variable r: stores the intermediate modular reduction result computed as r = c − κq

The algorithm employs two conditional reduction stages:

• Reduction-1 (Line 10): Checks if r ≥ q, and if satisfied, subtracts q from r and sets flag ρ1 = 1

• Reduction-2 (Line 14): Checks if the accumulated R ≥ q, and if satisfied, subtracts q and sets flag ρ2 = 1

The SRM tracks the frequency of reduction operations during algorithm execution. Four possible cases are identified:

1. No reduction (χ0)

2. Only Reduction-1 (χ1)

3. Only Reduction-2 (χ2)

4. Both reductions (χ3)

The probability relationship without any fault occurrence is: Pχ0 > Pχ2 > Pχ1 > Pχ3

The paper provides mathematical proofs (Theorem 1 and Theorem 2) establishing that:

• The Barrett quotient κ ∈ Q, Q−1 (exact quotient or one less)

• The intermediate remainder always satisfies 0 ≤ r < 2q

• Reduction-1 Only: Occurs rarely because the exact quotient κ = Q is produced for most intermediate values at every shift level. Table II shows that for l=12, w=4, the exact quotient is obtained for all 226 possible partial products when left-shift is 0, 4, or 8 bits, and for 221/226 and 154/226 cases for 12-bit and 16-bit shifts respectively.

• Reduction-2 Only: Occurs more frequently than Reduction-1 because it depends on normal accumulation of remainders (R + r ≥ q), which happens more often than Barrett quotient underestimation.

• Both Reductions: Has the lowest probability since Reduction-2 can only occur for a subset of cases where Reduction-1 is activated.

• No Reduction: Has the highest probability as it represents the complement of all reduction events.

The proposed BMM uses:

• Two multipliers (X1 and X2): X1 computes c by multiplying awi and bwj; X2 computes κ by multiplying c and μ

• Two subtraction blocks: −1 computes r, −2 computes Reduction-1 and Reduction-2

• A χ gen block that calculates χ0, χ1, and χ2 (χ3 is omitted to reduce hardware overhead since it cannot exclusively detect any fault not already detected by the other metrics)

• A matcher block that takes χ0, χ1, and χ2 and flags final fault occurrence

The implementation uses 128 instead of 100 for percentage calculations to avoid division operations (division by 128 can be implemented with a 7-bit shift).

For Kyber-768, the key generation requires 3 NTT operations on the secret vector s and 3 NTT operations on the error polynomial e. The secret polynomials are generated using PRF and CBD processes where the secret vector s is sampled uniformly and randomly. The fault-free percentage ranges are:

• χ0: 77.66–80.41%

• χ1: 0.14–0.61%

• χ2: 19.18–21.91%

• χ3: 0.00–0.24%

The CKKS key generation uses different polynomial degrees and moduli. The secret vector s is generated from a ternary or Gaussian distribution. The fault-free percentage ranges are:

• χ0: 80.06–83.81%

• χ1: 0.07–0.11%

• χ2: 16.11–19.85%

• χ3: 0.00–0.01%

Two types of faults are studied:

1. Random bit-flip faults: Bits are flipped from 0 to 1 at random positions in c, κ, and r

2. Burst bit-flip faults: Consecutive bit positions are flipped in these variables

For Kyber (n=256), NTT requires 1,024 butterfly iterations; for CKKS (n=4096), NTT requires 24,576 iterations. Faults are injected by varying the number of faulty NTT iterations (λ) and the number of faulty bits (φ).

• Kyber: Up to 128 faulty NTT iterations (out of 1,024) with any number of injected faults cause χ0, χ1, and χ2 to deviate from fault-free values, achieving 100% detection efficiency. When faulty iterations are 64 or fewer, detection efficiency decreases.

• CKKS: Up to 512 faulty NTT iterations (out of 24,576) achieve 100% detection efficiency. When faulty iterations are 512 or fewer, detection efficiency decreases.

For permanent faults (persisting throughout all NTT iterations), the scheme achieves 100% fault detection for both random and burst faults regardless of the number of faulty bits.

• Kyber BMM (l=12, w=4): 18.9% resource overhead

• Kyber BMM (l=12, w=6): 20.5% resource overhead

• Full Kyber BMM (l=12, w=12): 8.3% resource overhead

• CKKS BMM (l=32, w=8): 10.9% resource overhead

• CKKS BMM (l=32, w=16): 7.9% resource overhead

• Full CKKS BMM (l=32, w=32): 6.13% resource overhead

• Energy overhead is approximately 1% for all Kyber and CKKS variants

• Compared to recomputation-based approaches (RESWO, RESO, RENO by Baidya et al.) that incur approximately 85–88% slice overhead, the proposed SRM requires only 18.9% additional slices for equivalent Kyber configuration.

• Compared to Barrett Modular Redundancy (BMR) by Aghapour et al. with area overheads of 17.1–19.4% and energy overheads of 21.87–31.73%, the proposed SRM achieves comparable or lower area overhead while reducing energy overhead to below 3%.

When embedded in NTT architectures:

• Kyber NTT: approximately 5.2% area overhead, 1.2% delay overhead, <1% power overhead

• CKKS NTT: approximately 1.2% area overhead, 1.3% delay overhead, <1% power overhead

The proposed scheme achieves the lowest area, delay, and energy overhead among all existing protected NTT schemes compared in the study (including Sarker et al., Ahmadi et al., Ravi et al., Bauer et al., Jati et al., and Baidya et al.).

The paper proposes a novel statistical fault detection method based on reduction path execution patterns of a word-wise BMM. The scheme achieves comparable fault-detection capability with lower hardware-resource, delay, and energy overhead than existing BMM-specific fault-detection techniques. It can detect 100% of permanent faults and is effective in detecting transient faults. The implementation and test cases are made available on a public GitHub repository for independent verification.

Improvements to AI Systems Based on This Paper:

1. Fault-Aware Cryptographic Accelerator Design: AI systems can be enhanced to automatically generate hardware architectures for lattice-based PQC/FHE accelerators that embed statistical fault-detection monitors (like SRM) during design-space exploration. The improved AI can optimize trade-offs between fault-detection coverage (e.g., 100% permanent fault detection) and hardware overhead (e.g., <20% area, <3% energy) by learning from the paper’s overhead benchmarks (18.9% for Kyber, 10.9% for CKKS).

2. Real-Time Anomaly Detection in Cryptographic Operations: AI systems can be trained to monitor runtime statistical distributions of reduction events (χ0–χ3) in BMM units. The improved system can detect transient faults (e.g., bit-flips in c, κ, r) and permanent hardware Trojans by comparing observed χ-value frequencies against the paper’s fault-free baselines (e.g., Kyber: χ0=77–80%, χ2=19–22%, χ1<0.6%). This enables early warning of side-channel attacks or hardware degradation without full recomputation.

3. Adaptive Fault-Tolerance Policies: AI controllers can dynamically adjust fault-detection sensitivity based on operational context. For example, if the system detects χ-values deviating from expected ranges (e.g., χ1 exceeding 0.61% in Kyber), it can trigger fallback mechanisms (e.g., re-keying, redundant computation) or throttle operations. The improved AI can learn optimal thresholds for different PQC/FHE parameter sets (e.g., n=256 vs. n=4096) using the paper’s fault-injection results (e.g., 100% detection up to 128 faulty NTT iterations for Kyber, 512 for CKKS).

4. Hardware-Software Co-Design Optimization: AI-based compilers or hardware synthesis tools can use the paper’s architecture insights (e.g., omitting χ3 to save hardware, using 128 instead of 100 for division-free percentages) to generate more efficient fault-detection circuits. The improved AI can automatically select word-widths (w=4,6,8,12,16) and reduction-stage configurations to minimize overhead while maintaining detection guarantees, based on the paper’s resource overhead tables (6.13–20.5% area, 1% energy).

5. Predictive Maintenance for Cryptographic Hardware: AI systems can model long-term drift in χ-value distributions caused by aging or environmental stress. By correlating gradual deviations from the paper’s fault-free probabilities (e.g., Pχ0 > Pχ2 > Pχ1 > Pχ3) with hardware degradation, the improved AI can predict imminent faults and schedule preventive maintenance or key rotation before security is compromised.

6. Security-Aware Neural Architecture Search (NAS): The paper’s overhead data can be used as a reward signal in NAS frameworks to design BMM units that inherently resist fault-injection attacks. The improved AI can generate Pareto-optimal designs balancing area, delay, energy, and fault-detection coverage, leveraging the paper’s comparison data (e.g., 5.2% area overhead for Kyber NTT vs. 85–88% for recomputation-based methods).

7. Automated Threat Modeling for PQC/FHE Systems: AI systems can use the paper’s threat model (loop-abort, zeroizing attacks) to generate adversarial test cases for cryptographic implementations. The improved AI can simulate fault injections (random/burst bit-flips) and validate whether χ-monitoring correctly flags anomalies, enabling automated security certification of new hardware designs.

8. Energy-Aware Fault Detection Scheduling: AI power managers can use the paper’s finding that energy overhead is 1% to decide when to enable SRM monitoring. For battery-constrained devices, the improved AI can selectively activate fault detection only during critical operations (e.g., key generation, decryption) and disable it during non-sensitive tasks, using the paper’s detection-efficiency curves (e.g., 100% detection for ≥128 faulty iterations in Kyber) to set monitoring frequency.

Capabilities of the Improved AI System:

• Designs PQC/FHE accelerators with built-in, low-overhead fault detection (≤20% area, ≤3% energy) that catch 100% of permanent faults and most transient faults.

• Continuously monitors cryptographic hardware in real time, detecting side-channel attacks or hardware Trojans within milliseconds by analyzing statistical reduction patterns.

• Dynamically adjusts security postures (e.g., re-encryption, redundancy) based on fault-detection confidence levels, minimizing performance impact.

• Predicts hardware aging failures before they cause security breaches, enabling proactive maintenance.

• Automates the security validation of new cryptographic hardware designs against fault-injection attacks, reducing manual testing effort by orders of magnitude.

Polynomial multiplication is the most resource-, time-, and energy-critical operation in lattice-based Post-Quantum Cryptography (PQC) and Fully Homomorphic Encryption (FHE) schemes. Lattice-based PQC schemes such as Kyber and Dilithium have already been standardized, while lattice- based FHE schemes such as BGV, BFV, and CKKS are widely recognized as leading candidate in FHE area. Barrett Modular Multiplication (BMM) for polynomial multiplication is widely adopted in PQC and FHE hardware accelerators due to its hardware friendly nature and efficient modular reduction capabilities. However, Side-Channel Attacks (SCAs) and Hardware Trojans may introduce intentional faults, while aging and various other factors can cause unintentional faults. These faults may target the BM M unit, one of the most critical components of PQC and FHE infrastructures, potentially leading to information leakage and compromising system security. In this paper, we employ a Statistical Reduction Monitoring (SRM) method to protect the BM M unit against such adversarial conditions. The proposed approach incurs minimal hardware overhead while providing efficient detection of both random and bur