Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Compact Attribute-Based Encryption and Signcryption for General Circuits from Multilinear Maps Read chapter Read first chapter

2015 | OriginalPaper | Chapter

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

Author : Maciej Skórski

Published in: Progress in Cryptology -- INDOCRYPT 2015

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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.
This extends the result of Trevisan, Tulsani and Vadhan (CCC ’09), who proved a special case when Z is empty.
Our technique is based on the standard min-max theorem combined with a new convex \(L_2\)-approximation result resembling the well known result due to Maurey-Jones-Barron.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Non-malleable Extractors with Shorter Seeds and Their Applications
next chapter BitCryptor: Bit-Serialized Flexible Crypto Engine for Lightweight Applications
Appendix
Available only for authorised users
Footnotes
1
There are two ways to define conditional min-entropy as explained in Sect. 2. Our result holds in any case.
 
2
Here we slightly abuse the notation and for simplicity write \(\exp (\cdot )\) meaning the exponential function at such a base such that the written inequalities are valid.
 
3
The constant 6 can be replaced by 1, and even by any arbitrary small number, at the price of increasing the constant hidden under the asymptotic notation.
 
4
The constant 6 can be replaced by 1, and even by any arbitrary small number, at the price of increasing the constant hidden under the asymptotic notation.
 
Literature
[Bar93]
Barron, A.R.: Universal approximation bounds for superpositions of a sigmoidal function. IEEE Trans. Inf. Theory 39(3), 930–945 (1993)MATHMathSciNetCrossRef
[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
Metadata
Title
Efficiently Simulating High Min-entropy Sources in the Presence of Side Information
Author
Maciej Skórski
Copyright Year
2015
Book
Progress in Cryptology -- INDOCRYPT 2015

Print ISBN: 978-3-319-26616-9

Electronic ISBN: 978-3-319-26617-6

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-26617-6_17

Premium Partner

    Image Credits