Abstract
The one-wayness of linear permutations, i.e., invertible linear Boolean functions F: {0,1}n → {0, 1}n, is investigated. For linear permutations with a triangular matrix description (tlinear permutations), we prove that one-wayness, C(F−1)/C(F), is non-trivially upperbounded by 16√n, where C(.) denotes unrestricted circuit complexity. We also prove that this upper bound strengthens as the complexity of the inverse function increases, limiting the one-wayness of t-linear permutations with C(F−1) = n2/(c log2(n)) to a constant, i.e., a value that is independent of n. Direct implications for linear and also non-linear permutations are discussed. Moreover, and for the first time ever, a description is given about where, in the case of linear permutations, practical one-wayness would have to come from, if it exists.
Chapter PDF
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
V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. FaradŽev, “On economical construction of the transitive closure of an oriented graph,” Dokl. Akad. Nauk, vol. 194, pp. 487–488, 1970.
V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. FaradŽev, Engl. Transl.: Sov. Math. Dokl., vol. 11, pp. 1209–1210, 1970.
R. B. Boppana and J. C. Lagarias, “One-way functions and circuit complexity,” Information and Computation, vol. 74, pp. 226–240, 1987. Conf. version: Proc. 1st Ann. IEEE Symp. Structure in Complexity Th., pp. 51–65, 1986.
S. W. Boyack, The Robustness of Combinatorial Measures of Boolean Matrix Complexity. Ph.D. thesis, Massachusetts Inst. of Techn., 1985.
D. Coppersmith and S. Winograd, “Matrix multiplication via arithmetic progressions,” J. Symbolic Comput., vol. 9, pp. 251–280, 1990. Conf. version: Proc. 19th Ann. ACM Symp. Theory of Comput., pp. 1–6, 1987.
W. Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Trans. Inform. Theory, vol. IT-22, no. 6, pp. 644–655, Nov. 1976.
S. Goldwasser, “The search for provably secure cryptosystems,” in Cryptology and Computational Number Theory: Proc. Symp. Appl. Math., vol. 42 (C. Pomerance, ed.), pp. 89–113, Providence, RI: Amer. Math. Soc., 1990.
A. P. Hiltgen, “Constructions of feebly-one-way families of permutations,” Advances in Cryptology: Proc. Auscrypt'92, Springer, pp. 422–434, 1993.
A. P. Hiltgen, Cryptographically Relevant Contributions to Combinational Complexity Theory, vol. 3 of ETH Series in Information Processing, ed. J. L. Massey. Konstanz: Hartung-Gorre, 1994. Reprint of: Ph.D. thesis no. 10382, Swiss Federal Institute of Technology, ETH-Zürich, 1993.
A. P. Hiltgen and J. Ganz, “On the existence of specific complexity-asymmetric permutations,” Technical Report, Signal and Inform. Proc. Lab, ETH-Zürich, 1992.
R. Impagliazzo and M. Luby, “One-way functions are essential for complexity based cryptography,” Proc. 30th Ann. IEEE Symp. Foundations of Computer Sci., pp. 230–235, 1989.
J. L. Massey, “The difficulty with difficulty,” A Guide to the Transparencies from the Eurocrypt '96 IACR Distinguished Lecture, Signal and Inform. Proc. Lab., ETH Zürich, 1996. Available from http://www.iacr.org/conferences/ec96/massey.html.
A. Menezes, P. van Orschot, and S. Vanstone, Handbook of Applied Cryptography. CRC-Press Series on Discrete Mathematics and its Applications, CRC-Press: Boca Raton, 1997.
W. J. Paul, “Realizing Boolean functions on disjoint sets of variables,” Theoret. Comput. Sci., vol. 2, pp. 383–396, 1976.
V. Strassen, “Algebraic complexity theory,” in Handbook of Theoretical Computer Science, vol. A (J. van Leeuwen, ed.), ch. 11, Amsterdam: Elsevier, 1990.
C. Sturtivant and Z. Zhang, “Efficiently inverting bijections given by straight line programs,” Proc. 31th Ann. IEEE Symp. Foundations of Computer Sci., pp. 327–334, 1990.
D. Uhlig, “On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements,” Matemat. Zametki, vol. 15, no. 6, pp. 937–944, June 1974.
D. Uhlig, Engl. Transl.: Math. Notes Acad. Sci. USSR, vol. 15, pp. 558–562, 1974.
I. Wegener, The Complexity of Boolean Functions. New York: Wiley (Stuttgart: Teubner), 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hiltgen, A.P. (1998). Towards a better understanding of one-wayness: Facing linear permutations. In: Nyberg, K. (eds) Advances in Cryptology — EUROCRYPT'98. EUROCRYPT 1998. Lecture Notes in Computer Science, vol 1403. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054136
Download citation
DOI: https://doi.org/10.1007/BFb0054136
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64518-4
Online ISBN: 978-3-540-69795-4
eBook Packages: Springer Book Archive