Information Technology Reference
In-Depth Information
parameters (shares). The parameters should be very specific in order to prevent
the adversary from forging the authentication scheme.
Hence, the construction is based on three equations of three unknowns, and
therefore, using Lagrange interpolation function it is possible to determine a
unique polynomial
f
(
x
) of three parameters and of degree two:
2
f
(
x
)=
f
0
+
f
1
x
+
f
2
x
3 An Authentication Scheme
We start with the following authentication scheme. The main components of the
scheme are the (3,3) Shamir secret sharing scheme, an intractable hash func-
tion
H
and the Die-Hellman public-key system. The hash function is used as
a one-way function, and it should be a provable-secure hash function such as
SHA-1 [7] (the function takes an arbitrary random length bitstring and pro-
duces a string of 160 bits of message digest). The Die-Hellman cryptosystem
is used to generate public keys [4]. The public keys of the signer and the veri-
fier are used as shares in the Shamir secret sharing system, and at same time
they provide strong authentication and mutual correspondence between the two
communication parties.
As mentioned in section 2, the idea is to treat the message as a secret share,
and associate a number of parameters to the secret. The challenge for the verifier
is to reconstruct the secret based on the knowledge of the shares, much as any
secret sharing technique.
3.1 The Scheme
The scheme first establishes a Die-Hellman public-key system for both the
signer and verifier. The client uses the message, its public key, and the verifier
public key as parameters of the interpolation polynomial. As a result, we compute
the signature and hide the message as a secret. The verifier has to recompute
the secret based on its public key, client (signer) public key, and the signature.
If the secret and the message are the same, the authentication is accepted, as
illustrated in the following scheme.
Initialization
1. construct Die-Hellman public-key system by choosing
g
as primitive ele-
ment in
GF
(
q
), private keys
x
a
for the sender and
x
b
for the verifier.
2. let
y
a
=
g
x
a
and
y
b
=
g
x
b
be the public keys for the signer
A
and verifier
B
respectively.
