Here we enhance the basic protocol to solve the problems
noted in the previous section.
To make the proofs of security easier, we also include some other
values in the inputs of the hash functions. The
following is a fully secure protocol. (This protocol
is called PAK-R, as it is a slightly revised version
of the original PAK protocol from Eurocrypt 2000.)
The password is given as
,
and Alice and Bob's identites are given as A and B, respectively.
We also assume p=rq+1, and we require that q does not divide r.
Adding hq to Alice's computation of X randomizes the portion
of
outside the group generated by g. Then this
part is removed on Bob's side by raising
to
the rth power. This leaves gxr, so then we have to
remove the extra r added to the exponent by raising to the
.
Note that Bob does not have to check that X is in the group
generated by g, but only that
.
Briefly, the
reason is that the
value is a factor in the
value raised to the y by Bob, and this sufficiently randomizes
the Z value against a cheating Alice. (Of course this is proven
formally.)