We interact and transact by directing flocks of digital packets towards each other through cyberspace, carrying love notes, digital cash, and secret corporate documents. However, the technical wizardry enabling remote collaborations is founded on broadcasting everything as sequences of zeros and ones that one's own dog wouldn't recognize. How should you know that it $\emph{really is}$ me requesting from a laptop in Fiji a transfer of $100,000,000 to a bank. Fortunately, the magical mathematics of cryptography can help. That is, we need to have techniques that play a role of allowing one party to gain assurance that the identity of another is as declared. Names for such techniques include $\emph{identification}$ or$ \emph{identity verification}$.
To guarantee that an identification protocol withstands the attacks, the designed identification protocol should be strictly proven to be secure. However, the design of provably secure identification protocol has been regarded as a difficult task, but a fundamental task. As in the design of other cryptographic protocols, in provable security for identification schemes, first precise definitions of various attacks is given and then, using complexity theoretical techniques such as cryptographic reductions, their security is analyzed in mathematical way.
In this thesis, we deal with an interactive identification scheme based on the bilinear Diffie-Hellman problem and analyze its security. The scheme is more efficient than the Schnorr scheme and the Okamoto scheme with respect to preprocessing of prover and on-line processing overhead of both parties (prover and verifier). At the same time, security of our scheme is higher than or equal to previous schemes. We prove that this scheme is secure against active attacks as well as passive attacks if the bilinear Diffie-Hellman problem is intractable. Our proof is based on the fact that the computational Diffie-Hellman problem is hard in the additive group of points of an elliptic curve over a finite field, on the other hand, the decisional Diffie-Hellman problem is easy in the multiplicative group of the finite field mapped by a bilinear map. Finally, this scheme is compared with other identification schemes.
네트워크에 기반한 사이버 공간에서 현금, 연애편지, 비빌문서등이 디지털 패킷의 형태로 교환되고 있다. 그러나 디지털 통신에 의해 교환되는 메시지는 사람이 구별 할 수 없는 '0'과 '1'의 연속된 나열에 불과하므로, 개인 식별 (entity identification)이라는 본질적 문제를 수반한다. 개인 식별 문제의 대표적 예로서 "누군가 피지 (Fiji)에서 어떤 은행에 $100,000.000의 송금을 요청한다고 하면 그 은행은 그가 진짜 그인지 어떻게 확인 할 수 있는가?"라는 문제를 고려해보자. 사이버 공간같은 비대면 상황에서 한 사용자가 다른 사용자에 의해서 제시된 신원 (identity)이 맞다는 것을 보장해 주는 기법이 필요하며 이 기법을 식별 프로토콜이라 부른다.
본 본문에서는 일방향 함수 (one-way function)로 알려진 겹선형 디피-헬만 (bilinear Diffie-Hellman) 문제에 기반한 식별 프로토콜을 설계하고 이것의 안전성에 대한 정량적 근거를 제시한다. 식별 프로토콜이 가능한 공격에 대해서 안전하다는 것을 보장하기 위해 식별 프로토콜이 얼마나 안전한 가에 대한 정형적이고 엄격한 수학적 증명이 수반되어 한다. 안전성 증명 가능 (provably secure) 식별 프로토콜의 설계는 어려운 일이나 프로토콜의 설계에 기본적인 작업이다. 다른 암호 프로토콜의 설계와 마찬가지로 본 논문에서 식별 프로토콜의 안전성의 보장을 위해, 먼저 가능한 모든 공격에 대한 구별 및 수학적 정의가 이루어진다. 설계하고자 하는 시스템에 대한 공격 모델을 구성한 후 복잡도 이론 (complexity theory)에 근거한 암호학적 축소 (cryptographic reduction) 기법을 사용하여 주어진 시스템의 안전성이 얼마나 되는지 공격자의 자원에 관한 함수로 제시된다. 공격자 함수는 공격에 필요한 시간 및 성공 확률로 표현된다. 기본 식별 프로토콜에 대한 안전성 증명이 완료되면 일반화 된 식별 프로토콜로 확장 가능하다.
본 논문에서 제시한 식별 프로토콜은 겹선형 디피-헬만 문제에 기반하여 처음으로 제시된 식별 프로토콜이다. 키의 크기, 통신량, 신원기반 (identity-based) 기법으로의 확장가능성의 측면에서 기존의 기법과 비교할 하다. 또한 능동 공격 (active attacks)을 이용하여 제시된 프로토콜을 손상시키는 데 필요한 공격자의 자원을 정확하게 제시하고 있다. 본 논문에서 이용하는 디피-헬만 문제의 겹선형성 (bilinearity)의 구체적 예로서 베일 쌍 (Weil pairing)을 사용한다.
