□	본 연구는 2004년도 정보통신부 지원 대학 IT 연구센터 육성지원사업(C1090-0403-0005)의 연구비 지원으로 수행하였습니다.
‡	학생회원	:	성균관대학교 정보통신공학부
			hjkim@dosan.skku.ac.kr
§	비 회 원	:	성균관대학교 정보통신공학부
			yeosh72@hanmail.net
¶	종신회원	:	성균관대학교 정보통신공학부 교수
			dhwon@dosan.skku.ac.kr
	논문접수	:	2003년 10월 27일
	심사완료	:	2004년 09월 02일
CopyrightⒸ2004 한국정보과학회ː개인 목적이나 교육 목적인 경우, 이 저작물의 전체 또는 일부에 대한 복사본 혹은 디지털 사본의 제작을 허가합니다. 이 때, 사본은 상업적 수단으로 사용할 수 없으며 첫 페이지에 본 문구와 출처를 반드시 명시해야 합니다. 이 외의 목적으로 복제, 배포, 출판, 전송 등 모든 유형의 사용행위를 하는 경우에 대하여는 사전에 허가를 얻고 비용을 지불해야 합니다. 정보과학회논문지: 정보통신 제31권 제6호(2004.12)

Bilinear-pairing을 이용한 대리서명, ID 기반 부분은닉서명과 대리부분은닉서명 방식†

(Proxy Signature, ID-based Partially Blind Signature and Proxy
Partially Blind Signature using Bilinear-pairing)

김현주‡     여상희§     원동호¶

(Hyunjue Kim)      (Sanghee Yeo)       (Dongho Won)

요  약  대리서명은 대리서명자로 하여금 원서명자를 대신해서 서명하도록 하는 암호방식이고, 부분은닉서명은 서명자가 은닉서명을 발행할 때 그가 삽입하기를 원하는 어떠한 정보를 서명에 삽입할 수 있도록 하는 암호방식으로, 부분은닉성과 익명성(또는 불추적성)을 제공하기 때문에 전자상거래에서 전자화폐나 전자투표 등과 같은 사용자의 프라이버시 보호나 보안을 요구하는 응용분야에 중요하게 적용되는 기술이다. 본 논문에서는 bilinear-pairing을 이용한 대리서명 방식과 ID 기반 부분은닉서명 방식을 제안한다. 그리고 두 방식을 결합한 대리부분은닉서명 방식을 제안한다. 제안하는 방식들은 GDH군에서 성립하며 CDHP의 어려움에 기반을 두고 있다. 제안하는 ID 기반 부분은닉서명 방식과 대리부분은닉서명 방식에서 공통정보를 제거하면 두 서명 방식은 각각 ID 기반 은닉서명 방식과 대리은닉서명 방식이 된다.

키워드 : 대리서명 방식, ID 기반 부분은닉서명 방식, 대리부분은닉서명 방식, Gap Diffie-Hellman 문제, Bilinear-pairing

Abstract  Proxy signature scheme allow a designated proxy person to sign a message on behalf of the original signer. Partially blind signature scheme allows the signer to insert non-removable common information into his blind signature. Proxy signature and partially blind signature are very important technologies in secure e-commerce. In this paper we propose new proxy signature scheme and ID-based partially blind signature scheme using bilinear pairing. Further combining them, we propose a proxy partially blind signature scheme. The security of our schemes relies on the hardness of Computational Diffie-Hellman Problem. If we removing common information form propose ID-based partially blind signature scheme and proxy partially blind signature scheme, then they become variants of ID-based blind signature scheme and proxy blind signature scheme of Zhangs respectively.

Key words : Proxy signature, ID-based Partially Blind Signature scheme, Proxy Partially Blind Signatur scheme, Gap Diffie-Hellman Problem, Bilinear-pairing

1.  서 론

Bilinear-pairing을 이용한 대리서명, ID 기반 부분은닉서명과 대리부분은닉서명 방식

정보과학회논문지 : 정보통신 제 31 권 제 6 호(2004.12)

대리서명 방식은 원서명자가 자신의 부재중에 자신을 대신해서 서명을 할 수 있는 대리 서명자를 지정하여 대신 서명하도록 하는 서명 방식으로 기업의 대표가 과도한 업무나 또는 출장 등과 같은 이유로 제한된 기간 내에 반드시 서명을 해야하는 계약서나 문서에 서명을 못하게될 상황에 대한 해결책으로 유용하게 활용되고 있다. 대리서명 방식은 1996년 M. Mambo, K. Usuda와 E. Okamoto[1]에 의해서 처음 소개되었고, 그 후 많은 사람들에 의해서 연구되었다[2-7].

M. Mambo, K. Usuda와 E. Okamoto는 대리서명 방식을 위임의 형태에 따라서 완전 위임(full dele-gation), 부분 위임(partial delegation)과 보증 위임(delegation by warrant)으로 분류하였고 S. Kim, S. Park와 D. Won[2]은 부분 위임의 장점과 보증 위임의 장점을 결합한 보증부분위임(partial delegation with warrant)이라는 새로운 개념을 제안하였다. 본 논문에서 제안한 대리서명 방식은 보증부분위임방식이다.

대리서명은 다른 특수서명과 결합하여 또 다른 형태의 특수서명 방식을 생성한다[8-11]. 최근 F. Zhang은 ID 기반 은닉서명 방식과 F. Hess[12]의 ID 기반 서명 방식을 기초로 한 대리서명 방식을 제안하였고[13], 이 두 방식을 이용한 대리은닉서명 방식을 제안하였다[9].

1982년 D. Chaum[14]에 의해서 처음 소개된 은닉서명 방식은 은닉성과 익명성(또는 불추적성)을 제공하기 때문에 전자 투표나 전자화폐 등과 같은 보안을 요구하는 응용분야에 사용된다. 그러나 전자화폐는 전자적 특성상 쉽게 위조가 가능하여 이중사용의 문제점이 발생한다. 이에 대한 해결책으로, 전자화폐 자체가 특수한 구조를 가지도록 하여 매 지불시 마다 등록되는 데이타가 거의 동시에 모든 데이타베이스에 기록되도록 함으로써 이중 사용을 검출하는 방법이 있다. 그러나 이미 사용된 모든 전자화폐들에 대한 데이타베이스를 구축해야 한다는 사실은 데이타베이스의 크기가 무제한적으로 증가하게 됨을 암시하며 따라서 이에 대한 막대한 비용이 소요되는 문제를 야기한다. 이에 대한 해결책으로 부분은닉서명 방식이 제안되었다.

1996년 M. Abe와 E. Fujisaki[15]에 의해 소개된 부분은닉서명 방식은 서명자(은행)가 은닉서명을 발행할 때 그가 삽입하기를 원하는 어떠한 정보를 서명에 삽입할 수 있도록 하는 암호방식이다. 이때, 서명자는 자신이 삽입하고자 하는 정보가 서명에 삽입되었는지 확신할 수 있어야 한다. 또한 서명의뢰자가 그 정보를 제거하거나 변형할 수 없어야 한다. 부분은닉서명을 사용하여 은행은 모든 전자화폐에 만료부(expiration data)를 삽입하여 사용자(서명의뢰자)에게 발행하고, 사용자가 사용하여 기간 만료된 전자화폐에 관련된 기록은 은행의 데이타베이스에서 지워지도록 함으로써 데이타베이스의 무제한적인 증가 문제를 해결할 수 있다. 부분은닉서명 방식은 부분은닉성과 익명성을 제공하기 때문에 전자상거래에서 사용자의 프라이버시 보호나 보안을 요구하는 많은 응용분야에 유용하게 적용되는 암호방식으로 많은 사람들에 의해 연구되었다[16-19].

본 논문에서는 J. Cha와 J. Cheon[20]이 제안한 ID 기반 서명 방식을 기초로 한 새로운 대리서명 방식과 ID 기반 부분은닉서명 방식을 제안한다. 제안하는 대리서명 방식은 Zhang의 대리서명 방식에 비하여 서명 생성 시에 사용되는 계산량을 크게 줄인 효율적인 서명 방식이다. 그리고 제안하는 대리서명 방식과 ID 기반 부분은닉서명 방식을 결합한 대리부분은닉서명 방식을 제안한다. 제안하는 서명 방식들은 모두 GDH군에서 성립하며 CDHP의 어려움에 기반을 두고 있으며 서명검증에 bilinear-pairing을 사용한다. 제안하는 ID 기반 부분은닉서명 방식과 대리부분은닉서명 방식에서 공통정보를 제거하면 두 서명 방식은 각각 ID 기반 은닉서명 방식과 대리은닉서명 방식이 된다.

본 논문의 구성은 다음과 같다. 1장의 서론에 이어 2장에서는 본 논문에서 제안하는 서명 방식에 사용된 안전성 기반 문제인 GDHP와 서명 검증에 사용된 bilinear-pairing에 대하여 설명하고, 3장에서는 Zhang의 대리서명 방식, ID 기반 은닉서명 방식과 대리은닉서명 방식들을 살펴본다. 4, 5 그리고 6장에서는 각각 본 논문에서 제안하는 새로운 대리서명 방식, ID 기반 부분은닉서명 방식 그리고 대리부분은닉서명 방식에 대하여 설명하고 분석하며, 마지막으로 7장에서 결론을 도출한다.

2. GDHP와 Bilinear-pairing

CDHP(Computational Diffie-Hellman Problem)가 해결되면 DDHP(Decisional Diffie-Hellman Problem)가 해결됨을 알 수 있다. 그러나 그 역의 성립에 대하여는 알려진 사실이 없다. 이에 대하여 2001년 T. Okamoto와 D. Pointcheval[21]은 CDHP와 DDHP 해결의 어려움에 차이가 있을 경우, 이 차이에 기반한 서명 방식의 존재가능성을 제시하였다. 그들은 CDHP의 해결은 어려우면서, DDHP의 해결은 쉬운 군(Group)을 Gap Diffie-Hellman(GDH)군이라고 정의하고 이러한 문제를 GDH 문제라고 하였다. Diffie-Hellman 문제를 정리하면 다음과 같다.

∙계산적 Diffie-Hellman 문제 (CDHP: Computa-tional Diffie-Hellman Problem)

: [eqn: P``], [eqn: aP`]와 [eqn: bP`]로부터 [eqn: abP`]를 계산하는 문제

∙결정적 Diffie-Hellman 문제 (DDHP: Decisional Diffie- Hellman Problem)

: [eqn: P``], [eqn: aP`], [eqn: bP`]와 [eqn: cP`]로부터 [eqn: c`=`ab ``IN `Z/ELL]인지를 결정하는 문제

∙Gap Diffie-Hellman 문제 (GDHP: Gap Diffie- Hellman Problem)

: [eqn: P``], [eqn: aP`]와 [eqn: bP`]로부터 DDH Oracle을 이용하여 [eqn: abP`] 를 계산하는 문제

4.1 제안하는 대리서명 방식

참 고 문 헌

[ 1 ]	M. Mambo, K. Usuda and E. Okamoto, "Proxy Signature : Delegation of the Power to Sign Messages," In IEICE Trans. Fundamentals, Vol. E79-A, No. 9, pp. 1338-1353, Sep., 1996.

김 현 주

1995년 세명대학교 수학과 졸업(학사) 1997년 서강대학교 수학과 졸업(석사) 1999년～현재 성균관대학교 전기전자 및 컴퓨터공학부 박사과정. 관심분야는 암호이론, 전자상거래보안

여 상 희

1994년 순천향대학교 전산통계학과(학사) 2001년 충북대학교 경영학과(석사). 2002년～현재 성균관대학교 정보통신공학부 박사과정. 관심분야는 암호이론, 전자상거래보안

원 동 호

성균관대학교 전자공학과 졸업(학사, 석사, 박사). 1978년～1980년 한국전자통신연구원 전임연구원. 1985년～1986년 일본 동경공업대 객원연구원. 1988년～1999년 성균관대학교 교학처장, 전기전자 및 컴퓨터공학부장, 정보통신대학원장, 정보통신기술연구소장. 1996년～1998년 국무총리실 정보화추진위원회 자문위원. 2002년～2003년 한국정보보호학회장. 2003년～2004년 성균관대학교 연구처장. 1982년～현재 성균관대학교 정보통신공학부 교수. 2000년～현재 정보통신부 지정 정보보호인증기술연구센터장. 관심분야는 암호이론, 정보시스템보안 등