Journal of the Korea Institute of Information Security & Cryptology (정보보호학회논문지)

Korea Institute of Information Security and Cryptology (한국정보보호학회)
권호 표지
DOI QR코드

DOI QR Code

Efficient Finite Field Arithmetic Architectures for Pairing Based Cryptosystems

페어링 기반 암호시스템의 효율적인 유한체 연산기

  • Chang, Nam-Su (Graduate School of Information Management and Security, Korea University) ;
  • Kim, Tae-Hyun (Graduate School of Information Management and Security, Korea University) ;
  • Kim, Chang-Han (School of Information & Communication systems, Semyung University) ;
  • Han, Dong-Guk (Electronics and Telecommunications Research Institute) ;
  • Kim, Ho-Won (School of computer science and engineering in Pusan National University)
  • 장남수 (고려대학교 정보경영공학전문대학원) ;
  • 김태현 (고려대학교 정보경영공학전문대학원) ;
  • 김창한 (세명대학교) ;
  • 한동국 (한국전자통신연구원) ;
  • 김호원 (부산대학교 공과대학 정보컴퓨터공학부)
  • Published : 2008.06.30
Download PDF
⟨ Previous Next ⟩

Abstract

The efficiency of pairing based cryptosystems depends on the computation of pairings. pairings is defined over finite fileds GF$(3^m)$ by trinomials due to efficiency. The hardware architectures for pairings have been widely studied. This paper proposes new adder and multiplier for GF(3) which are more efficient than previous results. Furthermore, this paper proposes a new unified adder-subtractor for GF$(3^m)$ based on the proposed adder and multiplier. Finally, this paper proposes new multiplier for GF$(3^m)$. The proposed MSB-first bit-serial multiplier for GF$(p^m)$ reduces the time delay by approximately 30 % and the size of register by half than previous LSB-first multipliers. The proposed multiplier can be applied to all finite fields defined by trinomials.

페어링 기반의 암호시스템의 효율성은 페어링 연산의 효율성에 기반하며 페어링 연산은 유한체 GF$(3^m)$에서 많이 고려된다. 또한 페어링의 고속연산을 위하여 삼항 기약다항식을 고려하며 이를 기반으로 하는 하드웨어 설계방법에 대한 연구가 활발히 진행되고 있다. 본 논문에서는 기존의 GF(3) 연산보다 효율적인 새로운 GF(3) 덧셈 및 곱셈 방법을 제안하며 이를 기반으로 새로운 GF$(3^m)$ 덧셈-뺄셈 unified 연산기를 제안한다. 또한 삼항 기약다항식을 특징을 이용한 새로운 GF$(p^m)$ MSB-first 비트-직렬 곱셈기를 제안한다. 제안하는 MSB-first 비트-직렬 곱셈기는 기존의 MSB-first 비트-직렬 곱셈기보다 시간지연이 대략 30%감소하며 기존의 LSB-first 비트-직렬 곱셈기보다 절반의 레지스터를 사용하여 효율적이며, 제안하는 곱셈 방법은 삼항 기약다항식을 사용하는 모든 유한체에 적용가능하다.

Keywords

References

  1. P.S.L.M Barreto, S. Galbraith, C. O hEigeartaigh and M. Scott, "Efficient Pairing Computation on Supersingular Abelian Varieties," Designs, Codes and Cryptography, Vol.42, No.3, pp.239-271, 2007 https://doi.org/10.1007/s10623-006-9033-6
  2. P.S.L.M. Barreto, H.Y. Kim, B. Lynn, and M. Scott, "Efficient algorithm for pairing-based crypto systems," CRYPTO 2002, LNCS 2442, pp.354-368, Springer-Verlag, 2002
  3. G. Bertoin, L. Breveglieri, P. Fragneto, and G. Pelosi, "Parallel Hardware Architectures for the Clyptographic Tate Pairing," Proceedings of the Third International Conference on Information Technology : New Generations (ITNG'06), pp.186-191, 2006
  4. G. Bertoin, J. Guajardo, S. Kumar, G. Orlando C. Paar and T. Wollinger. "Efficient GF$_{p^m}$ Arith metic Architectures for Cryptographic Applications," CT-RSA 2003, LNCS 2612, pp.158-175 Springer-Verlag, 2003
  5. J. Beuchat, M. Shirase, T. Takagi, E. Okamoto, "An Algorithm for the Eta_T Pairing Calculation in Characteristic Three and its Hardware Implementation", 18th IEEE International Symposium on Computer Arithmetic, ARIT H-18, pp.97-104, 2007
  6. J. Beuchat, T. Miyoshi, Y. Oyama, E. Okamoto, "Multiplication over $F_{p^m}$： on FPGA : A Survey", ARC-2007, LNCS 4419, pp.214-225, Springer-Verlag, 2007
  7. I. Duursma and H.-S. Lee, "Tate pairing implementation for hyper elliptic curves y$^2$=x$^p$-x+d," Asiacrypt 2003, LNCS 2894, pp.111-123, Springer-Verlag, 2003
  8. S.D. Galbraith, K. Harrison, and D. Soldera, "Implementing the Tate pairing," ANTS V, LNCS 236 9, pp.324-337, Springer-Verlag, 2002
  9. P. Grabher and D. Page, "Hardware Acceleration of the Tate Pairing in Characteristic Three," CHES 2005, LNCS 3659, pp.398-411, Springer-Verlag, 2005
  10. R. Granger, D. Page, and M. Stam, "Hardware and software normal basis arithmetic for pairing based cryptography in characteristic three," IEEE Transactions on Computers, Vol.54, No 7, pp.852-860, July 2005 https://doi.org/10.1109/TC.2005.120
  11. T. Kerins, W. Marnane, E. Popovici, P. S. L. M. Barreto "Efficient Hardware for the Tate Pairing Calculation in Characteristic Three," CHES 2005, LNCS 3659, pp.398-411, Springer-Verlag, 2005
  12. T. Kerins, E. M. Popovici and W. P. Marnane, "Algorithms and Architectures for use in FPGA implementations of Identity Based Encryption Schemes," FPL 2004, LNCS 3203, pp.74-83, Springer-Verlag, 2004
  13. S. Kwon, "Efficient Tate pairing computation for elliptic curves over binary fields," ACISP 2005, LNCS 3574, pp.134-145, Springer-Verlag, 2005
  14. V. SMiller short Programs for functions on curves. Unpublished manuscript, 1986. http://clypto.sta.nford.edu/miller/miller.pdf
  15. D. Page and N. Smart "Hardware Implementation of Finite Fields of Characteristic Three," CHES 2002, LNCS 2523, pp.529-539, Springer-Verlag, 2003