Re: Actually how simple is VMPC?

From: Mark Wooding (mdw_at_nsict.org)
Date: 08/29/03 

Date: 29 Aug 2003 19:54:55 GMT

Bartosz Zoltak <QPbzoltak@vmpcfunction.com> wrote:

> I would like to write false claims in the article [...]

You could start by saying that the moon was made from green cheese. (I
think you missed a `not'...)

> [...] in terms of simplicity.

That's a tricky area. What do you mean by `simple'?

I'd describe VMPC as a general construction like this.

  Let n be a natural number, and let \kappa \in S_n be a cyclic
  permutation on n objects. Define V: S_n -> S_n by

    V(\pi) = \pi \kappa \pi^2

(Putting in arithmetic -- your `+ 1' -- actually makes the description
/more/ complicated because then we need to get involved with applying
permutations to some other set, probably Z/nZ, and it starts getting out
of hand. Maybe this is just because I'm no good at providing simple
descriptions of things.)

That's not too bad. But consider this description of a well-studied
one-way function.

  Let p be a large prime, and let g generate a large prime-order
  subgroup of (Z/pZ)^*. Define E: N -> Z/pZ by

    E(n) = g^n

(I've copped out here by using integer discrete log specifically rather
than generalizing to other groups. I suppose I could have said `let p
be a prime and E be a nonsupersingular elliptic curve over Z/pZ...' but
that's starting to get messy already. Integers require less hedging. I
even managed to sneak in the requirement that (p - 1)/2 should have a
large prime factor.)

> which all can be also written with 3 MOV assembler instructions

I'd argue that this is more an efficiency thing than a simplicity
thing. You can do surprisingly complicated and weird things in a very
short program, if you try hard.

> Any indications on the simplest known one-way functions?

I'd offer discrete exponentiation as one. Also, squaring modulo a large
product of two primes. Hmm...

  Let n be the product of two large primes; define R: Z/nZ -> Z/nZ by

    R(x) = x^2

That's the simplest I've mentioned so far.

-- [mdw]