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?

Standard