Indistinguishable patterns and white-box cryptography

[NotLiving]

Is there such a thing as the following?

Two finite and stable patterns that are both constructible but that are indistinguishable from each other by the outside world.

(Simple definition of constructible as I am thinking: able to be constructed via glider synthesis.)

(Stable: returning to its original state in a finite number of steps. As these are finite patterns, aperiodicity is irrelevant here.)

Extension question: Assuming it is, is it possible to do true white-box cryptography within Life, assuming the attacker was also within Life only? That is, is it possible to build, say, a (constructible) AES encryptor with a secret key that flat-out cannot be gotten via disassembly of the pattern using an external constructor? (A moot point in practice, as someone could read out the actual cells. Still interesting in theory, though.) Or at the very least, cannot be gotten in < exponential-time, as one can "just" brute-force through all possible keys of the length to find the one the matches in exponential time.

Reason for the questions: I was thinking about mind uploading and the question of if it's necessarily possible. Which led me to the thought of "I wonder if it's possible in a simplification of physical laws. Say... Life? It being possible in Life does not necessarily map to it being possible in real life, et cetera, but it's still something interesting to think about.

[BlinkerSpawn]

Define "indistinguishable".

[biggiemac]

I imagine that two patterns are "indistinguishable" if no possible signal coming from infinity can interact with both patterns to produce different ash. Then any difference between the patterns is entirely hidden from the outside world.

If the patterns converge upon the same ash in N generations, then we need to consider all possible interactions at the boundary N cells thick. I'm not sure how well a search for this type of thing exists.

[NotLiving]

So, "pattern" here means both alive and dead cells, as is the case with some Garden of Eden patterns.

With that in mind, two patterns being "indistinguishable" means that for every possible pattern P (or P') that contains one of the two patterns (C and C') embedded at (0,0), run for an arbitrary number of generations, outside of the area contained by the embedded pattern (C or C') the two patterns (P and P') evolve identically.

They need to be distinct, though, which in how I'm defining it means essentially "when embedded in the standard all-cells-dead infinite "pattern" they never converge to the same state". Otherwise this would be a trivial example:

Code: Select all

x = 5, y = 5, rule = B3/S23
5.$5.$2.1A2.$5.$5.!

and

Code: Select all

x = 5, y = 5, rule = B3/S23
5.$5.$2.1.2.$5.$5.!

(That is, 1 live or dead cell in the center of a two-wide moat of dead cells.)

About the only thing I could think of is if you manage to have a boundary that triggers a lightspeed wick toward the center to destroy the bit or lack thereof cleanly if there ever are any cells adjacent. But I don't know if that's possible for the corners, at the very least. And good luck doing this with glider-constructible constructs.

[dvgrn]

About the only thing I could think of is if you manage to have a boundary that triggers a lightspeed wick toward the center to destroy the bit or lack thereof cleanly if there ever are any cells adjacent. But I don't know if that's possible for the corners, at the very least. And good luck doing this with glider-constructible constructs.

Lightspeed wicks are perfectly glider-constructible -- see Golly's Patterns/Life/Spaceships/adjustable-Corder-lineship.rle for example. However, they're also incrementally de-constructible if you work at it carefully.

So possibly you could incrementally take apart any stable fortress you might construct, until the unknown bit became accessible.

Still, I think you can only stop a lightspeed wick from burning out of control if you have some access to it from the sides. So maybe if you stack enough wicks next to each other you could keep the structure safe from attack by controlled deconstruction.

But is there really a way to set up a lot of wicks leading to a central location, such that you couldn't light any of the wicks -- or any simultaneous or near-simultaneous combination of the wicks -- in such a way that the hidden information would fail to be destroyed?

You can easily set up reactions where a bit ON or OFF doesn't matter, or an entire still life doesn't matter:

Code: Select all

x = 61, y = 48, rule = LifeHistory
2A39.A$A.A37.A.A$.2A38.2A3$3A37.3A$2.A39.A$.A39.A24$12.2A38.2A$12.2A
38.2A$59.2A$59.2A8$10.2A$10.2A2$3A37.3A$2.A39.A$.A39.A!

But unless you can control the angle of approach with guaranteed-disassembly-proof walls, it will be easy to come in from another side and get a different reaction where the presence of that bit is important.

At the moment, if I had to pick sides, I'd bet on being able to retrieve the information, not on being able to successfully hide it from any possible attack. That's only for stable patterns, though -- if the Information Obscurers are allowed to hide things behind barberpoles or muttering moats or phoenixes or delicately balanced higher-period stuff, I'd have to think about it some more.

[NotLiving]

Hence why I asked...

It's an interesting question.

Personally, I'm in the "it's possible but good luck finding a pattern that works" camp.