×

One-way functions using algorithmic and classical information theories. (English) Zbl 1261.68074

Summary: We prove several results relating injective one-way functions, time-bounded conditional Kolmogorov complexity, and time-bounded conditional entropy.
First we establish a connection between injective, strong and weak one-way functions and the expected value of the polynomial time-bounded Kolmogorov complexity, denoted here by \(E(K ^{t }(x|f(x)))\). These results are in both directions. More precisely, conditions on \(E(K ^{t }(x|f(x)))\) that imply that \(f\) is a weak one-way function, and properties of \(E(K ^{t }(x|f(x)))\) that are implied by the fact that \(f\) is a strong one-way function. In particular, we prove a separation result: based on the concept of time-bounded Kolmogorov complexity, we find an interval in which every function \(f\) is a necessarily weak but not a strong one-way function.
Then we propose an individual approach to injective one-way functions based on Kolmogorov complexity, defining Kolmogorov one-way functions and prove some relationships between the new proposal and the classical definition of one-way functions, showing that a Kolmogorov one-way function is also a deterministic one-way function. A relationship between Kolmogorov one-way functions and the conjecture of polynomial time symmetry of information is also proved.
Finally, we relate \(E(K ^{t }(x|f(x)))\) and two forms of time-bounded entropy, the unpredictable entropy \(H ^{\text{unp}}\), in which “one-wayness” of a function can be easily expressed, and the Yao\(^{+}\) entropy, a measure based on compression/decompression schema in which only the decompressor is restricted to be time-bounded.

MSC:

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
94A17 Measures of information, entropy
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Barak, B., Shaltiel, R., Wigderson, A.: Computational analogues of entropy. In: Proceedings of International Conference on Random Structures and Algorithms, pp. 200–215 (2003) · Zbl 1279.68074
[2] Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput. 13(4), 850–864 (1984) · Zbl 0547.68046 · doi:10.1137/0213053
[3] Cachin, C.: Entropy Measures and Unconditional Security in Cryptography, 1st edn. ETH Series in Information Security and Cryptography. Hartung-Gorre, Konstanz (1997) · Zbl 1059.94527
[4] Chaitin, G.: On the length of programs for computing finite binary sequences. J. ACM 13(4), 547–569 (1966) · Zbl 0158.25301 · doi:10.1145/321356.321363
[5] Cover, T., Thomas, J.: Elements of Information Theory. Wiley-Interscience, New York (1991) · Zbl 0762.94001
[6] Goldreich, O.: Foundations of Cryptography. Cambridge University Press, Cambridge (2001) · Zbl 1007.94016
[7] Goldwasser, S., Micali, S., Rivest, R.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988) · Zbl 0644.94012 · doi:10.1137/0217017
[8] Golshani, L., Pasha, E., Yari, G.: Some properties of Renyi entropy and Renyi entropy rate. Inf. Sci. 179, 2426–2433 (2009) · Zbl 1169.94331 · doi:10.1016/j.ins.2009.03.002
[9] Impagliazzo, R., Levin, L., Luby, M.: Pseudo-random generation from one-way functions. In: Proceedings of Symposium on Theory of Computing’89, pp. 12–24. ACM, New York (1989)
[10] Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography. In: Proceedings of Symposium on Foundations of Computer Science’89 (1989)
[11] Jizba, P., Arimitsu, T.: The world according to Renyi: thermodynamics of multifractal systems. Ann. Phys. 312, 17 (2004) · Zbl 1044.82001 · doi:10.1016/j.aop.2004.01.002
[12] Kolmogorov, A.: Three approaches to the quantitative definition of information. Probl. Inf. Transm. 1(1), 1–7 (1965) · Zbl 0271.94018
[13] Li, M., Vitányi, P.: An Introduction to Kolmogorov Complexity and Its Applications. Springer, Berlin (2008) · Zbl 1185.68369
[14] Longpré, L., Mocas, S.: Symmetry of information and one-way functions. Inf. Process. Lett. 46(2), 95–100 (1993) · Zbl 0770.68079 · doi:10.1016/0020-0190(93)90204-M
[15] Longpré, L., Watanabe, O.: On symmetry of information and polynomial time invertibility. Inf. Comput. 121(1), 14–22 (1995) · Zbl 0832.68059 · doi:10.1006/inco.1995.1120
[16] Lu, C., Reyzin, L.: Conditional computational entropy, or toward separating pseudoentropy from compressibility. In: Proceedings of EUROCRYPT’07, pp. 169–186 (2007) · Zbl 1141.94357
[17] Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994) · Zbl 0833.68049
[18] Pinto, A.: Comparing notions of computational entropy. Theory Comput. Syst. 45, 944–962 (2009) · Zbl 1185.68371 · doi:10.1007/s00224-009-9177-7
[19] Renner, R., Wolf, S.: Simple and tight bounds for information reconciliation and privacy amplification. In: Advances in Cryptology–ASIACRYPT 2005. Lecture Notes in Computer Science, pp. 199–216. Springer, Berlin (2005) · Zbl 1154.94471
[20] Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: Proceedings of Symposium on Theory of Computing’90, pp. 387–394. ACM, New York (1990)
[21] Solomonoff, R.: A formal theory of inductive inference, part I. Inf. Control 7(1), 1–22 (1964) · Zbl 0258.68045 · doi:10.1016/S0019-9958(64)90223-2
[22] Yao, A.: Theory and applications of trapdoor functions (extended abstract). In: Proceedings of Symposium on Foundations of Computer Science, pp. 80–91 (1982)
[23] Zvonkin, A., Levin, L.: The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Mathematics Surveys 256, 83–124 (1970) · Zbl 0222.02027 · doi:10.1070/RM1970v025n06ABEH001269
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.