Cryptography Reference
In-Depth Information
2.4 Strongly Unforgeable One-Time Signature
We now review the definition and the security of signature schemes. A signature
scheme
Σ
=(
Gen
,
Sign
,
Ver
) consists of three PPT algorithms .
Gen
takes as
input a parameter
λ
, it outputs a verification key
vk
and a signing key
sk
,
(
vk, sk
)
←
Gen
(
λ
).
Sign
takes as input a signing key
sk
, and a message
m
,it
outputs a signature
σ
←
Sign
(
sk, m
).
Ver
takes as input a verification key
vk
,a
message
m
, and a signature
σ
, it outputs 0
/
1
←
Ver
(
vk,m,σ
).
We define the strong existential unforgeability under one-time chosen message
attack. Consider the following experiment between a challenger and an adversary
A
:
Experiment Exp
ots
-
suf
-
cma
Σ,A
(
λ
)
(
vk, sk
)
←
Gen
(
λ
)
←A
SIGN
(
sk,·
)
(
find,vk
)
If
Ver
(
vk, m
∗
,σ
∗
) = 1, then return 1 else return 0
where the oracle
SIGN
(
sk, m
) returns
σ
(
m
∗
,σ
∗
)
←
Sign
(
sk, m
)and
A
mayonlymake
at most one query to oracle
SIGN
(
sk,
·
).
A
is said to win the Experiment if (1)
Ver
(
vk, m
∗
,σ
∗
)=1;(2)(
m, σ
)
=(
m
∗
,σ
∗
). We define the advantage of
A
in
the above experiment as
Adv
ots
-
suf
-
cma
Σ,A
(
λ
)=Pr[
Exp
ots
-
suf
-
cma
Σ,A
(
λ
)=1]
.
A
one-time signature scheme
Σ
is said to be strongly unforgeable under chosen
message attacks if the advantage function is negligible in
λ
for all PPT
A
.
3M inCon ru on
We describe our construction in this section. In [10], Dodis and Katz provided a
formal definition of multiple encryption, and pointed out that threshold encryp-
tion is an application of multiple encryption. They also show how to construct
a scheme with their highest security, i.e. strong MCCA. In this section we use
weaker components to construct threshold schemes.
Let
=(
TGen
,
TEnc
,
TDec
) be a tag-based encryption,
SS
=(
Share
,
Rec
)
be a secret sharing scheme,
Σ
=(
Gen
,
Sign
,
Ver
) be a one-time signature scheme.
We assume that the shares of
TBE
SS
are in the message space of
TBE
,andthe
verification key is in the tag space of
TBE
. We construct a generic threshold
encryption scheme as follows:
ThGen
:
For
i
=1
, ..., n
,Let(
pk
i
,dk
i
)
←
TGen
(
λ
), and set
PK
=(
pk
1
, ..., pk
n
),
and
−−
SK
=(
dk
1
, ..., dk
n
). Send decryption key
dk
i
to server
i
by a trusted
dealer.
ThEnc
:
Given a plaintext
m
.Let(
s
1
, ..., s
n
)=
Share
(
m
), and (
vk, sk
)
←
Gen
(
λ
),
use
vk
as the tag for tag-based encryption. Set
c
i
=
TEnc
(
pk
i
,vk,s
i
), then,
compute the signature
σ
=
Sign
(
sk, c
1
, ..., c
n
). It outputs
c
=(
c
1
, ..., c
n
,
vk, σ
).
ThDec
:
Given a ciphertext
c
. For each server
i
,parses
c
as (
c
1
, ..., c
n
,vk,σ
), and
checks the signature. If
Ver
(
vk, c
1
, ..., c
n
,σ
) = 0, output
; else computes
s
i
=
TDec
(
dk
i
,vk,c
i
) using the private key
dk
i
. It returns the decryption
share
δ
i
=
s
i
.
⊥
