This time around, some thing interesting from the world of mathematics.
All of us dealt with functions of different types. We are introduced to functions when very early in school. Single varriable, multi varriable, simple and complex functions. And in college, functions declared, defined and studied. In this post, one such function, known as “one way function” is used widely in computer science.
Wonderful functions from math
Mathematics is full of functions. These functions are applied far and wide else where. Few are used many times where as few others are used little. And very often functions and equations are interchanged. The most celebrated of them all is –
Equations are used to depict the functions. You can state functions without the help of equation also. Computer science use lot of functions. And for variety of applications. It is beauty of math that you can design a function for almost anything.
Some times these functions can be designed based on algorithms. Or even abstract algorithms. All you need to know is the ingredients you need as an input for the function, and output it need to produce based on the input. Some time you just keep outputing constant value irrespective the input. This is known as constant function. So for any function, three things are important, first, the input it takes, second, the output it provides, third, the logic it uses to produce the output based on input.
One-way functions are the most interesting functions for their applicational purpose. These functions are used widely on computer programs to design cryptographic applications. Before we could get into that, the most important question is, what is one-way function?
One-way road sign
One-way functions are functions for which given an output it is computationaly infeasible to find out (or guess, if you are good at it!) what is in the input which produced the given output. This is the essense of the one-way functions. If we consider the following function as one-way function (which is strictly not). Now, there are few fundas one need to understand here.
First, the logic which is used to compute the output for a given input will be available to all. Which is the square of input (for our example). Secondly, with the output and logic, is it possible to compute the input. If you are given as 256. Can you find what the input could be? The catch is in the term “computationally infeasible“. We are not saying it cann’t be reversed at all, but with the available computing power it is impossible or it would take hundred of years to do so.
It is still an important problem for mathematicians and computer scientists to answer, do perfect one-way function exisist?
Random functions versus One-way functions
If you could remember, a basic necessity for a function is, for a given input, there can’t be two different outputs. Where as, pseudo random functions, which might be based on a key, if given an input, the value of output will be random. This random image will be dependent on the key. And there are pure random functions which are very difficult to predict the value if repeated. If I define the function to be rolling dice. And to be the output of it. Then this function is a pure random function. That is, we throw the dice first time and get four. Second time, if we repeat the same function, then there is no surity that you still get four. In other words, the function is not image preserving.
On the other hand, one-way functions are image preserving functions. For a given input, no matter what, how many times you repeat the experiment. You will get the same output. These functions but still behave like random functions. Because of this property, one-way functions find many application.
There are plenty of applications. Many important from cryptography and software, including my favourite hash functions. They are worth a seperate post. We shall discuss them later.