Information Technology Reference
In-Depth Information
et. al.
[1], and others [8] have studied the fundamentals of this cryptographic
primitive and have set its security proofs.
In this paper, we propose an innovative method of designing an authenti-
cation and signcryption schemes based on secret sharing technique. We begin
by describing the idea with an authentication scheme. Then, we introduce the
signcryption scheme, which provides privacy, authenticity, integrity and non-
repudiation, all in one shot. The distinguishing feature of the scheme is that
it introduces a new technique of digital signatures different from the classical
approaches, which are based on public-key cryptosystems or identity-based sys-
tems. Here, we exploit the shares of the secret sharing as a signature to a mes-
sage. The encrypted message and the signature require minimum space overhead,
and therefore it is superior in saving the bandwidth in congested communica-
tion channels. The verification is ecient and requires relatively small compu-
tation time. In general, the system is useful in many applications, especially in
real-time broadcast applications which require privacy and authentication with
non-repudiation property, yet with low overhead.
2 Theoretic Construction
The main structure of the system is the Shamir threshold secret sharing method
[12]. The main idea relates to the concept of verifiable secret sharing, illustrated
in [9].
Shamir's (
t, n
) threshold scheme (
t ≤ n
) is a method by which a trusted
party computes secret shares
s
i
,1
≤ i ≤ n
from initial secret
s
, such that any
t
or more users who pool their shares may easily recover
s
, but any group knowing
only
t −
1 or fewer shares may not. Shamir secret sharing is based on Lagrange
polynomial interpolation, and on the fact that a univariate polynomial
y
=
f
(
x
)
of degree
t−
1 is uniquely defined by
t
points (
x
i
,y
i
) with distinct
x
i
(since these
define
t
linearly independent equations in
t
unknowns). All calculations are done
in
GF
(
p
) where the prime
p
is selected to satisfy the security requirements.
The scheme is constructed by a trusted party. The computational cost of a
secret sharing scheme is in solving a set of linear systems of degree
t
, which is a
polynomial time complexity problem.
To establish a threshold secret sharing system, we need to determine the
number of shares and the threshold at which the signer is able to construct the
secret. Three parameters are chosen, i.e. a polynomial of degree two, because
that it is mathematically the minimum number of points which can determine
a unique solution for the Lagrange polynomial interpolation.
The idea is to treat the message as a secret, and associate a number of
parameters (shares) 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. If the verifier is able to compute the secret based on valid shares,
this proves that the message is genuine, since only unique points (shares) can
construct the polynomial. Any difference in the points would not reconstruct
the message (secret). Therefore, the sender computes the secret in terms of
