Moldenhauer has proposed proposed cryptographic protocols which make use of . 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 , a key-space consisting of some large number N (say, ) of automorphisms of , and a linear congruence generator with maximal period length.
To communicate securely, Alice and Bob privately agree on a free subgroup 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 , Alice generates an equally-long string of congruences using h, and sends the ciphertext as an unreduced word in , where we implicitly identify letters in the alphabet with corresponding generators of from S. She also sends z.
To decrypt the ciphertext, Bob calculates using h and then for all and , and uses this to chunk the ciphertext into words corresponding to individual letters, which are then decrypted using the corresponding .
This effectively uses the ginormous size of and its highly noncommutative nature (or, more precisely, the difficulty of guessing given h and , but not ) 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 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 , a freely reduced word in the free group, and an automorphism of infinite order.
Alice and Bob pick private keys , and publish as their public keys .
To securely send a message m to Bob, Alice computes the freely-reduced elements and send this to Bob as the ciphertext.
Bob decrypts the message by computes .
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 , have Bob not immediately decrypt, but instead compute and send this back to Alice, and then have Alice compute . Now Bob decrypts the message by computing .
We can modify this further for use as a signature / authentication protocol: as a signature to Bob, Alice sends to Bob; Bob computes and verifies that this matches with Alice’s public key .
The security of these modified protocols are based on the difficulty of efficiently of deducing a and b or m, given only f and the images and ; 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 ? 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 , since , and both and are exchanged in the protocol. How many of these would Eve need to collect before she can try to effectively reconstruct what is? How much will the cancellation / free reduction created by concatenating signatures (or other material) to the end of messages alleviate this?