Efficiently Simulating High Min-entropy Sources in the Presence of Side Information

详细信息    查看全文

• 关键词：Simulating high entropy ; Min ; entropy ; Convex \(L_2\) ; approximation
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9462
• 期：1
• 页码：312-325
• 全文大小：272 KB
• 参考文献：[Bar93]Barron, A.R.: Universal approximation bounds for superpositions of a sigmoidal function. IEEE Trans. Inf. Theory 39(3), 930–945 (1993)MATH MathSciNet CrossRef
  [BSW03] Barak, B., Shaltiel, R., Wigderson, A.: Computational analogues of entropy. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol. 2764, pp. 200–215. Springer, Heidelberg (2003)
  [CKLR11] Chung, K.-M., Kalai, Y.T., Liu, F.-H., Raz, R.: Memory delegation. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 151–168. Springer, Heidelberg (2011) CrossRef
  [CLP13] Chung, K.-M., Lui, E., Pass, R.: From weak to strong zero-knowledge and applications. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part I. LNCS, vol. 9014, pp. 66–92. Springer, Heidelberg (2015)
  [FH] Fuller, B., Hamlin, A.: Unifying leakage classes: simulatable leakage and pseudoentropy. In: Lehmann, A., Wolf, S. (eds.) Information Theoretic Security. LNCS, vol. 9063, pp. 69–86. Springer, Heidelberg (2015)
  [JP14] Jetchev, D., Pietrzak, K.: How to fake auxiliary input. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 566–590. Springer, Heidelberg (2014) CrossRef
  [SPY13] Standaert, F.-X., Pereira, O., Yu, Y.: Leakage-resilient symmetric cryptography under empirically verifiable assumptions. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 335–352. Springer, Heidelberg (2013) CrossRef
  [TTV09]Trevisan, L., Tulsiani, M., Vadhan, S.: Regularity, boosting, and efficiently simulating every high-entropy distribution. In: CCC (2009)
  [VZ13] Vadhan, S., Zheng, C.J.: A uniform min-max theorem with applications in cryptography. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 93–110. Springer, Heidelberg (2013) CrossRef
  
• 作者单位：Maciej Skórski (15)
  
  15. University of Warsaw, Warsaw, Poland
  
• 丛书名：Progress in Cryptology -- INDOCRYPT 2015
• ISBN：978-3-319-26617-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

In this paper we show that every source X having very high min-entropy conditioned on side information Z, can be efficiently simulated from Z. That is, there exists a simulator \(\mathsf {Sim}(\cdot )\) such that (a) it is efficient, (b) \((\mathsf {Sim}(Z),Z)\) and (X, Z) are indistinguishable and (c) the min-entropy of \(\mathsf {Sim}(Z)\) and X given Z is (almost, up to a few bits) the same. Concretely, the simulator achieves \((s,\epsilon )\)-indistinguishability running in time \(s\cdot \mathrm {poly}\left( \frac{1}{\epsilon },2^\varDelta ,|Z|\right) \), where \(\varDelta \) is the entropy deficiency and |Z| is the length of Z.