Making Cryptographic Primitives Harder

This paper studies a method for transforming ordinary cryptographic primitives to new harder primitives. Such a method is expected to lead to general schemes that make present cryptosystems secure against the attack of quantum computers. We propose a general technique to construct a new function from an ordinary primitive function f with a help of another hard function g so that the resulting function is to be new hard primitives. We call this technique a lifting of f by g. We show that the lifted function is harder than original functions under some simple conditions.