2011 | OriginalPaper | Buchkapitel
Almost Optimum t-Cheater Identifiable Secret Sharing Schemes
verfasst von : Satoshi Obana
Erschienen in: Advances in Cryptology – EUROCRYPT 2011
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In Crypto’95, Kurosawa, Obana and Ogata proposed a
k
-out-of-
n
secret sharing scheme capable of identifying up to
t
cheaters with probability 1 −
ε
under the condition
$t \leq \lfloor$
(
k
–1)/3. The size of share
$|{\cal V}_i|$
of the scheme satisfies
$|{\cal V}_i|$
=
$|{\cal S}|/\epsilon^{t+2}$
, which was the most efficient scheme known so far. In this paper, we propose new
k
-out-of-
n
secret sharing schemes capable of identifying cheaters. The proposed scheme possesses the same security parameters
t
,
ε
as those of Kurosawa
et al..
The scheme is surprisingly simple and its size of share is
$|{\cal V}_i|=|{\cal S}|/\epsilon$
, which is much smaller than that of Kurosawa
et al.
and is almost optimum with respect to the size of share; that is, the size of share is only one bit longer than the existing bound. Further, this is the first scheme which can identify cheaters, and whose size of share is independent of any of
n
,
k
and
t
. We also present schemes which can identify up to
$\lfloor{(k-2)/2}$
, and
$\lfloor{(k-1)/2}$
cheaters whose sizes of share can be approximately written by
$|{\cal V}_i|\approx (n\cdot(t+1)\cdot 2^{3t-1}\cdot|{\cal S}|)/\epsilon$
and
$|{\cal V}_i|\approx ((n\cdot t\cdot 2^{3t})^2\cdot|{\cal S}|)/\epsilon^2$
, respectively. The number of cheaters that the latter two schemes can identify meet the theoretical upper bound.