スカラー倍演算装置、スカラー倍演算方法、スカラー倍演算プログラム、記録媒体
【課題】符号付き二進法に適用できる同時スカラー倍演算法を実現する。
【解決手段】本発明のスカラー倍演算装置は、中間値計算部、元計算部、スカラー倍値計算部を備える。中間値計算部は、中間値ｅｄ（１），…，ｄ（Ｍ）（ｎ）をすべてのｄ（１），…，ｄ（Ｍ）の組合せについて求める。元計算部は、中間値計算部で求めたｄ（１），…，ｄ（Ｍ）の組合せのすべてについて、Ｅｄ（１），…，ｄ（Ｍ）Ｇを求める。スカラー倍値計算部は、ｄ（ｍ）の値が１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和から、ｄ（ｍ）の値が−１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和を減算した値をスカラー倍値ＥｍＧとする処理を、ｍ＝１からＭに対して行う。
【解決手段】本発明のスカラー倍演算装置は、中間値計算部、元計算部、スカラー倍値計算部を備える。中間値計算部は、中間値ｅｄ（１），…，ｄ（Ｍ）（ｎ）をすべてのｄ（１），…，ｄ（Ｍ）の組合せについて求める。元計算部は、中間値計算部で求めたｄ（１），…，ｄ（Ｍ）の組合せのすべてについて、Ｅｄ（１），…，ｄ（Ｍ）Ｇを求める。スカラー倍値計算部は、ｄ（ｍ）の値が１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和から、ｄ（ｍ）の値が−１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和を減算した値をスカラー倍値ＥｍＧとする処理を、ｍ＝１からＭに対して行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを暗号化する装置や認証する装置にかかわり、特に情報セキュリティを効率よく実現するためのスカラー倍演算装置、スカラー倍演算方法、スカラー倍演算プログラム、記録媒体に関する。
【背景技術】
【０００２】
楕円曲線暗号や署名の演算コストにおいて、群の元Ｇをスカラー倍する演算は大きな割合を占める。本明細書では、複数のスカラー倍を同時に行う場合に効率良く演算する方法について述べる。乗法群のべき乗でも同じ議論を適用できるが、本明細書では記述をスカラー倍に統一する。群の元Ｇに対して入力されたＭ個の整数Ｅ１，…，ＥＭについてＥ１Ｇ，…，ＥＭＧを求める演算を同時スカラー倍という。同時スカラー倍を効率良く実行するためには、２種類の戦略が考えられる。一つは、事前にＧに関する事前演算を行いストレージに保存しておく方法がある。十分な量のストレージがある場合にはこの方法の効果が高い。もう一つは、事前の計算を必要としない方法である。本明細書では後者の方式について検討を行う。
【０００３】
事前演算なしでスカラー倍を行う方式としては、スカラー値を二進展開して２倍演算と加算を行う方法（二進演算法）や、非特許文献１のＮＡＦ法や、非特許文献２のＢｏｏｔｈ法がある。これに対して複数のスカラー倍を同時に行うことで効率を向上した方式（非特許文献３，４，５など）が提案されてきた。
図１は、二進演算法の処理フローを示す図である。この処理フローでは、Ｍを２以上の整数、ｍを１以上Ｍ以下の整数、Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｇを群の元、Ｅ１，…，ＥＭを
【０００４】
【数１】
【０００５】
のように表現されるスカラーとし、元Ｇをスカラー倍した値Ｅ１Ｇ，…，ＥＭＧを求める。二進演算法では、Ｅｍがランダムな値の場合、二進演算法のコストは２倍演算がＭＮ回、加算演算が（１／２）ＭＮ回である。
【０００６】
また、楕円曲線上の点など、−１倍を行うのが容易な群でスカラー倍演算を行う場合、符号つき二進法（ＮＡＦ法：非特許文献１）が用いられることが多い。二進演算法は、２倍演算Ｎ回と加算演算Ｎ／２回で１つのスカラー倍演算を行うのに対し、符号つき二進法では、２倍演算Ｎ回と加算演算Ｎ／３回で１つのスカラー倍演算が行える。したがって、Ｍ個のスカラー倍演算では、２倍演算がＭＮ回、加算演算がＭＮ／３回である。
【０００７】
次に、非特許文献３の鶴岡法について説明する。最初に、入力されるスカラー値の数が２つの場合について説明する。Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｅ１，Ｅ２を
【０００８】
【数２】
【０００９】
と表現されるスカラー、Ｇを群の元とする。そして、
Ｈ１，１＝Ｅ１∧Ｅ２
Ｈ１，０＝Ｅ１−Ｅ１，１
Ｈ０，１＝Ｅ２−Ｅ１，１
のように中間値Ｈ１，１、Ｈ１，０、Ｈ０，１を求める。ただし、Ｅ１∧Ｅ２は、二進表現のＥ１とＥ２を各桁のビットごとに論理積を行うことをあらわす。Ｅ１、Ｅ２のｎビット目は、上記のようにｈ１（ｎ）、ｈ２（ｎ）のように表現できる。Ｈ１，１、Ｈ１，０、Ｈ０，１のｎビット目をｈ１，１（ｎ）、ｈ１，０（ｎ）、ｈ０，１（ｎ）と表現すると、ｈ１（ｎ）、ｈ２（ｎ）とｈ１，１（ｎ）、ｈ１，０（ｎ）、ｈ０，１（ｎ）の関係は、図２のようになる。
【００１０】
Ｅ１とＥ２が無相関であれば、Ｈ１，１、Ｈ１，０、Ｈ０，１のハミング重みは平均Ｎ／４であり、Ｈ１，１Ｇ、Ｈ１，０Ｇ、Ｈ０，１Ｇを、二進演算法を用いて同時に求める計算量は２倍演算がＮ回、加算が平均（３／４）Ｎ回となる。これらを用いてＥ１Ｇ、Ｅ２Ｇを以下のように求める。
Ｅ１Ｇ＝Ｈ１，０Ｇ＋Ｈ１，１Ｇ
Ｅ２Ｇ＝Ｈ０，１Ｇ＋Ｈ１，１Ｇ
この方法でＥ１Ｇ、Ｅ２Ｇを求めれば（Ｍ＝２の場合）、加算回数は（３／４）Ｎ＋２回となり、二進演算法の加算回数Ｎ回よりも少ない。したがって、鶴岡法の方が二進演算法よりも高速である。
【００１１】
図３に、鶴岡法でＭ個の同時スカラー倍を行なう場合の処理フローを示す。アルゴリズム中では記述の簡略化のため、中間値Ｈｄ（１），…，ｄ（Ｍ）をＢｋ、中間値Ｈｄ（１），…，ｄ（Ｍ）のｎビット目ｈｄ（１），…，ｄ（Ｍ）（ｎ）をｂｋ（ｎ）（ただし、１≦ｋ≦２Ｍ−１）と表しており、
【００１２】
【数３】
【００１３】
の関係がある。例えば、Ｍ＝２の場合は、ｂ１（ｎ）＝ｈ１，０（ｎ）、ｂ２（ｎ）＝ｈ０，１（ｎ）、ｂ３（ｎ）＝ｈ１，１（ｎ）である。なお、ｎ＝１〜Ｎのｂｋ（ｎ）を求めることはＢｋを求めることなので、ｂｋ（ｎ）も中間値と呼ぶこととする。
【００１４】
鶴岡法の場合、２倍演算がＭＮ回、加算演算が（１−（１／２）Ｍ）Ｎ＋α回である。なお、図３の方法をそのまま行うとα＝ｍ・２Ｍ−１であるが、非特許文献５の方法を用いることで、α＝２Ｍ＋１−２Ｍ−２回にできる。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography. CRC Pres, 1996.
【非特許文献２】Andrew D. Booth, ”A Signed Binary Multiplication Technique”, The Quarterly Journal of Mechanics and Applied Mathematics 1951 4(2),p.236-240, 1951.
【非特許文献３】鶴岡行雄, ”高速な多垂べき乗計算アルゴリズム”, Extended Abstract for JW-ISC’93, 電子情報通信学会技術研究報告. ISEC, 情報セキュリティ93(295), pp.103-111, 1993.
【非特許文献４】David M'Ra:ichi and David Naccache, ”Batch Exponentiation: A Fast DLP-based Signature Generation Strategy”, CCS ’96, Proceedings of the 3rd ACM Conference on Computer and Communications Security, March 14-16 1996, New Delhi, India, ACM, 1996.
【非特許文献５】Byungchun Chung, Junbeom Hur, Heeyoul Kim, Seong-Min Hong and Hyunsoo Yoon, ”Improved batch exponentiation”, Information Processing Letters 109 (2009) 832-837.
【発明の概要】
【発明が解決しようとする課題】
【００１６】
非特許文献３，４，５の方式も二進法に基づくもので、Ｍ＝２の場合にはＮＡＦ法（非特許文献１）よりも効率が悪いという欠点があった。本発明の目的は、非特許文献３の鶴岡法の概念を拡張し、符号付き二進法に適用できる同時スカラー倍演算法を実現することである。
【課題を解決するための手段】
【００１７】
本発明のスカラー倍演算装置は、Ｍを２以上の整数、ｍを１以上Ｍ以下の整数、Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｅ１，…，ＥＭを
【００１８】
【数４】
【００１９】
と表現されるスカラー、Ｇを群の元とし、元Ｇに対してスカラーＥ１，…，ＥＭをそれぞれ乗算した値であるスカラー倍値Ｅ１Ｇ，…，ＥＭＧを求める。本発明のスカラー倍演算装置は、中間値計算部、元計算部、スカラー倍値計算部を備える。中間値計算部は、ｄ（ｍ）∈｛０，１，−１｝として、
すべてのｍについてｄ（ｍ）＝ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝１
すべてのｍについてｄ（ｍ）＝−ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝−１
その他のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝０
である中間値ｅｄ（１），…，ｄ（Ｍ）（ｎ）を、ｄ（１）＝０，…，ｄ（Ｍ）＝０以外のすべてのｄ（１），…，ｄ（Ｍ）の組合せ（ただし、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つｅｄ（１），…，ｄ（Ｍ）（ｎ）とｅｄ’（１），…，ｄ’（Ｍ）（ｎ）はいずれか一方のみ）について求める。ｄ（１）＝０，…，ｄ（Ｍ）＝０の場合を求める必要がないのは、以降の計算で利用しないからである。また、ただし書きの理由は、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つときは、ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝（−１）×ｅｄ’（１），…，ｄ’（Ｍ）（ｎ）の関係が成り立つため、両方を求める必要がないからである。元計算部は、中間値計算部で求めたｄ（１），…，ｄ（Ｍ）の組合せのすべてについて、
【００２０】
【数５】
【００２１】
を求める。スカラー倍値計算部は、ｄ（ｍ）の値が１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和から、ｄ（ｍ）の値が−１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和を減算した値をスカラー倍値ＥｍＧとする処理を、ｍ＝１からＭに対して行う。
【発明の効果】
【００２２】
本発明のスカラー倍演算装置によれば、符号付き二進法に同時スカラー倍演算の考え方を適用できるので、群の元に複数のスカラー値をそれぞれ乗算するような場合に、従来技術に比べ演算量を少なくできる。
【図面の簡単な説明】
【００２３】
【図１】二進演算法の処理フローを示す図。
【図２】鶴岡法でのｎビット目の変換を示す図。
【図３】鶴岡法でＭ個の同時スカラー倍を行なう場合の処理フローを示す図。
【図４】本発明のスカラー倍演算装置の機能構成例を示す図。
【図５】本発明のスカラー倍演算装置の処理フローを示す図。
【図６】Ｍ＝２の場合のスカラーＥ１、Ｅ２のｎビット目ｅ１（ｎ）、ｅ２（ｎ）と、求めなければならない中間値ｅｄ（１），ｄ（２）（ｎ）の関係を示す図。
【図７】Ｍ＝２の場合のスカラーＥ１、Ｅ２のｎビット目ｅ１（ｎ）、ｅ２（ｎ）と、中間値ｅｄ（１），ｄ（２）（ｎ）の関係を示す図。
【図８】Ｍ＝３の場合のスカラーＥ１、Ｅ２、Ｅ３のｎビット目ｅ１（ｎ）、ｅ２（ｎ）、ｅ３（ｎ）と、求めなければならない中間値ｅｄ（１），ｄ（２），ｄ（３）（ｎ）の関係を示す図。
【図９】Ｍ＝３の場合のスカラーＥ１、Ｅ２、Ｅ３のｎビット目ｅ１（ｎ）、ｅ２（ｎ）、ｅ３（ｎ）と、中間値ｅｄ（１），ｄ（２），ｄ（３）（ｎ）の関係を示す１つ目の図。
【図１０】Ｍ＝３の場合のスカラーＥ１、Ｅ２、Ｅ３のｎビット目ｅ１（ｎ）、ｅ２（ｎ）、ｅ３（ｎ）と、中間値ｅｄ（１），ｄ（２），ｄ（３）（ｎ）の関係を示す２つ目の図。
【図１１】本発明のスカラー倍演算装置の詳細な処理フローの例を示す図。
【図１２】ＮＡＦ法によって二進法表現のスカラーＥｍを符号つき二進法表現のスカラーＥｍに変換するフローを示す図。
【図１３】二進法表現された０〜８とＮＡＦ法によって符号つき二進法表現に変換された０〜８を示す図。
【図１４】Ｂｏｏｔｈ法によって二進法表現のスカラーＥｍを符号つき二進法表現のスカラーＥｍに変換するフローを示す図。
【図１５】二進法表現された２ｎ−２桁〜２ｎ桁と、Ｂｏｏｔｈ法によって符号つき二進法表現に変換された２ｎ−１桁、２ｎ桁との関係を示す図。
【図１６】Ｍ個のＮ桁のスカラーを群の元に乗算する場合の各方式の演算量を比較するための図。
【発明を実施するための形態】
【００２４】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００２５】
装置構成、処理フロー
図４に本発明のスカラー倍演算装置の機能構成例を、図５に本発明のスカラー倍演算装置の処理フローを示す。本発明のスカラー倍演算装置１００は、Ｍを２以上の整数、ｍを１以上Ｍ以下の整数、Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｅ１，…，ＥＭを
【００２６】
【数６】
【００２７】
と表現されるスカラー、Ｇを群の元とし、元Ｇに対してスカラーＥ１，…，ＥＭをそれぞれ乗算した値であるスカラー倍値Ｅ１Ｇ，…，ＥＭＧを求める。スカラー倍演算装置１００は、中間値計算部１２０、元計算部１３０、スカラー倍値計算部１４０、記録部１９０を備える。中間値計算部１２０は、ｄ（ｍ）∈｛０，１，−１｝として、
すべてのｍについてｄ（ｍ）＝ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝１
すべてのｍについてｄ（ｍ）＝−ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝−１
その他のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝０
である中間値ｅｄ（１），…，ｄ（Ｍ）（ｎ）を、ｄ（１）＝０，…，ｄ（Ｍ）＝０以外のすべてのｄ（１），…，ｄ（Ｍ）の組合せ（ただし、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つｅｄ（１），…，ｄ（Ｍ）（ｎ）とｅｄ’（１），…，ｄ’（Ｍ）（ｎ）はいずれか一方のみ）について求める（Ｓ１２０）。ｄ（１）＝０，…，ｄ（Ｍ）＝０の場合を求める必要がないのは、以降の計算で利用しないからである。また、ただし書きの理由は、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つときは、ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝（−１）×ｅｄ’（１），…，ｄ’（Ｍ）（ｎ）の関係が成り立つため、両方を求める必要がないからである。したがって、中間値の数は（３Ｍ−１）／２個となる。また、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つ組合せのうちどちらを求めてもかまわない。
【００２８】
元計算部１３０は、中間値計算部１２０で求めたｄ（１），…，ｄ（Ｍ）の組合せのすべてについて、
【００２９】
【数７】
【００３０】
を求める（Ｓ１３０）。スカラー倍値計算部１４０は、ｄ（ｍ）の値が１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和から、ｄ（ｍ）の値が−１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和を減算した値をスカラー倍値ＥｍＧとする処理を、ｍ＝１からＭに対して行う（Ｓ１４０）。式で表現すると、
【００３１】
【数８】
【００３２】
のようになる。記録部１９０は、元Ｇ、スカラーＥｍ、中間値ｅｄ（１），…，ｄ（Ｍ）（ｎ）、Ｅｄ（１），…，ｄ（Ｍ）Ｇ、スカラー倍値ＥｍＧなどを記録する。
また、スカラー倍演算装置１００は、スカラー倍演算装置１００に入力されるスカラーが二進法表現の場合には表現変換部１１０を備えればよい。表現変換部１１０は、
【００３３】
【数９】
【００３４】
のように表現されるスカラーＥ１，…，ＥＭ（二進法表現のスカラー）を、
【００３５】
【数１０】
【００３６】
のように表現されるスカラーＥ１，…，ＥＭ（符号つき二進法表現のスカラー）に変換する（Ｓ１１０）。具体的な変換方法としては、ＮＡＦ法やＢｏｏｔｈ法などがある。
原理の説明
まず、Ｍ＝２の場合について説明する。図６にＭ＝２の場合のスカラーＥ１、Ｅ２のｎビット目ｅ１（ｎ）、ｅ２（ｎ）と、求めなければならない中間値ｅｄ（１），ｄ（２）（ｎ）の関係を示す。また、図７にＭ＝２の場合のスカラーＥ１、Ｅ２のｎビット目ｅ１（ｎ）、ｅ２（ｎ）と、中間値ｅｄ（１），ｄ（２）（ｎ）の関係を示す。
【００３７】
スカラーＥ１、Ｅ２のｎビット目ｅ１（ｎ）、ｅ２（ｎ）の値が０の場合、どんな乗算を行っても結果は０である。したがって、ｅ１（ｎ）、ｅ２（ｎ）の値が０以外の場合について考慮すればスカラー倍演算を実行できる。二進法の場合であれば０以外の値は１のみである。したがって、鶴岡法ではｈ１，０（ｎ）、ｈ０，１（ｎ）、ｈ１，１（ｎ）について考慮すればよかった。一方、本発明が採用した符号つき二進法の場合、０以外の値には１と−１がある。そこで、図６に示すように、ｅ１（ｎ）、ｅ２（ｎ）の値が１または−１の場合について中間値を求める。中間値として考えられる組合せは、ｅ１，１（ｎ）、ｅ１，０（ｎ）、ｅ１，−１（ｎ）、ｅ０，１（ｎ）、ｅ０，０（ｎ）、ｅ０，−１（ｎ）、ｅ−１，１（ｎ）、ｅ−１，０（ｎ）、ｅ−１，−１（ｎ）である。しかし、ｅ０，０（ｎ）はｅ１（ｎ）＝０、ｅ２（ｎ）＝０なので乗算で考慮する必要がない。また、ｅ１，１（ｎ）＝−ｅ−１，−１（ｎ）、ｅ１，０（ｎ）＝ｅ−１，０（ｎ）、ｅ１，−１（ｎ）＝ｅ−１，１（ｎ）、ｅ０，１（ｎ）＝ｅ０，−１（ｎ）の関係が成り立つので、一方を求めれば他方を求める必要はない。したがって、図６にしめした４つの中間値を求めれば十分である。なお、図６では、ｅ１，１（ｎ）、ｅ１，０（ｎ）、ｅ１，−１（ｎ）、ｅ０，１（ｎ）の４つを選択しているが、ｄ’（１）＝（−１）×ｄ（１）かつｄ’（２）＝（−１）×ｄ（２）が成り立つ他方を選択してもよい。
【００３８】
ｅ１（ｎ）、ｅ２（ｎ）と中間値ｅｄ（１），ｄ（２）（ｎ）との関係は図７に示したとおり、
ｄ（１）＝ｅ１（ｎ）かつｄ（２）＝ｅ２（ｎ）のときは
ｅｄ（１），ｄ（２）（ｎ）＝１
ｄ（１）＝−ｅ１（ｎ）かつｄ（２）＝−ｅ２（ｎ）のときは
ｅｄ（１），ｄ（２）（ｎ）＝−１
その他のときは
ｅｄ（１），ｄ（２）（ｎ）＝０
である。
【００３９】
図７から分かるように、ｅ１（ｎ）とｅ２（ｎ）の列では２／３が０以外である。一方、ｅ１，１（ｎ）、ｅ１，０（ｎ）、ｅ１，−１（ｎ）、ｅ０，１（ｎ）の列では、それぞれ２つのみ（２／９のみ）が０以外である。したがって、実際に乗算を行わなければならない部分が少なくなる。これらのことから、Ｍ＝２の場合には、ＮＡＦ法の加算回数は平均２／３Ｎ回なのに対し、ＮＡＦ法に本発明を適用した場合は加算回数は平均（５／９）Ｎ＋４回であり、（１／９）Ｎ−４回の加算を削減ができる。
【００４０】
図８にＭ＝３の場合のスカラーＥ１、Ｅ２、Ｅ３のｎビット目ｅ１（ｎ）、ｅ２（ｎ）、ｅ３（ｎ）と、求めなければならない中間値ｅｄ（１），ｄ（２），ｄ（３）（ｎ）の関係を示す。上述のように、求めなければならない中間値ｅｄ（１），ｄ（２），ｄ（３）（ｎ）の数は（３Ｍ−１）／２個なので、Ｍ＝３の場合には１３個である。図９、１０にＭ＝３の場合のスカラーＥ１、Ｅ２、Ｅ３のｎビット目ｅ１（ｎ）、ｅ２（ｎ）、ｅ３（ｎ）と、中間値ｅｄ（１），ｄ（２），ｄ（３）（ｎ）の関係を示す。この例でも、ｅ１（ｎ）、ｅ２（ｎ）、ｅ３（ｎ）の列では２／３が０以外である。一方、中間値ｅｄ（１），ｄ（２），ｄ（３）（ｎ）の列では、それぞれ２つのみ（２／２７のみ）が０以外である。したがって、計算回数を削減できる。同様にＭ＞３の場合にも中間値ｅｄ（１），…，ｄ（Ｍ）（ｎ）を利用することで、計算回数を削減できる。
【００４１】
詳細な処理フロー（アルゴリズムの具体例）
本発明のスカラー倍演算装置の詳細な処理フローの例を図１１に示す。図１１のＳｔｅｐ１、Ｓｔｅｐ２は前処理であり、各変数を初期値に設定している。Ｓｔｅｐ３は図５のＳ１２０に、Ｓｔｅｐ４はＳ１３０に、Ｓｔｅｐ５はＳ１４０に相当する。Ｓｔｅｐ６は結果を出力する処理である。
【００４２】
Ｓｔｅｐ３、Ｓｔｅｐ４、Ｓｔｅｐ５では、記述の簡略化のため、中間値Ｅｄ（１），…，ｄ（Ｍ）をＢｋ、中間値Ｅｄ（１），…，ｄ（Ｍ）のｎビット目ｅｄ（１），…，ｄ（Ｍ）（ｎ）をｂｋ（ｎ）（ただし、１≦ｋ≦２Ｍ−１）と表しており、
【００４３】
【数１１】
【００４４】
の関係がある。例えば、Ｍ＝２の場合は、ｂ１（ｎ）＝ｅ１，０（ｎ）、ｂ−１（ｎ）＝ｅ−１，０（ｎ）、ｂ３（ｎ）＝ｅ０，１（ｎ）、ｂ−３（ｎ）＝ｅ０，−１（ｎ）、ｂ４（ｎ）＝ｈ１，１（ｎ）、ｂ−２（ｎ）＝ｈ１，−１（ｎ）、ｂ２（ｎ）＝ｈ−１，１（ｎ）、ｂ−４（ｎ）＝ｈ−１，−１（ｎ）である。なお、ｎ＝１〜Ｎのｂｋ（ｎ）を求めることはＢｋを求めることなので、ｂｋ（ｎ）も中間値と呼ぶ。このようにｋとｄ（１），…，ｄ（Ｍ）の関係を決めているので、ｋを１から（３Ｍ−１）／２まで変化させれば、ｄ（１）＝０，…，ｄ（Ｍ）＝０以外のすべてのｄ（１），…，ｄ（Ｍ）の組合せ（ただし、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つｅｄ（１），…，ｄ（Ｍ）（ｎ）とｅｄ’（１），…，ｄ’（Ｍ）（ｎ）はいずれか一方のみ）について演算したことになる。
【００４５】
図１２はＮＡＦ法によって二進法表現のスカラーＥｍを符号つき二進法表現のスカラーＥｍに変換するフローを、図１３は二進法表現された０〜８とＮＡＦ法によって符号つき二進法表現に変換された０〜８を示す。また、図１４はＢｏｏｔｈ法によって二進法表現のスカラーＥｍを符号つき二進法表現のスカラーＥｍに変換するフローを、図１５は二進法表現された２ｎ−２桁〜２ｎ桁と、Ｂｏｏｔｈ法によって符号つき二進法表現に変換された２ｎ−１桁、２ｎ桁との関係を示す。ＮＡＦ法は、符号付き二進法表現のスカラーの各桁の０の確率を２／３、１または−１の確率を１／３にする方法である。また、Ｂｏｏｔｈ法は、符号付き二進法表現のスカラーの各桁の０の確率を５／８、１または−１の確率を３／８（奇数桁は０の確率が１／２、偶数桁は０の確率が３／４）にする方法である。本発明はＮＡＦ法やＢｏｏｔｈ法以外にも任意の符号つき二進法と組み合わせることができる。
【００４６】
演算量の比較
図１６は、Ｍ個のＮ桁のスカラーを群の元に乗算する場合の各方式の演算量を比較するための図である。どの方式も２倍演算はＭＮ回なので、図１６では加算回数のみを比較している。ただし、α＝２Ｍ＋１−２Ｍ−２、β＝３Ｍ−２Ｍ−１である。なお、符号付き二進法によって１つのスカラー倍を計算する場合にはＮＡＦ法のほうがＢｏｏｔｈ法よりも効率が良いが、同時スカラー倍の場合は逆転する場合がある。具体的には、Ｍ≧５の場合にはＢｏｏｔｈ法の方がＮＡＦ法よりも効率がよい。この例と同じように、単独での効率にかかわらず本発明と組み合わせることで効率がよくなる場合もあるので、適宜符号つき二進法を選定すればよい。
【００４７】
例えば、Ｍ＝２の場合、本発明＋ＮＡＦ法は、従来のＮＡＦ法（ＮＡＦ法単独）に比べ１１％の高速化が図れる。このように、本発明は、非特許文献３の鶴岡法の概念を拡張し、符号付き二進法に適用できる同時スカラー倍演算法を実現している。そして、Ｍ＝２の場合も含め、演算回数を削減できている。
【００４８】
プログラム、記録媒体
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４９】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５１】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００５２】
本発明は、群の元に対して複数のスカラー倍を同時に行うようなデータを暗号化する装置や認証する装置に利用できる。
【符号の説明】
【００５３】
１００ スカラー倍演算装置
１１０ 表現変換部
１２０ 中間値計算部
１３０ 元計算部
１４０ スカラー倍値計算部
１９０ 記録部
【技術分野】
【０００１】
本発明は、データを暗号化する装置や認証する装置にかかわり、特に情報セキュリティを効率よく実現するためのスカラー倍演算装置、スカラー倍演算方法、スカラー倍演算プログラム、記録媒体に関する。
【背景技術】
【０００２】
楕円曲線暗号や署名の演算コストにおいて、群の元Ｇをスカラー倍する演算は大きな割合を占める。本明細書では、複数のスカラー倍を同時に行う場合に効率良く演算する方法について述べる。乗法群のべき乗でも同じ議論を適用できるが、本明細書では記述をスカラー倍に統一する。群の元Ｇに対して入力されたＭ個の整数Ｅ１，…，ＥＭについてＥ１Ｇ，…，ＥＭＧを求める演算を同時スカラー倍という。同時スカラー倍を効率良く実行するためには、２種類の戦略が考えられる。一つは、事前にＧに関する事前演算を行いストレージに保存しておく方法がある。十分な量のストレージがある場合にはこの方法の効果が高い。もう一つは、事前の計算を必要としない方法である。本明細書では後者の方式について検討を行う。
【０００３】
事前演算なしでスカラー倍を行う方式としては、スカラー値を二進展開して２倍演算と加算を行う方法（二進演算法）や、非特許文献１のＮＡＦ法や、非特許文献２のＢｏｏｔｈ法がある。これに対して複数のスカラー倍を同時に行うことで効率を向上した方式（非特許文献３，４，５など）が提案されてきた。
図１は、二進演算法の処理フローを示す図である。この処理フローでは、Ｍを２以上の整数、ｍを１以上Ｍ以下の整数、Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｇを群の元、Ｅ１，…，ＥＭを
【０００４】
【数１】
【０００５】
のように表現されるスカラーとし、元Ｇをスカラー倍した値Ｅ１Ｇ，…，ＥＭＧを求める。二進演算法では、Ｅｍがランダムな値の場合、二進演算法のコストは２倍演算がＭＮ回、加算演算が（１／２）ＭＮ回である。
【０００６】
また、楕円曲線上の点など、−１倍を行うのが容易な群でスカラー倍演算を行う場合、符号つき二進法（ＮＡＦ法：非特許文献１）が用いられることが多い。二進演算法は、２倍演算Ｎ回と加算演算Ｎ／２回で１つのスカラー倍演算を行うのに対し、符号つき二進法では、２倍演算Ｎ回と加算演算Ｎ／３回で１つのスカラー倍演算が行える。したがって、Ｍ個のスカラー倍演算では、２倍演算がＭＮ回、加算演算がＭＮ／３回である。
【０００７】
次に、非特許文献３の鶴岡法について説明する。最初に、入力されるスカラー値の数が２つの場合について説明する。Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｅ１，Ｅ２を
【０００８】
【数２】
【０００９】
と表現されるスカラー、Ｇを群の元とする。そして、
Ｈ１，１＝Ｅ１∧Ｅ２
Ｈ１，０＝Ｅ１−Ｅ１，１
Ｈ０，１＝Ｅ２−Ｅ１，１
のように中間値Ｈ１，１、Ｈ１，０、Ｈ０，１を求める。ただし、Ｅ１∧Ｅ２は、二進表現のＥ１とＥ２を各桁のビットごとに論理積を行うことをあらわす。Ｅ１、Ｅ２のｎビット目は、上記のようにｈ１（ｎ）、ｈ２（ｎ）のように表現できる。Ｈ１，１、Ｈ１，０、Ｈ０，１のｎビット目をｈ１，１（ｎ）、ｈ１，０（ｎ）、ｈ０，１（ｎ）と表現すると、ｈ１（ｎ）、ｈ２（ｎ）とｈ１，１（ｎ）、ｈ１，０（ｎ）、ｈ０，１（ｎ）の関係は、図２のようになる。
【００１０】
Ｅ１とＥ２が無相関であれば、Ｈ１，１、Ｈ１，０、Ｈ０，１のハミング重みは平均Ｎ／４であり、Ｈ１，１Ｇ、Ｈ１，０Ｇ、Ｈ０，１Ｇを、二進演算法を用いて同時に求める計算量は２倍演算がＮ回、加算が平均（３／４）Ｎ回となる。これらを用いてＥ１Ｇ、Ｅ２Ｇを以下のように求める。
Ｅ１Ｇ＝Ｈ１，０Ｇ＋Ｈ１，１Ｇ
Ｅ２Ｇ＝Ｈ０，１Ｇ＋Ｈ１，１Ｇ
この方法でＥ１Ｇ、Ｅ２Ｇを求めれば（Ｍ＝２の場合）、加算回数は（３／４）Ｎ＋２回となり、二進演算法の加算回数Ｎ回よりも少ない。したがって、鶴岡法の方が二進演算法よりも高速である。
【００１１】
図３に、鶴岡法でＭ個の同時スカラー倍を行なう場合の処理フローを示す。アルゴリズム中では記述の簡略化のため、中間値Ｈｄ（１），…，ｄ（Ｍ）をＢｋ、中間値Ｈｄ（１），…，ｄ（Ｍ）のｎビット目ｈｄ（１），…，ｄ（Ｍ）（ｎ）をｂｋ（ｎ）（ただし、１≦ｋ≦２Ｍ−１）と表しており、
【００１２】
【数３】
【００１３】
の関係がある。例えば、Ｍ＝２の場合は、ｂ１（ｎ）＝ｈ１，０（ｎ）、ｂ２（ｎ）＝ｈ０，１（ｎ）、ｂ３（ｎ）＝ｈ１，１（ｎ）である。なお、ｎ＝１〜Ｎのｂｋ（ｎ）を求めることはＢｋを求めることなので、ｂｋ（ｎ）も中間値と呼ぶこととする。
【００１４】
鶴岡法の場合、２倍演算がＭＮ回、加算演算が（１−（１／２）Ｍ）Ｎ＋α回である。なお、図３の方法をそのまま行うとα＝ｍ・２Ｍ−１であるが、非特許文献５の方法を用いることで、α＝２Ｍ＋１−２Ｍ−２回にできる。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography. CRC Pres, 1996.
【非特許文献２】Andrew D. Booth, ”A Signed Binary Multiplication Technique”, The Quarterly Journal of Mechanics and Applied Mathematics 1951 4(2),p.236-240, 1951.
【非特許文献３】鶴岡行雄, ”高速な多垂べき乗計算アルゴリズム”, Extended Abstract for JW-ISC’93, 電子情報通信学会技術研究報告. ISEC, 情報セキュリティ93(295), pp.103-111, 1993.
【非特許文献４】David M'Ra:ichi and David Naccache, ”Batch Exponentiation: A Fast DLP-based Signature Generation Strategy”, CCS ’96, Proceedings of the 3rd ACM Conference on Computer and Communications Security, March 14-16 1996, New Delhi, India, ACM, 1996.
【非特許文献５】Byungchun Chung, Junbeom Hur, Heeyoul Kim, Seong-Min Hong and Hyunsoo Yoon, ”Improved batch exponentiation”, Information Processing Letters 109 (2009) 832-837.
【発明の概要】
【発明が解決しようとする課題】
【００１６】
非特許文献３，４，５の方式も二進法に基づくもので、Ｍ＝２の場合にはＮＡＦ法（非特許文献１）よりも効率が悪いという欠点があった。本発明の目的は、非特許文献３の鶴岡法の概念を拡張し、符号付き二進法に適用できる同時スカラー倍演算法を実現することである。
【課題を解決するための手段】
【００１７】
本発明のスカラー倍演算装置は、Ｍを２以上の整数、ｍを１以上Ｍ以下の整数、Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｅ１，…，ＥＭを
【００１８】
【数４】
【００１９】
と表現されるスカラー、Ｇを群の元とし、元Ｇに対してスカラーＥ１，…，ＥＭをそれぞれ乗算した値であるスカラー倍値Ｅ１Ｇ，…，ＥＭＧを求める。本発明のスカラー倍演算装置は、中間値計算部、元計算部、スカラー倍値計算部を備える。中間値計算部は、ｄ（ｍ）∈｛０，１，−１｝として、
すべてのｍについてｄ（ｍ）＝ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝１
すべてのｍについてｄ（ｍ）＝−ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝−１
その他のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝０
である中間値ｅｄ（１），…，ｄ（Ｍ）（ｎ）を、ｄ（１）＝０，…，ｄ（Ｍ）＝０以外のすべてのｄ（１），…，ｄ（Ｍ）の組合せ（ただし、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つｅｄ（１），…，ｄ（Ｍ）（ｎ）とｅｄ’（１），…，ｄ’（Ｍ）（ｎ）はいずれか一方のみ）について求める。ｄ（１）＝０，…，ｄ（Ｍ）＝０の場合を求める必要がないのは、以降の計算で利用しないからである。また、ただし書きの理由は、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つときは、ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝（−１）×ｅｄ’（１），…，ｄ’（Ｍ）（ｎ）の関係が成り立つため、両方を求める必要がないからである。元計算部は、中間値計算部で求めたｄ（１），…，ｄ（Ｍ）の組合せのすべてについて、
【００２０】
【数５】
【００２１】
を求める。スカラー倍値計算部は、ｄ（ｍ）の値が１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和から、ｄ（ｍ）の値が−１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和を減算した値をスカラー倍値ＥｍＧとする処理を、ｍ＝１からＭに対して行う。
【発明の効果】
【００２２】
本発明のスカラー倍演算装置によれば、符号付き二進法に同時スカラー倍演算の考え方を適用できるので、群の元に複数のスカラー値をそれぞれ乗算するような場合に、従来技術に比べ演算量を少なくできる。
【図面の簡単な説明】
【００２３】
【図１】二進演算法の処理フローを示す図。
【図２】鶴岡法でのｎビット目の変換を示す図。
【図３】鶴岡法でＭ個の同時スカラー倍を行なう場合の処理フローを示す図。
【図４】本発明のスカラー倍演算装置の機能構成例を示す図。
【図５】本発明のスカラー倍演算装置の処理フローを示す図。
【図６】Ｍ＝２の場合のスカラーＥ１、Ｅ２のｎビット目ｅ１（ｎ）、ｅ２（ｎ）と、求めなければならない中間値ｅｄ（１），ｄ（２）（ｎ）の関係を示す図。
【図７】Ｍ＝２の場合のスカラーＥ１、Ｅ２のｎビット目ｅ１（ｎ）、ｅ２（ｎ）と、中間値ｅｄ（１），ｄ（２）（ｎ）の関係を示す図。
【図８】Ｍ＝３の場合のスカラーＥ１、Ｅ２、Ｅ３のｎビット目ｅ１（ｎ）、ｅ２（ｎ）、ｅ３（ｎ）と、求めなければならない中間値ｅｄ（１），ｄ（２），ｄ（３）（ｎ）の関係を示す図。
【図９】Ｍ＝３の場合のスカラーＥ１、Ｅ２、Ｅ３のｎビット目ｅ１（ｎ）、ｅ２（ｎ）、ｅ３（ｎ）と、中間値ｅｄ（１），ｄ（２），ｄ（３）（ｎ）の関係を示す１つ目の図。
【図１０】Ｍ＝３の場合のスカラーＥ１、Ｅ２、Ｅ３のｎビット目ｅ１（ｎ）、ｅ２（ｎ）、ｅ３（ｎ）と、中間値ｅｄ（１），ｄ（２），ｄ（３）（ｎ）の関係を示す２つ目の図。
【図１１】本発明のスカラー倍演算装置の詳細な処理フローの例を示す図。
【図１２】ＮＡＦ法によって二進法表現のスカラーＥｍを符号つき二進法表現のスカラーＥｍに変換するフローを示す図。
【図１３】二進法表現された０〜８とＮＡＦ法によって符号つき二進法表現に変換された０〜８を示す図。
【図１４】Ｂｏｏｔｈ法によって二進法表現のスカラーＥｍを符号つき二進法表現のスカラーＥｍに変換するフローを示す図。
【図１５】二進法表現された２ｎ−２桁〜２ｎ桁と、Ｂｏｏｔｈ法によって符号つき二進法表現に変換された２ｎ−１桁、２ｎ桁との関係を示す図。
【図１６】Ｍ個のＮ桁のスカラーを群の元に乗算する場合の各方式の演算量を比較するための図。
【発明を実施するための形態】
【００２４】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００２５】
装置構成、処理フロー
図４に本発明のスカラー倍演算装置の機能構成例を、図５に本発明のスカラー倍演算装置の処理フローを示す。本発明のスカラー倍演算装置１００は、Ｍを２以上の整数、ｍを１以上Ｍ以下の整数、Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｅ１，…，ＥＭを
【００２６】
【数６】
【００２７】
と表現されるスカラー、Ｇを群の元とし、元Ｇに対してスカラーＥ１，…，ＥＭをそれぞれ乗算した値であるスカラー倍値Ｅ１Ｇ，…，ＥＭＧを求める。スカラー倍演算装置１００は、中間値計算部１２０、元計算部１３０、スカラー倍値計算部１４０、記録部１９０を備える。中間値計算部１２０は、ｄ（ｍ）∈｛０，１，−１｝として、
すべてのｍについてｄ（ｍ）＝ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝１
すべてのｍについてｄ（ｍ）＝−ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝−１
その他のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝０
である中間値ｅｄ（１），…，ｄ（Ｍ）（ｎ）を、ｄ（１）＝０，…，ｄ（Ｍ）＝０以外のすべてのｄ（１），…，ｄ（Ｍ）の組合せ（ただし、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つｅｄ（１），…，ｄ（Ｍ）（ｎ）とｅｄ’（１），…，ｄ’（Ｍ）（ｎ）はいずれか一方のみ）について求める（Ｓ１２０）。ｄ（１）＝０，…，ｄ（Ｍ）＝０の場合を求める必要がないのは、以降の計算で利用しないからである。また、ただし書きの理由は、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つときは、ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝（−１）×ｅｄ’（１），…，ｄ’（Ｍ）（ｎ）の関係が成り立つため、両方を求める必要がないからである。したがって、中間値の数は（３Ｍ−１）／２個となる。また、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つ組合せのうちどちらを求めてもかまわない。
【００２８】
元計算部１３０は、中間値計算部１２０で求めたｄ（１），…，ｄ（Ｍ）の組合せのすべてについて、
【００２９】
【数７】
【００３０】
を求める（Ｓ１３０）。スカラー倍値計算部１４０は、ｄ（ｍ）の値が１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和から、ｄ（ｍ）の値が−１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和を減算した値をスカラー倍値ＥｍＧとする処理を、ｍ＝１からＭに対して行う（Ｓ１４０）。式で表現すると、
【００３１】
【数８】
【００３２】
のようになる。記録部１９０は、元Ｇ、スカラーＥｍ、中間値ｅｄ（１），…，ｄ（Ｍ）（ｎ）、Ｅｄ（１），…，ｄ（Ｍ）Ｇ、スカラー倍値ＥｍＧなどを記録する。
また、スカラー倍演算装置１００は、スカラー倍演算装置１００に入力されるスカラーが二進法表現の場合には表現変換部１１０を備えればよい。表現変換部１１０は、
【００３３】
【数９】
【００３４】
のように表現されるスカラーＥ１，…，ＥＭ（二進法表現のスカラー）を、
【００３５】
【数１０】
【００３６】
のように表現されるスカラーＥ１，…，ＥＭ（符号つき二進法表現のスカラー）に変換する（Ｓ１１０）。具体的な変換方法としては、ＮＡＦ法やＢｏｏｔｈ法などがある。
原理の説明
まず、Ｍ＝２の場合について説明する。図６にＭ＝２の場合のスカラーＥ１、Ｅ２のｎビット目ｅ１（ｎ）、ｅ２（ｎ）と、求めなければならない中間値ｅｄ（１），ｄ（２）（ｎ）の関係を示す。また、図７にＭ＝２の場合のスカラーＥ１、Ｅ２のｎビット目ｅ１（ｎ）、ｅ２（ｎ）と、中間値ｅｄ（１），ｄ（２）（ｎ）の関係を示す。
【００３７】
スカラーＥ１、Ｅ２のｎビット目ｅ１（ｎ）、ｅ２（ｎ）の値が０の場合、どんな乗算を行っても結果は０である。したがって、ｅ１（ｎ）、ｅ２（ｎ）の値が０以外の場合について考慮すればスカラー倍演算を実行できる。二進法の場合であれば０以外の値は１のみである。したがって、鶴岡法ではｈ１，０（ｎ）、ｈ０，１（ｎ）、ｈ１，１（ｎ）について考慮すればよかった。一方、本発明が採用した符号つき二進法の場合、０以外の値には１と−１がある。そこで、図６に示すように、ｅ１（ｎ）、ｅ２（ｎ）の値が１または−１の場合について中間値を求める。中間値として考えられる組合せは、ｅ１，１（ｎ）、ｅ１，０（ｎ）、ｅ１，−１（ｎ）、ｅ０，１（ｎ）、ｅ０，０（ｎ）、ｅ０，−１（ｎ）、ｅ−１，１（ｎ）、ｅ−１，０（ｎ）、ｅ−１，−１（ｎ）である。しかし、ｅ０，０（ｎ）はｅ１（ｎ）＝０、ｅ２（ｎ）＝０なので乗算で考慮する必要がない。また、ｅ１，１（ｎ）＝−ｅ−１，−１（ｎ）、ｅ１，０（ｎ）＝ｅ−１，０（ｎ）、ｅ１，−１（ｎ）＝ｅ−１，１（ｎ）、ｅ０，１（ｎ）＝ｅ０，−１（ｎ）の関係が成り立つので、一方を求めれば他方を求める必要はない。したがって、図６にしめした４つの中間値を求めれば十分である。なお、図６では、ｅ１，１（ｎ）、ｅ１，０（ｎ）、ｅ１，−１（ｎ）、ｅ０，１（ｎ）の４つを選択しているが、ｄ’（１）＝（−１）×ｄ（１）かつｄ’（２）＝（−１）×ｄ（２）が成り立つ他方を選択してもよい。
【００３８】
ｅ１（ｎ）、ｅ２（ｎ）と中間値ｅｄ（１），ｄ（２）（ｎ）との関係は図７に示したとおり、
ｄ（１）＝ｅ１（ｎ）かつｄ（２）＝ｅ２（ｎ）のときは
ｅｄ（１），ｄ（２）（ｎ）＝１
ｄ（１）＝−ｅ１（ｎ）かつｄ（２）＝−ｅ２（ｎ）のときは
ｅｄ（１），ｄ（２）（ｎ）＝−１
その他のときは
ｅｄ（１），ｄ（２）（ｎ）＝０
である。
【００３９】
図７から分かるように、ｅ１（ｎ）とｅ２（ｎ）の列では２／３が０以外である。一方、ｅ１，１（ｎ）、ｅ１，０（ｎ）、ｅ１，−１（ｎ）、ｅ０，１（ｎ）の列では、それぞれ２つのみ（２／９のみ）が０以外である。したがって、実際に乗算を行わなければならない部分が少なくなる。これらのことから、Ｍ＝２の場合には、ＮＡＦ法の加算回数は平均２／３Ｎ回なのに対し、ＮＡＦ法に本発明を適用した場合は加算回数は平均（５／９）Ｎ＋４回であり、（１／９）Ｎ−４回の加算を削減ができる。
【００４０】
図８にＭ＝３の場合のスカラーＥ１、Ｅ２、Ｅ３のｎビット目ｅ１（ｎ）、ｅ２（ｎ）、ｅ３（ｎ）と、求めなければならない中間値ｅｄ（１），ｄ（２），ｄ（３）（ｎ）の関係を示す。上述のように、求めなければならない中間値ｅｄ（１），ｄ（２），ｄ（３）（ｎ）の数は（３Ｍ−１）／２個なので、Ｍ＝３の場合には１３個である。図９、１０にＭ＝３の場合のスカラーＥ１、Ｅ２、Ｅ３のｎビット目ｅ１（ｎ）、ｅ２（ｎ）、ｅ３（ｎ）と、中間値ｅｄ（１），ｄ（２），ｄ（３）（ｎ）の関係を示す。この例でも、ｅ１（ｎ）、ｅ２（ｎ）、ｅ３（ｎ）の列では２／３が０以外である。一方、中間値ｅｄ（１），ｄ（２），ｄ（３）（ｎ）の列では、それぞれ２つのみ（２／２７のみ）が０以外である。したがって、計算回数を削減できる。同様にＭ＞３の場合にも中間値ｅｄ（１），…，ｄ（Ｍ）（ｎ）を利用することで、計算回数を削減できる。
【００４１】
詳細な処理フロー（アルゴリズムの具体例）
本発明のスカラー倍演算装置の詳細な処理フローの例を図１１に示す。図１１のＳｔｅｐ１、Ｓｔｅｐ２は前処理であり、各変数を初期値に設定している。Ｓｔｅｐ３は図５のＳ１２０に、Ｓｔｅｐ４はＳ１３０に、Ｓｔｅｐ５はＳ１４０に相当する。Ｓｔｅｐ６は結果を出力する処理である。
【００４２】
Ｓｔｅｐ３、Ｓｔｅｐ４、Ｓｔｅｐ５では、記述の簡略化のため、中間値Ｅｄ（１），…，ｄ（Ｍ）をＢｋ、中間値Ｅｄ（１），…，ｄ（Ｍ）のｎビット目ｅｄ（１），…，ｄ（Ｍ）（ｎ）をｂｋ（ｎ）（ただし、１≦ｋ≦２Ｍ−１）と表しており、
【００４３】
【数１１】
【００４４】
の関係がある。例えば、Ｍ＝２の場合は、ｂ１（ｎ）＝ｅ１，０（ｎ）、ｂ−１（ｎ）＝ｅ−１，０（ｎ）、ｂ３（ｎ）＝ｅ０，１（ｎ）、ｂ−３（ｎ）＝ｅ０，−１（ｎ）、ｂ４（ｎ）＝ｈ１，１（ｎ）、ｂ−２（ｎ）＝ｈ１，−１（ｎ）、ｂ２（ｎ）＝ｈ−１，１（ｎ）、ｂ−４（ｎ）＝ｈ−１，−１（ｎ）である。なお、ｎ＝１〜Ｎのｂｋ（ｎ）を求めることはＢｋを求めることなので、ｂｋ（ｎ）も中間値と呼ぶ。このようにｋとｄ（１），…，ｄ（Ｍ）の関係を決めているので、ｋを１から（３Ｍ−１）／２まで変化させれば、ｄ（１）＝０，…，ｄ（Ｍ）＝０以外のすべてのｄ（１），…，ｄ（Ｍ）の組合せ（ただし、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つｅｄ（１），…，ｄ（Ｍ）（ｎ）とｅｄ’（１），…，ｄ’（Ｍ）（ｎ）はいずれか一方のみ）について演算したことになる。
【００４５】
図１２はＮＡＦ法によって二進法表現のスカラーＥｍを符号つき二進法表現のスカラーＥｍに変換するフローを、図１３は二進法表現された０〜８とＮＡＦ法によって符号つき二進法表現に変換された０〜８を示す。また、図１４はＢｏｏｔｈ法によって二進法表現のスカラーＥｍを符号つき二進法表現のスカラーＥｍに変換するフローを、図１５は二進法表現された２ｎ−２桁〜２ｎ桁と、Ｂｏｏｔｈ法によって符号つき二進法表現に変換された２ｎ−１桁、２ｎ桁との関係を示す。ＮＡＦ法は、符号付き二進法表現のスカラーの各桁の０の確率を２／３、１または−１の確率を１／３にする方法である。また、Ｂｏｏｔｈ法は、符号付き二進法表現のスカラーの各桁の０の確率を５／８、１または−１の確率を３／８（奇数桁は０の確率が１／２、偶数桁は０の確率が３／４）にする方法である。本発明はＮＡＦ法やＢｏｏｔｈ法以外にも任意の符号つき二進法と組み合わせることができる。
【００４６】
演算量の比較
図１６は、Ｍ個のＮ桁のスカラーを群の元に乗算する場合の各方式の演算量を比較するための図である。どの方式も２倍演算はＭＮ回なので、図１６では加算回数のみを比較している。ただし、α＝２Ｍ＋１−２Ｍ−２、β＝３Ｍ−２Ｍ−１である。なお、符号付き二進法によって１つのスカラー倍を計算する場合にはＮＡＦ法のほうがＢｏｏｔｈ法よりも効率が良いが、同時スカラー倍の場合は逆転する場合がある。具体的には、Ｍ≧５の場合にはＢｏｏｔｈ法の方がＮＡＦ法よりも効率がよい。この例と同じように、単独での効率にかかわらず本発明と組み合わせることで効率がよくなる場合もあるので、適宜符号つき二進法を選定すればよい。
【００４７】
例えば、Ｍ＝２の場合、本発明＋ＮＡＦ法は、従来のＮＡＦ法（ＮＡＦ法単独）に比べ１１％の高速化が図れる。このように、本発明は、非特許文献３の鶴岡法の概念を拡張し、符号付き二進法に適用できる同時スカラー倍演算法を実現している。そして、Ｍ＝２の場合も含め、演算回数を削減できている。
【００４８】
プログラム、記録媒体
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４９】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５１】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００５２】
本発明は、群の元に対して複数のスカラー倍を同時に行うようなデータを暗号化する装置や認証する装置に利用できる。
【符号の説明】
【００５３】
１００ スカラー倍演算装置
１１０ 表現変換部
１２０ 中間値計算部
１３０ 元計算部
１４０ スカラー倍値計算部
１９０ 記録部
【特許請求の範囲】
【請求項１】
Ｍを２以上の整数、ｍを１以上Ｍ以下の整数、Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｅ１，…，ＥＭを
【数１２】
と表現されるスカラー、Ｇを群の元とし、元Ｇに対してスカラーＥ１，…，ＥＭをそれぞれ乗算した値であるスカラー倍値Ｅ１Ｇ，…，ＥＭＧを求めるスカラー倍演算装置であって、
ｄ（ｍ）∈｛０，１，−１｝として、
すべてのｍについてｄ（ｍ）＝ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝１
すべてのｍについてｄ（ｍ）＝−ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝−１
その他のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝０
である中間値ｅｄ（１），…，ｄ（Ｍ）（ｎ）を、
ｄ（１）＝０，…，ｄ（Ｍ）＝０以外のすべてのｄ（１），…，ｄ（Ｍ）の組合せ（ただし、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つｅｄ（１），…，ｄ（Ｍ）（ｎ）とｅｄ’（１），…，ｄ’（Ｍ）（ｎ）はいずれか一方のみ）について求める中間値計算部と、
前記中間値計算部で求めたｄ（１），…，ｄ（Ｍ）の組合せのすべてについて、
【数１３】
を求める元計算部と、
ｄ（ｍ）の値が１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和から、ｄ（ｍ）の値が−１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和を減算した値をスカラー倍値ＥｍＧとする処理を、ｍ＝１からＭに対して行うスカラー倍値計算部と、
を備えるスカラー倍演算装置。
【請求項２】
Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｅ１，Ｅ２を
【数１４】
と表現されるスカラー、Ｇを群の元とし、元Ｇに対してスカラーＥ１，Ｅ２をそれぞれ乗算した値であるスカラー倍値Ｅ１Ｇ，Ｅ２Ｇを求めるスカラー倍演算装置であって、
ｄ（１）∈｛０，１，−１｝、ｄ（２）∈｛０，１，−１｝として、
ｄ（１）＝ｅ１（ｎ）かつｄ（２）＝ｅ２（ｎ）のときは
ｅｄ（１），ｄ（２）（ｎ）＝１
ｄ（１）＝−ｅ１（ｎ）かつｄ（２）＝−ｅ２（ｎ）のときは
ｅｄ（１），ｄ（２）（ｎ）＝−１
その他のときは
ｅｄ（１），ｄ（２）（ｎ）＝０
である中間値ｅｄ（１），ｄ（２）（ｎ）を、
ｄ（１）＝０，ｄ（２）＝０以外のすべてのｄ（１），ｄ（２）の組合せ（ただし、ｄ’（１）＝（−１）×ｄ（１）かつｄ’（２）＝（−１）×ｄ（２）が成り立つｅｄ（１），…，ｄ（Ｍ）（ｎ）とｅｄ’（１），…，ｄ’（Ｍ）（ｎ）はいずれか一方のみ）について求める中間値計算部と、
前記中間値計算部で求めたｄ（１），ｄ（２）の組合せのすべてについて、
【数１５】
を求める元計算部と、
ｄ（ｍ）の値が１であるすべてのＥｄ（１），ｄ（２）Ｇの和から、ｄ（ｍ）の値が−１であるすべてのＥｄ（１），ｄ（２）Ｇの和を減算した値をスカラー倍値ＥｍＧとする処理を、ｍ＝１からＭに対して行うスカラー倍値計算部と、
を備えるスカラー倍演算装置。
【請求項３】
請求項１記載のスカラー倍演算装置であって、
【数１６】
のように表現されるスカラーＥ１，…，ＥＭを、ＮＡＦ法を用いて
【数１７】
のように表現されるスカラーＥ１，…，ＥＭに変換する表現変換部
も備えることを特徴とするスカラー倍演算装置。
【請求項４】
請求項１記載のスカラー倍演算装置であって、
【数１８】
のように表現されるスカラーＥ１，…，ＥＭを、Booth法を用いて
【数１９】
のように表現されるスカラーＥ１，…，ＥＭに変換する表現変換部
も備えることを特徴とするスカラー倍演算装置。
【請求項５】
Ｍを２以上の整数、ｍを１以上Ｍ以下の整数、Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｅ１，…，ＥＭを
【数２０】
と表現されるスカラー、Ｇを群の元とし、元Ｇに対してスカラーＥ１，…，ＥＭをそれぞれ乗算した値であるスカラー倍値Ｅ１Ｇ，…，ＥＭＧを求めるスカラー倍演算方法であって、
中間値計算部が、ｄ（ｍ）∈｛０，１，−１｝として、
すべてのｍについてｄ（ｍ）＝ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝１
すべてのｍについてｄ（ｍ）＝−ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝−１
その他のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝０
である中間値ｅｄ（１），…，ｄ（Ｍ）（ｎ）を、
ｄ（１）＝０，…，ｄ（Ｍ）＝０以外のすべてのｄ（１），…，ｄ（Ｍ）の組合せ（ただし、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つｅｄ（１），…，ｄ（Ｍ）（ｎ）とｅｄ’（１），…，ｄ’（Ｍ）（ｎ）はいずれか一方のみ）について求める中間値計算ステップと、
元計算部が、前記中間値計算ステップで求めたｄ（１），…，ｄ（Ｍ）の組合せのすべてについて、
【数２１】
を求める元計算ステップと、
スカラー倍値計算部が、ｄ（ｍ）の値が１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和から、ｄ（ｍ）の値が−１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和を減算した値をスカラー倍値ＥｍＧとする処理を、ｍ＝１からＭに対して行うスカラー倍値計算ステップと、
を有するスカラー倍演算方法。
【請求項６】
Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｅ１，Ｅ２を
【数２２】
と表現されるスカラー、Ｇを群の元とし、元Ｇに対してスカラーＥ１，Ｅ２をそれぞれ乗算した値であるスカラー倍値Ｅ１Ｇ，Ｅ２Ｇを求めるスカラー倍演算方法であって、
中間値計算部が、ｄ（１）∈｛０，１，−１｝、ｄ（２）∈｛０，１，−１｝として、
ｄ（１）＝ｅ１（ｎ）かつｄ（２）＝ｅ２（ｎ）のときは
ｅｄ（１），ｄ（２）（ｎ）＝１
ｄ（１）＝−ｅ１（ｎ）かつｄ（２）＝−ｅ２（ｎ）のときは
ｅｄ（１），ｄ（２）（ｎ）＝−１
その他のときは
ｅｄ（１），ｄ（２）（ｎ）＝０
である中間値ｅｄ（１），ｄ（２）（ｎ）を、
ｄ（１）＝０，ｄ（２）＝０以外のすべてのｄ（１），ｄ（２）の組合せ（ただし、ｄ’（１）＝（−１）×ｄ（１）かつｄ’（２）＝（−１）×ｄ（２）が成り立つｅｄ（１），…，ｄ（Ｍ）（ｎ）とｅｄ’（１），…，ｄ’（Ｍ）（ｎ）はいずれか一方のみ）について求める中間値計算ステップと、
元計算部が、前記中間値計算ステップで求めたｄ（１），ｄ（２）の組合せのすべてについて、
【数２３】
を求める元計算部と、
スカラー倍値計算部が、ｄ（ｍ）の値が１であるすべてのＥｄ（１），ｄ（２）Ｇの和から、ｄ（ｍ）の値が−１であるすべてのＥｄ（１），ｄ（２）Ｇの和を減算した値をスカラー倍値ＥｍＧとする処理を、ｍ＝１からＭに対して行うスカラー倍値計算ステップと、
を有するスカラー倍演算方法。
【請求項７】
請求項５記載のスカラー倍演算方法であって、
表現変換部が、
【数２４】
のように表現されるスカラーＥ１，…，ＥＭを、ＮＡＦ法を用いて
【数２５】
のように表現されるスカラーＥ１，…，ＥＭに変換する表現変換ステップ
も有することを特徴とするスカラー倍演算方法。
【請求項８】
請求項５記載のスカラー倍演算方法であって、
表現変換部が、
【数２６】
のように表現されるスカラーＥ１，…，ＥＭを、Booth法を用いて
【数２７】
のように表現されるスカラーＥ１，…，ＥＭに変換する表現変換ステップ
も有することを特徴とするスカラー倍演算方法。
【請求項９】
請求項１から４のいずれかに記載のスカラー倍演算装置としてコンピュータを動作させるためのスカラー倍演算プログラム。
【請求項１０】
請求項９記載のスカラー倍演算プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１】
Ｍを２以上の整数、ｍを１以上Ｍ以下の整数、Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｅ１，…，ＥＭを
【数１２】
と表現されるスカラー、Ｇを群の元とし、元Ｇに対してスカラーＥ１，…，ＥＭをそれぞれ乗算した値であるスカラー倍値Ｅ１Ｇ，…，ＥＭＧを求めるスカラー倍演算装置であって、
ｄ（ｍ）∈｛０，１，−１｝として、
すべてのｍについてｄ（ｍ）＝ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝１
すべてのｍについてｄ（ｍ）＝−ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝−１
その他のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝０
である中間値ｅｄ（１），…，ｄ（Ｍ）（ｎ）を、
ｄ（１）＝０，…，ｄ（Ｍ）＝０以外のすべてのｄ（１），…，ｄ（Ｍ）の組合せ（ただし、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つｅｄ（１），…，ｄ（Ｍ）（ｎ）とｅｄ’（１），…，ｄ’（Ｍ）（ｎ）はいずれか一方のみ）について求める中間値計算部と、
前記中間値計算部で求めたｄ（１），…，ｄ（Ｍ）の組合せのすべてについて、
【数１３】
を求める元計算部と、
ｄ（ｍ）の値が１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和から、ｄ（ｍ）の値が−１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和を減算した値をスカラー倍値ＥｍＧとする処理を、ｍ＝１からＭに対して行うスカラー倍値計算部と、
を備えるスカラー倍演算装置。
【請求項２】
Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｅ１，Ｅ２を
【数１４】
と表現されるスカラー、Ｇを群の元とし、元Ｇに対してスカラーＥ１，Ｅ２をそれぞれ乗算した値であるスカラー倍値Ｅ１Ｇ，Ｅ２Ｇを求めるスカラー倍演算装置であって、
ｄ（１）∈｛０，１，−１｝、ｄ（２）∈｛０，１，−１｝として、
ｄ（１）＝ｅ１（ｎ）かつｄ（２）＝ｅ２（ｎ）のときは
ｅｄ（１），ｄ（２）（ｎ）＝１
ｄ（１）＝−ｅ１（ｎ）かつｄ（２）＝−ｅ２（ｎ）のときは
ｅｄ（１），ｄ（２）（ｎ）＝−１
その他のときは
ｅｄ（１），ｄ（２）（ｎ）＝０
である中間値ｅｄ（１），ｄ（２）（ｎ）を、
ｄ（１）＝０，ｄ（２）＝０以外のすべてのｄ（１），ｄ（２）の組合せ（ただし、ｄ’（１）＝（−１）×ｄ（１）かつｄ’（２）＝（−１）×ｄ（２）が成り立つｅｄ（１），…，ｄ（Ｍ）（ｎ）とｅｄ’（１），…，ｄ’（Ｍ）（ｎ）はいずれか一方のみ）について求める中間値計算部と、
前記中間値計算部で求めたｄ（１），ｄ（２）の組合せのすべてについて、
【数１５】
を求める元計算部と、
ｄ（ｍ）の値が１であるすべてのＥｄ（１），ｄ（２）Ｇの和から、ｄ（ｍ）の値が−１であるすべてのＥｄ（１），ｄ（２）Ｇの和を減算した値をスカラー倍値ＥｍＧとする処理を、ｍ＝１からＭに対して行うスカラー倍値計算部と、
を備えるスカラー倍演算装置。
【請求項３】
請求項１記載のスカラー倍演算装置であって、
【数１６】
のように表現されるスカラーＥ１，…，ＥＭを、ＮＡＦ法を用いて
【数１７】
のように表現されるスカラーＥ１，…，ＥＭに変換する表現変換部
も備えることを特徴とするスカラー倍演算装置。
【請求項４】
請求項１記載のスカラー倍演算装置であって、
【数１８】
のように表現されるスカラーＥ１，…，ＥＭを、Booth法を用いて
【数１９】
のように表現されるスカラーＥ１，…，ＥＭに変換する表現変換部
も備えることを特徴とするスカラー倍演算装置。
【請求項５】
Ｍを２以上の整数、ｍを１以上Ｍ以下の整数、Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｅ１，…，ＥＭを
【数２０】
と表現されるスカラー、Ｇを群の元とし、元Ｇに対してスカラーＥ１，…，ＥＭをそれぞれ乗算した値であるスカラー倍値Ｅ１Ｇ，…，ＥＭＧを求めるスカラー倍演算方法であって、
中間値計算部が、ｄ（ｍ）∈｛０，１，−１｝として、
すべてのｍについてｄ（ｍ）＝ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝１
すべてのｍについてｄ（ｍ）＝−ｅｍ（ｎ）のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝−１
その他のときは
ｅｄ（１），…，ｄ（Ｍ）（ｎ）＝０
である中間値ｅｄ（１），…，ｄ（Ｍ）（ｎ）を、
ｄ（１）＝０，…，ｄ（Ｍ）＝０以外のすべてのｄ（１），…，ｄ（Ｍ）の組合せ（ただし、ｄ’（１）＝（−１）×ｄ（１），…，ｄ’（Ｍ）＝（−１）×ｄ（Ｍ）が成り立つｅｄ（１），…，ｄ（Ｍ）（ｎ）とｅｄ’（１），…，ｄ’（Ｍ）（ｎ）はいずれか一方のみ）について求める中間値計算ステップと、
元計算部が、前記中間値計算ステップで求めたｄ（１），…，ｄ（Ｍ）の組合せのすべてについて、
【数２１】
を求める元計算ステップと、
スカラー倍値計算部が、ｄ（ｍ）の値が１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和から、ｄ（ｍ）の値が−１であるすべてのＥｄ（１），…，ｄ（Ｍ）Ｇの和を減算した値をスカラー倍値ＥｍＧとする処理を、ｍ＝１からＭに対して行うスカラー倍値計算ステップと、
を有するスカラー倍演算方法。
【請求項６】
Ｎを正の整数、ｎを０以上Ｎ以下の整数、Ｅ１，Ｅ２を
【数２２】
と表現されるスカラー、Ｇを群の元とし、元Ｇに対してスカラーＥ１，Ｅ２をそれぞれ乗算した値であるスカラー倍値Ｅ１Ｇ，Ｅ２Ｇを求めるスカラー倍演算方法であって、
中間値計算部が、ｄ（１）∈｛０，１，−１｝、ｄ（２）∈｛０，１，−１｝として、
ｄ（１）＝ｅ１（ｎ）かつｄ（２）＝ｅ２（ｎ）のときは
ｅｄ（１），ｄ（２）（ｎ）＝１
ｄ（１）＝−ｅ１（ｎ）かつｄ（２）＝−ｅ２（ｎ）のときは
ｅｄ（１），ｄ（２）（ｎ）＝−１
その他のときは
ｅｄ（１），ｄ（２）（ｎ）＝０
である中間値ｅｄ（１），ｄ（２）（ｎ）を、
ｄ（１）＝０，ｄ（２）＝０以外のすべてのｄ（１），ｄ（２）の組合せ（ただし、ｄ’（１）＝（−１）×ｄ（１）かつｄ’（２）＝（−１）×ｄ（２）が成り立つｅｄ（１），…，ｄ（Ｍ）（ｎ）とｅｄ’（１），…，ｄ’（Ｍ）（ｎ）はいずれか一方のみ）について求める中間値計算ステップと、
元計算部が、前記中間値計算ステップで求めたｄ（１），ｄ（２）の組合せのすべてについて、
【数２３】
を求める元計算部と、
スカラー倍値計算部が、ｄ（ｍ）の値が１であるすべてのＥｄ（１），ｄ（２）Ｇの和から、ｄ（ｍ）の値が−１であるすべてのＥｄ（１），ｄ（２）Ｇの和を減算した値をスカラー倍値ＥｍＧとする処理を、ｍ＝１からＭに対して行うスカラー倍値計算ステップと、
を有するスカラー倍演算方法。
【請求項７】
請求項５記載のスカラー倍演算方法であって、
表現変換部が、
【数２４】
のように表現されるスカラーＥ１，…，ＥＭを、ＮＡＦ法を用いて
【数２５】
のように表現されるスカラーＥ１，…，ＥＭに変換する表現変換ステップ
も有することを特徴とするスカラー倍演算方法。
【請求項８】
請求項５記載のスカラー倍演算方法であって、
表現変換部が、
【数２６】
のように表現されるスカラーＥ１，…，ＥＭを、Booth法を用いて
【数２７】
のように表現されるスカラーＥ１，…，ＥＭに変換する表現変換ステップ
も有することを特徴とするスカラー倍演算方法。
【請求項９】
請求項１から４のいずれかに記載のスカラー倍演算装置としてコンピュータを動作させるためのスカラー倍演算プログラム。
【請求項１０】
請求項９記載のスカラー倍演算プログラムを記録したコンピュータ読み取り可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２０１１−１４１４８８（Ｐ２０１１−１４１４８８Ａ）
【公開日】平成２３年７月２１日（２０１１．７．２１）
【国際特許分類】
【出願番号】特願２０１０−３２９５（Ｐ２０１０−３２９５）
【出願日】平成２２年１月８日（２０１０．１．８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年７月２１日（２０１１．７．２１）
【国際特許分類】
【出願日】平成２２年１月８日（２０１０．１．８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]