Encrypted Fractal Root Storage...

[Chris Thomasson]

Check this out:

-------
Original idea by Juaquin Anderson in the comments of the
following thread:

https://plus.google.com/+JuaquinAnderson/posts/L9A3Da8ju3B



FWIW, here is the content of the comment:
_________________________________________________
“This has me thinking.. All the structure, in the reverse
iteration, and the sequence of roots, as well as the structure
of the level sets with the escape time algorithim.
Someone
suggested using fractals for encryption..

A method that would
actually work would be to choose an interesting value of c,
like this one, as the key.

1) If the message has length n bits,
choose a point in the n'th level set. The point can be chosen
by taking a starting point just outside the circle delimiting
the target set, and applying inverse iteration, choosing roots
by sign according to the bits in the sequence to be encoded.

2) the result would be a point (x+yi) that is inside the nth level
set close to the Julia set.

3) encode that point accurately
enough to not confuse with points of a level deeper or further
out, and transmit that point.

4) receive that point.

5) decode
the point by applying forwards iteration with the key value c,
until the point lands in the target set. Tge decoded message
would have n bits determined by writing down the sign of the
imaginary component of the escape orbit for each iteration.



Sounds easy right?

:-)

The efficiency of the encrypted coding scheme has to do with
the fractal dimension of the Julia set, and the degree of
imbalance of the contractivity in the tree traversal of the
Julia set."
_________________________________________________


Juaquin Anderson has taken fractal encryption to another level
beyond the stuff I have been experiment with. He is basically
encoding a sequence of bytes inside a single complex number.
The reverse iteration method for a Julia set is being used to
store information. Lets say a byte. Well, a byte is made up of
a number of bits, on or off. These bits are used to decide which
root to choose for the square root of z during reverse iteration
of (z = z^2 + c). After this reverse iteration, one ends up with
an interesting point p. This point p can actually recreate the
bits of the byte when exposed to forward iteration. The number
of iterations for both forward and reverse iteration directly
corresponds to how many bits it stores. I can only do around 40
bits, but the little program I wrote just does 8 for clarity.

So, for encryption c is the secret key and the cipher text is a
list of complex numbers, or a single complex number if one uses
an arbitrary precision library to calculate both the reverse and
forward iterations.

Here is a simple proof of concept program in C++11 that encodes
a single byte:

http://pastebin.com/4Yu8uSKH

If one can encode a single byte, then one can encode multiple
bytes, and arbitrary binary files.

I know that this is going to work like a charm. I am working on
another proof of concept program that shows how to encode multiple
bytes in a single complex number, instead of the single byte
example shown here...


Any thoughts?

What do you think about the code? Is it crap?

;^)


Thank you all.


Also, I have a fractal encryption scheme that is actually compatible with this using minimal changes of incorporation:

http://www.fractalforums.com/fractals-in-nature/fractal-encryption/

What do you think of the code?

[eiffie]

I will look at the code now but the method sounds solid. This wasn't even an area of interest to me until yesterday I got the idea of doing the same thing with the Game Of Life (it is deterministic going forward but you can choose bits when going backward). This is MUCH more straight forward. Off to steal your code!
edit: The code seems to work fine - it would be awesome if it didn't lose precision! I will go experiment as well. Thanks for this!

[claude]

nice idea!  I thought about doing something similar with external angles in the Mandelbrot set, but Julia sets are better as you can pick a secret key c.

[Chris Thomasson]

I will look at the code now but the method sounds solid. This wasn't even an area of interest to me until yesterday I got the idea of doing the same thing with the Game Of Life (it is deterministic going forward but you can choose bits when going backward). This is MUCH more straight forward. Off to steal your code!
edit: The code seems to work fine - it would be awesome if it didn't lose precision! I will go experiment as well. Thanks for this!

Thank you for taking a look at the rather crude code. IMHO, it does indeed show how this can work. FWIW, here is another version of it that tests all bit patterns for a byte:

http://pastebin.com/VsvH3HdE

I am thinking of doing an HTML 5 app that visually shows how this works. IMHO, it is basically like storing information in a waveform. Also, AFAICT, Juaquin Anderson's original description has an error in it. He says that the sign of the imaginary part determines the proper bits to turn on during forward iteration. The code I quickly created shows that the sign of the real part is key to recreating the bit pattern. The signs of the imaginary parts are different than the information that was encoded during reverse iteration.

[Chris Thomasson]

nice idea!  I thought about doing something similar with external angles in the Mandelbrot set, but Julia sets are better as you can pick a secret key c.

Agreed! FWIW, the secret key c can be expanded into multiple c's during iteration. Think of a forward iteration like:

<quick pseudo-code>
___________________________________________

c[cmax] = { (julia point 0), (julia point 1), (julia point ...) };

for (unsigned int i = 0; i < imax; ++i)
{
    z = z^2 + c[i % cmax];
}

___________________________________________

One can expand the secret key space by using multiple Julia set seed points as c. FWIW, I have created some example renderings with this:







These did not have encrypted bit storage in mind, but they are all compatible with the overall technique.

There are many ways to create a larger keyspace. The one I have for my current fractal encryption:

http://funwithfractals.atspace.cc/ffe/

Is not that big, but gives an idea of how to do it.

[Chris Thomasson]

Humm... Another thought. So, wrt using multiple secret key's as c. I think the bits of the plaintext can be used to select from a pool of c's. AFAICT, this would greatly expand the key space. Not only does reverse iteration store data wrt roots of the sqrt of c, but it has multiple c's to choose from. The secret key would contain an array of different c's. The bits of the plaintext determine what c to use. any thoughts? Is this a crap idea? Humm...

[Chris Thomasson]

I will look at the code now but the method sounds solid. This wasn't even an area of interest to me until yesterday I got the idea of doing the same thing with the Game Of Life (it is deterministic going forward but you can choose bits when going backward). This is MUCH more straight forward. Off to steal your code!
edit: The code seems to work fine - it would be awesome if it didn't lose precision! I will go experiment as well. Thanks for this!

The precision loss is the bastard wall that is limiting the number of bits I can store in a complex number with double's. I can store 32, but anything larger than 40'ish starts to die, and produce radical errors during forward iteration, some bits actually decrypt, and others fail. I think an arbitrary precision lib can be used to store N bits in a single complex number. That would be interesting. I have not tried it yet. Humm...

[eiffie]

Yep I hit the 40 bit limit right away as I was wondering if this can do compression. You can use arbitrary precision but the complex number will have more bits than what is encrypted. (2x32 bit floats to 40 bits) No compression there - but IF there is a formula that works with integers to create the same +/- encoding then you could compress an arbitrary length string of bits into 2 integers (no fear of losing precision). Seems impossible on the face of it, but fun to try.

[Chris Thomasson]

Agreed! FWIW, the secret key c can be expanded into multiple c's during iteration.
[...]

FWIW, here is an example of using two secret keys at { -0.2, 0.0 } and { 0.3, 0.0 }:

[Chris Thomasson]

nice idea!  I thought about doing something similar with external angles in the Mandelbrot set, but Julia sets are better as you can pick a secret key c.

Yes. The secret key c is very interesting wrt how data can be stored. Very interesting.

 

Now, how to minimize precision loss!? Damn... 

[apeirographer]

Assuming I haven't completely misunderstood this concept, my preliminary experiments make it seem like it is trivial to find points that can reliably store 8 bytes, and not much harder to find ones that can store 9 or 10 bytes.  Higher than that might be impractically rare, and I'm going to take a wild guess and suggest that we won't find points that can reliably store more than 16 bytes while still being representable by two 64 bit floating point numbers.

I'll take a bit more time to try to understand what exactly is being described... because I'm definitely missing some parts still.  But if my subsequent playing around yields anything interesting, I'll post again.

Apeirographer

[Chris Thomasson]

Assuming I haven't completely misunderstood this concept, my preliminary experiments make it seem like it is trivial to find points that can reliably store 8 bytes, and not much harder to find ones that can store 9 or 10 bytes.  Higher than that might be impractically rare, and I'm going to take a wild guess and suggest that we won't find points that can reliably store more than 16 bytes while still being representable by two 64 bit floating point numbers.

I'll take a bit more time to try to understand what exactly is being described... because I'm definitely missing some parts still.  But if my subsequent playing around yields anything interesting, I'll post again.

Apeirographer

So far, I cannot find a point that can reliably store around 40 bits. If you can find one, please let me know. I have used points like { -0.74543, -0.11301 }, but they still fall apart during forward iteration wrt storing large numbers of bits! They start to escape during forward iteration, even though the reverse iteration keeps all points bounded to a "close" to the border formation. AFAICT, the precision loss starts to explode.

Damn!

FWIW, I think I managed to create a BuddaBrot like formation that is compatible with basically any reverse iteration Julia set. A crude initial example:



It might be able to be used in this type of encryption. Humm... The code that produces this rendering should be posted tonight or tomorrow. BTW, thank you all your interest!

 

;^)

[Chris Thomasson]

FWIW, the code for the reverse iteration wrt the "Buddhabrot" like reverse iterations can be found here:

https://plus.google.com/101799841244447089430/posts/UPf7RKrkiYm

FWIW, I thank you all for any interest you have in this subject.

 

[Chris Thomasson]

FWIW, the code for the reverse iteration wrt the "Buddhabrot" like reverse iterations can be found here:

https://plus.google.com/101799841244447089430/posts/UPf7RKrkiYm

FWIW, I thank you all for any interest you have in this subject.

 

http://pastebin.com/d6L89bBZ

I forgot to mention that the (c) for the function (ct_reversex) needs to be:

complex_t c = { 0.47, 0.7 };

 

[eiffie]

I thought you must be playing with the distance metric in that last pic because I was doing something similar s=sqrt(sqrt(x*x-y*y)) and getting similar lines. Thanks for sharing the code.