Concurrent error detection in semi-systolic dual basis multiplier over GF(2^m) using self-checking alternating logic

Author(s): C.W. Chiou ; W.-Y. Liang ; H.W. Chang ; J.-M. Lin ; C.-Y. Lee
DOI: 10.1049/iet-cds.2009.0243

For access to this article, please select a purchase option:

Buy article PDF

Buy Knowledge Pack

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership

Recommend Title Publication to library

IET Circuits, Devices & Systems — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Author(s): C.W. Chiou ¹ ; W.-Y. Liang ² ; H.W. Chang ² ; J.-M. Lin ³ ; C.-Y. Lee ⁴
- Affiliations: 1: Department of Computer Science and Information Engineering, Ching Yun University, Chung-Li, Taiwan
  2: Department of Computer Science and Information Engineering, National Taipei University of Technology, Taipei, Taiwan
  3: Department of Information Engineering and Computer Science, Feng Chia University, Taichung City, Taiwan
  4: Department of Computer Information and Network Engineering, Lunghwa University of Science and Technology, Taoyuan County, Taiwan
Source: Volume 4, Issue 5, September 2010, p. 382 – 391
DOI: 10.1049/iet-cds.2009.0243 , Print ISSN 1751-858X, Online ISSN 1751-8598

Multiplication is one of the most important finite field arithmetic operations in cryptographic computations. Recently, the attacks of fault-based cryptanalysis have been a critical threat to both symmetrical and asymmetrical cryptosystems. To prevent such kind of attacks, masking faulty signals and outputting only correct ciphers would be a feasible solution, especially suitable for finite field multiplication. Therefore a novel dual basis multiplier in GF(2^m) with concurrent error detection capability using self-checking alternating logic is presented. The new self-checking alternating logic dual basis multiplier saves about 67% space complexity as compared with other existing dual basis multiplier with concurrent error detection capability that uses the parity checking method. The proposed dual basis multiplier takes almost as low as one extra clock cycle to achieve concurrent error detection capability. Furthermore, any existing faults in fault model are ensured to be detectable through at least one input in the authors’ proposed scheme.

References

1. 1)
  - T. Itoh , S. Tsujii . Structure of parallel multipliers for a class of fields GF(2m). Inf. Comput. , 21 - 40
2. 2)
  - C.Y. Lee , C.W. Chiou , J.M. Lin . Concurrent error detection in a polynomial basis multiplier over GF(2m). J. Electron. Test Theory Appl. , 2 , 143 - 150
3. 3)
  - I.S. Reed , T.K. Truong . The use of finite fields to compute convolutions. IEEE Trans. Inf. Theory , 2 , 208 - 213
4. 4)
  - A. Reyhani-Masoleh , M.A. Hasan . Fault detection architectures for field multiplication using polynomial bases. IEEE Trans. Comput. , 9 , 1089 - 1103
5. 5)
  - Anderson, R.J., Kuhn, M.: `Low cost attack on tamper resistant devices', Proc. Fifth Int. Workshop on Security Protocols, 1997, p. 125–136, (LNCS, 1361).
6. 6)
  - Ç.K. Koç , B. Sunar . Low-complexity bit-parallel canonical and normal basis multipliers for a class of finite fields. IEEE Trans. Comput. , 3 , 353 - 356
7. 7)
  - Mastrovito, E.D.: `VLSI architectures for multiplication over finite field GF(2', in ‘Applied algebra, algebraic algorithms, and error-correcting codes’. Proc. Sixth Int. Conf., AAECC-6, July 1988, Rome, p. 297–309.
8. 8)
  - D.A. Reynolds , G. Metze . Fault detection capabilities of alternating logic. IEEE Trans. Comput. , 12 , 1093 - 1098
9. 9)
  - T.-H. Chen , Y.-P. Lee , L.-G. Chen . Concurrent error detection in array multipliers by BIDO. IEE Proc. Comput. Digital Technol. , 6 , 425 - 430
10. 10)
  - J.H. Patel , L.Y. Fung . Concurrent error detection in ALU's by recomputing with shifted operands. IEEE Trans. Comput. , 72 , 589 - 595
11. 11)
  - D. Boneh , R.A. Demillo , R.J. Lipton . On the importance of eliminating errors in cryptographic computations. J. Cryptol. , 101 - 119
12. 12)
  - C.W. Chiou , C.Y. Lee , A.W. Deng , J.M. Lin . Concurrent error detection in montgomery multiplication over GF(2m). IEICE Trans. Fundam. Electron. Commun. Comput. Sci. , 2 , 566 - 574
13. 13)
  - J.H. Patel , L.Y. Fung . Concurrent error detection in multiply and divide arrays. IEEE Trans. Comput. , 4 , 417 - 422
14. 14)
  - M. Diab , A. Poli . New bit-serial systolic multiplier for GF(2m) using irreducible trinomials. Electron. Lett. , 13 , 1183 - 1184
15. 15)
  - Bark, A., Kinne, C.: `The application of pulse position modulation to digital computers', Proc. National Electronics Conf., September 1953, p. 656–664.
16. 16)
  - C.Y. Lee , C.W. Chiou . Efficient design of low-complexity bit-parallel systolic hankel multipliers to implement multiplication in normal and dual bases of GF(2m). IEICE Trans. Fundam. Electron. Commun. Comput. Sci. , 11 , 3169 - 3179
17. 17)
  - C.C. Wang , T.K. Truong , H.M. Shao , L.J. Deutsch , J.K. Omura , I.S. Reed . VLSI architectures for computing multiplications and inverses in GF(2m). IEEE Trans. Comput. , 8 , 709 - 717
18. 18)
  - H. Fan , Y. Dai . Key function of normal basis multipliers in GF(2n). Electron. Lett. , 23 , 1431 - 1432
19. 19)
  - Minero, R.H., Anello, A.J., Furey, R.G., Palounek, L.R.: `Checking by pseuduplication', U.S., 3660646, May 1972.
20. 20)
  - F.J. MacWilliams , N.J.A. Sloane . (1977) The theory of error-correcting codes.
21. 21)
  - C.Y. Lee , C.W. Chiou , J.M. Lin . Concurrent error detection in a bit-parallel systolic multiplier for dual basis of GF(2m). J. Electron. Test Theory Appl. , 5 , 539 - 549
22. 22)
  - C.-L. Wey . Concurrent error detection in array dividers by alternating input data. IEE Proc.-E , 2 , 123 - 130
23. 23)
  - C.C. Wang . An algorithm to design finite field multipliers using a self-dual normal basis. IEEE Trans. Comput. , 10 , 1457 - 1459
24. 24)
  - G. Bertoni , L. Breveglieri , I. Koren , P. Maistri , V. Piuri . Error analysis and detection procedures for a hardware implementation of the advanced encryption standard. IEEE Trans. Comput. , 4 , 492 - 505
25. 25)
  - Coron, J.S.: `Resistance against differential power analysis attacks for elliptic curve cryptosystems', Proc. Cryptographic Hardware and Embedded Systems (CHES’99), 1999, p. 292–302, (LNCS, 1717).
26. 26)
  - S.T.J. Fenn , M. Benaissa , D. Taylor . Dual basis systolic multipliers for GF(2m). IEE Proc. Comput. Digit. Tech. , 1 , 43 - 46
27. 27)
  - N. Weste , K. Eshraghian . (1985) Principles of CMOS VLSI design: a system perspective.
28. 28)
  - S.T.J. Fenn , M. Benaissa , D. Taylor . GF(2m) multiplication and division over the dual basis. IEEE Trans. Comput. , 3 , 319 - 327
29. 29)
  - Woodard, S.E.: `Design of digital systems using self-checking alternating logic', 1977, PhD, University of Illinois at Urbana-Champaign, USA.
30. 30)
  - E.R. Berlekamp . Bit-serial reed-solomon encoder. IEEE Trans. Inf. Theory , 869 - 874
31. 31)
  - C. Paar , P. Fleischmann , P. Roelse . Efficient multiplier architectures for Galois Fields GF(24n). IEEE Trans. Comput. , 2 , 162 - 170
32. 32)
  - S. Fenn , M. Gossel , M. Benaissa , D. Taylor . On-line error detection for bit-serial multipliers in GF(2m). J. Electron. Test Theory Appl. , 29 - 40
33. 33)
  - C.W. Chiou . Concurrent error detection in array multipliers for GF(2m) fields. IEE Electron. Lett. , 14 , 688 - 689
34. 34)
  - Karri, R., Kuznetsov, G., Goessel, M.: `Parity-based concurrent error detection of substitution-permutation network block ciphers', Proc. CHES 2003, 2003, p. 113–124, (LNCS, 2779).
35. 35)
  - Messerges, T.S., Dabbish, E.A., Sloan, R.H.: `Power analysis attacks of modular exponentiation in smartcards', Proc. Cryptographic Hardware and Embedded Systems (CHES’99), 1999, p. 144–157, (LNCS, 1717).
36. 36)
  - H. Wu , M.A. Hasan , I.F. Blake . New low-complexity bit-parallel finite field multipliers using weakly dual bases. IEEE Trans. Comput. , 11 , 1223 - 1234
37. 37)
  - M. Joye , A.K. Lenstra , J.-J. Quisquater . Chinese remaindering based cryptosystems in the presence of faults. J. Cryptol. , 241 - 245
38. 38)
  - Yamamoto, H., Watanabe, T., Urano, Y.: `Alternating logic and its application to fault detection', Proc. 1970 IEEE Int. Computing Group Conf., June 1970, Washington, DC, p. 220–228.
39. 39)
  - M. Wang , I.F. Blake . Bit serial multiplication in finite fields. SIAM J. Discret. Math. , 1 , 140 - 148
40. 40)
  - M.A. Hasan , M. Wang , V.K. Bhargava . Modular construction of low complexity parallel multipliers for a class of finite fields GF(2m). IEEE Trans. Comput. , 8 , 962 - 971
41. 41)
  - R.E. Blahut . (1985) Fast algorithms for digital signal processing.
42. 42)
  - Kelsey, J., Schneier, B., Wagner, D., Hall, C.: `Side-channel cryptanalysis of product ciphers', Proc. ESORICS, September 1998, p. 97–110.
43. 43)
  - H. Wu , M.A. Hasan . Low complexity bit-parallel multipliers for a class of finite fields. IEEE Trans. Comput. , 8 , 883 - 887
44. 44)
  - M. Morii , M. Kasahara , D.L. Whiting . Efficient bit-serial multiplication and the discrete-time Wiener-Hopf equation over finite fields. IEEE Trans. Inf. Theory , 6 , 1177 - 1183
45. 45)
  - Reynolds, D.A., Metze, G.: `Fault detection capabilities of alternating logic', Proc. Sixth Ann. Symp. on Fault Tolerant Computing, June 1976, p. 157–162.
46. 46)
  - R. Lidl , H. Niederreiter . (1994) Introduction to finite fields and their applications.
47. 47)
  - C.-Y. Lee , J.-M. Lin , C.W. Chiou . Scalable and systolic architecture for computing double exponentiation over GF(2m). Acta Appl. Math. , 161 - 178
48. 48)
  - C.Y. Lee , C.W. Chiou , A.-W. Deng , J.M. Lin . Low-complexity bit-parallel systolic architectures for computing A(x)B2(x) over GF(2m). IEE Proc. Circuits Devices Syst. , 4 , 399 - 406
49. 49)
  - Biham, E., Shamir, A.: `Differential fault analysis of secret key cryptosystems', Proc. Crypto, 1997, p. 513–525, (LNCS, 1294).
50. 50)
  - Boneh, D., Demillo, R., Lipton, R.: `On the importance of checking cryptographic protocols for faults', Proc. Eurocrypt, 1997, p. 37–51, (LNCS, 1233).
51. 51)
  - C.Y. Lee , E.H. Lu , J.Y. Lee . Bit-parallel systolic multipliers for GF(2m) fields defined by all-one and equally-spaced polynomials. IEEE Trans. Comput. , 5 , 385 - 393
52. 52)
  - Massey, J.L., Omura, J.K.: `Computational method and apparatus for finite field arithmetic', U.S., 4587627, May 1986.
53. 53)
  - J. Wakerly . (1980) Error detecting codes, self-checking circuits and applications.
54. 54)
  - Reyhani-Masoleh, A., Hasan, M.A.: `Error detection in polynomial basis multipliers over binary extension fields', Proc. Cryptographic Hardware and Embedded Systems-CHES 2002, 2003, p. 515–528, (LNCS, 2523).
55. 55)
  - T.C. Bartee , D.J. Schneider . Computation with finite fields. Inform. Comput. , 79 - 98
56. 56)
  - A. Reyhani-Masoleh , M.A. Hasan . A new construction of Massey-Omura parallel multiplier over GF(2m). IEEE Trans. Comput. , 5 , 511 - 520

Concurrent error detection in semi-systolic dual basis multiplier over GF(2m) using self-checking alternating logic

Concurrent error detection in semi-systolic dual basis multiplier over GF(2m) using self-checking alternating logic

Buy article PDF

Buy Knowledge Pack

Thank you

References

Related content

Concurrent error detection in semi-systolic dual basis multiplier over GF(2^m) using self-checking alternating logic

Concurrent error detection in semi-systolic dual basis multiplier over GF(2^m) using self-checking alternating logic