Cryptography Reference
In-Depth Information
Table 1.
Comparisons among schemes
Schemes PK Size
SK Size
Ciphertext
Assumption RO Quantum
of Each
Size
Free
Attack
Sever
Resistance
SG98
(
n
+2)
|
G
|
|
Z
q
|
5
|
G
|
+2
|
Z
q
|
CDH
×
×
√
5
|
G
|
(
L
+5)
|
Z
q
|
4
|
G
|
×
CG99
DDH
√
BBH06 (
n
+4)
|
G
|
|
G
|
2
|
G
|
+
|
G
T
|
+
|
SIGN
|
DBDH
×
√
(
n
+4)
|
G
|
|
Z
q
|
2
|
G
|
+
|
G
T
|
+
|
SIGN
|
×
AT09
DBDH
√
√
γ
5
γ
2
BD10
(2
n −
1)
γ
SIVP
γ
4
√
√
2
nγ
3
log
γ
γ
2
log
γ
2
nγ
2
log
γ
Ours
SIVP
δ
γ
† n
denotes the number of the server,
γ
denotes the dimension of the lattice,
δ>
1 denotes some constant (e.g.
δ
=1
.
01) such that an approximation factor
δ
γ
for
SIVP cannot be achieved in polynomial time, and
L
denotes the number of decryption
performed before the public and secret keys need to be refreshed.
fits the definition of threshold tag-based encryption schemes [1], TTBE for short,
and achieves the selective-tag CCA security without using the one-time signature.
Briefly, a threshold tag-based encryption scheme is very similar to a threshold en-
cryption scheme, except that the encryption, decryption and combination algo-
rithms take additionally a “tag” as input. The security definition of selective-tag
CCA of TTBE is very similar to the traditional tag-based encryption.
Comparisons.
A few constructions of lossy trapdoor functions have been pro-
posed. Peikert and Waters [23] presented constructions based on the decisional
Die-Hellman (DDH) and learn with errors (LWE) assumption. Then, Rosen
and Segev [26] proposed composite residuosity assumption based constructions.
Recently Freeman et al. [14] proposed constructions based on quadratic residu-
osity assumption and
d
-Linear assumption with slight lossiness. We focus on the
construction proposed by Peikert and Waters [23] which is based on the LWE
assumption which was shown by Regev [25] and Peikert [22] to be as
worst-
case
instances of shortest independent vector problem (SIVP) and gap shortest
vector problem (GapSVP) in integer lattices. In [20] they show how to con-
struct a strongly unforgeable one-time signature from chameleon hash function.
A chameleon hash function can be obtained based on SIS assumption [5] which
is related to worst-case lattice-based assumptions such as the hardness of SIVP
problem. There is also a method [18], which is analogous to the construction of
chameleon hash, to construct commitment schemes based on SIS assumption.
Therefore, we obtain lattice based
robust
secret sharing scheme.
Table 1 shows comparisons among our scheme and other threshold schemes
[29,4,3,1,2], We take attention to the eciency between the BD10 [2] scheme
and ours. In practice, The number of servers
n
will be small, such as 7 or 10.
According to the table, when using the same large lattice dimension, the public
key size of our scheme is less than BD10 [2] by a factor
γ
2
, but with the expense
of larger secret size and ciphertext size by a factor
γ
. Overall the eciency of
our scheme is slightly better than the BD10 [2] scheme.
