http://iet.metastore.ingenta.com
1887

Concurrent error detection and correction in dual basis multiplier over GF(2m)

Concurrent error detection and correction in dual basis multiplier over GF(2m)

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

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

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

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Circuits, Devices & Systems — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Fault-based side-channel cryptanalysis is a useful technique against symmetrical and asymmetrical encryption/decryption algorithms. Thus, eliminating cryptographic computation errors become critical in preventing such kind of attacks. A simple way to eliminating cryptographic computation errors is to output correct or corrected ciphers. Multiplication is the most important finite field arithmetic operation in the cryptographic computations. By using time redundancy technique, a novel dual basis (DB) multiplier over Galois fields (2m) will be presented with lower space complexity and feedback-free property. Based on the proposed feedback-free DB multiplier, the DB multiplier with a concurrent error detection (CED) capability is also easily developed. Compared with the existing DB multiplier with CED capability, the proposed one saves about 90% of time-area complexity. No existing DB multiplier in the literature has concurrent error correction (CEC) capability. Based on the proposed DB multiplier, a novel DB multiplier with CEC capability is easily designed. The proposed DB multiplier with CEC capability requires only about 3% of extra space complexity and 15% of time complexity when compared with the proposed DB multiplier without CEC.

References

    1. 1)
      • F.J. MacWilliams , N.J.A. Sloane . (1977) The theory of error-correcting codes.
    2. 2)
      • R. Lidl , H. Niederreiter . (1994) Introduction to finite fields and their applications.
    3. 3)
      • R.E. Blahut . (1985) Fast algorithms for digital signal processing.
    4. 4)
      • I.S. Reed , T.K. Truong . The use of finite fields to compute convolutions. IEEE Trans. Inf. Theory , 2 , 208 - 213
    5. 5)
      • B. Benjauthrit , I.S. Reed . Galois switching functions and their applications. IEEE Trans. Comput. , 78 - 86
    6. 6)
      • C.C. Wang , D. Pei . A VLSI design for computing exponentiation in GF(2m) and its application to generate pseudorandom number sequences. IEEE Trans. Comput. , 2 , 258 - 262
    7. 7)
      • E.R. Berlekamp . Bit-serial Reed-Solomon encoder. IEEE Trans. Inf. Theory , 869 - 874
    8. 8)
      • 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
    9. 9)
      • T.C. Bartee , D.J. Schneider . Computation with finite fields. Inf. Comput. , 79 - 98
    10. 10)
      • Mastrovito, E.D., Mora, T.: `VLSI architectures for multiplication over finite field GF(2', Proc. 6th Int. Conf., AAECC-6, July 1988, Rome, p. 297–309.
    11. 11)
      • Mastrovito, E.D.: `VLSI architectures for computations in Galois fields', 1991, PhD, Linköping University, Department of Electrical Engineering, Linköping, Sweden, 1991.
    12. 12)
      • Ç.K. Koç , B. Sunar . Low-complexity bit-parallel canonical and normal basis multipliers for a class of finite fields. IEEE Trans. Comput. , 3 , 353 - 356
    13. 13)
      • T. Itoh , S. Tsujii . Structure of parallel multipliers for a class of fields GF(2m). Inf. Comput. , 21 - 40
    14. 14)
      • 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
    15. 15)
      • 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
    16. 16)
      • H. Wu . Bit-parallel finite field multiplier and squarer using polynomial basis. IEEE Trans. Comput. , 7 , 750 - 758
    17. 17)
      • C.W. Chiou , C.-Y. Lee , J.-M. Lin . Efficient systolic arrays for power-sum, inversion, and division in GF(2m). Int. J. Comput. Sci. Eng. Syst. , 1 , 27 - 41
    18. 18)
      • 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
    19. 19)
      • 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
    20. 20)
      • C.-Y. Lee , Y.-H. Chen , C.W. Chiou , J-M. Lin . Unified parallel systolic multipliers over GF(2m). J. Comput. Sci. Technol. , 1 , 28 - 38
    21. 21)
      • Massey, J.L., Omura, J.K.: `Computational method and apparatus for finite field arithmetic', U.S., 4,587,627, 1986.
    22. 22)
      • 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
    23. 23)
      • A. Reyhani-Masoleh , M.A. Hasan . A new construction of Massey-Omura parallel multiplier over GF(2m). IEEE Trans. Comput. , 5 , 511 - 520
    24. 24)
      • S. Oh , C.H. Kim , J. Lim , D.H. Cheon . Efficient normal basis multipliers in composite fields. IEEE Trans. Comput. , 10 , 1133 - 1138
    25. 25)
      • C.K. Koc , B. Sunar . An efficient optimal normal basis type II multiplier. IEEE Trans. Comput. , 1 , 83 - 87
    26. 26)
      • N. Takagi , J.-I. Yoshiki , K. Takagi . A fast algorithm for multiplicative inversion in GF(2m) using normal basis. IEEE Trans. Comput. , 5 , 394 - 398
    27. 27)
      • 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
    28. 28)
      • C.W. Chiou , C.Y. Lee . Multiplexer-based double-exponentiation for normal basis of GF (2m). Comput. Secur. , 1 , 83 - 86
    29. 29)
      • I.S. Hsu , T.K. Truong , L.J. Deutsch , I.S. Reed . A comparison of VLSI architecture of finite field multipliers using dual, normal, or standard bases. IEEE Trans. Comput. , 6 , 735 - 739
    30. 30)
      • 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
    31. 31)
      • H. Wu , M.A. Hasan . Low complexity bit-parallel multipliers for a class of finite fields. IEEE Trans. Comput. , 8 , 883 - 887
    32. 32)
      • S.T.J. Fenn , M. Benaissa , D. Taylor . GF(2m) multiplication and division over the dual basis. IEEE Trans. Comput. , 3 , 319 - 327
    33. 33)
      • C.C. Wang . An algorithm to design finite field multipliers using a self-dual normal basis. IEEE Trans. Comput. , 10 , 1457 - 1459
    34. 34)
      • S.T.J. Fenn , M. Benaissa , D. Taylor . Dual basis systolic multipliers for GF(2m). IEE Proc. Comput. Digit. Tech. , 1 , 43 - 46
    35. 35)
      • M. Wang , I.F. Blake . Bit serial multiplication in finite fields. SIAM J. Discret. Math. , 1 , 140 - 148
    36. 36)
      • M. Diab , A. Poli . New bit-serial systolic multiplier for GF(2m) using irreducible trinomials. Electron. Lett. , 13 , 1183 - 1184
    37. 37)
      • Boneh, D., DeMillo, R., Lipton, R.: `On the importance of checking cryptographic protocols for faults', Proc. Eurocrypt, 1999, p. 37–51, Springer LNCS 1233.
    38. 38)
      • Biham, E., Shamir, A.: `Differential fault analysis of secret key cryptosystems', Proc. Crypto, 1997, p. 513–525, Springer LNCS 1294.
    39. 39)
      • Kelsey, J., Schneier, B., Wagner, D., Hall, C.: `Side-channel cryptanalysis of product ciphers', Proc. ESORICS, September 1998, Springer, p. 97–110.
    40. 40)
      • Anderson, R.J., Kuhn, M.: `Low cost attack on tamper resistant devices', Proc. 5th Int. Workshop on Security Protocols, 1997, Lecture Notes in Computer Sciences, Springer-Verlag, LNCS 1361.
    41. 41)
      • Messerges, T.S., Dabbish, E.A., Sloan, R.H.: `Power analysis attacks on modular exponentiation in smartcards', Proc. Cryptographic Hardware and Embedded Systems (CHES'99), LNCS 1717, 1999.
    42. 42)
      • Coron, J.S.: `Resistance against differential power analysis attacks for elliptic curve cryptosystems', Proc. Cryptographic Hardware and Embedded Systems (CHES'99), LNCS 1717, 1999, p. 292–302.
    43. 43)
      • Karri, R., Kuznetsov, G., Goessel, M.: `Parity-based concurrent error detection of substitution-permutation network block ciphers', Proc. CHES 2003, 2003, Springer LNCS 2779, p. 113–124.
    44. 44)
      • 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
    45. 45)
      • M. Joye , A.K. Lenstra , J.-J. Quisquater . Chinese remaindering based cryptosystems in the presence of faults. J. Cryptol. , 241 - 245
    46. 46)
      • D. Boneh , R.A. DeMillo , R.J. Lipton . On the importance of eliminating errors in cryptographic computations. J. Cryptol. , 101 - 119
    47. 47)
      • 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
    48. 48)
      • Reyhani-Masoleh, A., Hasan, M.A.: `Error detection in polynomial basis multipliers over binary extension fields', Proc. Cryptographic Hardware and Embedded Systems-CHES 2002, LNCS 2523, 2003, p. 515–528.
    49. 49)
      • A. Reyhani-Masoleh , M.A. Hasan . Fault detection architectures for field multiplication using polynomial bases. IEEE Trans. Comput. , 9 , 1089 - 1103
    50. 50)
      • 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
    51. 51)
      • C.W. Chiou . Concurrent error detection in array multipliers for GF(2m) fields. IEE Electron. Lett. , 14 , 688 - 689
    52. 52)
      • 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
    53. 53)
      • 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
    54. 54)
      • J.H. Patel , L.Y. Fung . Concurrent error detection in ALU's by recomputing with shifted operands. IEEE Trans. Comput. , 7 , 589 - 595
    55. 55)
      • J.H. Patel , L.Y. Fung . Concurrent error detection in multiply and divide arrays. IEEE Trans. Comput. , 4 , 417 - 422
    56. 56)
      • Minero, R.H., Anello, A.J., Furey, R.G., Palounek, L.R.: `Checking by pseuduplication', U.S., 3660646, May 1972.
    57. 57)
      • National Institute for Standards and Technology, ‘Digital Signature Standard’, FIPS publication 186-2, January 2000.
    58. 58)
      • Hewlett Packard: ‘Table of low-weight binary irreducible polynomials’, HPL-98-135, 1998.
    59. 59)
      • N. Weste , K. Eshraghian . (1985) Principles of CMOS VLSI design: a system perspective.
    60. 60)
      • M74HC86: ‘Quad exclusive OR gate, 2001 STMicroelectronics’, http://www.st.com/stonline/books/pdf/docs/2006.pdf.
    61. 61)
      • M74HC08: ‘Quad 2-input AND gate, 2001 STMicroelectronics’, http://www.st.com/stonline/books/pdf/docs/1885.pdf.
    62. 62)
      • M74HC174: ‘Hex D-type flip flop with clear, 2001 STMicroelectronics’, http://www.st.com/stonline/products/literature/ds/1914/M74HC174.pdf.
    63. 63)
      • M74HC32: ‘Quad 2-input OR gate, 2001 STMicroelectronics’, http://www.st.com/stonline/books/pdf/docs/1944.pdf.
    64. 64)
      • M74HC4075: ‘Triple 3-input OR gate, 2001 STMicroelectronics’, http://www.st.com/stonline/books/pdf/docs/1970.pdf.
    65. 65)
      • J. Wakerly . (1980) Error detecting codes, self-checking circuits and applications.
    66. 66)
      • S.W. Wei . VLSl architectures for computing exponentiations, multiplicative inverses, and divisions in GF(2m). IEEE Trans. Circuits Syst. , 10 , 847 - 855
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds_20080122
Loading

Related content

content/journals/10.1049/iet-cds_20080122
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address