Algorithms via geometry

Configuration spaces and their geometry

For a fixed natural number n and manifold X, the configuration space \mathrm{Conf}^n X is space of all tuples of n distinct points in X, i.e. we may think of it as the open manifold X^n - \Delta, where here $\latex \Delta$ denotes the extended diagonal consisting of all n-tuples where the values of at least two coordinates coincide.

Configuration spaces arise naturally in the consideration of certain problems in physics, and more recently and more concretely in robotics: here, for instance, the manifold X may be taken to be the space our n robots are moving around, and then \mathrm{Conf}^n X represents all the possible combinations (“configurations”) of positions which the robots can occupy at any point in time. A path in $latex \mathrm{Conf}^n X$ then represents a set of possible simultaneous trajectories, and so the study of the configuration space and its properties becomes useful to motion planning.

More broadly, we may consider more general configuration spaces which represent the possible positions, or more general states, of a given robotic (or other) system, and think of paths in these configuration spaces as ways for the system to move from one position / state to another.

Sometimes the configuration spaces can be CAT(0), or even cubulated (i.e., in this context, made homeomorphic or maybe even bi-Lipschitz to a CAT(0) cube complex), and that can be convenient for developing algorithms to solve corresponding problems in robotics.This is the case, for instance, for a model robotic arm operating in a tunnel.

A slightly different application in which non-positively curved configuration spaces have also made an appearance is to phylogenetic trees.

Comparisons in image spaces

Suppose we have a collection of images of comparable two-dimensional surfaces, say neural images of the exterior surface of the human brain, or shapes of various animal bones, and we wish to compare them in some way, or perhaps obtain some “best match” mapping between a given neural image and some standard structural template/s.

This sounds very much like the question asked and addressed by Teichmüller theory: what are the natural maps between two different geometries on the same topological surface? In the case of higher-genus surfaces, the answer that Teichmüller theory gives is “extermal quasiconformal maps”, and more generally, and indeed something which forms an important part of the backdrop for Teichmüller theory in the first place, uniformization tells us that any compact surface is conformally equivalent to a sphere, torus, or hyperbolic surface.

Hence conformal maps and their geometry become natural tools in this sort of shape analysis, and quasiconformal maps (and possibly Teichmüller theory) can come into the picture when either discrete approximations or higher-genus surfaces are involved. Notions of distance between shapes, based on some notion of deformation energy, or on quasiconformal constants, can be useful in making quantitative statements such as “this shape is closer to model shape A than to model shape B.”

Cryptography from geometric group theory

Non-commutative cryptography uses cryptographic primitives, methods and systems based on non-commutative algebraic structure, as opposed to most familiar cryptographic systems, which are based on the commutative algebra underlying number theory.

Many of the protocols are very similar or analogous to those in more familiar (“commutative”) cryptographic systems, the main difference being that the hard (or, in many cases, presumed-to-be-hard based on existing evidence—rigorous cryptanalysis is still in many cases an open problem) problems underlying the security of the proposed primitives and/or systems come from group theory, or the theory of other non-commutative algebraic structures.

For instance, here is a general protocol for encryption / decryption: let G be a group, and let and B be commuting subgroups—i.e. ab = ba for all a \in A, b \in B, or in other words A \subset N_G(B), B \subset N_G(A), and fix x \in G (to be made public.) Alice and Bob choose secret keys a and b from A and publish y = x^a, z = x^b as public keys.

To send an encrypted message m, Alice picks a random r \in B and sends (x^r, H(z^r) \oplus m), where is some hash function and \oplus denotes XOR.

To recover the plaintext, Bob computes z^r = (x^b)^r = x^{br} = (x^r)^b and then m = H(z^r) \oplus m \oplus H(Z^r).

In the commutative setting, where we interpret G as (some finite quotient of) a integer ring and x^r as exponentiation, the security of this protocol would depend on the difficulty of finding discrete logarithms.

In the non-commutative setting, in a somewhat egregious abuse of notation, we interpret x^r as conjugation, and then the security of the protocol would depend on the difficulty of the conjugacy search problem (i.e. given z, t \in G, find r \in G s.t. t = rzr^{-1}.)

The difficulty of the conjugacy search problem in a given group, as well as other desirable properties (from either a security or an implementation standpoint), such as efficiently solvable word problem, computable normal forms, and super-polynomial growth function, is something that is often most (or at least more) easily studied using geometric methods.

Hence some of the groups which have been suggested in the context of this application: braid groups, Grigorchuk’s group, Thompson’s group/s, Artin groups, free groups, etc.

Other (apparently, or provably) difficult problems arising in geometric group theory may also be used, e.g. subgroup isomorphism in RAAGs (although this may potentially be less tenable in light of Babai’s recent breakthrough in graph isomorphism) or subgroup distortion in hyperbolic groups.

Non-commutative cryptography is still in many ways a nascent field; there are few concrete manifestations—the Algebraic Eraser is a rare example of one—and its security is presumed but yet to be fully tested—as demonstrated by the ongoing debate over the security of the Algebraic Eraser. Perhaps partly due to the relative lack of real-world applications, and partly due to the novelty of the field, cryptanalysis and work to establish the security of proposed protocols has been relatively slow in coming, although such work does exist.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s