An Isaac Newton Institute Programme

Logic and Algorithms

Observations on inverting the VMPC one-way function

3rd May 2006

Author: Kamil Kulesza (Cambridge)

Abstract

Informally speaking, one-way functions are functions for which it is "easy" to compute their values from their arguments but it is "computationally infeasible" to reverse them i.e. to find their arguments knowing their values. A rigorous definition of the terms "easy" and "computationally infeasible" is necessary but would detract from the simple idea that is being conveyed. Existence of one-way functions is only conjectured and closely connected with Cook’s hypothesis. Roughly speaking, if P is not equal NP such functions should exist. Apart from theoretical importance, one-way functions are fundamental for complexity based cryptography. Problem is being attacked in many ways and there are several instances which are perceived to be good candidates, for instance factorisation or discreet logarithm. There are also practical reasons to search for new candidates. We investigate the possibilities of inverting the VMPC one-way function, which was proposed at Fast Software Encryption 2004. (VMPC stands for Variably Modified Permutation Composition). First, we describe the function using the language of permutation theory. Next, easily invertible instances of VMPC are derived. We also show that no VMPC function is one-to-one. Implications of these results for cryptographic applications of VMPC conclude the presentation.