Visual Cryptography - A fractal approach

Introduction

History

The word fractal was coined by Mandelbrot in the 1970s. He dates the orgin of 'Fractal Geometry' from 1975 but indicates that objects now considered as fractal existed long before that decade. Many naturally occuring objects, such as trees, coastlines or clouds, are now considered to have fractal properties; and much of the current interest in the topic stems from the attempts to simulate such natural phenomena using computer graphics. Other more abstract forms of fractal objects were devised by artists and mathematicians, and again the availability of current techniques of computer graphics has given new insight into the structure of such objects.

A Simple Explanation Of Fractal Geometry

While the classical Euclidean geometry works with objects which exist in integer dimensions, fractal geometry deals with objects in non-integer dimensions. Euclidean geometry is a description lines, ellipses, circles, etc. Fractal geometry, however, is described in algorithims -- a set of instructions on how to create a fractal.


The world as we know it is made up of objects which exist in integer dimensions, single dimensional points, one dimensional lines and curves, two dimension plane figures like circles and squares, and three dimensional solid objects such as spheres and cubes. However, many things in nature are described better with dimension being part of the way between two whole numbers. While a straight line has a dimension of exactly one, a fractal curve will have a dimension between one and two, depending on how much space it takes up as it curves and twists. The more a fractal fills up a plane, the closer it approaches two dimensions. In the same manner of thinking, a wavy fractal scene will cover a dimension somewhere between two and three. Hence, a fractal landscape which consists of a hill covered with tiny bumps would be closer to two dimensions, while a landscape composed of a rough surface with many average sized hills would be much closer to the third dimension.


A More Complete Explanation of Fractal Geometry and Fractal Dimensions

Fractal Dimensions can be demonstated by first defining a fractal set as Nn = C/rnD where Nn is the number of fragments with the linear dimension defined as rn, C is some constant, and D defines the fractal dimension. If this equation is rearranged with simple algebra, the outcome is D = [ ln(Nn + 1/Nn) ] / [ ln(rn/rn + 1) ]. Given a line of unit length, we can divide it in varying ways and do different things with each segment. For the first example (figure 1a), if the segment is divided into two parts, making r1 = 1/2. One of the parts is kept and the other is disposed of, so N1 = 1. If we divide the remaining segment into two parts and again only keep one of the fragments, then r2 = 1/4 and N2=1. If this process is repeated (iterated), D turns out to be zero, which give the equivalent to the Euclidean point. Regardless of the number of iterations, at order n, Nn=1. Hence, D will always be zero. This way of thinking makes sense because if you were to take a line segment and continually divide it into two, keeping only one of the pieces, the length of the line segment will approach zero as the order approaches infinity.


A Euclidean line which exists in the first dimension can be demonstrated just as easily. This example is modeled in figure 1b. The line segement is again divided into two parts; however, we keep all the fragments, so r1 = 1/2 and N1 = 2. Iterating again, we get r2 = 1/4 and N2 = 4. Hence, ln(2) / ln(2) = 1. This also makes sense because we never remove any part of line so it will always remain of unit length.


In the first two examples, the results were both Euclidean figures with dimensions of zero and one, respectively. It is, however, just as easy to create a line segment with a fractal dimension between zero and one.

In figure 1c we divide the line segment into three different parts and keep only the two end pieces. After the first iteration, we get r1 = 1/3 and N1 = 2. When this process is repeated, we get r2 = 1/9 and N2 = 4. Therefore, D = ln(2) / ln(3) = 0.6309.

To show how to generate line segements with a varying fractal dimension, we start with a line segment of unit length and divide it into five distinct parts (figure 1d). By keeping only the two end pieces and the center piece, we get r1 = 1/5 and N1 = 3. Iterating again, we get r2 = 1/25 and N2 = 9. In this example D = ln(3) / ln(5) = 0.6826. As this process is iterated, the infinite set of points is called dust. This term will be explained later.









Figure 1. Demonstration of fractal dimensions with Euclidean line segments.


Fractal dimensions are not limited to being between zero and one. We can also apply the same method to the Euclidean square to produce items with a fractal dimension between zero and two. For each of the following examples, each square will be divided into nine squares of equal size, making r1 = 1/9. The iterations continues n times. To demonstrate the Euclidean point (figure 2a), we keep only one square with each iterations, making N1=Nn=1. In the next example (figure 2b), we keep only the top three squares with each iteration, making N1 = 3 and N2 = 9. Through this process we discover a Euclidean line with a dimension of one. The last Euclidean figure which can be derived from this example is the plane (figure 2c). To accomplish this, we keep all the squares with each iteration.


To produce a figure with a fractal dimension, we will keep only the two pieces in the upper left and lower right corner with each iteration (figure 2d), making N1 = 2 and N2 = 4. Hence, at the second order D = ln(2) / ln(3) = 0.6309. On the other hand, if we remove only the center piece with each iteration, as in figure 2e, we N1 = 8 and N2 = 64. This example produces a fractal dimension of 1.8928.
















Figure 2. Demonstration of fractal dimensions with Euclidean planes.


Calculating Fractal Dimensions

Now you understand what fractal dimensions are and where they come from, but how are they calculated? For certain objects which with you have delt all of your life, such as squares, lines, and cubes, it is easy to assign a dimension. You intuitively feel that a square has two dimensions, a line has one dimension, and a cube has three dimensions. You might feel this way because there are two directions in which you can move on asquare, one direction on a lines, and three directions in a cube, but what about fractals? Sometimes you can move in a certain number of directions and sometimes you can move in a different number of directions. This is what causes fractal dimensions to be non-integers.


To derive a formula which will work with all figures, lets first look at how to calculate the dimensions for the figures which we already know. A line can be divided into n = n1 seperate pieces. Each of those pieces is 1/n the size of the whole line and each piece, if magnified n times, would look exactly the same as the original. Repeating the process for a square, we find that is can be divided into n2 pieces. The same concept holds true for a cube, we need n3 pieces to reassemble a cube. Each of the pieces would be 1/n the size of the whole figure. The exponent in each of these examples is the dimension. For fractals, we need a generalized formula, which can be derived from what we already know. The steps bellow assume you have a working knowledge of logarithims and basic algebra.


Note: ln denotes loge and may be refered to as the natural logarithim. Because of the way in which this formula ends up, it is independant of the base used for the logarithims.


for a line: ln(number of divisions) = ln(n1)

for a square: ln(number of divisions) = ln(n2)

for a cube: ln(number of divisions) = ln(n3)


If you look back, the figure was divided into pieces that when zoomed in on n times, revealed to starting figure. Because of this, we divide the ln(number of divisions) by the natural logarithim of the magnification factor. The resulting formula gives the dimension, represented by D.


D=ln(number of divisions)/ln(magnification factor)


for a line: D = ln(n1)/ln(n) = 1

for a square: D = ln(n2)/ln(n) = 2

for a cube: D = ln(n3)/ln(n) = 3


Each of these examples was easy because the magnification factor was always n. But for fractals, magnification factor will be a constant, which varies for each fractal. Because you are unfamiliar with specific fractals, we can not examine specific cases now. Under the section Individual Fractals the dimension of the individual fractals will be examined in more detail.


What Are Fractals?

For the most part, when the word fractal is mentioned, you immediately think of the stunning pictures you have seen that were called fractals. But just what exactly is a fractal? Basically, it is a rough geometric figure that has two properties: First, most magnified images of fractals are essentially indistinguishable from the unmagnified version. This property of invariance under a change of scale if called self-similiarity. Second, fractals have fractal dimensions, as were described above. The word fractal was invented by Benoit Mandelbrot, "I coined fractal from the Latin adjective fractus. The corresponding Latin verb frangere means to break to create irregular fragments. It is therefore sensible and how appropriate for our needs! - that, in addition to fragmented, fractus should also mean irregular, both meanings being preserved in fragment."


Graphical Representation Of Fractals

Graphically, fractals are images created out of the process of a mathematical exploration of the space in which they are plotted. For this page, a computer screen will represent the space which is being explored. Each point in the area is tested in some way, usually an equation iterating for a given period of time. The equations used to test each point in the testing region are often extremely simple. Each particular point in the testing region is used as a starting point to test a given equation in a finite period of time. If the equation escapes, or becomes very large, within the period of time, it is colored white. If if doesn't escape, or stays within a given range through out the time period, it is colored black. Hence, a fractal image is a graphical representation of the points which diverge, or go out of control, and the points which converge, or stay inside the set. To make fractal images more elablorate and interesting, color is added to them. Rather than simply plotting a white point if it escapes, the point is assigned a color relative to how quickly it escaped. The images produced are very elaborate and possess non-Euclidean geometry. Fractals can also be produced by following a set of instructions such as remove the center third of a line segment.


Real-Life Relevance And Importance of Fractals and Fractal Geometry

Fractals have and are being used in many different ways. Both artist and scientist are intrigued by the many values of fractals. Fractals are being used in applications ranging form image compression to finance. We are still only beginning to realize the full importance and usefullness of fractal geometry.


One of the largest relationships with real-life is the similarity between fractals and objects in nature. The resemblance many fractals and their natural counter-parts is so large that it cannot be overlooked. Mathematical formulas are used to model self similiar natural forms. The pattern is repeated at a large scale and patterns evolve to mimic large scale real world objects.


One of the most useful applications of fractals and fractal geometry in in image compression. It is also one of the more controversial ideas. The basic concept behind fractal image compression is to take an image and express it as an iterated system of funtions. The image can be quickly displayed, and at any magnification with infinite levels of fractal detail. The largest problem behind this idea is deriving the system of functions which describe an image.


One of the more trivial applications of fractals is their visual effect. Not only do fractals have a stunning aesthic value, that is, they are remarkably pleasing to the eye, but they also have a way to trick the mind. Fractals have been used commercially in the film industry, in films such as Star Wars and Star Trek. Fractal images are used as an alternative to costly elaborate sets to produce fantasy landscapes.


Another seemingly unrelated application of fractals and chaos is in music. Some music, including that of Back and Mozart, can be stripped down so that is contains as little as 1/64th of its notes and still retain the essence of the composer. Many new software applications are and have been developed which contain chaotic filters, similiar to those which change the speed, or the pitch of music.


Fractal geometry also has an application to biological analysis. Fractal and chaos phenomena specific to non-linear systems are widely observed in biological systems. A study has established an analytical method based on fractals and chaos theory for two patterns: the dendrite pattern of cells during development in the cerebellum and the firing pattern of intercelluar potential. Variation in the development of the dendrite stage was evaluated with a fractal dimention. The order in many ion channels generating the firing pattern was also evaluated with a fractal dimension, enabling the high order seen there to be quantized.


Fractal geometry is also finding some place in cryptography particularly in Visual Cryptography. There is some research going on in this field but a lot has to go in before we can see a good cryptosystem based on fractals. The inherent nature of random behaviour of fractals makes it hard to understand.


Cryptography & Fractals


The concept of fractals is used to create encryption methods in Visual cryptography. One of the main advantage of fractal objects is that they are infinte repetition of the same object so , when you introduce randomness in this process we get a pretty good cryptosystem. Fractal geometry is nature's geometry, so it is truly random but implementing fractal geometry in finite space with various constraints gives us a psuedo-fractal object.

There are lot of physical limitations which restricts fractal geometry to assume a truly random form. One of the successful implementation of fractal based encryption system is FITIN ( Fractal Iteration of Information ) which is understandably does'nt use the fractal geometry to the fullest because of physical limitations. The fractal encryption which is achieved through this method is so far linear which makes it not so good for serious data encryption nevertheless it is step towards achiveing the ultimate cryptosystem.


Before we go into details of FITIN, first let's understand a basic visual encryption method. In normal visual cryptography a image is encrypted by XOR ing the image with a key. Key can be a small image with randomly selected pixel colors, now you keep XOR ing this key with the pixels of the actual image until you finish doing it to all the pixels in the image. Now what you get is a image which has unrelated pixel colors when compared to the actual image. This picture can be decrypted by XOR ing the encrypted picture with the same key which was used for encrytion. This is a primitive example, lot of variable parameters can be used to make it even more harder to break.

Example for Visual cryptography:

This example demonstrates encryption using graphics. This first screen shot shows the beginning screen. The areas of the screen on the left are boxes filled with random colors. These boxes represent keys.

The image on the right is a fractal image that will be used to demonstrate Exclusive-OR (X-OR) addition. ( figure -3(a))

Step - 1 : When a key is selected and moved over the fractal image, the individual pixels of random color are added to the coresponding pixels of the underlying image. This addition is performed using X-OR binary addition. This creates a new color for each pixel. The new color is different than the original image and the key. (figure -3(b))


Step - 2 : When the same key is selected and moved over the first key image, the pixels of random color are added to the coresponding pixels of the underlying image. The addition is again performed using X-OR binary addition. This recreates the original color for each pixel of the underlying image, and restores it to its unecrypted image. (figure -3(c))


Step - 3 : When the secret key is selected and moved over image, the pixels are again added together using X-OR binary addition. The next step involves the use of a second key, either a private key or a public key depending on the need. The second key encrypts the secret key as well as the image. (figure -3(d))


Step - 4 : When the second key is applied over the image again, the pixels are again added together using X-OR binary addition. This removes the second key and allows the recipiant to verify that the image was sent from the proper source without being tampered with.(figure -3(e))


Step - 5 : As before when the secret key is applied over the image again, the pixels are again added together using X-OR binary addition. This removes the secret key and restores the image to its original unencrypted condition.

(figure -3(f))




fig-3(a) and fig-3(b)





fig-3(c) and fig-3(d)




fig-3(e) and fig-3(f)


Fractal encryption uses the same procedure with fractal geometry involved. A brief idea about FITIN is explained in the next section.


Fractal Iteration of Information (FITIN)


Introduction


Encryption and decryption are based on a symmetry leading to reversibility. Symmetry and reversibility are intimely related to conservation laws. Information conservation plays also a crucial role in fractal growth. The (shannon) information scalar is a scale-invariant (conserved) property of a perfectly growing fractal. As we can show, reversible diffusion of information can be obtained if we apply the weak XOR-operation in a higher dimensional space in the context of a binary convolution where addition (subtraction) and multiplication are replaced by XOR and AND, respectively.

Algorithm:

Definitions


P1a: 1st half of image pattern, coordinates (x1a, y1a), 0 <= x1a < nx1, 0 <= y1a < ny1

P1b: 2nd half of image pattern, coordinates (x1b, y1b), 0 <= x1b < nx1, 0 <= y1b < ny1

Total image P1ab = P1a + P1b, decomposed like

abababababa...

bababababab...

abababababa...

bababababab...

.......................


P2: fractal filter image pattern (key1 pattern), coordinates (x2, y2) or (x2', y2'), 0 <= x2 < nx2, 0 <= y2 < ny2, size of P2 small compared to the size of P1a or P1b


(x2', y2') = Ci(x2, y2) is a maximum entropy cipher confusing the filter coordinates, the cipher is initialized by the key1 pattern P2 or any secondary key2 pattern.

Algorithm steps (Fractal Iteration of Information (FITIN))


Encryption


repeat until desired level of diffusion (iterationLevel) reached {


Part A:


do for all points (x1a, y1a) in P1a {

do for all points (x2, y2) in P2 {

(x2', y2') = Ci(x2, y2)

x1b = (x1a - x2' + nx2/2 ) MOD nx1

y1b = (y1a - y2' + ny2/2) MOD ny1

P1a(x1a, y1a) = P1a(x1a, y1a) XOR (P1b(x1b, y1b) AND P2(x2', y2'))

}

}


Part B:


do for all points (x1b, y1b) in P1b {

do for all points (x2, y2) in P2 {

(x2', y2') = Ci(x2, y2)

x1a = (x1b - x2' + nx2/2) MOD nx1

y1a = (y1b - y2' + ny2/2) MOD ny1

P1b(x1b, y1b) = P1b(x1b, y1b) XOR (P1a(x1a, y1a) AND P2(x2', y2'))

}

}

}

Decryption


with


A := Part A ; B := Part B


the iteration sequences are:


Encryption: A, B, A, B, ... , A, B

Decryption: B, A, B, A, ... , B, A


Central fact: P1a = P1a XXOR P1b XXOR P1b


XXOR stands for the extended ... XOR ( ... AND ... ) ... binary convolution contained in Part A and Part B.


Notes:




Example nx2 = 6 nxa = nxb = 60 , iterationLevel = 5 for an overall diffiusion of information.







Conclusion


The power of FITIN is the reversible and fractal diffusion of image information leading to a maximum entropy mixture of colour values. FITIN increases stochasticy and decreases the ability to detect.




previous page