In this thesis, we propose algorithms to speed up the scalar multiplication, one of the bottleneck operations in elliptic curve cryptography, and introduce methods to analyse algorithms for scalar multiplications. To reduce a computation time of the operation, the method that we interest in this work is to change the representation of a scalar, that is to represent a positive integer using other representations than the binary representation with digit set {0,1}. Many representations such as the binary representation with digit set {-1, 0, 1} are redundant, i.e. there are many ways to represent a scalar in the representation. The computation time of scalar multiplication strongly depends on how we represent the scalar. For example, the Hamming weight is important factor to speed up the operation on the binary representation. Then, conversion algorithms to find the way to represent a positive integer for faster scalar multiplication are studied in many works, such as work by Muller, which propose a conversion algorithm for binary representation with digit set {0, ±1, ±3, ... , ±(2h + 1) } for any natural number h. We are also interested in an efficiency of each conversion on scalar multiplication. For binary representation, we use average joint Hamming density to evaluate the conversion, and minimal average joint Hamming density is devised to find the efficiency of each representation given an optimal conversion. By Muller, it is known that the average joint Hamming density of binary representation with digit set {0, ±1, ±3, ... ,±(2h + 1)} is 1/(h + 2).

Most of the works on improving the number representation on scalar multiplication are based on the mathematical construction of the representations. The construction helps them to devise the algorithm with fast conversion time and output expansions with minimal weight. Also, the minimal average joint Hamming density can be calculated from the construction. However, finding the mathematical construction of many representations are not trivial, and are still not attained. The optimal conversions with their average efficiency are still open problems. These include many representations practically used in scalar multiplication. The problem is harder when we consider multi-scalar multiplication, which is the crucial operation in elliptic curve signature verification. This operation depends on the expansion of more than one scalar. To find the optimal conversion, we have to take all scalars involved in the operation into account. In this case, the mathematical construction becomes more complicated, and has not been found in most cases even for the binary representation with digit set {0, ±1, ±3}.

In our approach, we do not consider the mathematical constructions, but propose the optimal conversions directly from the structure of each representation based on dynamic programming scheme. Thus, we are able to obtain the optimal conversions based on dynamic programming scheme for many classes of representations whose optimal conversions have not been proposed. These include r-radix representation, which is the representation with base more than 2 used for speeding up pairing-based cryptography. Also, we can find the optimal conversions for scalar-multiplication using a double-base chain, the representation simultaneously using two bases. The outputs of our optimal conversions improve the results of the previous works by 3.2 - 11.3% in less than a second for 192 to 448-bit inputs with Java implementation on a personal computer. Moreover, we find the optimal conversions for multi-scalar multiplication, and solve the open problem proposed by Solinas in 2001.

From our optimal conversions, we construct Markov chains automatically. Then, we find the efficiency of each representation from its stationary distribution of the Markov chains. This enables us to find the minimal average Hamming density automatically. Although the number of states in the Markov chains is generally infinite, we propose many methods to reduce the number of states. The most important technique is that we define the similarity between the states, and consider the similar state as one state. Using the methods, the finiteness of Markov chain with the existence of stationary distribution is proven in a class of representation whose digit set be a finite set such that there exists a natural number Λ where digit set DS ⊆ {0, ±1, ... , ±Λ} and {0, ±1, ±Λ} ⊆ DS. The class covers most of representations practically used in scalar multiplication such as the representation which digit set are {0, ±1} and {0, ±1, ±3}. One of the most notable results from this method is the minimal average joint Hamming weight of multi-scalar multiplication when two scalars are considered and digit set is {0, ±1, ±3}. We can show that the value is 0.3575. This improves the best upper bound 0.3616 proposed by Dahmen, Okeya, and Takagi in 2007. As we have found the minimal average joint Hamming weight of many representations, we can analyze the trend of the value on each digit set. In addition to the trend in binary representation found by Muller, we have discovered a relationship between digit set and minimal average joint Hamming weight in r-radix representation for scalar multiplication. For multi-scalar multiplication with two integers, we found the minimal average joint Hamming weight of the representation when the digit set is a subset of {0, ±1, ±3}. As a result, we discover a number of representations which have a small difference in the computation time of multi-scalar multiplication, but have a large advantage in the pre-computation step over representations proposed in previous works.

From the average joint Hamming weight, we explore more properties of the automatically-constructed finite state machine. We can find how minimal Hamming weight of all positive integers span when it is expanded in each representation. We show that these representations are always normal, and we use this fact with the spanning deviation to propose an effective countermeasure of side channel attacks.

本論文は、楕円曲線暗号の計算上ボトルネックとなっているスカラー乗法を、スカラー表現を乗法の計算をより高速に行うことが可能なように表現することによって、高速化するアルゴリズムを提案したものである。

本論文は六章からなり、第一章では、まず、本論文のようなスカラー乗法計算の高速化が求められる背景として現在最も用いられている暗号技術のひとつである楕円曲線暗号における問題を挙げ、研究の必要性および動機づけを明らかにしている。さらに、これまでのスカラー乗法計算を効率化するための手法の基本的な考え方の概略を述べるとともに、本論文がそれらに対してどのような貢献を行ったかを概観している。さらに第二章においては、本論文の背景知識として、楕円曲線暗号、その中で用いられるスカラー乗法、そのスカラー乗法を高速化するための既知のスカラー表現方法の概略を紹介している。

スカラー乗法の効率化は、積をとる2つのスカラーのそれぞれの表現間で定義されるハミング距離が小さいような2つのスカラーの表現を見つけることができれば、達成されるが、第三章では、本論文の中核となる、ハミング距離を理論的に最小化する手法を提案している。さらに、第四章では、その理論的な性能をマルコフ連鎖解析の手法を用いて解析し、一部のスカラー表現においては、提案手法が最適であることを示すなど、永年の未解決問題を解決している。さらに、第五章においては、第四章までのスカラー表現をさらに複数の底に対応した場合のスカラー乗法を効率化するスカラー表現を最適化する手法について提案を行っている。第六章では、本論文で提案した手法と有効性を総括し、さらに今後考察すべき課題についての展望が示されている。以上のように、本論文は、スカラー乗算という基本的演算を効率化するアルゴリズムを提案することによって、楕円曲線暗号演算の効率化を図ることに成功したものである。

なお、本論文の第三章、第四章、第五章は、枝廣正人氏、今井浩氏との共同研究であるが、論文提出者が主体となって立案、分析、検証を行ったもので、論文提出者の寄与が十分であると判断する。

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。