International Journal of Network Security, Vol.14, No.1, PP.116–122, Jan. 2012 116
Publicly Verifiable Secret Sharing Schemes Using
Bilinear Pairings
Youliang Tian
1,2
, Changgen Peng
2
, and Jianfeng Ma
1
(Corresponding author: Changgen Peng)
Key Laboratory of Computer Networks and Information Security
1
Ministry of Education, Xidian University, Xi’an 710071, China
(Email: youliangtian@163.com)
College of Science, Guizhou University, Guiyang 550025, China
2
(Received Sep. 4, 2010; revised and accepted DEc. 26, 2010)
Abstract
A non-interactive, simple and efficient publicly verifiable
secret sharing (PVSS) is constructed based on the bi-
linear pairing on elliptic curves, which has all advan-
tages of Schoenmakers’ PVSS in [15]. Moreover, in the
scheme’s distribution of shares phase, only using bilinear-
ity of bilinear paring, anybody can verify that the par-
ticipants received whether correct shares without imple-
menting interactive or the non-interactive protocol and
without construction so called witness of shares applying
Fiat-Shamir’s technique. Subsequently, in the scheme’s
reconstruction of secret phase, the released shares may
be verified by anybody with the same method. Since the
PVSS need not to implement non-interactive protocol and
construct witness in order to prevent malicious players,
hence it reduces the overhead of communication. Finally,
the PVSS has been extensions to the case without a dealer
(or without a trusted center). A distributive publicly ver-
ifiable secret sharing (DPVSS) is proposed, which also
reduces the overhead of communication. Analysis shows
that these schemes are more secure and effective than oth-
ers, and it can be more applicable in special situation.
Keywords: Bilinear pairing, cryptography, Diffie-Hellman
assumption, publicly verifiable secret sharing, secret shar-
ing
1 Introduction
Secret sharing schemes were introduced independently
in [16] and [1] and since then much work has been put
into the investigation of such schemes. In a Secret Sharing
scheme, the dealer shares a secret among n participants
such that only specified subsets of the whole participants’
can later recover the secret. In the so called (k, n) thresh-
old model for secret sharing, the sharing is done so that
subsets of k or more participants can later reconstruct
the secret, while subsets of at most k − 1 participants
have no information about it. The basic model for secret
sharing distinguishes at least two protocols: (i) a distri-
bution protocol in which the secret is distributed by a
dealer among the participants, and (ii) a reconstruction
protocol in which the secret is recovered by pooling the
shares of a qualified subset of the participants. In the
basic scheme (e.g., [1, 16] for threshold secret sharing) we
assumed that the dealer and all participants is reliable,
however, a misbehaving dealer or participants can deal
inconsistent shares to the participants, from which they
will not be able to reconstruct a secret. To prevent such
malicious behavior of the dealer and players, one needs to
implement a protocol through which a consistent dealing
can be verified by the recipients of shares. Thus basic
schemes solve the problem for the case that all players in
the scheme are honest.
In verifiable secret sharing (VSS) [6, 7, 13] the object
is to resist malicious players, such as (i) a dealer send-
ing incorrect shares to some or all of the participants,
and (ii) participants submitting incorrect shares during
the reconstruction protocol. Verifiable secret sharing or
the basic schemes such as [1, 14, 16] all require the avail-
ability of private channels from the dealer to each of the
participants individually. However, communication over
the private channels is clearly not publicly verifiable. In
publicly verifiable secret sharing (PVSS), as intro duced
by Stadler [17], it is an explicit goal that not just the par-
ticipants can verify their own shares, but that anybody
can verify that the participants received correct shares.
It is explicitly required that can be verified publicly. In
fact, the VSS scheme of [6] already achieved this prop-
erty. Hence, publicly verifiable secret sharing (PVSS) is
a special kind of secret sharing, in which any-body, not
just the participants, can verify whether the dealer dis-
tributed correct to each participants at the secret distri-
bution phase and whether each participant releases the
correct share at reconstruction phase. Furthermore, in
an efficient PVSS, private channels are not assumed be-
tween the dealer and the participant. In the reference [10],