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.

Questions, Reading Notes

Cryptosystems using free group automorphisms

Moldenhauer has proposed proposed cryptographic protocols which make use of \mathrm{Aut}(F_n). Here we describe them, for the fun of it, and because a potential closer analysis of their security suggests potentially interesting problems (or perhaps exercises—I don’t know enough / haven’t spent enough time to be able to judge) regarding automorphisms of free groups.

One-time pads of free group automorphisms

Choose a free group F_q, a key-space (\phi_n)_{n=1}^N consisting of some large number N (say, 2^{128}) of automorphisms of F_q, and a linear congruence generator h: \mathbb{Z}/N \to \mathbb{Z}/N with maximal period length.

To communicate securely, Alice and Bob privately agree on a free subgroup F_U with rank equal to the alphabet size, a (minimal Nielsen-reduced freely-reduced) free generating set U, and a starting seed for the linear congruence generator.

To securely send a message m = m_1 \cdots m_z, Alice generates an equally-long string of congruences k_1 \cdots k_z using h, and sends the ciphertext \phi_{k_1}(m_1) \cdots \phi_{k_z}(m_z) as an unreduced word in F_q, where we implicitly identify letters in the alphabet with corresponding generators of F_U from S. She also sends z.

To decrypt the ciphertext, Bob calculates k_1 \cdots k_z using h and then \phi_{k_r}(u) for all 1 \leq r \leq z and u \in U, and uses this to chunk the ciphertext into words corresponding to individual letters, which are then decrypted using the corresponding \phi_{k_r}^{-1}.

This effectively uses the ginormous size of \mathrm{Aut}(F_n) and its highly noncommutative nature (or, more precisely, the difficulty of guessing \phi_{k_1}, \dots, \phi_{k_z} given h and \phi_{k_1}(m_1) \cdots \phi_{k_z}(m_z), but not k_1) for cryptographic security, although the protocol itself (a one-time pad) is not terribly sophisticated.

Vague hyperbolic language aside, the security of this system really rests on how the automorphisms \phi_i are randomly chosen. Moldenhauer proposes a system which uses binary strings, of varying lengths (details unspecified here) and maps these to Whitehead automorphisms in some systematically random way.

Question: Is the proposed method of  generating the automorphisms secure, or is it vulnerable to heuristic or other attacks?

Public-key encryption with free group automorphisms

Moldenhauer also suggests a public-key protocol: here the public parameters consist of the free group F_q, a freely reduced word w \neq 1 in the free group, and an automorphism f: F \to F of infinite order.

Alice and Bob pick private keys a, b \in \mathbb{Z}_{>0}, and publish as their public keys f^a(w), f^b(w).

To securely send a message m to Bob, Alice computes the freely-reduced elements m \cdot f^a(f^b(w)) =: c and send this to Bob as the ciphertext.

Bob decrypts the message by computes c_1 \cdot (f^b(f^a(w)))^{-1} = m \cdot f^{a+b}(w) f^{-(b+a)}(c) = m.

Security here is based on the difficulty of determining how much cancellation happens. Presumably, though, not all of the plaintext is cancelled most of the time, so there will likely be some substantial chunk of plaintext just hanging out in front, which seems … not optimal.

Slightly more secure might be to have Alice send f^a(m), have Bob not immediately decrypt, but instead compute f^{b+a}(m) and send this back to Alice, and then have Alice compute f^{-a}(f^{b+a}(m)) = f^b(m). Now Bob decrypts the message by computing m =  f^{-b}(f^b(m)).

We can modify this further for use as a signature / authentication protocol: as a signature to Bob, Alice sends f^a(f^b(w)) = f^{a+b}(w) to Bob; Bob computes f^{-b}(f^{a+b}(w)) and verifies that this matches with Alice’s public key f^a(w).

The security of these modified protocols are based on the difficulty of efficiently of deducing and b or m, given only f and the images f^a(m), f^b(m) and f^{a+b}(m); i.e. the difficulty of the (analogue of the) discrete logarithm in generic infinite cyclic subgroups of the free group.

Questions: Do generic infinite-order automorphisms of the free group actually have good properties from the standpoint of these cryptographic applications? How much cancellation can we typically expect in freely reducing m \cdot f^{a+b}(w)? Moldenhauer’s arXiv preprint doesn’t appear to address these questions, although her thesis might.

Also: if Eve observes a lot of the Alice’s comunications secured using this last protocol, she will see a lot of pairs (x, f^a(x)), since f^{a+b}(m) = f^a(f^b(m)), and both f^{a+b}(m) and f^b(m) are exchanged in the protocol. How many of these would Eve need to collect before she can try to effectively reconstruct what f^a is? How much will the cancellation / free reduction created by concatenating signatures (or other material) to the end of messages alleviate this?