Faster MapToPoint on Supersingular Elliptic Curves in Characteristic 3

スポンサーリンク

概要

• 論文の詳細を見る

• Pairing-based cryptosystems are generally constructed using many functions such as pairing computation, arithmetic in finite fields, and arithmetic on elliptic curves. MapToPoint, which is a hashing algorithm onto an elliptic curve point, is one of the functions for constructing pairing-based cryptosystems. There are two MapToPoint algorithms on supersingular elliptic curves in characteristic three, which is used by ηT pairing. The first is computed by using a square root computation in F3m, and the computational cost of this algorithm is O(log m) multiplications in F3m. The second is computed by using an (m-1)×(m-1) matrix over F3. It can be computed by O(1) multiplications in F3m. However, this algorithm needs the off-line memory to store about m F3m-elements. In this paper, we propose an efficient MapToPoint algorithm on the supersingular elliptic curves in characteristic three by using 1/3-trace over F3m. We propose 1/3-trace over F3m, which can compute solution x of x3-x=c by using no multiplication in F3m. The proposed algorithm is computed by O(1) multiplications in F3m, and it requires less than m F3-elements to be stored in the off-line memory to efficiently compute trace over F3m. Moreover, in our software implementation of F3509, the proposed MapToPoint algorithm is approximately 35% faster than the conventional MapToPoint algorithm using the square root computation on an AMD Opteron processor (2.2GHz).

• 2011-01-01

著者

• KAWAHARA Yuto

  Future University-Hakodate

• TAKAHASHI Gen

  NTT Information Sharing Platform Laboratories, NTT Corporation

• TAKAGI Tsuyoshi

  Future University-Hakodate

• Takagi Tsuyoshi

  Future Univ.‐hakodate Hakodate‐shi Jpn

• Kobayashi Tetsutaro

  Ntt Information And Communication Systems Laboratories

• Takahashi Gen

  Ntt Information Sharing Platform Laboratories Ntt Corporation

関連論文

• Faster MapToPoint on Supersingular Elliptic Curves in Characteristic 3
• Candidate One-Way Functions on Non-Supersingular Elliptic Curves(Elliptic Curve Cryptography, Cryptography and Information Security)
• Non-Supersingular Elliptic Curves for Pairing-Based Cryptosystems(Discrete Mathematics and Its Applications)
• Efficient Implementation of the Pairing on Mobilephones Using BREW
• Generalized Powering Functions and Their Application to Digital Signatures(Digital Signature, 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
• Defeating Simple Power Analysis on Koblitz Curves(Discrete Mathematics and Its Applications)
• Security Analysis of the SPA-Resistant Fractional Width Method(Elliptic Curve Cryptography, Cryptography and Information Security)
• A New Upper Bound for the Minimal Density of Joint Representations in Elliptic Curve Cryptosystems(Discrete Mathematics and Its Applications)
• Anonymous Hierarchical Identity-Based Encryption with Short Ciphertexts
• Faster MapToPoint on Supersingular Elliptic Curves in Characteristic 3
• Fast Modular Inversion Algorithm to Match Any Operation Unit (Special Section on Discrete Mathematics and Its Applications)
• Efficient τ-Adic Sliding Window Method on Elliptic Curve Cryptosystems(Special Section on Cryptography and Information Security)
• A More Compact Representation of XTR Cryptosystem
• Efficient Hyperelliptic Curve Cryptosystems Using Theta Divisors(Elliptic Curve Cryptography, Cryptography and Information Security)
• Some Efficient Algorithms for the Final Exponentiation of ηT Pairing
• Universal ηT pairing algorithm over arbitrary extension degree (ワイドバンドシステム)
• Universal ηT pairing algorithm over arbitrary extension degree (情報セキュリティ)
• Universal ηT pairing algorithm over arbitrary extension degree (情報理論)
• Lenient/Strict Batch Verification in Several Groups(Special Section on Cryptography and Information Security)
• A Cyclic Window Algorithm for Elliptic Curves over OEF(Special Section on Cryptography and Information Security)
• Efficient Implementation of Pairing-Based Cryptography on a Sensor Node
• Security of ESIGN-PSS(Information Security)

もっと見る 閉じる

スポンサーリンク