Abstract
We study conditional computational entropy: the amount of randomness a distribution appears to have to a computationally bounded observer who is given some correlated information. By considering conditional versions of HILL entropy (based on indistinguishability from truly random distributions) and Yao entropy (based on incompressibility), we obtain:
-
a separation between conditional HILL and Yao entropies (which can be viewed as a separation between the traditional HILL and Yao entropies in the shared random string model, improving on Wee’s 2004 separation in the random oracle model);
-
the first demonstration of a distribution from which extraction techniques based on Yao entropy produce more pseudorandom bits than appears possible by the traditional HILL-entropy-based techniques;
-
a new, natural notion of unpredictability entropy, which implies conditional Yao entropy and thus allows for known extraction and hardcore bit results to be stated and used more generally.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Blum, M., De Santis, A., Micali, S., Persiano, G.: Noninteractive zero-knowledge. SIAM Journal on Computing 20(6), 1084–1118 (1991)
Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications (extended abstract). In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, Chicago, Illinois, 2–4 May 1988, pp. 103–112 (1988)
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)
Carter, J.L., Wegman, M.N.: Universal classes of hash functions. Journal of Computer and System Sciences 18, 143–154 (1979)
Diffie, W., Hellman, M.E.: New directions in cryptography. IEEE Transactions on Information Theory 22(6), 644–654 (1976)
Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. Technical Report 2003/235, Cryptology ePrint archive (2006), http://eprint.iacr.org , Previous version appeared at EUROCRYPT 2004
Gennaro, R., Krawczyk, H., Rabin, T.: Secure hashed Diffie-Hellman over non-DDH groups. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 361–381. Springer, Heidelberg (2004)
Goldreich, O., Levin, L.: A hard-core predicate for all one-way functions. In: Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, Seattle, Washington, 15-17 May 1989, pp. 25–32 (1989)
Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Sciences 28(2), 270–299 (1984)
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: Construction of pseudorandom generator from any one-way function. SIAM Journal on Computing 28(4), 1364–1396 (1999)
Impagliazzo, R.: Remarks in open problem session at the dimacs workshop on pseudorandomness and explicit combinatorial constructions (1999)
Lepinski, M., Micali, S., Shelat, A.: Fair-zero knowledge. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 245–263. Springer, Heidelberg (2005)
Naor, M.: Evaluation be easier than generation. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, 22-24 May 1996, pp. 74–83 (1996)
Nisan, N., Zuckerman, D.: Randomness is linear in space. Journal of Computer and System Sciences 52(1), 43–53 (1996)
Radhakrishnan, J., Ta-Shma, A.: Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Computing 13(1), 2–24 (2000)
Renner, R., Wolf, S.: Smooth rényi entropy and applications. In: Proceedings of IEEE International Symposium on Information Theory, June 2004, p. 233 (2004)
Renner, R.S., Wolf, S.: Simple and tight bounds for information reconciliation and privacy amplification. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 199–216. Springer, Heidelberg (2005)
Shannon, C.E.: A mathematical theory of communication. Bell System Technical Journal, 27, 379–423, 623–656 (1948), Reprinted in: Slepian, D. (ed.), Key Papers in the Development of Information Theory, IEEE Press, New York (1974)
Shaltiel, R.: Recent developments in explicit constructions of extractors. Bulletin of the EATCS 77, 67–95 (2002)
Trevisan, L.: Construction of extractors using pseudo-random generators (extended abstract). In: STOC, pp. 141–148 (1999)
Ta-Shma, A., Zuckerman, D.: Extractor codes. In: STOC, pp. 193–199 (2001)
Trevisan, L., Vadhan, S.P., Zuckerman, D.: Compression of samplable sources. Technical Report TR05-012, Electronic Colloquium on Computational Complexity, ECCC (2005)
Wee, H.: On pseudoentropy versus compressibility. In: IEEE Conference on Computational Complexity, pp. 29–41. IEEE Computer Society Press, Los Alamitos (2004)
Yao, A.C.: Theory and applications of trapdoor functions. In: 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, 3-5 November 1982, pp. 80–91. IEEE Computer Society Press, Los Alamitos (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hsiao, CY., Lu, CJ., Reyzin, L. (2007). Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility. In: Naor, M. (eds) Advances in Cryptology - EUROCRYPT 2007. EUROCRYPT 2007. Lecture Notes in Computer Science, vol 4515. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72540-4_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-72540-4_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72539-8
Online ISBN: 978-3-540-72540-4
eBook Packages: Computer ScienceComputer Science (R0)