Radix-r Non-Adjacent Form and Its Application to Pairing-Based Cryptosystem(Elliptic Curve Cryptography, <Special Section>Cryptography and Information Security)

スポンサーリンク

概要

• 論文の詳細を見る

• Recently, the radix-3 representation of integers is used for the efficient implementation of pairing based cryptosystems. In this paper, we propose non-adjacent form of radix-r representation (rNAF) and efficient algorithms for generating rNAF. The number of non-trivial digits is (r-2)(r+1)/2 and its average density of non-zero digit is asymptotically (r-1)/(2r-1). For r=3, the non-trivial digits are {±2, ±4} and the non-zero density is 0.4. We then investigate the width-w version of rNAF for the general radix-r representation, which is a natural extension of the width-w NAF. Finally we compare the proposed algorithms with the generalized NAF (gNAF) discussed by Joye and Yen. The proposed scheme requires a larger table but its non-zero density is smaller even for large radix. We explain that gNAF is a simple degeneration of rNAF--we can consider that rNAF is a canonical form for the radix-r representation. Therefore, rNAF is a good alternative to gNAF.

• 社団法人電子情報通信学会の論文
• 2006-01-01

著者

• Takagi Tsuyoshi

  School Of Systems Information Science Future University-hakodate

• Yen Sung-ming

  Laboratory Of Cryptography And Information Security (lcis):department Of Computer Science And Inform

• David REIS

  School of Electrical and Computer Engineering, State University of Campinas

• WU Bo-Ching

  Laboratory of Cryptography and Information Security (LCIS)

• David Reis

  School Of Electrical And Computer Engineering State University Of Campinas

• Wu Bo-ching

  Laboratory Of Cryptography And Information Security (lcis):department Of Computer Science And Inform

関連論文

• 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)
• 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
• Universal ηT pairing algorithm over arbitrary extension degree (ワイドバンドシステム)
• Universal ηT pairing algorithm over arbitrary extension degree (情報セキュリティ)
• Universal ηT pairing algorithm over arbitrary extension degree (情報理論)

スポンサーリンク