Cryptography Reference
In-Depth Information
We first consider the
message privacy
in the model. A (
t
p
,n
)-threshold encryp-
tion scheme
THE
=(
ThGen
,
ThEnc
,
ThDec
,
ThCom
) consists of four algorithms:
ThGen
:
takes as input a security parameter
λ
, the number of decryption servers
n
(
≥
1), and the threshold parameter
t
p
(1
≤
t
p
≤
n
); it outputs
(
PK,
−−
SK
)
←
ThGen
(
λ, n, t
p
)
,
where
PK
is the public encryption key, and
−−
SK
=(
SK
1
, ..., SK
n
) is the list
of private keys. For 1
≤
i
≤
n
, the private key
SK
i
is given to server
i
by a
trusted dealer.
ThEnc
:
takes as input a public key
PK
and a message
m
, and outputs a cipher-
text
ψ
←
ThEnc
(
PK,m
)
.
ThDec
:
takes as input a private key
SK
i
, and a ciphertext
ψ
, and outputs a
decryption share
δ
i
←
ThDec
(
SK
i
,ψ
)
.
ThCom
:
(deterministic) takes as input all the the decryption shares
S
=(
δ
1
, ...δ
n
),
and outputs the message
m
=
ThCom
(
S
)
.
For correctness, we need that for any plaintext
m
, any output
ψ
of
ThEnc
(
PK,m
),
and all decryptions
S
of
ψ
,wehave
ThCom
(
S
)=
m
.
Data Privacy.
We define the security of threshold encryption formally under
chosen-ciphertext attack with
static
server corruption. Consider the following
experiment between a challenger and an adversary
A
:
Experiment Exp
the
-
cca
THE,A
(
λ
)
(
i
1
, ..., i
t
p
)
,St
0
←A
(
λ, Init
)
(
PK,
−−
SK
)
←
ThGen
(
λ
)
(
m
0
,m
1
,St
)
←A
TDEC
(
i,SK
i
,·
)
find,PK,
(
SK
i
1
, ..., SK
i
t
p
)
,St
0
,c
∗
←
ThEnc
(
PK,m
b
)
b
←A
TDEC
(
i,SK
i
,·
)
(
guess, c
∗
,St
)
If
b
=
b
then return 1 else return 0
b
←{
0
,
1
}
where the oracle
TDEC
(
i, SKi,
i
,c
) returns
δ
i
=
ThDec
(
SK
i
,c
) with the restriction
that
is not allowed to query the oracle for
c
∗
in the
guess
phase. Both messages
must be the same size. We define the advantage of
A
A
in the above experiment
(
λ
)=
2
as
Adv
the
-
cca
THE,A
Pr [
Exp
the
-
cca
THE,A
1
=1]
−
.
A threshold encryption
THE
is
said to be secure against chosen-ciphertext attacks with privacy threshold
t
p
if
the advantage function is negligible for all PPT
A
.
Decryption Robustness.
The correctness property of the threshold encryption
only ensures correct decryption when all algorithms are honestly and correctly
executed. Just as in the case of secret sharing, however, one may often desire
fault-tolerance, robustness, and/or soundness. As in the case of secret sharing,
these are parameterized by thresholds
t
f
,t
r
,t
s
, whose meaning is completely
analogous to their meaning in the case of secret sharing (described earlier). Our
constructions can achieve optimal
t
s
=0,
t
r
=
t
f
,andany
t
p
<t
f
.
