Canal-U

5.6. An Efficient Provably Secure One-Way Function

In this session, we are going to see how to build an efficient provably secure one-way function from coding theory. As you know, a one-way function is a function which is simple to evaluate and which should be as fast as possible and hard to invert, ideally with good security arguments. There are many applications of one-way functions, especially in symmetric cryptography. For example, for compression functions to build hash functions, expansion functions to build pseudorandom number generators but many more. Unfortunately, one-way functions are hard to build. We know some very fast functions which have very few security arguments and we have some very strong security arguments for functions which are very slow. What we will try to do is to get a fast and secure function. Niederreiter Encryption is a good candidate for one-way function. Any public key encryption scheme is a one-way function with a trapdoor, which is the decryption key. It has very strong security arguments usually a proof of security. But public key encryption is usually very slow, especially if you take construction from numbers theory, you require an expentiation which is expensive to compute. Niederreiter Encryption is much faster than other public key schemes. It simply converts the input into a low weight word. There are many different techniques to do this and then compute its syndrome which is only a few XORs, especially if the weight is very small.  The trapdoor can be easily removed by simply using a random binary matrix which is enough when we don't need to invert this one-way function. And with a few tweaks, it can be made even faster than the usual Niederreiter Encryption. Here, we will give an overview of the one-way function we are building. The parameters are matrix H of size r*n and the constant weight encoding function φ which takes l bits and output a word of weight w and length n. The one-way function simply takes an input x and computes φ(x) and multiplies it by H to obtain a value, a syndrome y. Security of this function: inverting the function requires to solve an instance of syndrome decoding; and efficiency: if φ is fast and w is small, then the function can be very efficient.