Cryptography Reference
In-Depth Information
Ecient Threshold Encryption
from Lossy Trapdoor Functions
Xiang Xie
1
,
2
,RuiXue
1
, and Rui Zhang
1
1
The State Key Laboratory of Information Security
Institute of Software, Chinese Academy of Sciences
2
Graduate University of Chinese Academy of Sciences
{
xiexiang,rxue,r-zhang
}
@is.iscas.ac.cn
Abstract.
This paper discusses the problem of building secure threshold
public key encryption (TPKE) schemes from lossy trapdoor functions,
which can in turn be built from a number of assumptions, e.g. lattices.
Our methodology is generic and our concrete instantiation is more e-
cient than previous construction.
Keywords:
threshold public key encryption, lossy trapdoor functions,
lattices.
1
Introduction
A threshold public key encryption (TPKE) scheme [8,9,13,17] distributes the
decryption power among
n
decryption servers so that
k
servers or more working
together can do the decryption. Not only TPKE itself provides useful func-
tionalities, it is also an important building block for other cryptographic prim-
itives, such as mix-net (anonymous channel) [6], public key encryption with
non-interactive opening [7,15,16]. Currently popular TPKE schemes are often
based on discrete-logarithm type or RSA type assumptions [9,29,4,3]. It is worth
emphasizing that most known TPKE schemes become insecure in the existence
of quantum attackers though they achieve good eciency. Therefore, it is both
necessary and challenging to build alternative ecient constructions of TPKE
from other assumptions valid even against quantum attackers.
In this paper, we give a new construction of TPKE from lossy trapdoor func-
tions [23], which can be implemented using a number of assumptions including
lattices. Instantiating our methodology, we obtain a TPKE scheme, which is
(slightly) more ecient than the only known TPKE based on lattices [2].
Let us briefly explain our ideas here. First recall that in [10], Dodis and Katz
proposed a generic construction of TPKE based on so-called multiple encryp-
tion techniques [31,10]. However, a prerequisite of their construction is that each
encryption component must be adaptively chosen-tag secure. We remark that
no ecient scheme was known previously on how to build such primitives using
This work is partially supported by the Fund of the National Natural Science Foun-
dation of China under Grants No. 60873260 and the National High Technology
Research and Development Program of China under Grant No. 2009AA01Z414.
