Reduction Optimal Trinomials for Efficient Software Implementation of the ηT Pairing
スポンサーリンク
概要
- 論文の詳細を見る
The ηT pairing for supersingular elliptic curves over GF(3m) has been paid attention because of its computational efficiency. Since most computation parts of the ηT pairing are GF(3m) multiplications, it is important to improve the speed of the multiplication when implementing the ηT pairing. In this paper we investigate software implementation of GF(3m) multiplication and propose using irreducible trinomials xm+axk+b over GF(3) such that k is a multiple of w, where w is the bit length of the word of targeted CPU. We call the trinomials “reduction optimal trinomials (ROTs).” ROTs actually exist for several ms and for typical values of w=16 and 32. We list them for extension degrees m=97, 167, 193, 239, 317, and 487. These ms are derived from security considerations. Using ROTs, we are able to implement efficient modulo operations (reductions) for GF(3m) multiplication compared with cases in which other types of irreducible trinomials are used (e. g., trinomials with a minimum k for each m). The reason for this is that for cases using ROTsa, the number of shift operations on multiple precision data is reduced to less than half compared with cases using other trinomials. Our implementation results show that programs of reduction specialized for ROTs are 20-30% faster on 32-bit CPU and approximately 40% faster on 16-bit CPU compared with programs using irreducible trinomials with general k.
- （社）電子情報通信学会の論文
- 2008-09-01
著者
-
IZU Tetsuya
FUJITSU LABORATORIES Ltd. and FUJITSU Ltd.
-
Takagi Tsuyoshi
School Of Systems Information Science Future University-hakodate
-
NAKAJIMA Toshiya
Fujitsu Ltd.
-
Izu Tetsuya
Fujitsu Laboratories Ltd.
-
Izu Tetsuya
Fujitsu Ltd. Kawasaki‐shi Jpn
関連論文
- Extending Bleichenbachers Forgery Attack
- Small Secret CRT-Exponent Attacks on Takagis RSA
- Reduction Optimal Trinomials for Efficient Software Implementation of the ηT Pairing
- Generalized Powering Functions and Their Application to Digital Signatures(Digital Signature, Cryptography and Information Security)
- A Practical Countermeasure against Address-bit Differential Power Analysis (特集:プライバシを保護するコンピュータセキュリティ技術)
- Radix-r Non-Adjacent Form and Its Application to Pairing-Based Cryptosystem(Elliptic Curve Cryptography, Cryptography and Information Security)
- Distributed Noise Generation for Density Estimation Based Clustering without Trusted Third Party
- Security and Correctness Analysis on Privacy-Preserving k-Means Clustering Schemes
- A Note on the Lattice Factoring Method (Cryptography and Information Security)
- Small Secret CRT-Exponent Attacks on Takagi's RSA
- A Note on the Lattice Factoring Method
- Side Channel Cryptanalysis on XTR Public Key Cryptosystem(Discrete Mathematics and Its Applications)
- Universal ηT pairing algorithm over arbitrary extension degree (ワイドバンドシステム)
- Universal ηT pairing algorithm over arbitrary extension degree (情報セキュリティ)
- Universal ηT pairing algorithm over arbitrary extension degree (情報理論)
- Detailed Cost Estimation of CNTW Forgery Attack against EMV Signature Scheme
- Experimental Analysis of Cheon's Algorithm against Pairing-friendly Curves
- Extending Bleichenbacher's Forgery Attack