Cryptography Reference
In-Depth Information
lattices. However, we revisit their proof, and find that this strong requirement is
not necessary. In fact, a strictly weaker component, namely, public key encryp-
tion secure against selective-chosen tag attack (sTag), is already sucient.
Next, towards our goal of TPKE resilient to quantum attackers, we demon-
strate a public key encryption from lossy trapdoor functions meets this desirable
requirement [23], namely, security against selective-tag and adaptive chosen ci-
phertext attack. Note that in their paper [23], Peikert and Waters proved that the
scheme is passively chosen ciphertext secure (CCA1). However, our result shows
actually it also provides adaptive chosen ciphertext security under a selective-
tag setting. Combine the above two strategies together, we achieve an ecient
construction for TPKE from lossy trapdoor functions.
Instantiating our generic construction with lattices, we obtain a concrete
TPKE scheme under hardness of the shortest independent vector problem (SIVP).
We then compare our TPKE with some well-known schemes in the literature and
conclude our TPKE scheme is ecient.
1.1 Related Work
Desmedt first introduced the concept of threshold encryption [8]. Dodis and
Katz gave a generic construction of threshold decryption schemes [10]. The first
practical TPKE with chosen ciphertext security (CCA) [21,24,12] was proposed
by Shoup and Gennaro [29]. Canetti and Goldwasser [4] gave the first TPKE
in the standard model, but their security model was weaker than [29]. Boneh,
Boyen and Halevi proposed the first TPKE scheme with threshold decryption
without random oracles [3], but their scheme, and the subsequent schemes all
require pairings [1]. The first threshold decryption scheme based on lattice was
proposed by Bendlin and Damg ard [2].
1.2 Our Contributions
First, we show that a generic CCA secure threshold public key encryption scheme
in the standard model can be derived from tag-based public key encryption
schemes which only require weak security. Dodis and Katz proposed a generic
CCA secure construction whose components are tag-based public key encryption
schemes. While the our constructions are selective-tag CCA security for the
encryption components. We improve their results.
Next, we revisit the security of a CCA1-secure public key scheme from lossy
trapdoor functions [23], and prove that this scheme also provides selective-tag se-
curity against CCA attacks. Finally, combine the two results together, we design
an ecient TPKE scheme from lossy trapdoor functions, which can be imple-
mented using lattices. We also give comparisons among known TPKE schemes.
2
Preliminaries
In this section, we review some useful notations and definitions.
Notations.
If
x
is a string, then
|
x
|
denotes its length, while if
S
is a set then
|
S
|
denotes its size. If
S
is a set then
s
←
S
denotes the operation of picking an
