TY - GEN
T1 - Non-malleable extractors with shorter seeds and their applications
AU - Yao, Yan Qing
AU - Li, Zhou Jun
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - Motivated by the problem of how to communicate over a public channel with an active adversary, Dodis and Wichs (STOC’09) introduced the notion of a non-malleable extractor. A non-malleable extractor nmExt: {0, 1}n×{0, 1}d→ {0, 1}mtakes two inputs, a weaklyrandom W and a uniformly random seed S, and outputs a string which is nearly uniform, given S as well as nmExt(W,A(S)), for an arbitrary function A with A(S) ≠ S. In this paper, by developing the combination and permutation techniques, we improve the error estimation of the extractor of Raz (STOC’05), which plays an extremely important role in the constraints of the non-malleable extractor parameters including seed length. Then we present improved explicit construction of non-malleable extractors. Though our construction is the same as that given by Cohen, Raz and Segev (CCC’12), the parameters are improved. More precisely, we construct an explicit (1016, (formula presented)-non-malleable extractor nmExt: {0, 1}n× {0, 1}d→ {0, 1} with n = 210and seed length d = 19, while Cohen et al. showed that the seed length is no less than (formula presented)+66. Therefore, our method beats the condition “2.01 ・ log n ≤ d ≤ n” proposed by Cohen et al., since d is just 1.9 ・ log n in our construction. We also improve the parameters of the general explicit construction given by Cohen et al. Finally, we give their applications to privacy amplification.
AB - Motivated by the problem of how to communicate over a public channel with an active adversary, Dodis and Wichs (STOC’09) introduced the notion of a non-malleable extractor. A non-malleable extractor nmExt: {0, 1}n×{0, 1}d→ {0, 1}mtakes two inputs, a weaklyrandom W and a uniformly random seed S, and outputs a string which is nearly uniform, given S as well as nmExt(W,A(S)), for an arbitrary function A with A(S) ≠ S. In this paper, by developing the combination and permutation techniques, we improve the error estimation of the extractor of Raz (STOC’05), which plays an extremely important role in the constraints of the non-malleable extractor parameters including seed length. Then we present improved explicit construction of non-malleable extractors. Though our construction is the same as that given by Cohen, Raz and Segev (CCC’12), the parameters are improved. More precisely, we construct an explicit (1016, (formula presented)-non-malleable extractor nmExt: {0, 1}n× {0, 1}d→ {0, 1} with n = 210and seed length d = 19, while Cohen et al. showed that the seed length is no less than (formula presented)+66. Therefore, our method beats the condition “2.01 ・ log n ≤ d ≤ n” proposed by Cohen et al., since d is just 1.9 ・ log n in our construction. We also improve the parameters of the general explicit construction given by Cohen et al. Finally, we give their applications to privacy amplification.
KW - Extractors
KW - Non-malleable extractors
KW - Privacy amplification protocol
KW - Seed length
UR - https://www.scopus.com/pages/publications/84951871187
U2 - 10.1007/978-3-319-26617-6_16
DO - 10.1007/978-3-319-26617-6_16
M3 - 会议稿件
AN - SCOPUS:84951871187
SN - 9783319266169
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 293
EP - 311
BT - Progress in Cryptology – INDOCRYPT 2015 - 16th International Conference on Cryptology in India, Proceedings
A2 - Biryukov, Alex
A2 - Goyal, Vipul
PB - Springer Verlag
T2 - 16th International Conference on Cryptology in India, INDOCRYPT 2015
Y2 - 6 December 2015 through 9 December 2015
ER -