nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Unifying Computational Entropies via Kullback–Leibler Divergence

verfasst von : Rohit Agrawal, Yi-Hsiu Chen, Thibaut Horel, Salil Vadhan

Erschienen in: Advances in Cryptology – CRYPTO 2019

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We introduce hardness in relative entropy, a new notion of hardness for search problems which on the one hand is satisfied by all one-way functions and on the other hand implies both next-block pseudoentropy and inaccessible entropy, two forms of computational entropy used in recent constructions of pseudorandom generators and statistically hiding commitment schemes, respectively. Thus, hardness in relative entropy unifies the latter two notions of computational entropy and sheds light on the apparent “duality” between them. Additionally, it yields a more modular and illuminating proof that one-way functions imply next-block inaccessible entropy, similar in structure to the proof that one-way functions imply next-block pseudoentropy (Vadhan and Zheng, STOC ‘12).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel The Distinction Between Fixed and Random Generators in Group-Based Assumptions

Nur mit Berechtigung zugänglich

Recall that for random variables A and B with \({{\,\mathrm{Supp}\,}}(A)\subseteq {{\,\mathrm{Supp}\,}}(B)\), the relative entropy is defined by

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-26951-7_28/487852_1_En_28_IEq34_HTML.gif

Relative entropy is also commonly referred to as Kullback–Liebler divergence, which explains the standard \({{\,\mathrm{KL}\,}}\) notation. We prefer to use relative entropy to have more uniformity across the notions discussed in this work.

We used the unconventional notation y for the instance (instead of x) because our relations will often be of the form \(\varPi ^f\) for some function f; in this case an instance is some y in the range of f and a witness for y is any preimage \(x\in f^{-1}(y)\).

For the theorems in this paper that relate two notions of hardness, the notation \(t'=\varOmega (t)\) means that there exists a constant C depending only on the computational model such that \(t'\ge C\cdot t\).

As already mentioned in the introduction, this notion was in fact called “\({{\,\mathrm{KL}\,}}\)-hardness for sampling” in [21] but we rename it here to unify the terminology between the various notions discussed here.

We write \(m+1\) the total number of blocks, since in this section we will think of \(Y_{m+1}\) (also written as W) as the witness of distributional search problem and \((Y_1,\dots ,Y_m)\) are the blocks of the instance as in the previous section.

For example, the distribution \((Y_{\le m}, Y_{m+1}) = (f(U), U)\) for a function f and uniform input U is always a flat distribution even if f itself is not regular.

Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo random bits. In: Proceedings of the 23th Annual Symposium on Foundations of Computer Science (FOCS), pp. 112–117 (1982)

Brassard, G., Chaum, D., Crépeau, C.: Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci. 37(2), 156–189 (1988)MathSciNetCrossRef

Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Trans. Inf. Theor. 22(6), 644–654 (1976)MathSciNetCrossRef

Ding, Y.Z., Harnik, D., Rosen, A., Shaltiel, R.: Constant-round oblivious transfer in the bounded storage model. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 446–472. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_25CrossRef

Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792–807 (1986)MathSciNetCrossRef

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), pp. 218–229. ACM Press (1987)

Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38(1), 691–729 (1991)MathSciNetMATH

Haitner, I., Holenstein, T., Reingold, O., Vadhan, S.P., Wee, H.: Universal one-way hash functions via inaccessible entropy. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 616–637. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_31CrossRef

Haitner, I., Nguyen, M., Ong, S.J., Reingold, O., Vadhan, S.: Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM J. Comput. 39(3), 1153–1218 (2009)MathSciNetCrossRef

10.

Haitner, I., Reingold, O., Vadhan, S.: Efficiency improvements in constructing pseudorandom generators from one-way functions. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pp. 437–446 (2010)

11.

Haitner, I., Reingold, O., Vadhan, S., Wee, H.: Inaccessible entropy. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC 2009), pp. 611–620, 31 May–2 June 2009

12.

Haitner, I., Reingold, O., Vadhan, S.P.: Eciency improvements in constructing pseudorandom generators from one-way functions. SIAM J. Comput. 42(3), 1405–1430 (2013). https://doi.org/10.1137/100814421MathSciNetCrossRefMATH

13.

Haitner, I., Reingold, O., Vadhan, S.P., Wee, H.: Inaccessible entropy I: inaccessible entropy generators and statistically hiding commitments from one-way functions (2016). www.cs.tau.ac.il/~iftachh/papers/AccessibleEntropy/IE1.pdf. To appear. Preliminary version, named Inaccessible Entropy, appeared in STOC 2009

14.

Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)MathSciNetCrossRef

15.

Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pp. 230–235 (1989)

16.

Naor, M.: Bit commitment using pseudorandomness. J. Cryptol. 4(2), 151–158 (1991)CrossRef

17.

Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for NP using any one-way permutation. J. Cryptol. 11(2), 87–108 (1998). Preliminary version in CRYPTO 1992MathSciNetCrossRef

18.

Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pp. 33–43. ACM Press (1989)

19.

Nisan, N., Zuckerman, D.: Randomness is linear in space. J. Comput. Syst. Sci. 52(1), 43–52 (1996)MathSciNetCrossRef

20.

Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pp. 387–394 (1990)

21.

Vadhan, S.P., Zheng, C.J.: Characterizing pseudoentropy and simplifying pseudorandom generator constructions. In: Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, pp. 817–836 (2012). http://doi.acm.org/10.1145/2213977.2214051

22.

Yao, A.C.: Theory and applications of trapdoor functions. In: Proceedings of the 23th Annual Symposium on Foundations of Computer Science (FOCS), pp. 80–91 (1982)

Titel: Unifying Computational Entropies via Kullback–Leibler Divergence
verfasst von: Rohit Agrawal
Yi-Hsiu Chen
Thibaut Horel
Salil Vadhan
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2019
Print ISBN: 978-3-030-26950-0

Electronic ISBN: 978-3-030-26951-7

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-26951-7_28

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner