Throughout this thesis, we have focused on developing new pairing formulae and signature schemes using bilinear property that pairings can provide.
The former contains three pairings: squared pairings, the qth powered pairing and the zeta pairing. We first investigate the relationship between powers of pairings and plain pairings in ordinary elliptic curves. Along these lines, we show that the squared Weil/Tate pairing for arbitrary chosen point can be transformed into a plain Weil/Tate pairing for the trace zero point which has a special form to compute them more efficiently. This transformation requires only a cost of some Frobenius actions. Similarly, we can derive an explicit formula for the 4th powered Weil pairing represented as the optimized plain Weil pairing. Next, two kinds of pairings are proposed, motivated by the eta pairing approach of Barreto et al.. One is the qth powered Tate pairing that is derived from the property of [q] map in supersingular curves. This has the same efficiency with the eta pairing. approach without any restriction. From this freedom of restriction, it becomes applicable for the reduced Tate pairing whereas the eta pairing approach seems to be only related to the modified Tate pairing since the condition requires a distortion map. As a result, we can also derive new pairing formulae that maintain the above advantage, and moreover improve the efficiency by a factor close to 2. These are not only comparable to the new algorithms by Barreto et al. but also based on more generic view. It is also shown that a rather complicated final powering in our new algorithms as well as Barreto et al.'s can be replaced by a qth Frobenius action. The other pairing that we provide is the zeta pairing. At the first glance, it is inefficient compared with the reduced Tate pairing in supersingular curves. However, it turns out that the simplified final exponentiation of the zeta pairing brings relative efficiency improvement as the security parameters for pairing based cryptographic applications increase. In addition, the zeta pairing formula enables us to have an explicit formula for powers of the Weil pairing and relates it with the Tate pairing.
As applications based on pairings over elliptic curves, we propose the security notion of certificate-based signature that uses the same parameters and certificate revocation strategy as the encryption scheme presented at Eurocrypt 2003 by Gentry. Certificate-based signature preserves advantages of certificate-based encryption, such as implicit certification and no private key escrow. We present concrete certificate-based signature schemes derived from pairings on elliptic curves and prove their security in the random oracle model assuming that the underlying group is GDH. Additionally, we propose a concrete delegation-by-certificate proxy signature scheme which is derived from a certificate-based signature scheme after simple modifications. Our proxy scheme is provably secure in the random oracle model under the security notion defined by Boldyreva, Palacio and Warinschi. At last, we analyze several concrete proxy signature schemes proposed by Zhou et al. and Lu et al. from the verifiability point of view.
최근 타원곡선 암호 분야에서 가장 활발하게 연구되고 있는 분야가 바로 겹선형 함수 기반 암호 시스템이다. 겹선형 함수의 성질을 이용한 Joux의 1회 3자 키교환 기법을 시작으로 오랫동안 풀리지 않던 문제였던 실제적인 개인식별정보 기반 암호 기법 (Identity-based encryption scheme)이 Boneh-Franklin에 의해 제안한 이후 현재까지 다양한 형태의 겹선형 기반 암호 프로토콜이 제안되고 있다. 이러한 암호 프로토콜의 실용화는 핵심이 되는 겹선형 함수의 효율성에 의존하는 것으로 실제 이를 구현하기 위해서 사용될 수 있는 것은 초특이 곡선 (supersingular curve)이나 특수한 성질을 만족하는 정규 타원곡선(ordinary curve)상의 Weil/Tate 페어링이 유일하다. 이와 같은 맥락에서 본 논문에서는 크게 새로운 겹선형 함수식들을 이용한 효율성 향상 가능성과 겹선형 기반의 서명기법들에 대한 연구가 수행되었다.
우선 새로운 겹선형 함수식에 대한 연구로서는 제곱승 페어링, q승 페어링, 그리고 제타 페어링들을 제안한다. 첫번째로 제곱승 페어링에 대한 연구를 통해 임의로 선택된 점의 제곱승 Weil/Tate 값을 효율적인 계산을 가능하게 하는 Trace 0 인 점들의 Weil/Tate 값으로 단지 몇번의 프로베니우스(Frobenius)의 비용으로 대체하여 구할수 있다는 것을 보인다. 그리고 이 결과를 확장하여 4승 Weil 페어링을 최적화된 Weil 페어링 식으로 표현한다. 두번째와 세번째 페어링들은 Barreto등의 에타 페어링 접근방법을 통해 얻어지게 된다. q승 Tate 페어링은 초특이 곡선에서의 [q]배 함수의 성질에 의해 유도 되는데, 에타 페어링과 동일한 효율성을 보장하는 동시에 어떤 조건식에도 의존하지 않는 장점을 가진다. 또한 루프의 길이를 반으로 줄여주는 새로운 알고리즘을 제안하며 여기서 요구되는 다소 복잡한 마지막 지수승이 포로베니우스의 비용으로 대체될수 있다는 것을 보인다. 세번째 페어링인 제타 페어링은 초특이, 정규 타원곡선 모두에서 같은 성질을 가지는 프로베니우스 함수로 유도된다. 기존의 페어링과 비교하여 비효율적으로 보이나 높은 안전성 수준이 요구되는 환경에서는 단순화된 마지막 멱승으로 인해 얻어지는 이점을 가지게 된다. 또한 제타페어링을 통해 Weil 페어링의 적당한 승수와 Tate 페어링 사이의 관계식을 얻을수 있다.
한편 겹선형 기반 암호 프로토콜에 대한 연구로서는 서명 기법들에 대한 연구가 수행되었다. 첫번째로 Euro 2003에서 Gentry에 의해 제안된 인증서 기반 암호 기법(Certificate-based encryption scheme)과 동일한 파라메터와 인증서 폐기 전략을 사용하는 새로운 개념의 인증서 기반 서명 기법(Certificate-based signature scheme:CBS)을 제안한다. CBS는 암묵적인 인증을 통해 기존의 공개키 서명기법에서 필수적인 인증서 교환의 필요성을 제거하고 개인식별정보 기반 서명 기법(Identity-based signature scheme)에서의 3자에 의한 비밀키 소유의 문제를 해결하는 이점을 가지고 있다. 본 논문에서는 겹선형 함수기반 암호 환경에서의 구체적인 CBS기법을 설계하고 그 안전성을 랜덤 오라클 모델하에서 증명한다. 나아가서 제안된 CBS 개념은 위임 서명 기법을 자연스럽게 유도하게 된다. 두번째로 Zhou등과 Lu등에 의해 제안된 RSA 및 이산로그문제 기반의 몇몇 위임 서명 기법을 분석하여 Verifiability 관점에서의 취약점을 제시한다.
