**Introduction** : The basic idea behind the proposal is to integrate authentication and key distribution protocol. Immense work has been done to design a secure key distribution protocol starting with Needham Schroeder and evolving to OAKELEY, SKEME, IKE and ultimately to Diffie Hellman Protocol and PKI. Though much work has been done in the field of Data Integrity, Non Repudiation and Secrecy, password based authentication is still the Achilles heel of cryptography. In the presence of Byzantine Adversaries like Man In The Middle(MITM) even a combination of multi factor authentication and PKI fails.

**The Gap-DH problem**

Okamoto and Pointcheval formalized the gap between inverting and decisional

problem . In particular, they applied it to the Diffie-Hellman problems:

– The Inverting Diffie-Hellman Problem **(C-DH)** (a.k.a. the **Computational**

**Diffie-Hellman Problem**): given a triple of G elements (g, g^a, g^b), find the

element C = g^ab.

– **The Decision Diffie-Hellman Problem (D-DH)**: given a quadruple of G elements

(g, g^a, g^b, g^c), decide whether c = ab mod q or not.

–** The Gap Diffie-Hellman Problem (G-DH)**: given a triple (g, g^a, g^b), find the

element C = g^ab with the help of a Decision Diffie-Hellman Oracle (which

answers whether a given quadruple is a Diffie-Hellman quadruple or not).

**Bilinear maps and pairings **

The bilinear maps used in cryptography are the Weil and Tate pairings on some

elliptic curves.

Let G and G1 be two groups of order some large prime q, denoted

multiplicatively. An admissible bilinear map is a map e : G × G ->G1 that is:

– bilinear: e(ga, hb) = e(g, h)ab for all g, h 2 G and all a, b belongs to Z,

– non-degenerate: for g and h two generators of G, we have e(g, h) =/= 1,

– computable: there exists an efficient algorithm to compute e(g, h) for any

g, h belongs to G.

In the case of the Weil and Tate pairings, G is a subgroup of the additive group

of points of an elliptic curve E/Fp, and G1 is the multiplicative group of the

extension field Fp2 . However, in order to remain close to the identification scheme

of Schnorr, we choose to keep the multiplicative notation both for G and G1.

**Proposed Protocol **

From now on, G is a group in which the Gap Diffie-Hellman problem is intractable.

We assume the existence of an admissible linear map e : G×G -> G1

and G and G1 are of order q and we denote by g a generator of G.

The prover holds public parameters

g, g^a, g^n, e(g, g), v = e(g, g)^a

and a secret S = g^a. Here public key is g^n, where n is the corresponding private key. The value v is given in the public parameters in order to withdraw its computation by the verifier. The scheme we propose is a zero-knowledge proof of knowledge of the

value g^a obtained by iterating l times the algorithm. Along with the proof of knowledge the public key of the Prover is embedded into the proof so that while verifying the secret’s knowledge, the verifier will also enter the public key of prover as a parameter and verify the authenticity of the secret as well as of the key. So from now onwards, Man In The Middle cannot just forward the prover’s proof and forward his public key to establish a secure channel. MITM will be unable to separate the key part from the proof of secret provided and thus will be incapable of carrying out attacks like active phishing where he first forwards his public key to server and then user’s credentials. By using the proposed protocol server will detect that the credentials forwarded does not belong to the particular public key supplied earlier to establish the secure channel.

Step 1: Here Prover choose a random number in the prescribed range and computer W ( a mapping on G1). Then we introduce the public key in the picture and computer mapping of public key using the random number r. ‘r’ is only known to the prover and is created for obfuscation. The result V is sent to the verifier.

Step 2: The Verifier computes another random number c and sends it to Prover.

Step 3: The Prover uses c to computer a product Y on G, which comprises of secret, unknown r and public key computed r-1 times.

Step 4. The Verifier multiplies the resultant Y with the known public key of prover and computes its mapping. If the mapping is equivalent to the product of mapping received in step 1 and mapping of secret c times then the proof is accepted.

To prove the security of the scheme under the G-DH problem, we follow the

outline of general zero-knowledge proofs. Namely, we prove the completeness and the soundness of the scheme. Finally we prove the protocol is zero-knowledge.

During the proof, the prover and the verifier are modeled by Probabilistic

Polynomial time Turing Machines (PPTM).

**Completeness **

If the legitimate prover and the verifier both follow the scheme, then it always

succeeds. Indeed, at each iteration, the probability of success is equal to 1 since:

e(g, Z ) = e(g, g^r × g^ac × g^nr) = e(g, g)r+ac+nr = e(g, g)^r × e(g, g)^ac × e(g, g) ^nr=

{e(g, g) ^nr × e(g, g)^r} × e(g, g)^ac = V ×

**Zero Knowledge**

The present identification scheme satisfies the zero-knowledge property. To simulate

in polynomial time (in |I|) the communications between a real prover and

a (not necessarily honest) verifier, we use the following algorithm M :

For the simulation of one round, M randomly picks c in [[0, 2k[[, randomly

picks Y in G and computes W = e(g, Y ) × v−1. M then sends W to the verifier

which answers ˜c. If c = ˜c then the triple (W, c, Y ) is kept, otherwise M computes method.

In average, the equality c = ˜c holds after 2^k tests. To obtain, l triples, M

constructs l×2^k triples. If l×2^k is polynomial in |I|, then we obtain a polynomial

time algorithm.

**Soundness**

(under work )

Pingback: Network Security: Wrote a brief proposal on solving Man in the middle ( active phishing ) via combining Zero knowledge authentication with public key verification. Any views? - Quora