Provably secure identification protocol based on the bilinear diffie-hellman problem

Abstract

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 e...