TY - JOUR

T1 - One-way permutations, computational asymmetry and distortion

AU - Birget, Jean Camille

N1 - Funding Information:
✩ Supported by NSF grant CCR-0310793. Some of the results of this paper were presented at the AMS Section Meeting, October 21–23, 2005, Lincoln, Nebraska (http://www.ams.org/amsmtgs/2117_program.html), and at the conference “Various Faces of Cryptography,” 10 November 2006 at City College of CUNY, New York. The first version of the paper appeared in http://arxiv.org/abs/0704.1569 (12 April 2007). E-mail address: [email protected].

PY - 2008/12/1

Y1 - 2008/12/1

N2 - Computational asymmetry, i.e., the discrepancy between the complexity of transformations and the complexity of their inverses, is at the core of one-way transformations. We introduce a computational asymmetry function that measures the amount of one-wayness of permutations. We also introduce the word-length asymmetry function for groups, which is an algebraic analogue of computational asymmetry. We relate combinational circuits to words in a Thompson monoid, over a fixed generating set, in such a way that circuit size is equal to word-length. Moreover, combinational circuits have a representation in terms of elements of a Thompson group, in such a way that circuit size is polynomially equivalent to word-length. We show that circuits built with gates that are not constrained to have fixed-length inputs and outputs, are at most quadratically more compact than circuits built from traditional gates (with fixed-length inputs and outputs). Finally, we show that the computational asymmetry function is closely related to certain distortion functions: The computational asymmetry function is polynomially equivalent to the distortion of the path length in Schreier graphs of certain Thompson groups, compared to the path length in Cayley graphs of certain Thompson monoids. We also show that the results of Razborov and others on monotone circuit complexity lead to exponential lower bounds on certain distortions.

AB - Computational asymmetry, i.e., the discrepancy between the complexity of transformations and the complexity of their inverses, is at the core of one-way transformations. We introduce a computational asymmetry function that measures the amount of one-wayness of permutations. We also introduce the word-length asymmetry function for groups, which is an algebraic analogue of computational asymmetry. We relate combinational circuits to words in a Thompson monoid, over a fixed generating set, in such a way that circuit size is equal to word-length. Moreover, combinational circuits have a representation in terms of elements of a Thompson group, in such a way that circuit size is polynomially equivalent to word-length. We show that circuits built with gates that are not constrained to have fixed-length inputs and outputs, are at most quadratically more compact than circuits built from traditional gates (with fixed-length inputs and outputs). Finally, we show that the computational asymmetry function is closely related to certain distortion functions: The computational asymmetry function is polynomially equivalent to the distortion of the path length in Schreier graphs of certain Thompson groups, compared to the path length in Cayley graphs of certain Thompson monoids. We also show that the results of Razborov and others on monotone circuit complexity lead to exponential lower bounds on certain distortions.

KW - Combinatorial group theory

KW - Complexity

UR - http://www.scopus.com/inward/record.url?scp=54449096932&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=54449096932&partnerID=8YFLogxK

U2 - 10.1016/j.jalgebra.2008.05.035

DO - 10.1016/j.jalgebra.2008.05.035

M3 - Article

AN - SCOPUS:54449096932

SN - 0021-8693

VL - 320

SP - 4030

EP - 4062

JO - Journal of Algebra

JF - Journal of Algebra

IS - 11

ER -