How Braids can help can protect your data.

In the world of the internet, where personal information is exchanged every day, robust encryption algorithms are of the utmost importance. While older encryption algorithms used only one “key” (the information needed to encrypt and decrypt a message), modern ones utilise two: a private key, which is never shared, and a public key, which can safely be shared with others without revealing how to decrypt your messages. These two keys can be used together to send encrypted messages and allow them to be decrypted by recipients.

As an example, a popular current encryption algorithm, RSA, uses the multiple of two extremely large prime numbers as the public key (used for encryption). The private key (used for decryption) is derived from the two primes using a different method. In theory, it is possible to find the factors of the public key and derive the private key, but finding factors of numbers hundreds of digits long is, in practice, extremely time consuming for computers. It is this difficulty that prevents the RSA encryption from being broken on a reasonable time scale and keeps all our personal data safe from hackers.

This article will explore the workings of a different encryption algorithm, the AEKAP, and how the unique properties of braids and matrices over finite fields can be used to create an alternative algorithm to protect your data.

First, we must understand what is meant by braids in a mathematical context. A braid is a collection of strands that can cross over or under each other whose points of origin and endpoints are fixed, such as in the image below.

Other than the start and end points, the strands themselves can be stretched, pushed or pulled, allowing braids to be morphed into one another. For example, the two braids below are considered to be equal as the left one can be transformed into the right one by simply pushing the strand starting at point 2 to the left.

Two braids can also be vertically attached end-to-end as in the image below to produce a new braid.

This process can be thought of as analogous to multiplication in the real numbers and has properties similar to that. For example, the number 1 in the context of multiplication is the identity; it has the property that 1 * x = x * 1. A similar identity exists in the world of braids, the braid with no crosses, only going straight down.

If we multiply this braid by any other braid by the process described above, it will only make the strands longer and not introduce any new twists, but we have already stated that we can shorten the strands while keeping the braid the same, so this does not change the actual braid itself.

In addition, every real number x, x ≠ 0 has an inverse 1/x such that x * 1/x = 1/x * x = 1. Likewise, each braid also has an inverse. This inverse can be taken by flipping the braid upside down. Adding this inverse to the original braid results in the identity, as illustrated below.

Taking the original braid

And multiplying by the inverse braid

Gives us a braid that we can morph into the identity braid (pull the first strand to the left and the second strand to the right)

A common notation for braids in order to avoid having to draw the braid itself each time is to use braid generators. A generator is a single crossing of two adjacent strands. For example, for a braid of 4 strands, the generators b₁, b₂, b₃ are shown below,

Each of these generators involve the left braid going over the right braid, but the reverse is also possible, so it is necessary for us to also have their inverses, b₁⁻¹, b₂⁻¹, b₃⁻¹ which have the left going under the right,

Now that we have these generators, we can write each braid as a product of braid generators, called a braid word. For example, the braid β

Can be written as the braid word β = b₁⁻¹b₂b₃b₂⁻¹

Viewing braids as products of generators allows us to understand more about them. The identity we explored earlier

Can be expressed in terms of generators as b₂b₁b₂ = b₁b₂b₁, and more generally as bₙ₊₁bₙbₙ₊₁ = bₙbₙ₊₁bₙ. Another property that emerges when dealing with braids of at least 4 strands is called far commutativity.

Since the crossings can be pulled up and down, the two braids above are actually equal, giving us the identity b₁b₃ = b₃b₁ or, more generally, bₖbⱼ = bⱼbₖ if |k - j| ≥ 2.

Braids are also intimately connected with permutations. A permutation of a set of points, such as {1,2,3,4} is the term for a shuffle of these points. An example of this is a permutation  that shuffles these points in the way

1 → 2, 2 → 3, 3 → 4, 4 → 1

The connection between this and braids is quite intuitive if we now consider the braid β

Following the strands of β, we see that this braid actually shuffles the points in the same way as our permutation  from before. This means that the braid  has produced a permutation of the set {1,2,3,4}. This connection between the infinite group of braids of  strands and the finite group of permutations of the set {1, 2, …, n} is one of the properties that allows for cryptographic applications such as the AEKAP protocol, which we can now discuss meaningfully using this basis.

The AEKAP conducts operations over a finite field, so it is necessary to explain this. A finite field can be thought of as a restriction of the numbers available. As an example, using the set F₇ = {0, 1, 2, 3, 4, 5, 6} means that you may only use the numbers 0 through 6. Addition and multiplication are defined using mod notation, meaning that

a = b mod p

Where a is the remainder when b is divided by p. For example,

29 = 1 mod 7

All operations over a finite field are conducted mod p, where p is the number of elements. Thus, operations in the field F₇ must be conducted mod 7. Other than this restriction, finite fields can be used the same way as the real numbers, you can have matrix entries in them, polynomials can have coefficients in them, etc.

We have said that each braid β with N strands can be made up of braid generators bₙ. Each of these single crossings can also be associated with a permutation as discussed above, which we will label σₙ. On top of this, each bₙ can be associated with a matrix whose entries are polynomials in the variables {t₁, t₂, ..., tₙ}. The matrix associated with each generator is called the coloured Burau matrix of bₙ and is written as CB(bₙ). Taking the example of braids on 4 strands, we have the matrices

With these tools at our disposal, we can define the product of any two coloured Burau/permutation pairs with the operation °

Where

Represents the permutation σ₁ acting on the matrix, shuffling {t₁, t₂, t₃, t₄} the same way it would shuffle {1, 2, 3, 4}. Therefore,

And the dot notation · represents matrix multiplication and permutation composition, as appropriate. The coloured Burau matrices for the inverse generators also arise from the above equation, and are

We can thus define the pair (CB(β), σᵦ) for any braid β which is written as the product of generators

Through repeated use of this operation

This allows us to associate a permutation and coloured Burau matrix to any braid, not only the generators and lets us move to cryptographic applications.

To use this cryptographically, we must first introduce another operation. If we choose 4 non-zero field elements from F₇ to be {τ₁, τ₂, τ₃, τ₄} ⊂ F₇, which we will call t-values, then the notation

Means that we substitute the t-values into the polynomial, such that

This can also be used for matrices with polynomial entries in the same way, simply substituting in the t-values. Next, we define the operation of E-multiplication. This will take two ordered pairs

Where M is a 4x4 matrix with entries in F₇, σ₀ is a permutation of the set {1, 2, 3, 4}, β is a braid with 4 strands, and σᵦ is the permutation associated with β. Note that the number of strands and the finite field can be larger (and probably should be for any serious applications) but these parameters are being used to illustrate the process.

The output given by E-multiplication, using the notation

Is another ordered pair, with M' being another 4x4 matrix with entries in F₇ and σ' is another permutation of the set {1, 2, 3, 4}.

When β is a single generator bᵢ, we can define the output of E-multiplication as

For the general case, when β can be any n-stranded braid, written as the product of generator

E-multiplication can be defined using an iterative procedure, such that

All the arithmetic in this process is performed over the finite field chosen, in this example, F₇. Thus, for example, -1 = 6 mod 7.

The AEKAP is a procedure that allows two users, Alice and Bob, to evaluate a shared secret k that can be used in authentication using their own private key and the public key of the other user.

Each user, for example, Alice, will generate a matrix with finite field entries Mₐ and a braid βₐ. Crucially, although this braid has n strands, Alice will only use the first n/2 strands to form her braid. This pair (Mₐ, βₐ) will form Alices private key.

Bob will then do the same, generating his private key (Mₚ, βₚ), generating βₚ from the remaining part of the braid group (the last n/2 strands)

Using the notation id for the identity permutation (which doesn’t shuffle anything), Alice and Bob can generate their public keys using the formula

Then, Alice can evaluate the shared secret k by performing the operation

And Bob will evaluate

Although the proof of this is beyond this article, these two computations will both result in the same shared secret k, mostly due to two key features. The matrices Mₐ and Mₚ are chosen specifically to have the property that Mₐ · Mₚ = Mₚ · Mₐ. On top of this, the parts of the braid group assigned to Alice and Bob are also chosen so that they take advantage of the property of far commutativity mentioned before, so that βₐ · βₚ = βₚ · βₐ. Overall, both Alice and Bob are able to arrive at the same shared secret without revealing enough information for others to uncover it. This shared secret can then be used as an encryption key or as some kind of authentication, to keep Alice and Bob’s data safe.

This alternative algorithm can allow for encryption similar to that of the traditional RSA algorithms but is based on the properties of braids instead of large numbers. This protocol has several advantages over the RSA, but also some significant downsides. This process, although it seems more complicated, is actually much more efficient with computing resources, and can be used more effectively on fairly small-scale devices. On top of this, with the advent of quantum computing, it has already been proven that RSA encryptions can be easily broken with something called Shor’s algorithm – seriously undermining its long-term viability. However, the current applications of AEKAP are not generally completely trusted for a variety of reasons.

The RSA encryption has been mathematically proven to have no faster solution with traditional computers than is currently known, while the AEKAP relies on assumptions that it is hard to crack, with no underlying mathematical proof. In addition, there have been a few successful attacks against the AEKAP. Although some people maintain that with proper parameter choices, these attacks would not succeed, it has nonetheless harmed the perception of AEKAP. In addition, some of the parameter choices recommended would undermine the efficiency of the protocol, which is its primary advantage.

Ultimately, braid-based encryption is unlikely to ever be widely implemented in the form described in this article due to the disadvantages and history of being broken, but it is currently being used in a limited capacity in certain products in which it is the most efficient option available. Braids are nevertheless fascinating pieces of mathematics, and other applications to cryptography are in research, which have the possibility to surpass the AEKAP in practical applications.

-Nikolai Veitman