In this thesis, we study recent results of two kinds of cryptographic objects: elliptic curve and braid group cryptosystem and our contributions on it.
For elliptic curve cryptosystem, we focus on two topics: elliptic curve point counting and pairing based cryptosystems. After Satoh proposed a p-adic method for counting points on elliptic curves over finite fields, several useful techniques have evolved to improve the computational efficiency of the basic Satoh algorithm. The evolution of these techniques has proved remarkably successful and reduced the computational efficiency by asymptotically optimal. We briefly review p-adic methods and present an improved algorithm. It is mainly based on the Satoh-Skjernaa-Taguchi (SST) algorithm and the modified SST algorithm, and uses a Gaussian normal basis (GNB) of small type. We show that a Gaussian normal basis can be lifted form $\mathbb{F}_q$ to $\mathbb{Z}_q$ in a natural way. From the specific properties of GNBs, efficient multiplication and the Frobenius substitution are available. Thus a fast norm computation algorithm is derived. As a result, we reduced the time complexity of both algorithms from $O(N^{2μ+0.5})$ to $O(N^{2μ +{1\choosμ +1}})$ and the space complexity still fits in $O(N^2)$ for either a small characteristic. So, applying our contribution to other recent improvements allows to compute the number of points of an elliptic curve defined over large finite fields.
Pairing based cryptosystems are currently one of the most active areas of research in elliptic curve cryptography. Especially, the identity based encryption scheme of Boneh and Franklin has spurred a tremendous amount of new cryptographic research. We describe a number of simple yet amazing applications of pairings and propose a certificate-based signature scheme that can share parameters and certificate revocation strategy with the encryption scheme proposed by Gentry. We first suggest a formal security model of a certificate-based signature scheme and then construct a concrete scheme provably secure in the random oracle model assuming the underlying group is GDH. As an application, we also show that a certificate-based signature scheme gives rise to a delegation-by-certificate proxy signature scheme following to the formal security model proposed by Boldyreva et al., and that it is secure in the random oracle model.
As a candidate for cryptographically promising noncommutative groups, braid groups have received wide attention due to efficient implementation and several hard problems. After Anshel et al. proposed a key agreement protocols, a practical public key encryption scheme based on braid groups (BPKE) was introduced by Ko et al. The second part of this thesis is about security analysis of this encryption scheme. We demonstrates how to solve its underlying problem using the Burau representation. By this method, we show that the private-key can be recovered from the public-key for several parameters with significant probability in a reasonable time. Our attack can be mounted directly on the revised scheme mentioned by Cha it et al. as well. On the other hand, we give a new requirement for secure parameters against our attack, which more or less conflicts with that against brute force attack.
본 논문에서는 타원곡선과 땋임군에 기반한 암호 시스템에 관한 최근의 연구결과들을 정리한다.
타원곡선 암호 시스템의 경우 최근에 가장 활발하게 연구되고 있는 타원곡선 위수계산 알고리즘과 겹선형 함수 (bilinear map)를 이용한 암호시스템에 대한 연구결과들을 정리한다. Saoth 의 새로운 형태의 위수계산 알고리즘이 등장한 이후 이 알고리즘의 제한조건을 완화하면서 계산 효율성을 높이고자 하는 연구들이 지속적으로 수행되고 있다. 이러한 연구들의 결과, 현재 타원곡선 위수계산 알고리즘의 계산 효율성은 거의 최적화 단계라고 볼 수 있다. 본 논문에서는 이러한 일련의 연구결과들을 간단하게 정리해 보는데 특히 Satoh-Skjernaa-Taguchi 의 알고리즘 (SST algorithm)과 Gaudry 의 알고리즘 (MSST algorithm)을 소개하고 작은 형 (type)의 Gaussian 정규기저 (normal basis)를 가지는 유한체 상에서 구현할 경우 나타나는 장점에 대해 집중적으로 다룬다. 유한체의 Gaussian 정규기저를 p-adic 체로 자연스럽게 올릴 수 있다는 사실을 이용하여 위수계산 알고리즘의 직접적인 계산이 이루어 지는 p-adic 체에서의 효율적인 곱셈과 Frobenius 연산이 가능하다는 것을 보이고, 이로 인한 norm 계산 알고리즘의 효율성 향상으로 SST 나 MSST 알고리즘의 공간 복잡도를 $O(N^2)$으로 유지하면서, 시간 복잡도가 $O(N^{2μ+0.5})$ 에서 $O(N^{2μ+{1\choosμ+1}})$으로 향상됨을 확인하며 그 구현결과들을 정리한다.
겹선형 함수 기반 암호 시스템은 현재 타원곡선 암호에서 가장 활발하게 연구되고 있는 분야로 Boneh 와 Franklin 의 사용자 ID 기반 암호기법 (identity-based encryption scheme)이 제안된 이후 많은 연구 결과들이 제안되고 있다. 본 논문에서는 그 중에서 핵심이 되는 몇 가지 암호 기본 요소 (primitive)들에 대해 소개하고 최근 Gentry가 Eurocrypt 2003에서 기존의 PKI 시스템에서 나타나는 인증서 분배 문제를 해결하기 위해 제안한 인증기반 암호 기법 (certificate-based encryption scheme)에 대응하는 서명 기법 (signature scheme)을 제안한다. 이를 위해 우선 이 서명 기법의 형식모델 (formal model)을 정의하고 랜덤 오라클 모델 (random oracle model)하에서 gap Diffie-Hellman 군에서 정의되는 안전성이 증명가능한 실제 서명 기법을 제안한다. 또한 이에 대한 응용으로 Boldyreva, Palacio 그리고 Warinschi 의 형식모델에 맞춘 랜덤 오라클 모델하에서 안전성이 증명가능한 대리서명 기법 (proxy signature scheme)을 제안한다.
기존의 소인수 분해나 이산대수 문제에 의존하지 않는 새로운 형태의 암호 시스템을 개발하고자 하는 노력의 일환으로 땋임군에서 정의되는 암호 시스템이 여러 암호학자들의 관심을 끌고있다. Anshel 등의 열쇠교환 기법이 제안된 이후, Crypto 2000 에서 Ko 등에 의해 암호기법이 제안되었는데 본 논문에서는 이 암호기법의 안전성에 대해 분석한다. 이를 위해 기존의 분석방법들을 살펴보고 Burau 재표현 (representation)을 이용하여 암호 기법의 기반문제에 대한 해결방법을 제안하며 이를 통해 일부분의 안전성 인수 (security parameter)가 취약함을 보인다. 특히 본 논문의 제안방법은 Asiacrypt 2001에서 Cha 등이 제안한 교정된 암호 기법에도 적용 가능한 최초의 방법이다.
