arXiv CS open access

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

2026 · arxiv_cs

arXiv CS · Papers · 2026

cryptography cybersecurity privacy security

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

A Lightweight Fault-Detection Scheme for Barrett Modular Multiplication Using Multiple Conditional Reduction Paths Rourab Paul∗, Member, IEEE, Paresh Baidya†, Krishnendu Guha‡, Amlan Chakrabarti§ ∗ Department of Computer Science and Engineering, Shiv Nadar University, Chennai, Tamil Nadu, India † Department of Computer Science and Engineering, Siksha ‘O’ Anusandhan Deemed to be University, Bhubaneswar, India ‡ School of Computer Science and Information Technology, University College Cork, Ireland § School of IT, University of Calcutta, West Bengal, India

arXiv:2608.10736v1 [cs.CR] 11 Aug 2026

∗ rourabpaul@snuchennai.edu.in

Abstract—Polynomial multiplication is the most resource, time-, and energy-critical operation in lattice-based PostQuantum Cryptography (PQC) and Fully Homomorphic Encryption (FHE) schemes. Lattice-based PQC schemes such as Kyber and Dilithium have already been standardized, while latticebased 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 efﬁcient 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 efﬁcient detection of both random and burst faults under both permanent and transient fault conditions. Index Terms—Barrett Modular Multiplication, Polynomial Multiplication, Fault, NTT, FPGA.

I. I NTRODUCTION Decimation-in-Time (DIT) and Decimation-in-Frequency (DIF) Number Theoretic Transform (NTT) is the backbone of lattice-based post-quantum cryptography (PQC) and fully homomorphic encryption (FHE). It signiﬁcantly accelerates polynomial multiplication by reducing the computational complexity of multiplying two degree-(n − 1) polynomials from O(n2 ) to O(n log n). Therefore, polynomial multiplication in NIST-standardized lattice-based cryptographic schemes such as Kyber [1] and Dilithium [2], as well as in FHE schemes including Brakerski Fan Vercauteren (BFV) [3] and Brakerski Gentry Vaikuntanathan (BGV) [4], which are part of the NIST FHE standardization framework, can be signiﬁcantly accelerated through dedicated hardware accelerators based on the N T T . DIT uses the Cooley Tukey (CT) butterﬂy structure, whereas DIF employs the Gentleman Sande (GS) butterﬂy structure. Both the CT and GS butterﬂy units require modular multiplication as a fundamental operation. Barrett [5] modular

multiplication (BMM) is one of the most efﬁcient and widely adopted algorithms for performing modular multiplication in lattice-based cryptographic schemes. However, due to the globalization of the silicon supply chain, hardware Trojans have emerged as a signiﬁcant threat to PQC and FHE hardware accelerators. Since the BM M is one of the most resource, power-, and time-critical components in PQC and FHE implementations, it represents an attractive target for adversaries. By compromising the BM M , attackers can disrupt the functionality of the entire PQC and FHE infrastructure deployed in secure processors. As a result, it potentially leading to erroneous computations, denial-of-service attacks, or leakage of sensitive information. A. Threat Model Lattice-based PQC schemes often require a sampler to generate errors and secrets. Thomas Espitau et al. [6] perform a loop-abort attack on the samplers used in CRYSTALS-Kyber, FrodoKEM, BLISS, and the GPV signature scheme. The error or secret polynomial in the lattice-based PQC schemes mentioned above can be written as e = [e0 , e1 , e2 , . . . , en−1 ]. Espitau et al. [6] show that by aborting the sampling process before completion, an attacker can obtain a lower-degree polynomial of the form e = [e0 , e1 , . . . , ep−1 , 0, 0, . . .], where the remaining coefﬁcients are zero due to the premature termination of the sampler. As a result, this breaks the intended masking and leaks linear equations that reveal information about the secret. The N T T operations of Kyber and Dilithium in the PQC library for ARM Cortex-M4 (PQM4) [7] were successfully attacked by [8] Ravi et al. They targets the modular multiplication operation of N T T and makes the twidle factor (root of unity) zero which produces a lower degree polynomial at the output of N T T . It is to be noted that, in lattice-based PQC and FHE schemes, polynomial multiplication is typically performed between a twiddle factor and another operand, which is a coefﬁcient of the transformed polynomial and may originate from secret vectors, error polynomials, ciphertext polynomials, or other intermediate polynomials. In Kyber, the key generation, encryption, and decryption processes pass the

secret polynomial s, error polynomial e, ephemeral secret r, noise polynomials e1 (vector) and e2 (scalar), and the ﬁrst ciphertext component u to the N T T operation [1]. In CKKS, the key generation, encryption, and decryption processes involve the secret polynomial s, public polynomial a, error polynomial e, ephemeral secret v, and noise polynomials e0 and e1 , with ciphertext components (c0 , c1 ) [9]. Similarly, other latticebased PQC schemes such as Dilithium, NTRU and Falcon, as well as FHE schemes including BGV and BFV, require multiple polynomials to be transformed into the N T T domain for efﬁcient polynomial multiplication. Therefore, zeroizing attacks [8] and loop-abort attacks [6] can produce lower-degree polynomials at the N T T output, thereby reducing the entropy of the secret and error polynomials in PQC and FHE schemes. B. Literature The fault-detection literature for PQC and FHE can be broadly divided into two categories in this context. 1) Fault Detection for PQC and FHE: Several fault detection architectures have been proposed as error detection mechanisms for various cryptographic primitives, which are the fundamental building blocks of PQC and FHE protocols. Fault detection techniques, including cyclic redundancy check (CRC) [10], RENO [11], RESO [12], REMO [13] and RECO [12] are commonly adopted due to their low implementation overhead and ease of integration. In paper [12], Canto et al. propose recomputation-based fault detection architectures for lattice-based key encapsulation mechanisms (KEMs) FrodoKEM, Saber, and NTRU on a Kintex Ultrascale+ FPGA. These schemes use multiplication units such as matrix-by-matrix, matrix-by-vector, vector-by-vector, and polynomial multiplications. Their work introduce Recomputing with Shifted Operands (RESO), Re-computing with Negated Operands (RENO) and Re-computing with Scaled Operands (RECO) for the Multiply-Accumulate (MAC) operation to detect both transient and permanent faults with high error coverage and minimal performance overhead. In artcile[10], Canto et al. presented a CRC-based error detection technique for ﬁnite-ﬁeld multipliers in the Luov post-quantum signature scheme. The proposed CRC-5-based architecture is implemented on a Kintex UltraScale+ FPGA and achieves high fault coverage with acceptable hardware overhead. In the article [11], Sarker et al. have implemented fault detection architectures for hardware/software co-design implementations of the N T T accelerator on Zynq UltraScale+ and Spartan7 devices. They propose error detection through recomputing with negated operands (RENO) and recomputing with negated and swapped operands to detect both transient and permanent faults in the N T T accelerator. The result demonstrates that placing RENO deeper in the logic path increases slice utilization but increases error detection efﬁciency exceeding 99% against stuck-at fault models. Saeed et al. [13] proposed a lightweight fault detection architecture for modular exponentiation C = X Y mod q, a crucial operation of numerous cryptographic applications such as difﬁe-Hellman key exchange, RSA cryptosystems,

ElGamal encryption, and some PQC schemes. The proposed Recomputation with Modular Offset (REMO) computes C ′ = (X + Of f set)Y mod q. Then it compares the result of the modular exponentiation unit, C, and the REMO unit, C ′ , to detect faults. This method achieves nearly 100% error detection with minimal computational and area overhead. 2) BMM Speciﬁc fault Detection: To protect the BM M , serves as a critical modular multiplication unit within the N T T of lattice-based PQC and FHE schemes, many countermeasures and security mechanisms have been proposed in the literature. Aghapour et al. [14] implements safeguards for BM M and Barrett Modular Reduction (BM R). For BM R they used a probability approximation. As shown in Eq. 1, two intermediate remainders, r1 and r2 , are computed to determine the ﬁnal remainder r. Here, N is a p-bit integer, while u is a 2p-bit integer. q̂ is precomputed constant. r1 = u mod bp+1 , r2 = (q̂N ) mod bp+1 , r = r1 − r2

(1)

The ﬁnal remainder is calculated by a while loop as shown in Eq. 2. The theoretical property of BM M says that there is approximately a 99% probability that only a single subtraction will be required within the ﬁnal correction loop, whereas there is approximately a 1% probability that two subtraction operations will be required before obtaining the ﬁnal remainder. while (r ≥ N ) do r ← r − N

(2)

For BM M , Aghapour et al. [14] uses Recomputation with Modular Offset (REMO) scheme. To detect fault of ab mod q, they calculate (a+k1 q)(b+k2 q) mod q where k1 and k2 are random integers. In a fault-free situation, both computations produce same outputs. However, any mismatch between the two outputs is interpreted as an a fault, and an error ﬂag is asserted. Baidya et al. [15] proposed three recomputation-based fault detection techniques, namely Recomputation with Negated Operand (RENO), Recomputation with Shifted Operand (RESO), and Recomputation with Swapped Operand (RESWO). Baidya et al. [15] proposed protection schemes for the BM M and reported the fault-detection overhead at the N T T level. However, the overhead of RESO, RECO, and RESWO recomputation-based fault detection schemes was not evaluated separately for the BM M . If quantiﬁed at the BM M level, the additional computations introduced by recomputation would likely result in a signiﬁcant overhead. C. Contribution The existing fault detection schemes for BMMs are predominantly recomputation-based, resulting in signiﬁcant area and energy overheads. In this work, we propose a word-wise BMM architecture consisting of two reduction stages. By exploiting the probabilistic behavior of the conditional execution paths within these reduction stages, we design a Statistical Reduction Monitor (SRM) for fault detection. The main contributions of this work are summarized as follows:

Statistical Reduction-Aware Fault Detection: The proposed fault detection scheme exploits the statistical behavior of the two reduction stages employed in the word-wise BMM. Unlike existing recomputation-based approaches, the proposed Statistical Reduction Monitor (SRM) leverages the intrinsic probability distribution of reduction-path execution to detect faults. • Ultra-Lightweight Protection for BMM Architectures: The proposed scheme achieves efﬁcient fault detection with minimal resource and energy overhead, making it one of the lightest-weight protection mechanisms specifically designed for BMM architectures. The protected BMM is also integrated into the N T T , and to the best of our knowledge, it achieves the lowest area, delay, and energy overhead among all existing protected N T T schemes. • Comprehensive Validation Against Diverse Fault Models: The extensive simulation and hardwareemulation results demonstrate that the proposed wordwise BM M achieves high fault-detection efﬁciency against both random and burst fault injections during the Kyber and CKKS key-generation processes. The proposed fault-detection scheme effectively detects both transient and permanent faults while incurring minimal hardware overhead. This paper is organized as follows. Sec. I introduces the problem statement. Sec. II presents the algorithm of the proposed word-wise BMM. Sec. III describes the proposed Statistical Reduction Monitor (SRM). Sec. IV details the hardware architecture of the proposed word-wise BMM. Sec. V and Sec. VI discuss the secret-vector generation processes of Kyber and CKKS, and the corresponding fault-injection methodologies, respectively. Sec. VII presents the error-detection efﬁciency and hardware overhead of the proposed fault-detection scheme. Finally, Sec. VIII concludes the paper. •

II. BARRETT M ODULAR M ULTIPLICATION BMM (W ORDWISE ) The 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 a and b. The indices i and j are used to select the corresponding windows from a and b, respectively. As shown in Algorithm 1, the variables c, κ, and r are used to store intermediate values during each iteration. The variable c stores the shifted partial multiplication result obtained from the product of the selected words from a and b. The variable κ stores the truncated lower bits of the product j 2l kbetween c and the precomputed constant µ, where µ = 2q . The variable r stores the intermediate modular reduction result computed as r = c − κq. This step provides an approximate reduction of the partial product with respect to the modulus q. In line 10 of Algorithm 1, the ﬁrst conditional reduction checks whether r ≥ q. If this condition is satisﬁed, the modulus q is subtracted from r, and the ﬂag ρ1 is set to indicate that a correction was performed. Otherwise, the value of r is directly accumulated into R. This ﬁrst conditional

Algorithm 1 Wordwise BMM Input a = (al−1 , ...a1 , a0 ), b = (bl−1 , ...b1 , b0 ) 2×l q = (ql−1 , ...q1 , q0 ) where µ = ⌊ 2 q ⌋ & k = 2 × l Output c = (cl−1 , ...c1 , c0 ), ρ1 , ρ2 1: R = 0, ρ1 = 0, ρ2 = 0 l 2: for i=0 to ( w − 1) do 3: for j=0 to ( wl − 1) do 4: awi = a[iw+w−1...iw] 5: bwj = b[jw+w−1...iw] 6: c = awi × bwj 7: c = c || (i + j) × w{0} 8: κ = (c × µ)[2k−1...k] 9: r =c−κ×q 10: if (r ≥ q) then ⊲ Reduction-1 11: R = R + r − q, ρ1 = 1 12: else 13: R = R + r, ρ1 = 0 14: if R ≥ q then ⊲ Reduction-2 15: R = R − q, ρ2 = 1 16: else 17: ρ2 = 0 18: return R, ρ1 , ρ2

reduction is named as Reduction − 1 Similarly, in line 14 of Algorithm 1, a second reduction named as Reduction − 2 is applied to ensure that the accumulated R remains within the valid range [0, q − 1]. If R ≥ q, the modulus q is subtracted once more and the ﬂag ρ2 is set to 1. These ρ1 and ρ2 are the inputs of our statistical reduction monitoring. TABLE I: Parameters and Description Parameters c, κ and r n−1 λ χ0 φ nχ0 , χ0 nχ1 , χ1 nχ2 , χ2 nχ3 , χ3

Description Three internal register of wordwise BMM Degree of polynomial Number of faulty loops in the N T T , out of n ×log2 (n) 2 total loops Number of faulty loops in the N T T (same total: n × 2 log2 (n)) Number of faulty bits Number of operations without any reduction; nχ0 expressed as a percentage (%) Number of operations with Reduction-1 (Line 10 of Algorithm 1); nχ1 expressed as a percentage (%) Number of operations with Reduction-2 (Line 14 of Algorithm 1); nχ2 expressed as a percentage (%) Number of operations with Reduction-1 and Reduction-2 (Line 10 & Line 14 of Algorithm 1); nχ3 expressed as a percentage (%)

III. FAULT D ETECTION WITH S TATISTICAL R EDUCTION M ONITORING (SRM) Our Statistical Reduction Monitoring (SRM) tracks the frequency of reduction operations during the execution of the algorithm. For the two reduction steps: Reduction − 1 and Reduction − 2 described in Line 10 and Line 14 of Algorithm 1, respectively, four possible cases may occur: (i)

TABLE II: Distribution of Exact and Approximate Quotients for different Left-Shift where l=12, w=4 Left Shift (line 7 of Algo. 1) ≪0 ≪4 ≪8 ≪ 12 ≪ 16

Possible Values of c at line 6 of Algo. 1 226 226 226 226 226

κ=

j k c q

226 226 226 221 154

κ=

j k c q

−1

0 0 0 5 72

no reduction, (ii) only the reduction-1, (iii) only the reduction2, and (iv) both reductions. Sec III-A explains that when the input operand a is a uniformly distributed random number and b is an N T T twiddle factor (which is generally the case during key generation in lattice-based PQC and FHE schemes) as shown in Algorithm 1, the proposed word-wise BM M most frequently bypasses both reduction stages, referred to as the ’no reduction’ case (i). In contrast, the simultaneous execution of both reduction stages, referred to as the ’both reduction’ case (iv), occurs with the lowest probability. The ’only reduction-2’ case (iii) is the second most frequent execution path, whereas the ’only reduction-1’ case (ii) is the third most frequent. The same statistical execution pattern can be explained when the input operand a in Algorithm 1 corresponds to the intermediate N T T coefﬁcients derived from the secret key during the key generation process of both Kyber and CKKS. The details observation is discussed in Sec. V-A and Sec. V-B. As shown in Algorithm 2, the SRM takes ρ1 and ρ2 as inputs form Algorithm 1 and computes the percentages χ0 , χ1 , χ2 , and χ3 , corresponding to the four cases mentioned above. A. Explanation of Probabilities If total n events are there, probability for ’No Reduc0 tion’ is Pχ0 = nχ n , Probability for ’ only the reduction-1’ is 2 1 , Probability for ’ only the reduction-2’ is Pχ2 = nχ Pχ1 = nχ n n 3 and ﬁnally Probability for ’both reduction’ is Pχ3 = nχ . Here n n=nχ0 +nχ1 +nχ2 +nχ3 . From our experimental observation, the probability relationship without any fault occurrence in c, κ and r can be expressed as: Pχ0 > Pχ2 > Pχ1 > Pχ3

(3)

1) Probability of Reduction-1 Only: The reduction-1 stage calculated by line 9 of Algorithm 1 is an intermediate remainder r. r = c − κq,

(4)

where c is the intermediate shifted product and κ is the approximate quotient derived from the Barrett approximation that satisﬁes Theorem 1 which shows that only two cases are possible κ = Q or κ = Q − 1. If κ = Q event occurs then the resulting remainder satisﬁes 0 ≤ r < q [by Eq. 18 of Theorem 2]. Then, the reduction-1 stage is never executed. When κ = Q − 1 occurs, then q ≤ r < 2q [by Eq. 19 of Theorem 2]. which activates reduction-1 only operation.

Table II presents the distribution of the exact and approximate Barrett quotients for all possible intermediate partial products generated by the proposed word-wise multiplication under the Kyber N T T parameter set. As shown in Algorithm 1, Line 6 computes the product of two w-bit words : awi and bwi . For w=4, the maximum partial product is 15 × 15 = 225, therefore, 226 distinct possible values in the range [0,225]. Theorem 1 guarantees that the computed j k quotient κ can only be equal to the exact quotient Q ( qc ) j k or Q-1( qc − 1). Table II shows that the exact quotient is obtained for all 226 possible partial products when the leftshift amount is 0, 4, or 8 bits in line 7 of the Algorithm 1. For the 12-bit left shift, the exact quotient is produced for 221 out of 226 cases, whereas for the 16-bit left shift, the exact quotient is produced 154 outjofk226 cases, with the remaining cases corresponding to the qc − 1 approximation predicted by Theorem 1. Therefore, the Table II demonstrates that the exact quotient κ = Q produces for most of the intermediate values at every shift level and the event κ = Q − 1 occurs infrequently. Thus, the quotient κ = Q − 1, which is the necessary condition for activating reduction-1 only, occurs for only a relatively small number of intermediate values. Hence, the probability of triggering reduction-1 is very low. Pχ1 = P (r ≥ q),

(5)

remains signiﬁcantly smaller than the probabilities of the remaining execution paths. 2) Probability of Reduction-2 Only: The probability of reduction-2 only happened when reduction-1 is skipped. If κ j k c is q , then the intermediate remainder satisﬁes 0 ≤ r < q. Therefore, the Reduction-1 stage is not activated. Since the Barrett approximation yields the exact quotient in the overwhelming majority of executions, this Reduction-1 occurs with a very less probability. Thereafter, both branches of the Reduction 1 stage accumulate the intermediate partial remainder r, into the intermediate variable R. Therefore, Reduction-2 only dependsP on the accumulated value R from previous iterations. R = ri . Even of each individual partial remainder satisfy 0 ≤ ri ≤ q. Thus Reduction-1 depends onj Barrett k approximation error which requires a rare event κ = qc − 1, however, Reduction-2 only depends on normal accumulation of remainders which requires R + r ≥ q. This accumulation occurs relatively much more frequently as compared to Barrett quotient underestimation, hence, Pχ2 > Pχ1 . 3) Probability of Both Reduction: Reduction-1 in Algorithm 1 is triggered when the accumulated intermediate value R, generated from the previous iterations, exceeds the modulus q. However, the occurrence of Reduction-1 does not necessarily imply the occurrence of Reduction-2. Although Reduction1 reduces the accumulated value, the resulting intermediate value may still remain below the q required to activate Reduction-2. Consequently, not all executions of Reduction-1 lead to the execution of Reduction-2. As discussed in Section III-A1, the probability of triggering Reduction-1, denoted

by Pχ1 , is relatively low. Since Reduction-2 can only occur for a subset of the cases in which Reduction-1 is activated, it follows that Pχ3 ≤ Pχ1 . 4) Probability of No Reduction: The no-reduction case occurs when none of the reduction events, namely the Reduction1 only event, the Reduction-2 only event, and the both reductions event, is activated. As discussed in Section III-A1, Pχ1 is already relatively small, which consequently makes Pχ3 even less probable. Furthermore, the intermediate value R is accumulated from r. Since, the accumulated value R is, in most cases, smaller than modulus q. Therefore, the probability of triggering Reduction-2 only, Pχ2 , is also relatively low. As a result, a large fraction of executions bypass both reduction stages simultaneously. Since the no-reduction event represents the complement of all reduction events, Pχ0 = 1 − (Pχ1 + Pχ2 + Pχ3 ) ,

(6)

it exhibits the highest occurrence probability among all execution paths. Algorithm 2 Statistical Reduction Monitoring (SRM) Input ρ1 , ρ2 ; Output f 1: nχ0 = 0, nχ1 = 0, nχ2 = 0, nχ3 = 0 l × wl 2: σ = N R × w 3: if (ρ1 = 0) and (ρ2 = 0) then 4: nχ0 ← nχ0 + 1 5: if (ρ1 = 1) and (ρ2 = 0) then 6: nχ1 ← nχ1 + 1 7: if (ρ1 = 0) and (ρ2 = 1) then 8: nχ2 ← nχ2 + 1 9: if (ρ1 = 1) and (ρ2 = 1) then 10: nχ3 ← nχ3 + 1 11: if check = 1 then 12: for i = 0 to 3 do nχi × 100 13: χi ← σ 14: for i = 0 to 3 do 15: if χi < χi,min or χi > ci,max then 16: χi,fault ← 1 17: else 18: χi,fault ← 0 19: f = χ0,fault || χ1,fault || χ2,fault || χ3,fault 20: return f

Theorem 1 (Exact Quotient Property of Barrett Reduction). Let c = m2s [in line 7 of Algorithm 1], where m denotes the partial product of two j kk j k w-bit words and s is the corresponding left-shift. Let Q = qc be the exact quotient, and let µ = 2q be the Barrett precomputed constant, where k = 2 × l is the Barrett scaling factor. The quotient computed by approximate Barrett reduction is κ = cµ [in line 8 of Algorithm 1]. Then, k 2 κ ∈ {Q, Q − 1}.

Proof. Since µ = k that µ + δ = 2q

j kk 2 q

, there exists an δ, 0 < δ < 1 such

. Therefore, µ 1 δ = − k. k 2 q 2

(7)

Now, substituting this expression into the Barrett approximate quotient κ = 2cµk gives δ 1 κ= c − k q 2 c δc = − q 2k

(8) (9)

Let us assume the exact division as c c c and f = f rac( ), 0 ≤ f < 1. = Q + f, where Q = q q q (10) Hence, κ = Q + f − 2δck . Since 0 ≤ 2δck < 1, the subtraction term can reduce the integer part by at most one. Therefore, κ ∈ {Q, Q − 1}. If f > 2δck , then Q<Q+f −

δc < Q + 1, 2k

(11)

which yields κ = Q. Otherwise, f ≤ 2δck , which implies Q−1 < Q+f − 2δck < Q, and therefore κ = Q − 1. Thus,  c δc   f = frac > k, Q, q 2 (12) κ=  δc c  Q − 1, f = frac ≤ k. q 2

Hence, completes the proof. j k Theorem 2. Let κ = 2cµk , exact quotient Q = qc where j kk µ = 2q and let the Barrett remainder be computed as r = c − κq. Then the remainder produced by the proposed Barrett modular multiplication algorithm always satisﬁes 0 ≤ r < 2q. j kk Proof. Since µ = 2q therefore, the ﬂoor function gives µ≤

2k . q

(13)

Now, multiply both sides by the non-negative integer c. Then we have, c 2k cµ ≤ . (14) q Dividing both sides by 2k gives c cµ ≤ . k 2 q Since the ﬂoor function preserves inequality, j cµ k c κ= k ≤ . 2 q

Hence,

c − κ ≥ 0. q

(15)

Multiplying both sides by the positive modulus q gives c − κ q ≥ 0. (16) q Now, we have r = c − κq c c = − κ q ≥ 0. −κ q ≥ q q Therefore, r ≥ 0. Thus, the remainder computed by the proposed Barrett modular multiplication algorithm is always non-negative. Now, from theorem 1, κ ∈ {Q, Q − 1}. Therefore, only two cases need to be considered. Case 1: Exact Quotient (κ = Q) then the remainder becomes r = c − κq = c − Qq. By the Euclidean division theorem, clearly we can write 0 ≤ c − Qq < q,

(17)

0≤r<q

(18)

percentages (base 100), the actual SRM implementation uses 128 instead of 100 to avoid division operations. This is because division by 100 is computationally expensive in hardware, whereas division by 128 can be efﬁciently implemented using a 7-bit shift operation. From the experimental results reported in Table III, Table IV, Table V, Table VI, Table VII, and Table VIII, it is observed that χ3 cannot exclusively detect any fault occurrence that is not already detected by χ0 , χ1 , or χ2 . Therefore, to reduce hardware overhead, the SRM omits the computation of χ3 .Finally, the matcher block takes χ0 , χ1 , and χ2 from the χ gen block and ﬂags the ﬁnal fault occurrence at f . This proposed BM M has two pipeline stages. In the ﬁrst pipeline stage, the computation is performed up to the shifted c, as stated in line 7 of Algorithm 1. In the second pipeline stage, the ﬁnal computation of R is performed through two reduction conditions. if r>q w

, q

<< 1

, q

which implies

gen

-1

q r

1 2 0 1 2

macther

SRM

Case 2: Approximate Quotient (κ = Q − 1) Substituting κ = Q − 1 into the remainder equation gives r = c − κq = c − (Q − 1)q = (c − Qq) + q Since, 0 ≤ c − Qq < q, by the equation 17 Adding q throughout the inequality gives, q ≤ c−Qq+q < 2q. Therefore, q ≤ r < 2q. (19) Hence, by combining above two cases, the intermediate remainder computed by the proposed Barrett modular multiplication is always satisﬁes 0 ≤ r < 2q. IV. H ARDWARE A RCHITECTURE OF SRM P ROTECTED BM M As shown in Fig. 1, the proposed BM M uses 2 multipliers X1 and X2 where X1 is used to compute c by multiplying awi and bwj (line 6 of Algorithm 1). The X2 multiplier is used to compute κ by multiplying c and µ (line 9 of Algorithm 1).Among the two subtraction blocks, −1 and −2 , −1 is used to compute r at line 8 of Algorithm 1, whereas −2 is used to compute Reduction-1 and Reduction-2. The subtractor −2 also computes ρ1 and ρ2 , where ρ1 is set to 1 if the Reduction-1 condition is satisﬁed; otherwise, it is set to 0. Similarly, ρ2 is asserted if the Reduction-2 condition is satisﬁed; otherwise, it remains deasserted. The χ gen block takes ρ1 and ρ2 as input and run Algorithm 2 and calculate χ0 , χ1 and χ2 . Although the calculations of χ0 , χ1 , and χ2 in Algorithm 2 are expressed as

-2

Fig. 1: Hardware Architecture of Wordwise BMM V. S ECRET V ECTORS IN N T T FOR K YBER & CKKS In this paper, we have studied two cases to validate our proposed fault detection approach using a multi-conditional reduction path: secret vector generation in the CRYSTALSKyber PQC algorithm and the CKKS FHE algorithm. Both cases validate the probability distribution of the four reduction situations explained in Sec. III-A. A. Secret Vector in Kyber The three Kyber variants, namely Kyber-512, Kyber-768, and Kyber-1024, consist of three main processes: Key Generation, Encryption, and Decryption. Let us consider the example of Kyber-768, which requires 3 N T T operations on the secret vector s and 3 N T T operations on the error polynomial e. Similarly, the encryption and decryption processes also require multiple N T T and inverse N T T operations. Our word-wise BM M is the most resource, time, and power critical operation among all these N T T computations. Although BM M is used in different stages of Kyber key generation, encryption, and decryption, this paper discusses the secret vector generation process in greater detail. As per FIPS203 [1], these secret polynomials are generated using speciﬁc PRF and CBD processes, where the secret vector s is sampled in a uniform and random manner. As shown in Algorithm 1, the word-wise BM M used inside the N T T takes s as input a and the twiddle factor ω as input b. This forward N T T transformation is shown in line 10 of Kyber Key

Generation, shown in Algorithm 3. Our SR method monitors the behavior of the N T T operation running with the wordwise BM M by tracking how many times it executes without Reduction 1 and Reduction 2 (nχ0 ), with only Reduction 1 (nχ1 ), with only Reduction 2 (nχ2 ), and with both Reduction 1 and Reduction 2 (nχ3 ). The percentage values of χ0 , χ1 , χ2 , and χ3 remain within the ranges of 77.66–80.41, 0.14– 0.61, 19.18–21.91, and 0.00–0.24, respectively, when no fault occurs throughout the 1024 N T T iterations.

Algorithm 4 CKKS.KeyGen() 1: Input: Ring dimension N , modulus q 2: Output: Secret key sk 3: Output: Public key pk 4: a ← Rq

5: s ← χN 6: e ← χN 7: ŝ := NTT(s) 8: ê := NTT(e) 9: â := NTT(a)

Algorithm 3 Kyber.CPA.PKE.KeyGen() 1: Output: Secret key sk ∈ B12·k·n/8 2: Output: Public key pk ∈ B12·k·n/8+32

3: d ← B32

4: (ρ, σ) := G(d) 5: N := 0 6: for i = 0 to k − 1 do 7: for j = 0 to k − 1 do 8:

Â[i][j] := Parse(XOF (ρ, j, i))

9: for i = 0 to k − 1 do

s[i] := CBDη1 (PRF(σ, N )) N := N + 1 12: for i = 0 to k − 1 do 13: e[i] := CBDη1 (PRF(σ, N )) 14: N := N + 1 15: ŝ := NTT(s) 16: ê := NTT(e) 17: t̂ := Â ◦ ŝ + ê 18: pk := (E12 (t̂ mod q)kρ) 19: sk := E12 (ŝ mod q) return (pk, sk) 10:

11:

B. Secret Vector in CKKS As mentioned in Section V-A, the key generation process of the CKKS algorithm has similar requirements for the wordwise BM M operation inside its N T T computation. The primary difference is that the word-wise BM M used in the CKKS N T T operates with different polynomial degrees n− 1 and moduli q. The secret vector generation s of CKKS is generated from a ternary or Gaussian distribution. As shown in line 7 of Algorithm 4, s is passed through an N T T operation. Similar to the Kyber variants, our wordwise BM M serves as the fundamental building block of this N T T operation, which is also the most power- and resource-critical component. Our SR method monitors the behavior of the N T T operation running with the worwise BM M by tracking Reduction-1 and Reduction-2. The percentages corresponding to the four possible conditions, namely no reduction χ0 , only Reduction1 χ1 , only Reduction-2 χ2 , and both reductions 1 and 2 χ3 , range from 80.06%–83.81%, 0.07%–0.11%, 16.11%–19.85%, and 0.00%–0.01%, respectively.

10: b̂ := −(â ◦ ŝ + ê) mod q 11: pk := (b̂, â) 12: sk := ŝ

return (pk, sk) VI. FAULT I NJECTION IN N T T FOR K YBER & CKKS In this paper, we study two types of fault injection on the N T T intermediate variables c, κ, and r: random bit-ﬂip faults and burst bit-ﬂip faults. In random fault injection, bits are ﬂipped from 0 to 1 at random positions in c, κ, and r, whereas in burst fault injection, consecutive bit positions are ﬂipped in these variables. For an (n − 1)-degree polynomial, the N T T requires n2 log n butterﬂy iterations, and in each iteration, the BM M is invoked. For our test cases, Kyber uses n = 256 and CKKS uses n = 4096, resulting in 1024 and 24576 N T T iterations, respectively. Random and burst faults are injected during each N T T iteration for both Kyber and CKKS. Table I presents the description of all parameters used in this study. Here, λ represents the number of faulty N T T iterations, and φ denotes the number of faulty bits in the faulty N T T loop. As shown in Table III, Table IV and Table V, faults are injected into the three intermediate registers c, κ, and r, respectively, used in the BM M of Kyber’s N T T by varying λ and φ. It is observed that up to 128 faulty N T T iterations, with any number of injected faults, cause the values of χ0 , χ1 , and χ2 to deviate from their corresponding values obtained when no faults occur in any N T T loop. Therefore, if the fault persists for at least 128 N T T iterations in Kyber’s N T T , our model can detect any number of faulty bits with 100% efﬁciency. When the number of faulty N T T iterations is 64 or fewer, some values of χ0 , χ1 , and χ2 may coincide with their corresponding values obtained when no faults occur in any N T T loop. Therefore, beyond 64 faulty iterations during the secret vector computation process in Kyber’s N T T , the fault detection efﬁciency decreases from 100%. The detailed values of χ0 , χ1 , χ2 and χ3 for the secret vector computation process in Kyber N T T are shown in Table III, Table IV and Table V. Similarly, the same study is conducted for the secret vector computation in CKKS’s N T T , as shown in Tables VI, VII, and VIII, by varying the number of faulty loops λ, the number of faulty bits φ, and the fault locations at c, κ, and r, respectively. Results show that up to 512 faulty N T T iterations in CKKS, with any number of injected faults, cause the values of χ0 , χ1 , and χ2 to deviate from their corresponding values obtained

λ ×

χ0 (%) χ1 (%) χ2 (%) χ3 (%) 77.66–80.41 0.14–0.61 19.18–21.91 0.00, 0.24 Random Fault in c 1024 1 56.11–58.72 2.31–3.57 38.24–40.87 0.14, 0.60 512 1 65.49–68.58 1.16–2.22 29.61–32.76 0.05, 0.37 128 1 73.81–76.81 0.41–1.09 22.41–25.55 0.00, 0.26 64 1 75.42–78.50 0.29–0.82 20.93–23.87 0.00, 0.25 1024 2 48.81–51.43 5.10–6.88 41.80–44.39 0.47, 1.17 512 2 61.39–64.89 2.47–3.99 31.62–34.67 0.17, 0.68 128 2 72.79–75.97 0.73–1.55 22.91–26.12 0.02, 0.35 64 2 74.87–78.09 0.47–1.04 21.14–24.28 0.00, 0.27 1024 3 45.66–48.32 7.44–9.60 41.95–44.43 0.81, 1.63 512 3 60.12–63.30 3.73–5.28 31.52–34.71 0.36, 0.97 128 3 72.41–75.42 1.01–1.89 22.91–26.00 0.07, 0.42 64 3 74.91–77.97 0.51–1.28 21.08–24.16 0.02, 0.33 Burst Fault in c 1024 1 55.97–58.66 2.30–3.59 38.19–40.74 0.12, 0.56 512 1 65.56–68.57 0.98–2.18 29.54–32.65 0.04, 0.37 128 1 73.63–76.89 0.42–1.06 22.34–25.69 0.00, 0.27 64 1 75.41–78.49 0.28–0.88 20.91–23.99 0.00, 0.24 1024 2 57.16–59.95 2.55–3.98 36.30–39.13 0.28, 0.85 512 2 66.02–69.05 1.25–2.31 28.80–31.92 0.10, 0.51 128 2 73.85–77.03 0.42–1.12 21.98–25.25 0.01, 0.27 64 2 75.53–78.83 0.29–0.86 20.54–23.85 0.00, 0.26 1024 3 57.86–60.66 2.51–4.04 35.53–38.17 0.36, 1.03 512 3 66.60–69.33 1.30–2.35 28.26–31.22 0.13, 0.60 128 3 74.21–77.48 0.44–1.07 21.61–24.96 0.00, 0.31 64 3 75.81–78.54 0.28–0.87 20.79–23.57 0.00, 0.28 λ : # Faulty Loops, φ : # Faulty bits, l=12, w=4, q=3329, n=256

χ0 (%) χ1 (%) χ2 (%) χ3 (%) 77.66–80.41 0.14–0.61 19.18–21.91 0.00, 0.24 Random Fault in r 1024 1 69.79–72.03 2.46–3.88 24.59–26.79 0.13, 0.54 512 1 72.73–75.20 1.29–2.38 22.75–25.29 0.03, 0.36 128 1 75.63–78.65 0.46–1.11 20.52–23.56 0.00, 0.25 64 1 76.52–79.38 0.30–0.86 20.07–22.75 0.00, 0.24 1024 2 64.52–67.05 4.24–6.21 26.88–29.67 0.31, 0.90 512 2 70.08–72.76 2.22–3.46 24.14–26.73 0.11, 0.53 128 2 74.80–77.99 0.61–1.39 20.88–24.03 0.00, 0.29 64 2 76.11–78.96 0.37–0.97 20.24–23.12 0.00, 0.26 1024 3 59.47–62.23 5.77–8.00 30.09–32.66 0.47, 1.22 512 3 67.33–70.05 2.96–4.41 25.80–28.91 0.20, 0.68 128 3 74.25–77.50 0.81–1.66 21.28–24.41 0.02, 0.34 64 3 75.72–78.95 0.44–1.16 20.18–23.34 0.01, 0.27 Burst Fault in r 1024 1 69.56–72.06 2.53–3.85 24.56–26.95 0.14, 0.56 512 1 72.82–75.50 1.36–2.38 22.55–25.22 0.04, 0.35 128 1 75.79–78.58 0.44–1.12 20.56–23.36 0.00, 0.27 64 1 76.56–79.43 0.28–0.88 19.90–22.80 0.00, 0.26 1024 2 66.61–69.10 2.93–4.44 26.82–29.22 0.20, 0.71 512 2 70.97–73.67 1.53–2.57 23.97–26.76 0.07, 0.44 128 2 75.21–78.14 0.48–1.20 20.76–23.95 0.00, 0.29 64 2 76.17–79.21 0.30–0.94 20.02–23.07 0.00, 0.23 1024 3 64.61–67.36 6.86–8.95 24.49–26.87 0.26, 0.80 512 3 69.98–72.75 3.47–5.15 22.63–25.28 0.10, 0.49 128 3 75.07–77.99 0.98–1.86 20.49–23.35 0.01, 0.30 64 3 75.75–79.34 0.56–1.33 19.67–23.30 0.00, 0.26 λ : # Faulty Loops, φ : # Faulty bits, l=12, w=4, q=3329, n=256

TABLE III: Random and Burst Fault in c for Kyber

TABLE V: Random and Burst Fault in r for Kyber

λ ×

φ 0

χ0 (%) χ1 (%) χ2 (%) χ3 (%) 77.66–80.41 0.14–0.61 19.18–21.91 0.00, 0.24 Random Fault in κ 1024 1 94.64–96.46 3.54–5.36 0.00–0.02 0.00, 0.04 512 1 85.83–88.56 1.81–2.93 9.17–11.59 0.00, 0.15 128 1 79.73–82.51 0.52–1.23 16.45–19.35 0.00, 0.21 64 1 78.67–81.60 0.33–0.91 17.73–20.68 0.00, 0.22 1024 2 98.43–99.20 0.80–1.57 0.00–0.00 0.00, 0.01 512 2 87.48–90.30 0.49–1.15 9.07–11.70 0.00, 0.17 128 2 9.93–82.91 0.15–0.75 16.51–19.57 0.00, 0.23 64 2 78.85–81.64 0.15–0.66 17.84–20.67 0.00, 0.26 1024 3 99.37–99.86 0.14–0.63 0.00–0.00 0.00, 0.00 512 3 88.21–90.52 0.17–0.61 9.09–11.44 0.00, 0.16 128 3 80.11–83.37 0.15–0.59 16.16–19.37 0.00, 0.24 64 3 78.78–81.96 0.17–0.62 17.63–20.82 0.00, 0.25 Burst Fault in κ 1024 1 94.76–96.48 3.50–5.24 0.00–0.02 0.00, 0.05 512 1 86.04–88.74 1.79–2.99 9.03–11.66 0.00, 0.17 128 1 79.43–82.55 0.48–1.23 16.50–19.70 0.00, 0.23 64 1 78.74–81.60 0.31–0.93 17.85–20.54 0.00, 0.27 1024 2 95.50–97.09 2.91–4.50 0.00–0.01 0.00, 0.03 512 2 86.48–88.89 1.46–2.64 8.97–11.48 0.00, 0.16 128 2 79.62–82.70 0.43–1.12 16.33–19.57 0.00, 0.22 64 2 78.63–81.62 0.30–0.87 17.84–20.71 0.00, 0.23 1024 3 96.20–97.50 2.50–3.80 0.00–0.01 0.00, 0.02 512 3 86.70–89.28 1.26–2.24 9.00–11.50 0.00, 0.17 128 3 79.73–82.77 0.41–1.07 16.46–19.48 0.00, 0.23 64 3 78.53–81.61 0.26–0.85 17.78–20.86 0.00, 0.24 λ : # Faulty Loops, φ : # Faulty bits, l=12, w=4, q=3329, n=256

TABLE IV: Random and Burst Fault in κ for Kyber

when no faults occur in any N T T loop. Therefore, if the fault persists for at least 512 N T T iterations in CKKS N T T , our model can detect any number of faulty bits with 100% efﬁciency. When the number of faulty N T T iterations is 512 or fewer, some values of χ0 , χ1 , and χ2 may coincide with their corresponding values obtained when no faults occur in

λ ×

φ 0

any N T T loop. Therefore, beyond 512 faulty iterations during the secret vector computation process in CKKS N T T , the fault detection efﬁciency decreases from 100%. The detailed values of χ0 , χ1 , χ2 and χ3 for the secret vector computation process in CKKS N T T are shown in Table VI, Table VII and Table VIII. λ ×

φ 0

χ0 (%) χ1 (%) χ2 (%) χ3 (%) 80.06–83.81 0.07–0.11 16.11–19.85 0.00, 0.01 Random Fault in c 24576 1 59.07–59.45 0.64–0.74 39.79–40.18 0.04, 0.07 1024 1 74.61–76.59 0.12–0.16 23.28–25.25 0.00, 0.01 512 1 76.42–78.66 0.09–0.14 21.22–23.46 0.00, 0.01 128 1 78.60–81.63 0.08–0.12 18.29–21.29 0.00, 0.01 24576 2 54.04–54.45 1.36–1.53 44.00–44.42 0.11, 0.15 1024 2 74.39–76.34 0.14–0.19 23.49–25.41 0.00, 0.01 512 2 76.20–78.72 0.11–0.16 21.14–23.65 0.00, 0.01 128 2 78.56–81.72 0.09–0.13 18.18–21.32 0.00, 0.01 24576 3 51.60–51.97 2.20–2.40 45.51–45.89 0.19, 0.24 1024 3 74.24–76.11 0.18–0.24 23.67–25.54 0.01, 0.02 512 3 76.17–78.73 0.13–0.18 21.11–23.66 0.00, 0.01 128 3 78.31–81.60 0.09–0.13 18.30–21.57 0.00, 0.01 Burst Fault in c 24576 1 59.08–59.46 0.64–0.74 39.79–40.18 0.04, 0.07 1024 1 74.73–76.50 0.11–0.16 23.38–25.12 0.00, 0.01 512 1 76.45–78.75 0.10–0.14 21.13–23.41 0.00, 0.01 128 1 78.75–81.80 0.08–0.12 18.11–21.14 0.00, 0.01 24576 2 54.05–54.40 1.37–1.51 44.00–44.39 0.11, 0.15 1024 2 74.32–76.23 0.14–0.19 23.59–25.49 0.00, 0.01 512 2 76.36–78.80 0.11–0.16 21.06–23.49 0.00, 0.01 128 2 78.66–81.82 0.08–0.13 18.08–21.23 0.00, 0.01 24576 3 51.60–51.97 2.22–2.39 45.52–45.87 0.19, 0.24 1024 3 74.20–76.06 0.18–0.24 23.73–25.57 0.01, 0.02 512 3 76.28–78.84 0.13–0.18 21.01–23.57 0.00, 0.01 128 3 78.65–81.69 0.09–0.13 18.20–21.23 0.00, 0.01 λ : # Faulty Loops, φ : # Faulty bits, l=32, w=8, q=1811939329, n=4096

TABLE VI: Random and Burst Fault in c for CKKS

λ ×

φ 0

24576 1024 512 128 24576 1024 512 128 24576 1024 512 128

1 1 1 1 2 2 2 2 3 3 3 3

24576 1024 512 128 24576 1024 512 128 24576 1024 512 128

1 1 1 1 2 2 2 2 3 3 3 3

χ0 (%) χ1 (%) χ2 (%) 80.06–83.81 0.07–0.11 16.11–19.85 Random Fault in κ 59.08–59.44 0.63–0.75 39.80–40.19 74.66–76.58 0.12–0.16 23.28–25.20 76.49–78.83 0.10–0.14 21.06–23.39 78.79–81.80 0.08–0.12 18.11–21.10 54.02–54.42 1.37–1.53 44.01–44.42 74.47–76.20 0.14–0.20 23.62–25.36 76.33–78.63 0.11–0.16 21.23–23.52 78.59–81.77 0.09–0.13 18.13–21.30 51.59–51.97 2.22–2.41 45.49–45.89 74.23–76.26 0.18–0.24 23.52–25.55 76.10–78.70 0.13–0.18 21.14–23.73 78.76–81.73 0.09–0.13 18.17–21.12 Burst Fault in κ 59.09–59.45 0.64–0.74 39.80–40.17 74.68–76.76 0.11–0.16 23.10–25.17 76.45–78.85 0.10–0.14 21.03–23.41 78.63–81.79 0.08–0.12 18.12–21.26 54.03–54.43 1.35–1.52 43.98–44.41 74.47–76.18 0.15–0.19 23.66–25.35 76.35–78.75 0.11–0.16 21.11–23.50 78.67–81.73 0.09–0.13 18.15–21.21 51.60–51.96 2.21–2.39 45.52–45.90 74.24–76.20 0.18–0.23 23.59–25.53 76.33–78.59 0.13–0.18 21.25–23.52 78.63–82.03 0.09–0.13 17.88–21.24

χ3 (%) 0.00, 0.01 0.04, 0.07 0.00, 0.01 0.00, 0.01 0.00, 0.01 0.11, 0.15 0.00, 0.01 0.00, 0.01 0.00, 0.01 0.19, 0.24 0.01, 0.02 0.00, 0.01 0.00, 0.01 0.04, 0.08 0.00, 0.01 0.00, 0.01 0.00, 0.01 0.11, 0.15 0.00, 0.01 0.00, 0.01 0.00, 0.01 0.19, 0.24 0.00, 0.02 0.00, 0.01 0.00, 0.01

TABLE VII: Random and Burst Fault in κ for CKKS λ ×

φ 0

χ0 (%) χ1 (%) χ2 (%) χ3 (%) 80.06–83.81 0.07–0.11 16.11–19.85 0.00, 0.01 Random Fault in r 24576 1 59.08–59.45 0.63–0.74 39.80–40.18 0.04, 0.07 1024 1 74.72–76.46 0.12–0.16 23.41–25.14 0.00, 0.01 512 1 76.44–78.82 0.10–0.14 21.07–23.44 0.00, 0.01 128 1 78.69–81.81 0.08–0.12 18.11–21.21 0.00, 0.01 24576 2 54.03–54.42 1.37–1.50 44.01–44.41 0.11, 0.16 1024 2 74.47–76.32 0.14–0.19 23.51–25.36 0.00, 0.01 512 2 76.33–78.61 0.11–0.16 21.27–23.53 0.00, 0.01 128 2 78.66–81.82 0.09–0.13 18.08–21.21 0.00, 0.01 24576 3 51.59–51.98 2.22–2.39 45.49–45.89 0.19, 0.24 1024 3 74.23–76.04 0.18–0.23 23.74–25.55 0.01, 0.02 512 3 76.28–78.59 0.13–0.18 21.26–23.55 0.00, 0.01 128 3 78.69–81.74 0.09–0.13 18.16–21.19 0.00, 0.01 Burst Fault in r 24576 1 59.09–59.47 0.64–0.74 39.79–40.16 0.04, 0.08 1024 1 74.56–76.49 0.12–0.16 23.37–25.30 0.00, 0.01 512 1 76.35–78.75 0.10–0.14 21.12–23.52 0.00, 0.01 128 1 78.78–82.03 0.08–0.12 17.87–21.10 0.00, 0.01 24576 2 54.03–54.42 1.37–1.51 44.00–44.39 0.11, 0.15 1024 2 74.47–76.28 0.14–0.20 23.56–25.35 0.00, 0.01 512 2 76.31–78.72 0.11–0.16 21.15–23.55 0.00, 0.01 128 2 78.53–81.93 0.08–0.13 17.97–21.35 0.00, 0.01 24576 3 51.60–51.98 2.21–2.39 45.54–45.87 0.19, 0.24 1024 3 74.22–76.21 0.18–0.24 23.58–25.55 0.01, 0.02 512 3 76.23–78.66 0.13–0.18 21.18–23.59 0.00, 0.01 128 3 78.61–81.66 0.09–0.13 18.24–21.28 0.00, 0.01 λ : # Faulty Loops, φ : # Faulty bits, l=32, w=8, q=1811939329, n=4096

TABLE VIII: Random and Burst Fault in r for CKKS VII. R ESULT & D ISCUSSION The proposed protected word-wise BM M is implemented in VHDL on an Artix-7 FPGA using Vivado 23.2. The proposed wordwise BM M is implemented with kyber and CKKS parameter set. The results of the proposed methods are compared in terms of overhead and error-detection efﬁciency

in the following two sections, namely Sec. VII-A and Sec. VII-B, respectively. A. Overhead The overhead of the proposed fault-detection scheme for the BM M is evaluated using three approaches: (i) overhead analysis across different BM M word sizes for the Kyber and CKKS parameter sets, and (ii) overhead comparison of the proposed BM M against existing fault-detection solutions reported in the literature and (iii) comparison of the overhead of the proposed protected BM M placed inside the N T T with existing protected N T T schemes 1) Impact of Wordsize and parameter set on Hardware Overhead: As shown in Table IX, the Kyber BM M with word sizes 4 and 6 incurs resource overheads of 18.9% and 20.5%, respectively. However, the full Kyber BM M implementation without word-wise partitioning incurs only an 8.3% resource overhead. Similarly, for CKKS, the proposed wordwise BM M with word sizes 8 and 16 incurs resource overheads of 10.9% and 7.9%, respectively. However, the full CKKS BM M implementation without word-wise partitioning incurs only a 6.13% resource overhead. The energy overhead of the proposed method is approximately 1% for all Kyber and CKKS variants. 2) Comparison with Existing Fault-Detection Schemes for BMM: To the best of our knowledge, only two existing works, [15] and [14], have proposed fault-detection mechanisms for BMM based on recomputation. Compared with these approaches, the proposed SRM-based fault-detection scheme achieves signiﬁcantly lower hardware and energy overhead while maintaining effective fault-detection capability. Recomputation based approaches RESWO, RESO, and RENO proposed by Baidya et al. [15] incur approximately 85%–88% slice overhead, the proposed SRM requires only 18.9% additional slices for the equivalent Kyber conﬁguration (l=12,w=4,q=3329). Similarly Barrett Modular Redundancy (BMR) scheme of Aghapour et al. has 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 the energy overhead to below 3%. This low overhead of our proposed scheme is achieved through its statistical monitoring methodology, unlike existing approaches that rely on arithmetic recomputation or redundant hardware units. The statistical observation on the intrinsic reductionpath execution of the word-wise BM M by our proposes SRM scheme achieves minimal additional logic, leading to substantially lower area and energy consumption while preserving the original performance characteristics of the BM M architecture. 3) Overhead of BMM Embedded in N T T : The proposed protected BM M with SRM is embedded in the Kyber and CKKS N T T s, resulting in approximately 5.2% and 1.2% area overhead, 1.2% and 1.3% delay overhead, and <1% and <1% power overhead, respectively. We identiﬁed six additional studies [11, 16, 20, 17, 18, 15] in which the authors proposed N T T protection schemes targeting different subcomponents

Application

Conﬁg (l, w, q)

SEC

Slice

LUT/FF/DSP

Power (mW)

BMM BMM+SRM

Kyber, 12, 4, 3329 Kyber, 12, 4, 3329

38 83

100 / 47 / 2 163 / 156 / 2

106 107

BMM BMM+SRM

Kyber, 12, 6, 3329 Kyber, 12, 6, 3329

43 93

113 / 47 / 2 176 / 146 / 2

108 109

BMM BMM+SRM

Kyber, 12, 12, 3329 Kyber, 12, 12, 3329

13 56

31 / 26 / 5 94 / 112 / 5

106 107

BMM

CKKS, 32, 8, 1811939329 CKKS, 32, 8, 1811939329 CKKS, 32, 16, 1811939329 CKKS, 32, 16, 1811939329 CKKS, 32, 32, 1811939329 CKKS, 32, 32, 1811939329 FHE, 1024, 32, -

238 283 (18.9%↑) 243 293 (20.5%↑) 513 556 (8.3%↑) 374

234 / 84 / 3

130

415 (10.9%↑) 476

115

295 / 183 / 3

131

184 / 44 / 4

514 (7.9%↑) 652

114

692 (6.13%↑) 5146 (17.1%↑) 456 (85.3%↑) 463 (88.2%↑) 462 (87.8%↑) 6556 (19.4%↑)

BMM+SRM BMM BMM+SRM BMM BMM+SRM Aghapour et al. [14] REMO+BMM Baidya et al.[15] RESWO+BMM Baidya et al.[15] RESO+BMM Baidya et al.[15] RENO+BMM Aghapour et al. [14] BMR

PQC, 12, 4, 3329 PQC, 12, 4, 3329 PQC, 12, 4, 3329 FHE, 2048, 32, -

Energy (nJ) 10.6 10.7 (0.9%↑) 5.4 5.45 (0.27%↑) 2.54 2.56 (0.7%↑) 22.1

CC 10 10

CP (ns) 9.46 9.33

CLK (MHz) 100 100

5 5

9.32 9.42

100 100

2 2

11.67 11.53

83 83

8.78

100

8.87

100

131

22.27 (0.7%↑) 6.55

8.71

100

245 / 143 / 4

131.5

6.75 (3%↑)

9.04

100

163 / 66 / 6

131

2.62

8.36

100

222 / 165 / 6

132

9.12

100

13720 / 10522 / 4

7365

23.2

162/ 70 / 4

2.64 (0.7%↑) 17.91 (21.87%↑) 10.8

9.63

100

147/ 75 / 4

10.9

9.64

100

174/ 72 / 4

10.8

9.8

100

18801 / 11646 / 4

3.04 (31.73%↑)

2264

17.9

TABLE IX: Hardware Overhead Comparison of BMM and BMM+SRM Work

Sarker et al.[11] Sarker et al. [11] Ahmadi et al. [16] Ravi et al. [8] Bauer et al. [17] Jati et al. [18] Baidya et al. [15] Baidya et al. [15] Baidya et al. [15] Our Our

Type of Fault Detection & Target HW RENO v1/ v2/ v3 for Falcon and NTRU NT T RENO v1/v2/v3 for Falcon and NTRU NT T Correlated Check sum for Kyber N T T Checking Entropy Polynomial Evaluation and Interpolation for Dilithium N T T Randomized Memory Address for Kyber NT T RESWO for Kyber N T T (wordwise) RESO for Kyber N T T (wordwise) RENO for Kyber N T T (wordwise) SRM for Kyber N T T (wordwise) SRM for CKKS N T T (wordwise)

Platform

Overhead(%)

Frq.

(%) Error

(MHz.)

Coverage

99.51/99.67 /99.41

Area

Delay

Energy

20.2%↑*/ 15.3%↑*/ 21.5%↑* 24.24%↑*/ 14%↑*/ 17.8%↑*

8.46%↑/ 15.88%↑)/ 13.71%↑ 9.32%↑/ 19.66%↑/ 21.78%↑

15.6%↑/ 7.6%↑/ 11.2%↑ 20.47%↑/ 13.27%↑/ 17.26%↑

Artix-7 FPGA

25.1%↑

41.3% ↑

51.5%↑

140

∼ 53 – ∼ 99.99

ARM Cortex M4

Artix 7 FPGA

24.29*

3.8

1.45

100

99.97

Artix 7 FPGA

34.34

5.8

2.97

100

99.97

Artix 7 FPGA

24.71*

0.75

2.14

100

99.97

Artix 7 FPGA

5.2*

1.2

100

33 – 100

Artix 7 FPGA

1.2*

1.3

100

36 – 100

Spartan7 FPGA

Zynq FPGA

∗ If slice usage is not available we calculate SEC=0.25 × LUTs + 0.125 × FFs + 100 × DSPs + 200 × BRAMs [19].

TABLE X: Overhead Comparison with N T T literature

NR = Not Reported

of the N T T . Sarker et al. protected modular multiplication, modular addition, and modular subtraction of N T T using a recomputation-based fault-detection technique, RENO on Spartan 7 and Zynq FPGA. Ahmadi et al. [16] implemented a correlated checksum-based fault-detection scheme for N T T polynomials on an Artix-7 FPGA. Similar increments and decrements in checksum-based fault detection may not be able to detect fault occurrences. Baidya et al. [15] implemented three recomputation-based fault-detection techniques, namely RESO, RENO, and RESWO, for the protection of the BM M modular multiplication unit employed within the N T T . Jati et al. [18] implemented a randomized memory addressing scheme for the Kyber N T T . This randomization is feasible because the order in which twiddle factors are read from memory within a stage does not affect the correctness of the N T T computation. The resulting randomized memory access pattern mitigates soft analytical side-channel attacks (SASCA). Bauer et al. [17] employed a polynomial evaluation and interpolation technique for fault detection at the N T T output, resulting in a substantial timing overhead of 72% on the ARM Cortex-M4 platform. Ravi et al. [8] demonstrated a zeroizing attack on the N T T running on the ARM CortexM4 platform, which can reduce the entropy of the secret polynomial used in lattice-based PQC. A detailed discussion is available in Sec. I-A. As a countermeasure, the authors proposed measuring the entropy of the N T T output. As shown in Table X, the proposed SRM method incurs the lowest area, delay, and energy overhead among all existing protected N T T schemes.

total 1,024 iterations in Kyber N T T and 24,576 iterations in CKKS N T T . If a fault persists for at least 128 out of the 1,024 Kyber N T T iterations, the proposed fault model still achieves a 100% fault detection rate. Similarly, for CKKS N T T , if the fault persists for at least 512 out of the 24,576 N T T iterations, the proposed model is still able to detect the fault with 100% accuracy. When the number of N T T iterations affected by a transient fault falls below 64 for Kyber and below 128 for CKKS, the fault detection rate of the proposed scheme begins to decrease. 2) Error Emulation: In the fault emulation process, a fault injector hardware is built which directly connected with the three registers c, κ and r where we consider fault locations. This fault injector may be introduced in the design in the form of hardware Trojan. Under faulty conditions, the fault injector can modify any targeted bit of c, κ, or r in either randomfault or burst-fault mode. The simulation results are reported in Tables III, Tables IV, Tables V, Tables VI, Tables VII and Tables VIII as simulation enables the efﬁcient evaluation of a signiﬁcantly larger number of fault samples than hardware emulation. Fault Type

Random

B. Error Detection Efﬁciency The error detection efﬁciency is evaluated using two approaches: simulation-based fault injection and emulated fault injection. 1) Error Simulation: The error injection procedure was simulated using Python on Ubuntu 24.04 running on an Intel i5 processor, where each N T T operation was executed 100,000 times for random and burst faults. For Kyber, a complete N T T computation requires 1,024 N T T iterations, resulting in 1,024 BM M calls. Similarly, for CKKS, a complete N T T computation requires 24,576 N T T iterations, resulting in 24,576 BM M calls. Since each N T T iteration performs exactly one BM M operation, the total number of BM M calls is equal to the total number of N T T iterations. For both Kyber and CKKS KeyGen operations, we varied the number of faulty N T T iterations (λ) and the number of faulty bits (φ), and investigated whether the metrics χ0 , χ1 , and χ2 deviated from their corresponding values under fault-free conditions. As reported in Table XI and Table XII, for Kyber and CKKS key generation, respectively, the proposed scheme achieves a 100% fault detection rate for both random and burst fault injections under permanent fault conditions, irrespective of the number of faulty bits (φ). Here, a permanent fault refers to a fault that persists in any of the intermediate registers c, κ, or r throughout all N T T iterations. For transient faults, the number of affected N T T iterations is reduced from the

Burst

128–1024 64 32 32 128–1024 64 128–1024 64 64 128–1024 64 32 32 128–1024 64 64 128–1024 64 64

1–11 1-11 1 2–11 1–11 1–11 1–11 1 2–11 1–11 1–11 1 2–11 1–11 1 2–11 1–11 1 2–11

Fault Location c c c c κ κ r r r c c c c κ κ κ r r r

Efﬁciency (%) 100 ∼96.12–100 ∼30.62 ∼60.77–100 100 ∼ 36 100 ∼46.12 ∼90.39–100 100 ∼96.49–100 ∼29.40 ∼29.87–79.21 100 ∼33.18 ∼33–66 100 ∼46.68 ∼67.67–100

TABLE XI: BMM Fault Coverage for Kyber (l=12, w=4, q=3329) Fault Type

Random

Burst

512–24576 128 128–1024 64 128–1024 64 64 512–24576 128 512–24576 128 512–24576 128

1–11 1-11 1–11 1–11 1–11 1 2–11 1–11 1–11 1–11 1-11 1–11 1–11

Fault Location c c κ κ r r r c c κ κ r r

Efﬁciency (%) 100 ∼50.89– 100 ∼ 36 100 ∼46.12 ∼90.39–100 100 ∼50.78–100 100 ∼50.89–100 100 ∼52.23–100

TABLE XII: BMM Fault Coverage for CKKS (l=32, w=8, q=1811939329)

VIII. C ONCLUSION BM M is the most critical hardware component of N T T used in lattice based cryptogarphy. Since the BM M consumes a signiﬁcant portion of the hardware resources and energy budget of lattice-based PQC and FHE accelerators, it becomes an attractive target for attackers. This paper proposes and implements a novel statistical fault detection method based on the reduction path execution patterns of a word-wise BMM. To the best of our knowledge, the proposed scheme achieves comparable fault-detection capability with lower hardwareresource, delay and energy overhead than existing BMM speciﬁc fault-detection techniques reported in the literature. The proposed schemes can detect 100% of permanent faults and are also effective in detecting transient faults. Furthermore, when the proposed SRM and BM M are incorporated into the N T T architecture, the resulting design exhibits the lowest area, energy, and timing overhead among all existing architectures considered in this work, to the best of our knowledge. To promote open research and reproducibility, implementation and associated test cases of wordwise BM M are uploaded on a public GitHub repository 1 , enabling independent veriﬁcation and thorough validation of the proposed methodology. R EFERENCES [1] National Institute of Standards and Technology. ModuleLattice-Based Key-Encapsulation Mechanism Standard. Federal Information Processing Standards Publication 203, aug 2024. [2] National Institute of Standards and Technology (NIST). Module lattice-based digital signature standard. Federal Information Processing Standards Publication 204, August 2024. [3] Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Paper 2012/144, 2012. [4] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory, 6(3), July 2014. [5] Paul Barrett. Implementing the rivest shamir and adleman public key encryption algorithm on a standard digital signal processor. In Andrew M. Odlyzko, editor, Advances in Cryptology — CRYPTO’ 86, pages 311–323, Berlin, Heidelberg, 1987. Springer Berlin Heidelberg. [6] Thomas Espitau, Pierre-Alain Fouque, Benoît Gérard, and Mehdi Tibouchi. Loop-abort faults on lattice-based signature schemes and key exchange protocols. IEEE Transactions on Computers, 67(11):1535–1549, 2018. [7] Matthias J. Kannwischer, Joost Rijneveld, Peter Schwabe, and Ko Stoffelen. pqm4: Testing and benchmarking nist pqc on arm cortex-m4. Cryptology ePrint Archive, Report 2019/844, 2019. Available at https://eprint.iacr.org/2019/844. 1 https://github.com/rourabpaul1986/wordwise_pipelined_barrett

[8] Prasanna Ravi, Bolin Yang, Shivam Bhasin, Fan Zhang, and Anupam Chattopadhyay. Fiddling the twiddle constants - fault injection analysis of the number theoretic transform. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022. [9] {Jung Hee} Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology – ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Proceedings, Lecture Notes in Computer Science (including subseries Lecture Notes in Artiﬁcial Intelligence and Lecture Notes in Bioinformatics), pages 409–437. Springer Verlag, 2017. Publisher Copyright: © International Association for Cryptologic Research 2017.; 23rd Annual International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2017 ; Conference date: 03-12-2017 Through 07-12-2017. [10] Alvaro Cintas Canto, Mehran Mozaffari-Kermani, and Reza Azarderakhsh. Reliable crc-based error detection constructions for ﬁnite ﬁeld multipliers with applications in cryptography. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 29(1):232–236, 2021. [11] Ausmita et al., Sarker and Canto. Error detection architectures for hardware/software co-design approaches of number-theoretic transform. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 42(7):2418–2422, 2023. [12] Alvaro Cintas Canto, Ausmita Sarker, Jasmin Kaur, Mehran Mozaffari Kermani, and Reza Azarderakhsh. Error detection schemes assessed on fpga for multipliers in lattice-based key encapsulation mechanisms in postquantum cryptography. IEEE Transactions on Emerging Topics in Computing, 11(3):791–797, 2023. [13] Saeed Aghapour, Kasra Ahmadi, Mehran Mozaffari Kermani, and Reza Azarderakhsh. Efﬁcient fault detection architectures for modular exponentiation targeting cryptographic applications benchmarked on fpgas, 2024. [14] Saeed Aghapour, Kiarash Sedghighadikolaei, Attila A. Yavuz, Bechir Hamdaoui, and Mehran MozaffariKermani. Efﬁcient fault-detection architectures for barrett reduction and multiplication in classical and postquantum cryptographic systems. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, pages 1–13, 2025. [15] Paresh Baidya, Rourab Paul, Vikas Srivastava, and Sumit Kumar Debnath. Error detection schemes for barrett modular multiplication of ct-bu on fpga in pqc and fhe. IEEE Transactions on Emerging Topics in Computing, 14(2):734–745, 2026. [16] Kasra Ahmadi, Saeed Aghapour, Mehran Mozaffari Kermani, and Reza Azarderakhsh. Efﬁcient algorithm-level error detection for number-theoretic transform used for kyber assessed on fpgas and arm. ACM Trans. Embed.

Comput. Syst., 24(5), September 2025. [17] Sven Bauer, Fabrizio De Santis, Kristjane Koleci, and Anita Aghaie. A fault-resistant NTT by polynomial evaluation and interpolation. Cryptology ePrint Archive, Paper 2024/788, 2024. [18] A. Jati, N. Gupta, A. Chattopadhyay, and S. Sanadhya. “a conﬁgurable crystals-kyber hardware implementation with side-channel protection”. ACM Trans. Embed. Comput. Syst., 23(2), March 2024. [19] Weiqiang Liu, Sailong Fan, Ayesha Khalid, Ciara Rafferty, and Máire O’Neill. Optimized schoolbook polynomial multiplication for compact lattice-based cryptography on fpga. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 27(10):2459–2463, 2019. [20] Prasanna Ravi, Anupam Chattopadhyay, Jan Pieter D’Anvers, and Anubhab Baksi. Side-channel and fault-injection attacks over lattice-based post-quantum schemes (kyber, dilithium): Survey and new results. ACM Trans. Embed. Comput. Syst., 23(2), March 2024.

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

Analyze & explore related research in Conceptio

Related documents