## 3 Multiplication Methods over \(GF(2^{m})\) on 8-bit AVR MCUs
### Block-Comb Based Multiplication Methods  
As an alternative to binary field multiplication using LUT, the Block-Comb (\(BC\)) multiplication method was originally proposed for efficient field multiplication of \(\eta_{T}\) pairing over \(GF(2^{239})\) on an ATmega128 MCU [6]. In the \(BC\) multiplication method, both the multiplier and the multiplicand of multiplication are partitioned into \(s\)-byte blocks. Then, partial products of generated blocks are calculated by a column-wise fashion. Each of the partial products is calculated with the \(LtR\) Comb method for performance efficiency. Namely, in the \(BC\) multiplication method, the set of accessible registers are partitioned into three parts; \(s\) registers, \(s\) registers, and \(2s+1\). These partitioned three parts of registers are used for a multiplicand, a multiplier, and the result of the partial multiplication, respectively. Because the intermediate results are kept in the set of working registers of \(2s+1\), the results of partial multiplications positioned in the identical column can be updated directly intothe registers without accessing memory, which decreases the count of redundant memory accesses. In [6], [PERSON] et al. drew a conclusion that six is the optimum block size \(s\) based on the fact that \((4s+1)<26\) on 8-bit AVR MCUs. [PERSON] et al.'s \(BC\) multiplication method calculates a multiplication over \(GF(2^{239})\) in 9511 clock cycles (\(cc\)).  
[PERSON] et al. [7] proposed the Unbalanced Block-Comb multiplication method (\(UBC\)), which can expand the block size from 6 to 7 for a multiplication over \(GF(2^{163})\). They exploited the fact that the tested bits of a multiplier become unnecessary during a partial product computation process. In other words, they recycled the register used to keep the multiplier in order to hold the multiplicand's the most significant byte. Consequently, the expanded block size decreases the count of partial multiplication from sixteen to nine when calculating a field multiplication over \(GF(2^{163})\). Note that block size 7 (resp. block size 6) partitions a 163-bit field element into 3 blocks (resp. 4 blocks). [PERSON] et al.'s \(UBC\) could calculate a 163-bit binary multiplication within 4546 \(cc\). Then, [PERSON] et al. [8] presented the so-called Karatsuba Block-Comb multiplication method (\(KBC\)), an integration of the Karatsuba technique and the Block-Comb multiplication approach, which decreases the count of partial multiplications from nine to six at the cost of several low cost field additions when calculating a multiplication over \(GF(2^{163})\). \(KBC\) could accomplish 3274 \(cc\) for a multiplication over \(GF(2^{163})\). They also proposed a constant version of their Karatsuba Block Comb multiplication technique. Although it accomplished resistance against a timing attack, it can still be attacked by a simple power analysis. In 2018, [PERSON] et al. [9] proposed an enhanced version of the Karatsuba Block-Comb (\(EKBC\)) multiplication technique by applying a new multiplier encoding method, which can greatly decrease the count of registers necessary for keeping the multiplier. In addition, they showed that with their proposed technique, the maximum block size of the Block-Comb multiplication method could be 8 on 8-bit AVR MCUs. As a result, they accomplished a new timing record for NIST-compliant K-233 elliptic curve scalar multiplication. Until now, \(EKBC\) is regarded as the fastest multiplication method over a binary field on 8-bit AVR MCUs.