Analysis of Baby-Step Giant-Step Algorithms for Non-uniform Distributions (Fundamental) (<Special Section>Cryptography and Information Security)

スポンサーリンク

概要

• 論文の詳細を見る

• The baby-step giant-step algorithm, BSGS for short, was proposed by Shanks in order to compute the class number of an imaginary quadratic field. This algorithm is at present known as a very useful tool for computing with respect to finite groups such as the discrete logarithms and counting the number of the elements. Especially, the BSGS is normally made use of counting the rational points on the Jacobian of a hyperelliptic curve over a finite field. Indeed, research on the practical improvement of the BSGS has recently received a lot of attention from a cryptographic viewpoint. In this paper, we explicitly analyze the modified BSGS, which is for non-uniform distributions of the group order, proposed by Blackburn and Teske. More precisely, we refine the Blackburn-Teske algorithm, and also propose a criterion for the decision of the effectiveness of their algorithm; namely, our proposed criterion explicitly shows that what distribution is needed in order that their proposed algorithm is faster than the original BSGS. That is, we for the first time present a necessary and sufficient condition under which the modified BSGS is effective.

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

著者

• Kanayama Naoki

  Department of Bioscience and Biotechnology, Graduate School of Natural Science and Technology, Okaya

• Kanayama Naoki

  Department Of Bioscience And Biotechnology Graduate School Of Natural Science And Technology Okayama

• Kanayama Naoki

  Department Of Information And Communication Engineering The University Of Electro-comrnunications

• Kanayama N

  Waseda Univ. Tokyo Jpn

• UCHIYAMA Shigenori

  NTT Information Sharing Platform Laboratories, NTT Corporation

• Matsuo Kazuto

  Graduate School Of Information Security Institute Of Information Security:research And Development I

• Uchiyama S

  Ntt Information Sharing Platform Laboratories

• Uchiyama Shigenori

  Ntt Information Sharing Platform Laboratories

• MATSUO Kazuto

  Research and Development Initiative, Chuo University

• NAGAO Koh-ichi

  Faculty of Engineering, Kanto Gakuin University

• Nagao Koh-ichi

  Faculty Of Engineering Kanto Gakuin University

関連論文

• Conditional transformation of immunoglobulin mutation pattern from gene conversion into point mutation by controlling XRCC3 expression in the DT40 B cell line(CELL AND TISSUE ENGINEERING)
• Efficient affinity maturation of antibodies in an engineered chicken B cell line DT40-SW by increasing point mutation
• The Vanstone-Zuccherato Schemes Revisited(Information Security)
• Efficient affinity maturation of antibodies in an engineered chicken B cell line DT40-SW by increasing point mutation(CELL AND TISSUE ENGINEERING)
• Optimised Versions of the Ate and Twisted Ate Pairings
• Conditional transformation of immunoglobulin mutation pattern from gene conversion into point mutation by controlling XRCC3 expression in the DT40 B cell line
• Enhancement of antibody production from a chicken B cell line DT40 by reducing Pax5 expression(MEDICAL BIOTECHNOLOGY)
• Novel In Vitro Screening System for Monoclonal Antibodies Using Hypermutating Chicken B Cell Library(METHOD)
• Optimised Versions of the Ate and Twisted Ate Pairings
• Non-optimistic Secure Circuit Evaluation Based on ElGamal Encryption and Its Applications(Protocols,Cryptography and Information Security)
• 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)
• Remarks on Elliptic Curve Discrete Logarithm Problems(Special Section on Cryptography and Information Security)
• The co-Diffie-Hellman Problem over Elliptic Curves
• Improvements of Addition Algorithm on Genus 3 Hyperellipic Curves and Their Implementation(Public Key Cryptography)(Cryptography and Information Security)
• Baby Step Giant Step Algorithms in Point Counting of Hyperelliptic Curves
• Analysis of Baby-Step Giant-Step Algorithms for Non-uniform Distributions (Fundamental) (Cryptography and Information Security)
• Generating Secure Genus Two Hyperelliptic Curves Using Elkies' Point Counting Algorithm
• On the Euclidean Algorithm of Polynomials (Special Section on Discrete Mathematics and Its Applications)
• Scalar Multiplication on Pairing Friendly Elliptic Curves
• A Note on the Pairing Computation Using Normalized Miller Functions
• Implementation of an Elliptic Curve Scalar Multiplication Method Using Division Polynomials

もっと見る 閉じる

スポンサーリンク