Sparse extractor families for all the entropy
Refereed conference paper presented and published in conference proceedings

替代計量分析
.

其它資訊
摘要We consider the problem of extracting entropy by sparse transformations, namely functions with a small number of overall input-output dependencies. In contrast to previous works, we seek extractors for essentially all the entropy without any assumption on the underlying distribution beyond a min-entropy requirement. We give two simple constructions of sparse extractor families. These are collections of sparse functions such that for any distribution X on inputs of sufficiently high min-entropy, the output of most functions from the collection on input X is statistically close to uniform. For strong extractor families (i.e., functions in the family do not take additional randomness) we give upper and lower bounds on the sparsity that are tight up to a constant factor for a wide range of min-entropies. We then prove that for some min-entropies weak extractor families can achieve better sparsity. We show how this construction can be used towards more efficient parallel transformation of (non-uniform) one-way functions into pseudorandom generators. More generally, sparse extractor families can be used instead of pairwise independence in various randomized or nonuniform settings where sparsity or preserving locality (i.e., parallelism) is of interest. © 2013 ACM.
著者Bogdanov A., Guo S.
會議名稱2013 4th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2013
會議開始日09.01.2013
會議完結日12.01.2013
會議地點Berkeley, CA
會議國家/地區美國
詳細描述organized by ACM,
出版年份2013
月份2
日期11
頁次553 - 560
國際標準書號9781450318594
語言英式英語
關鍵詞parallel cryptography, random matrices, randomness extraction

上次更新時間 2020-25-10 於 00:54