Cryptography Reference
In-Depth Information
=
c
∗
, which is not allowed
to ask in selective-tag CCA security. This is a stronger security requirement
than selective-tag CCA security. In [10] the components for a threshold scheme
should achieve full-tag CCA security, while we point that for our construction,
the weaker definition is sucient.
can make decryption queries for (
τ
∗
,c
)with
c
A
2.2 Secret Sharing
SS
=(
Share
,
Rec
).
Share
(
·
A secret sharing scheme consists of two algorithms
)
takes as input a message
m
, and outputs
n
secret shares
s
1
, ..., s
n
.
Rec
(
)isa
deterministic algorithm which takes as input
n
shares
s
1
, ..., s
n
, and outputs
message
m
or
·
. The security of a secret sharing scheme is quantified by several
thresholds, we use the definition used in [10].
⊥
1.
t
p
-the
privacy
threshold. Determines the maximum number of shares which
reveal “no information” about the massage (the distribution of these shares
does not depend on the message.).
2.
t
f
-the
fault-tolerance
threshold. Determines the minimum number of cor-
rect shares which suce to recover the message, when the other shares are
missing.
3.
t
r
-the
robustness
threshold. Determines the minimum number of correct
shares which suce to recover the message, when the other shares are ad-
versarially set.
4.
t
s
-the
soundness
threshold. Determines the minimum number of correct
shares which ensure that it is impossible to recover an incorrect message
m
/
∈{
m,
⊥}
, when the other shares are adversarially set.
The above thresholds must satisfy
t
p
+1
t
r
.The
security properties corresponding to the thresholds above can all be formalized
in a straightforward way. We say the above scheme a (
t
p
,t
f
,t
r
,t
s
,n
)-secure secret
sharing scheme. We use
SS
instead of a share verification algorithm proposed in
[29]. Shamir's scheme [27] is a classical example achieves information-theoretic
privacy with
t
f
=
t
p
+ 1. In [10] they presented two methods to transform any
(
t
p
,t
f
,n
)-secure secret sharing scheme into a
robust
(
t
p
,t
f
,t
r
,t
s
,n
)-secure secret
sharing scheme, achieving optimal values
t
s
=0and
t
r
=
t
f
≤
t
f
≤
t
r
≤
n
and
t
s
≤
by using signature
schemes and commitment schemes.
2.3 Threshold Encryption
The concept of threshold encryption was first proposed in [8]. In a threshold
encryption scheme, there is a single public key, but the corresponding private
decryption key is shared among a set of decryption servers. A user who wants
to encrypt a message can run the encryption algorithm using the public key.
A user who wants to decrypt a ciphertext gives the ciphertext to the servers,
requesting a decryption share. When the user collects all the shares, he can apply
a combining algorithm to obtain the message.