Comment by cyanmagenta

eieiogames@gmail.com is great (or whatever's best for you on https://eieio.games/whats-my-deal)

I think the biggest rabbit hole I went down was trying to use FEAL (which is very breakable) and exploiting the things that make it breakable. But this is very much not my area of expertise - I was learning as I was working - so it's very possible either that that was a dumb idea or that it was a great idea that I didn't figure out.

I also considered things like "focus on add lots of entropy to groups of 200 or so UUIDs, but have obvious patterns beyond that" which I think would be a reasonable strategy; here I just kind of ran out of time (I told myself I'd make this in a week)

Did some light reading about a few other things but nothing substantial

I did some fooling around with this and it seems promising.

The first problem is that, when your enciphering function is a matrix, f(0) = 0. This looks bad, but we can easily solve that problem by starting the webpage sequence at an index higher than 0.

I tried to work through a much smaller version of the problem* by hand, and it looks like this:

We have our enciphering matrix N:

    [[1 1 1 1 1]
     [1 0 0 1 1]
     [1 1 1 0 0]
     [0 1 1 1 0]
     [1 0 1 0 0]]

and our deciphering matrix D, the inverse of N:

    [[1 1 1 0 0]
     [0 0 1 0 1]
     [1 1 1 0 1]
     [1 1 0 1 0]
     [0 1 1 1 0]]

We want to find the next index whose encipherment ends in -110. This sets up a system of equations Dx = y, where x_3 = 1, x_4 = 1, x_5 = 0, and y tells us the index of x. By multiplying that out, we get:

    y_1 = x_1 + x_2 + 1
    y_2 = 1
    y_3 = x_1 + x_2 + 1
    y_4 = x_1 + x_2 + 1
    y_5 = x_2

So we can freely choose any values for y_1 and y_5, and the rest will be filled in by constraints.

Assuming we want the least possible value for y, this means we will pick y_1 = 0 and y_5 = 0, which then tells us that we want index [0 1 0 0 0], and we can jump to there. If we wanted the least possible value for y above a threshold (such as the current viewport), we'd pick y_n values accordingly.

Instinct tells me that libraries should exist for quickly solving systems of linear equations like this.

(For full full-text search, we'd need to do this several times, also finding solutions for the enciphered values 110xx, and x110x. This multiplies the work we need to do and the storage we need to use by an amount that is linear in the difference in length between the search string and the full UUID, which is still a lot better than trial-and-error.)

* I ended up doing it in 5 bits because every random 4x4 matrix I generated was noninvertible.

Hi! I do not know enough of the relevant math to appreciate what you're doing here (yet); I am going to try to do some reading to understand this better, but if you have any advice on where I should start I will gladly take it.