There are many situations where it is necessary to 'prove' one's identity. Typical scenarios are to login to a computer, to get access to an account for electronic banking or to withdraw money from an automatic teller machine. Older methods use passwords or PIN's to implement user identification. Though successfully used in certain environments, these methods also have weakness. For example, anyone to whom you must give your pass-word to be verified has the ability to use this password and impersonate you. Zero-knowledge (and other) identification schemes provide a new type of user identification. It is possible for you to authenticate yourself without giving to the authenticator any knowledge to impersonate you.
This thesis deals with a technique, called an $\emph{identification scheme}$ or entity authentication scheme, which allows one party to gain assurances that the identity of another is as declared, thereby preventing impersonation. Our proposed identification scheme is based on braid groups. Most of cryptosystems are based on commutative groups, but new cryptosystems based on non-commutative groups have been proposed. ($\emph{Braid cryptosystem}$ is one of them.) These systems are very difficult to analyze for their non-commutative properties. In the recent years, beginning with [44], several authors proposed to build secure cryptographical schemes using noncommutative groups, in particular Artin's braid groups [1, 29, 30, 34], a natural idea as, on the one hand, braid groups are more complicated than Abelian groups, but, on the other hand, they are not too complicated to be worked with. In particular, the conjugacy problem in braid groups is algorithmically difficult, and it consequently provides one-way functions.
In this thesis we construct two new interactive identification schemes. One is based on the conjugacy problem and another is based on decision DiffieHellman (DDH) assumption. The first scheme is the primary one based on conjugacy problem over a braid group. We prove that the scheme based on conjugacy problem is secure against active attacks if the k-simultaneous conjugator search problem (k-SCSP) is intractable. Our proof is based on the fact that the conjugacy search problem (CSP) is hard in braid group, on the other hand, the conjugacy decision problem (CDP) is easy in braid group by Ko $\emph{et al.'}$s algorithm. Second scheme has some limitation for adversary. That is an adversary can view only k-times interactions. Under the DDH assumption and simulator's limitation, we prove the scheme is secure against impersonation attack. $\emph{i.e,}$, the impersonator has negligible advantage.
빌딩의 입구나 공항의 출입국관리 게이트에서 상대의 신원을 검증하기 위해서 운전면허증과 패스포트 등의 신분증명서를 제시하여 증명을 한다. 그러나, 이것들은 비교적 위조가 간단하다는 결점을 갖는다. 그래서 이후에는 위조가 어려운 IC카드 등의 전자매체를 이용한 인증시스템이 보급될 것이다. 또한 네트워크를 통한 각종 서비스에서 과금의 대상이 되는 이용자의 정당성을 확인하는 개인식별은 필수적이다. 식별은 서로 통신하는 송,수신자의 한쪽이 다른 한쪽의 신원을 어떤 프로토콜을 사용하여 확인하는 방법 또는 과정이며, 이때 사용되는 기법을 식별 프로토콜이라 한다.
식별 프로토콜은 기본적으로 증명자와 검증자로 구성된다. 증명자가 검증자에게 자신의 신원을 확인시키는 동시에 공격자가 자신의 신원을 위장하는 것을 어렵게 하는 것이 식별 프로토콜의 목표이다. 검증자의 입장에서 볼 때, 식별 프로토콜의 결과는 증명자가 주장하는 신원을 올바른 것으로 수락하거나 거절하는 것이다. 구체적으로 식별기법이 추구하는 바는 다음과 같다.
1. 증명자와 검증자가 모두 적법한 사용자일 경우에 증명자는 검증자에게 자신의 신원을 확인시킬 수 있어야 한다. 즉, 검증자는 식별프로토콜의 실행결과로 증명자의 신원이 올바른 것으로 수락한다.
2. 정보양도에 대한 안전성 : 검증자가 증명자의 신원을 확인하는 과정에 사용된 정보를 이용하여 제 3의 사용자에게 검증자가 증명자의 신원을 위장할 수 없어야 한다.
3. 위장에 대한 안전성 : 증명자가 아닌 공격자가 검증자에게 자신이 증명자인 것으로 위장할 수 있는 확률은 무시할 수 있어야 한다. 무시할 수 있다는 의미는 위장할 수 있는 확률이 너무 작아서 실질적인위협 요소가 되지 못한다는 것이다.
4. 정보 양도 및 위장에 대하여 다음의 상황을 가정하여도 안전하여야 한다.
· 증명자와 검증자간의 이전의 식별 과정은 관찰 가능하다.
· 공격자는 증명자 또는 검증자로서 이전의 프로토콜 실행에 참여하였다.
· 공격자의 주도하에 식별 프로토콜이 동시에 여러번 수행된다.
영지식 식별 프로토콜은 프로토콜의 실행 과정에서 공격자가 위장하는데 도움이 되는 어떠한 부분 정보도 나타내지 않는 것을 아이디어로 한다.
식별의 가장 주된 응용 분야는 자원에 대한 접근제어이다. 실례로 특정 개체마다 접근 권한이 주어진 환경으로, 컴퓨터 계정에 대한 지역 또는 원거리 접근, 현금 자동 지급기에서의 현금 인출, 특정 통신 포트를 사용할 수 있는 통신 권한, 소프트웨어에 대한 접근 등이 있다. 대부분의 응용 환경에서 식별의 역할은 신원이 확인된 개체에게만 자원의 사용을 허가하겠다는 것이다.
본 논문은 우선 증명가능한 안전성을 지니는 개인식별기법에 관한 요구사항을 논한다. 식별기법에 대한 다양한 공격방법과 영지식대화증명을 통한 식별기법의 안전성을 논한 뒤, 수동적 공격자의 신원위조 공격에 안전한 개신식별기법으로 비가환군의 일종인 땋임군에 기반한 새로운 개인식별기법과 결정적 디피헬만 가정에 기반한 개인식별기법을 제안한다. 이중 땋임군에서의 개인 식별기법은 군이 갖는 비가환 특성때문에 기존의 안전성 분석기법이 적용되기 어려운 이유로 그 의미를 찾을 수 있다. 설계한 제안 기법의 안전성은 땋임군에서의 k연립 공액찾기 문제와 매칭 세쌍 찾기 문제의 어려움에 기반하고 있으며, 이 안전성을 지식의 영지식 증명을 통해서 증명한다. 본 제안 기법은 땋임군 중 공액찾기 문제는 해결 가능성 없는 문제이고, 공액 결정 문제는 해결 가능성 있는 문제를 제공하는 비가환군에서 정의되었다.
결정적 디피헬만 가정에 기반한 기법은 공격자의 능력에 제한을 두고 그 안전성을 증명하였다. 본 기법은 최대 k회의 인터렉션만을 허용한다. 이 기법은 우선 랜덤오라클 모델이 아닌 스탠더드 모델에서의 안전성을 제공한다는 장점을 지닌다. 제안 기법에서 위장공격을 하고자 하는 공격자가 검증자로 부터 신원을 수락받는 어드밴티지는 무시해도 좋을(negligible)한 양으로 측정된다. 적당한 회수의 라운드를 반복해서 옳바른 증명자의 신원을 확인할 수 있다.
